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