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