txgraph.cpp
1 // Copyright (c) The Bitcoin Core developers 2 // Distributed under the MIT software license, see the accompanying 3 // file COPYING or http://www.opensource.org/licenses/mit-license.php. 4 5 #include <bench/bench.h> 6 #include <random.h> 7 #include <txgraph.h> 8 #include <util/feefrac.h> 9 10 #include <cassert> 11 #include <cstdint> 12 13 namespace { 14 15 std::strong_ordering PointerComparator(const TxGraph::Ref& a, const TxGraph::Ref& b) noexcept 16 { 17 return (&a) <=> (&b); 18 } 19 20 void BenchTxGraphTrim(benchmark::Bench& bench) 21 { 22 // The from-block transactions consist of 1000 fully linear clusters, each with 64 23 // transactions. The mempool contains 11 transactions that together merge all of these into 24 // a single cluster. 25 // 26 // (1000 chains of 64 transactions, 64000 T's total) 27 // 28 // T T T T T T T T 29 // | | | | | | | | 30 // T T T T T T T T 31 // | | | | | | | | 32 // T T T T T T T T 33 // | | | | | | | | 34 // T T T T T T T T 35 // (64 long) (64 long) (64 long) (64 long) (64 long) (64 long) (64 long) (64 long) 36 // | | | | | | | | 37 // | | / \ | / \ | | / 38 // \----------+--------/ \--------+--------/ \--------+-----+----+--------/ 39 // | | | 40 // B B B 41 // 42 // (11 B's, each attaching to up to 100 chains of 64 T's) 43 // 44 /** The maximum cluster count used in this test. */ 45 static constexpr int MAX_CLUSTER_COUNT = 64; 46 /** The number of "top" (from-block) chains of transactions. */ 47 static constexpr int NUM_TOP_CHAINS = 1000; 48 /** The number of transactions per top chain. */ 49 static constexpr int NUM_TX_PER_TOP_CHAIN = MAX_CLUSTER_COUNT; 50 /** The (maximum) number of dependencies per bottom transaction. */ 51 static constexpr int NUM_DEPS_PER_BOTTOM_TX = 100; 52 /** Set a very large cluster size limit so that only the count limit is triggered. */ 53 static constexpr int32_t MAX_CLUSTER_SIZE = 100'000 * 100; 54 /** Set a very high number for acceptable cost, so that we certainly benchmark optimal 55 * linearization. */ 56 static constexpr uint64_t HIGH_ACCEPTABLE_COST = 100'000'000; 57 58 /** Refs to all top transactions. */ 59 std::vector<TxGraph::Ref> top_refs; 60 /** Refs to all bottom transactions. */ 61 std::vector<TxGraph::Ref> bottom_refs; 62 /** Indexes into top_refs for some transaction of each component, in arbitrary order. 63 * Initially these are the last transactions in each chains, but as bottom transactions are 64 * added, entries will be removed when they get merged, and randomized. */ 65 std::vector<size_t> top_components; 66 67 InsecureRandomContext rng(11); 68 auto graph = MakeTxGraph(MAX_CLUSTER_COUNT, MAX_CLUSTER_SIZE, HIGH_ACCEPTABLE_COST, PointerComparator); 69 70 // Construct the top chains. 71 for (int chain = 0; chain < NUM_TOP_CHAINS; ++chain) { 72 for (int chaintx = 0; chaintx < NUM_TX_PER_TOP_CHAIN; ++chaintx) { 73 int64_t fee = rng.randbits<27>() + 100; 74 FeePerWeight feerate{fee, 1}; 75 graph->AddTransaction(top_refs.emplace_back(), feerate); 76 // Add internal dependencies linking the chain transactions together. 77 if (chaintx > 0) { 78 graph->AddDependency(*(top_refs.rbegin()), *(top_refs.rbegin() + 1)); 79 } 80 } 81 // Remember the last transaction in each chain, to attach the bottom transactions to. 82 top_components.push_back(top_refs.size() - 1); 83 } 84 85 // Make the graph linearize all clusters acceptably. 86 graph->GetBlockBuilder(); 87 88 // Construct the bottom transactions, and dependencies to the top chains. 89 while (top_components.size() > 1) { 90 // Construct the transaction. 91 int64_t fee = rng.randbits<27>() + 100; 92 FeePerWeight feerate{fee, 1}; 93 TxGraph::Ref bottom_tx; 94 graph->AddTransaction(bottom_tx, feerate); 95 // Determine the number of dependencies this transaction will have. 96 int deps = std::min<int>(NUM_DEPS_PER_BOTTOM_TX, top_components.size()); 97 for (int dep = 0; dep < deps; ++dep) { 98 // Pick an transaction in top_components to attach to. 99 auto idx = rng.randrange(top_components.size()); 100 // Add dependency. 101 graph->AddDependency(/*parent=*/top_refs[top_components[idx]], /*child=*/bottom_tx); 102 // Unless this is the last dependency being added, remove from top_components, as 103 // the component will be merged with that one. 104 if (dep < deps - 1) { 105 // Move entry top the back. 106 if (idx != top_components.size() - 1) std::swap(top_components.back(), top_components[idx]); 107 // And pop it. 108 top_components.pop_back(); 109 } 110 } 111 bottom_refs.push_back(std::move(bottom_tx)); 112 } 113 114 // Run the benchmark exactly once. Running it multiple times would require the setup to be 115 // redone, which takes a very non-negligible time compared to the trimming itself. 116 bench.epochIterations(1).epochs(1).run([&] { 117 // Call Trim() to remove transactions and bring the cluster back within limits. 118 graph->Trim(); 119 // And relinearize everything that remains acceptably. 120 graph->GetBlockBuilder(); 121 }); 122 123 assert(!graph->IsOversized(TxGraph::Level::TOP)); 124 // At least 99% of chains must survive. 125 assert(graph->GetTransactionCount(TxGraph::Level::TOP) >= (NUM_TOP_CHAINS * NUM_TX_PER_TOP_CHAIN * 99) / 100); 126 } 127 128 } // namespace 129 130 static void TxGraphTrim(benchmark::Bench& bench) { BenchTxGraphTrim(bench); } 131 132 BENCHMARK(TxGraphTrim);