bench: make MerkleRoot benchmark more representative

l0rinc · hodlinator · l0rinc · commit 1a768c0d4c27 · 2025-12-11T14:47:48.000+01:00
Two versions are run now, one with the mutation calculations, the other without.
To avoid unwanted compiler optimizations, we assert the expected hash, which should inhibit aggressive optimization.

To make the benchmark more similar to production `ComputeMerkleRoot` call sites, the input leaves-copying is made explicit before each run.

&gt; ./build/bin/bench_bitcoin -filter='MerkleRoot.*' -min-time=1000

|             ns/leaf |              leaf/s |    err% |     total | benchmark
|--------------------:|--------------------:|--------:|----------:|:----------
|               44.26 |       22,592,347.11 |    0.0% |      1.10 | `MerkleRoot`
|               44.74 |       22,352,771.64 |    0.1% |      1.10 | `MerkleRootWithMutation`

Massif memory measurements show the excessive memory reservations:

    MB
1.332^        :
     | #      :
     | #      :
     | #      :
     | #      :
     | #    @ :
     | #    @ :
     | #    @ :
     | #    @ :
     | #    @ :
     | #    @ :
     | #    @ :
     | #    @ :
     | #::::@::::::::::::::::::::::::::::::::::::::::::::::::::::::@:::::@::::
     | #: ::@::::: :::::::: :: ::: :::::: : : :: ::: ::: : : : ::::@:::::@::::
     | #: ::@::::: :::::::: :: ::: :::::: : : :: ::: ::: : : : ::::@:::::@::::
     | #: ::@::::: :::::::: :: ::: :::::: : : :: ::: ::: : : : ::::@:::::@::::
     | #: ::@::::: :::::::: :: ::: :::::: : : :: ::: ::: : : : ::::@:::::@::::
     | #: ::@::::: :::::::: :: ::: :::::: : : :: ::: ::: : : : ::::@:::::@::::
     | #: ::@::::: :::::::: :: ::: :::::: : : :: ::: ::: : : : ::::@:::::@::::
   0 +-----------------------------------------------------------------------&gt;s
     0                                                                   226.2

showing the reallocations clearly in the stacks:
97.87% (1,366,841B) (heap allocation functions) malloc/new/new[], --alloc-fns, etc.
-&gt;41.25% (576,064B) 0x969717: allocate (new_allocator.h:151)
| -&gt;41.25% (576,064B) 0x969717: allocate (allocator.h:203)
|   -&gt;41.25% (576,064B) 0x969717: allocate (alloc_traits.h:614)
|     -&gt;41.25% (576,064B) 0x969717: _M_allocate (stl_vector.h:387)
|       -&gt;41.25% (576,064B) 0x969717: _M_realloc_append&lt;const uint256&amp;&gt; (vector.tcc:572)
|         -&gt;41.25% (576,064B) 0x969717: push_back (stl_vector.h:1427)
|           -&gt;41.25% (576,064B) 0x969717: ComputeMerkleRoot(std::vector&lt;uint256, std::allocator&lt;uint256&gt; &gt;, bool*) (merkle.cpp:55)
|             -&gt;41.25% (576,064B) 0x2235A7: operator() (merkle_root.cpp:31)
|               -&gt;41.25% (576,064B) 0x2235A7: ankerl::nanobench::Bench&amp; ankerl::nanobench::Bench::run&lt;MerkleRoot(ankerl::nanobench::Bench&amp;)::{lambda()

Co-authored-by: Hodlinator &lt;172445034+hodlinator@users.noreply.github.com&gt;
diff --git a/src/bench/merkle_root.cpp b/src/bench/merkle_root.cpp
@@ -7,21 +7,34 @@
 #include <random.h>
 #include <uint256.h>
 
+#include <cassert>
 #include <vector>
 
 static void MerkleRoot(benchmark::Bench& bench)
 {
-    FastRandomContext rng(true);
-    std::vector<uint256> leaves;
-    leaves.resize(9001);
-    for (auto& item : leaves) {
+    FastRandomContext rng{/*fDeterministic=*/true};
+
+    std::vector<uint256> hashes{};
+    hashes.resize(9001);
+    for (auto& item : hashes) {
         item = rng.rand256();
     }
-    bench.batch(leaves.size()).unit("leaf").run([&] {
-        bool mutation = false;
-        uint256 hash = ComputeMerkleRoot(std::vector<uint256>(leaves), &mutation);
-        leaves[mutation] = hash;
-    });
+
+    constexpr uint256 expected_root{"d8d4dfd014a533bc3941b8663fa6e7f3a8707af124f713164d75b0c3179ecb08"};
+    for (bool mutate : {false, true}) {
+        bench.name(mutate ? "MerkleRootWithMutation" : "MerkleRoot").batch(hashes.size()).unit("leaf").run([&] {
+            std::vector<uint256> leaves;
+            leaves.resize(hashes.size());
+            for (size_t s = 0; s < hashes.size(); s++) {
+                leaves[s] = hashes[s];
+            }
+
+            bool mutated{false};
+            const uint256 root{ComputeMerkleRoot(std::move(leaves), mutate ? &mutated : nullptr)};
+            assert(!mutate || mutated == (root.GetUint64(0) & 1));
+            assert(root == expected_root);
+        });
+    }
 }
 
 BENCHMARK(MerkleRoot, benchmark::PriorityLevel::HIGH);
