merkle: pre‑reserve leaves to prevent reallocs with odd vtx count #32497

l0rinc · 2025-05-14T13:01:42Z

Summary

ComputeMerkleRoot duplicates the last hash when the input size is odd. If the caller provides a std::vector whose capacity equals its size, that extra push_back forces a reallocation, doubling its capacity (causing peak memory usage of 3x the necessary size).

This affects roughly half of the created blocks (those with odd transaction counts), causing unnecessary memory fragmentation during every block validation.

Fix

Pre-reserves vector capacity to account for the odd-count duplication using (size + 1) & ~1ULL.
- This syntax produces optimal assembly across x86/ARM and 32/64-bit platforms for GCC & Clang.
Eliminates default construction of uint256 objects that are immediately overwritten by switching from resize to reserve + push_back.

Memory Impact

Memory profiling shows 50% reduction in peak allocation (576KB → 288KB) and elimination of reallocation overhead.

Validation

The benchmark was updated to use an odd leaf count to demonstrate the real-world scenario where the reallocation occurs.

A full -reindex-chainstate up to block 896 408 ran without triggering the asserts.

Validation asserts

Temporary asserts (not included in this PR) confirm that push_back never reallocates and that the coinbase witness hash remains null:

if (hashes.size() & 1) {
    assert(hashes.size() < hashes.capacity()); // TODO remove
    hashes.push_back(hashes.back());
}

leaves.reserve((block.vtx.size() + 1) & ~1ULL); // capacity rounded up to even
leaves.emplace_back();
assert(leaves.back().IsNull()); // TODO remove

Benchmark Performance

While the main purpose is to improve predictability, the reduced memory operations also improve hashing throughput slightly.

DrahtBot · 2025-05-14T13:01:47Z

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

Code Coverage & Benchmarks

For details see: https://corecheck.dev/bitcoin/bitcoin/pulls/32497.

Reviews

See the guideline for information on the review process.

Type	Reviewers
ACK	optout21, hodlinator
Concept NACK	darosior
Concept ACK	luke-jr
Stale ACK	yuvicc, vasild

If your review is incorrectly listed, please copy-paste  into the comment that the bot should ignore.

Conflicts

No conflicts as of last run.

luke-jr

utACK main commit. Not sure why the benchmark is being changed.

src/consensus/merkle.cpp

src/bench/merkle_root.cpp

l0rinc

Thanks for the review!

src/bench/merkle_root.cpp

src/consensus/merkle.cpp

yuvicc

Concept ACK

Memory allocation/deallocation is slow and expensive.

yuvicc · 2025-06-13T20:42:19Z

I have thought on changing the benchmark tests as we would want to test the worst case scenario right? or else we could have both case for testing?

yuvicc

Benchmark Testing

master@5757de4ddd37f9321ee6b338b40888fd3561fc00

With 9000

|             ns/leaf |              leaf/s |    err% |     total | benchmark
|--------------------:|--------------------:|--------:|----------:|:----------
|               52.62 |       19,005,746.07 |    0.2% |      0.01 | `MerkleRoot`
|               52.64 |       18,998,504.40 |    0.3% |      0.01 | `MerkleRoot`
|               52.63 |       18,999,727.67 |    0.2% |      0.01 | `MerkleRoot`

With 9001

|             ns/leaf |              leaf/s |    err% |     total | benchmark
|--------------------:|--------------------:|--------:|----------:|:----------
|               53.50 |       18,693,063.88 |    0.3% |      0.01 | `MerkleRoot`
|               53.53 |       18,681,211.49 |    0.5% |      0.01 | `MerkleRoot`
|               53.49 |       18,694,053.87 |    0.5% |      0.01 | `MerkleRoot`

Commit 39b6c139bd6be33699af781f1d71f6fed303d468

With 9000

|             ns/leaf |              leaf/s |    err% |     total | benchmark
|--------------------:|--------------------:|--------:|----------:|:----------
|               52.51 |       19,043,628.95 |    0.2% |      0.01 | `MerkleRoot`
|               52.52 |       19,040,989.96 |    0.2% |      0.01 | `MerkleRoot`
|               52.53 |       19,036,358.39 |    0.2% |      0.01 | `MerkleRoot`

With 9001

|             ns/leaf |              leaf/s |    err% |     total | benchmark
|--------------------:|--------------------:|--------:|----------:|:----------
|               53.40 |       18,713,525.67 |    0.3% |      0.01 | `MerkleRoot`
|               53.44 |       19,314,655.73 |    0.3% |      0.01 | `MerkleRoot`
|               53.41 |       18,883,462.75 |    0.3% |      0.01 | `MerkleRoot`

l0rinc · 2025-06-15T10:06:53Z

Updated the benchmark to showcase the before/after state better (resembles production code changes), by splitting out the vector copies to the unmetered lambda and having an odd number of elements.
Changed the previous leaves.reserve((block.vtx.size() + 1) & ~1ULL) rounding to leaves.reserve(block.vtx.size() + (block.vtx.size() & 1)).

yuvicc

Code review ACK 4cc5942895673591de4edceb6dd0c7188c302a72

Testing

Before Master@9a7eece5a4

ns/leaf	leaf/s	err%	total	benchmark
53.75	18,605,160.70	0.7%	0.01	`MerkleRoot`
53.64	18,643,002.35	0.1%	0.01	`MerkleRoot`
53.91	18,548,704.52	0.4%	0.01	`MerkleRoot`

After commit@4cc5942895673591de4edceb6dd0c7188c302a72

ns/leaf	leaf/s	err%	total	benchmark
57.67	17,340,305.39	0.0%	0.52	`MerkleRoot`
57.69	17,332,534.96	0.0%	0.52	`MerkleRoot`
58.14	17,199,057.10	0.0%	0.52	`MerkleRoot`

maflcko

not sure how meaningful this is, but it looks like there are a bunch of unrelated style changes that don't seem to have a benefit?

src/bench/merkle_root.cpp

src/consensus/merkle.cpp

l0rinc

The changes revert the original benchmark's behavior of including the leaf vector in the benchmark (more explicitly and reserved like the production code).
I've also changed the emplace_back calls for the hashes to push_bash and reverted the original loop conditions to minimize the diff in critical code sections.

Note to yuvicc: previous benchmark version was measuring something else than master (only the merkle call without the vector copy), so we can't directly compare the results.

~~The new results don't show any significant speed increase, only the memory allocation is more predictable - which isn't captured by the benchmark anymore.~~

src/bench/merkle_root.cpp

src/consensus/merkle.cpp

l0rinc · 2025-06-25T21:33:42Z

I've rebased the changed and adjusted the benchmark to be more similar to the other production usages in the first commit, rounded to even in the second (optimization) commit, so that we can realistically measure the speed difference before and after:

% build/bin/bench_bitcoin -filter='MerkleRoot' --min-time=1000

Before 7f620cffebee593e48434cf182cc2fd64a6d76be:

ns/leaf	leaf/s	err%	total	benchmark
45.50	21,975,688.66	0.0%	1.10	`MerkleRoot`
45.53	21,962,546.91	0.1%	1.10	`MerkleRoot`
45.53	21,965,162.52	0.0%	1.10	`MerkleRoot`

After a73dd45e95f5e909d0950ba7c76225589df74854:

ns/leaf	leaf/s	err%	total	benchmark
45.04	22,200,976.95	0.1%	1.10	`MerkleRoot`
44.97	22,235,208.25	0.1%	1.10	`MerkleRoot`
45.01	22,217,033.81	0.1%	1.10	`MerkleRoot`

yuvicc · 2025-06-27T07:22:24Z

lgtm re-ACK be8f3053a7ad526823f32f1a70847b9c06c4c54b

Before e87430ed5fad6f9d90c1e7d256b9b8276b936c24

ns/leaf	leaf/s	err%	total	benchmark
53.83	18,577,129.91	0.1%	1.10	`MerkleRoot`
53.62	18,648,858.81	0.1%	1.10	`MerkleRoot`
53.70	18,621,594.40	0.1%	1.10	`MerkleRoot`

After be8f3053a7ad526823f32f1a70847b9c06c4c54b

ns/leaf	leaf/s	err%	total	benchmark
53.02	18,860,232.62	0.2%	1.10	`MerkleRoot`
52.88	18,910,755.68	0.0%	1.10	`MerkleRoot`
52.89	18,906,671.63	0.1%	1.10	`MerkleRoot`

l0rinc · 2025-07-30T23:58:15Z

Rebased and added a new commit on top for deduplicating the integer rounding. Ready for review again.

DrahtBot · 2025-07-30T23:58:57Z

🚧 At least one of the CI tasks failed.
_{Task lint: https://github.com/bitcoin/bitcoin/runs/47077763348}
_{LLM reason (✨ experimental): Lint check failed due to missing include guards in src/util/ints.h.}

Hints

Try to run the tests locally, according to the documentation. However, a CI failure may still
happen due to a number of reasons, for example:

Possibly due to a silent merge conflict (the changes in this pull request being
incompatible with the current code in the target branch). If so, make sure to rebase on the latest
commit of the target branch.
A sanitizer issue, which can only be found by compiling with the sanitizer and running the
affected test.
An intermittent issue.

Leave a comment here, if you need help tracking down a confusing failure.

optout21 · 2025-08-07T06:36:53Z

LGTM!
Minor comments:

Maybe add a note to the ComputeMerkleRoot declaration, that the hashes input is expected to have one extra capacity (in case size is odd). Minor, as this function is not used directly much.
Even more, it could debug-assert that capacity is even, but this may be a bit of a stretch.

darosior · 2025-11-13T16:11:48Z

Sorry to be this guy again, but it seems to me unreasonable to touch such critical consensus code for such marginal benefits. Unless observable benefits can be shown, i lean toward Concept NACK.

l0rinc · 2025-11-21T16:14:21Z

Unless observable benefits can be shown

The change itself is trivial, it's just a +1 for the reserve before calling the Merkle calculation.
I don't mind simplifying the change if you think that's easier to review (I could also just bump leaves.reserve(block.vtx.size()) to leaves.reserve(block.vtx.size() + 1) without the refactors).
Originally it was similar to that, but based on concerns to decouple callers from needing to know the internals of Merkle calculations, I extracted the loops.

I'm open to simplifying it back to just a reserve if you think that's easier to review, but I'd argue that the underlying incorrect memory reservation is a minor bug that should be fixed.

While this change does result in small speedup, the primary purpose is to avoid having to reallocate 2x additional memory for a predictable calculation - less memory fragmentation, lower memory usage, more predictable behavior.
Let's quantify the impact: running massif for the benchmark with an odd leaf count shows the memory peaks clearly:

massif measurement comparing the two commits for 200 second benchmark run

COMMITS="f2334a0ae056a9e3cba218206d139b3688eeda96 de6a28396b8bf7a3fd1124418b4cd5beba1906d6"; \
CC=gcc; CXX=g++; \
BASE_DIR="/mnt/my_storage"; LOG_DIR="$BASE_DIR/logs"; \
FILTER="MerkleRoot"; MIN_TIME=200000; \
mkdir -p "$LOG_DIR"; \
(echo "memory benchmark | filter=$FILTER | min-time=${MIN_TIME}ms | $(hostname) | $(uname -m) | $(lscpu | grep 'Model name' | head -1 | cut -d: -f2 | xargs) | $(nproc) cores | $(free -h | awk '/^Mem:/{print $2}') RAM";) &&\
(for c in $COMMITS; do git log -1 --pretty='%h %s' $c || exit 1; done; echo "") && \
for COMMIT in $COMMITS; do \
  SHORT_COMMIT=${COMMIT:0:8}; \
  echo "Processing commit $SHORT_COMMIT..."; \
  git fetch -q origin $COMMIT && git checkout -q $COMMIT && \
  git clean -fxd && git reset --hard && \
  cmake -B build -G Ninja -DCMAKE_BUILD_TYPE=RelWithDebInfo -DBUILD_BENCH=ON -DENABLE_IPC=OFF && \
  ninja -C build bench_bitcoin -j2 && \
  valgrind --tool=massif --time-unit=ms \
    --massif-out-file="$LOG_DIR/massif-bench-$FILTER-$SHORT_COMMIT.out" \
    build/bin/bench_bitcoin -filter="$FILTER" --min-time=$MIN_TIME && \
  ms_print "$LOG_DIR/massif-bench-$FILTER-$SHORT_COMMIT.out" | tee "$LOG_DIR/massif-bench-$FILTER-$SHORT_COMMIT.txt" && \
  echo "Completed $SHORT_COMMIT"; \
done && \
echo "" && echo "Results in: $LOG_DIR/massif-bench-$FILTER-*.{out,txt}"

We can also clearly see the difference in the capture stack traces.
Before, having 1.3 MB peak memory usage:

    MB
1.332^        :                                                               
     | #      :                                                               
     | #      :                                                               
     | #      :                                                               
     | #      :                                                               
     | #    @ :                                                               
     | #    @ :                                                               
     | #    @ :                                                               
     | #    @ :                                                               
     | #    @ :                                                               
     | #    @ :                                                               
     | #    @ :                                                               
     | #    @ :                                                               
     | #::::@::::::::::::::::::::::::::::::::::::::::::::::::::::::@:::::@::::
     | #: ::@::::: :::::::: :: ::: :::::: : : :: ::: ::: : : : ::::@:::::@::::
     | #: ::@::::: :::::::: :: ::: :::::: : : :: ::: ::: : : : ::::@:::::@::::
     | #: ::@::::: :::::::: :: ::: :::::: : : :: ::: ::: : : : ::::@:::::@::::
     | #: ::@::::: :::::::: :: ::: :::::: : : :: ::: ::: : : : ::::@:::::@::::
     | #: ::@::::: :::::::: :: ::: :::::: : : :: ::: ::: : : : ::::@:::::@::::
     | #: ::@::::: :::::::: :: ::: :::::: : : :: ::: ::: : : : ::::@:::::@::::
   0 +----------------------------------------------------------------------->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.
->41.25% (576,064B) 0x969717: allocate (new_allocator.h:151)
| ->41.25% (576,064B) 0x969717: allocate (allocator.h:203)
|   ->41.25% (576,064B) 0x969717: allocate (alloc_traits.h:614)
|     ->41.25% (576,064B) 0x969717: _M_allocate (stl_vector.h:387)
|       ->41.25% (576,064B) 0x969717: _M_realloc_append<const uint256&> (vector.tcc:572)
|         ->41.25% (576,064B) 0x969717: push_back (stl_vector.h:1427)
|           ->41.25% (576,064B) 0x969717: ComputeMerkleRoot(std::vector<uint256, std::allocator<uint256> >, bool*) (merkle.cpp:55)
|             ->41.25% (576,064B) 0x2235A7: operator() (merkle_root.cpp:31)
|               ->41.25% (576,064B) 0x2235A7: ankerl::nanobench::Bench& ankerl::nanobench::Bench::run<MerkleRoot(ankerl::nanobench::Bench&)::{lambda()

After, having a 0.8 MB peak memory usage

    KB
801.4^ #                                                                      
     | #                                                                      
     | #                                                                      
     | #                                                                      
     | #                                                                      
     | #                                                                      
     | #                                                                      
     | #                                                         :::::@:::::@:
     | #:::@@@::@:::::::::::::::@::@:@:::@@:::::::::@::::::@:::::@::::@:::::@:
     | #:::@ @: @:::::::::::::::@::@:@:::@ :::: ::::@::::::@:::::@::::@:::::@:
     | #:::@ @: @:::::::::::::::@::@:@:::@ :::: ::::@::::::@:::::@::::@:::::@:
     | #:::@ @: @:::::::::::::::@::@:@:::@ :::: ::::@::::::@:::::@::::@:::::@:
     | #:::@ @: @:::::::::::::::@::@:@:::@ :::: ::::@::::::@:::::@::::@:::::@:
     | #:::@ @: @:::::::::::::::@::@:@:::@ :::: ::::@::::::@:::::@::::@:::::@:
     | #:::@ @: @:::::::::::::::@::@:@:::@ :::: ::::@::::::@:::::@::::@:::::@:
     | #:::@ @: @:::::::::::::::@::@:@:::@ :::: ::::@::::::@:::::@::::@:::::@:
     | #:::@ @: @:::::::::::::::@::@:@:::@ :::: ::::@::::::@:::::@::::@:::::@:
     | #:::@ @: @:::::::::::::::@::@:@:::@ :::: ::::@::::::@:::::@::::@:::::@:
     | #:::@ @: @:::::::::::::::@::@:@:::@ :::: ::::@::::::@:::::@::::@:::::@:
     | #:::@ @: @:::::::::::::::@::@:@:::@ :::: ::::@::::::@:::::@::::@:::::@:
   0 +----------------------------------------------------------------------->s
     0                                                                   227.5

and the stacks don't show reallocs anymore:

96.37% (790,809B) (heap allocation functions) malloc/new/new[], --alloc-fns, etc.
->35.10% (288,064B) 0x2234AF: allocate (new_allocator.h:151)
| ->35.10% (288,064B) 0x2234AF: allocate (allocator.h:203)
|   ->35.10% (288,064B) 0x2234AF: allocate (alloc_traits.h:614)
|     ->35.10% (288,064B) 0x2234AF: _M_allocate (stl_vector.h:387)
|       ->35.10% (288,064B) 0x2234AF: reserve (vector.tcc:79)
|         ->35.10% (288,064B) 0x2234AF: ToMerkleLeaves<std::vector<uint256>, MerkleRoot(ankerl::nanobench::Bench&)::<lambda()>::<lambda(bool, const auto:46&)> > (merkle.h:19)
|           ->35.10% (288,064B) 0x2234AF: operator() (merkle_root.cpp:25)
|             ->35.10% (288,064B) 0x2234AF: ankerl::nanobench::Bench& ankerl::nanobench::Bench::run<MerkleRoot(ankerl::nanobench::Bench&)::{lambda()

hodlinator

Concept ACK de6a28396b8bf7a3fd1124418b4cd5beba1906d6

ComputeMerkleRoot(std::vector<uint256> hashes, ...) takes a vector by value, but luckily call sites already move into it, and since the underlying array/memory is transferred on move, the capacity "transfers as well" - neat!

Sorry to be this guy again, but it seems to me unreasonable to touch such critical consensus code for such marginal benefits. Unless observable benefits can be shown, ...

Thanks for being that guy!

Going by #32497 (comment) and #32497 (comment) there seems to be a 2% speed increase for computing merkle roots.

I cannot spot any issue with how this PR currently changes the consensus code. However, maybe we could reduce the scope of the change somewhat to make it more palatable. Here is my attempt:
master...hodlinator:bitcoin:refs/heads/pr/32497_minimal#diff-706988c23877f8a557484053887f932b2cafb3b5998b50497ce7ff8118ac85a3 (link directly to src/consensus/merkle.cpp)

This 2% speed increase in merkle root computation is probably not at all measurable for a full IBD though. So if there is no variant of this optimization that inspires confidence, I can understand the push-back.

src/test/merkle_tests.cpp

src/consensus/merkle.cpp

l0rinc

Latest push:

rebases against latest master;
reverts code back to simply change leaves.resize(block.vtx.size()) constructs before calling ComputeMerkleRoot to .reserve((block.vtx.size() + 1) & ~1ULL);
** added godbolt reproducer for each important combination of compiler and architecture
Separates the test changes to a separate commit explaining the motivation in the commit message
updated commit messages and PR descriptions.

src/test/merkle_tests.cpp

src/consensus/merkle.cpp

src/bench/merkle_root.cpp

hodlinator

Reviewed e3b02f1539e59a6a20a00b4161219b5aba6fefed

Thanks for reverting to a simpler version of this change!

2 inline questions.

src/bench/merkle_root.cpp

src/test/merkle_tests.cpp

src/consensus/merkle.cpp

hodlinator

ACK 8af0a3a

While the benefit of this change to consensus code is low, it's been simplified back to a more easily reviewable version.

The benchmark now has two parts, one that detects mutation issues and one which does not, corresponding to the non-witness & witness merkle root computations performed by Bitcoin Core on mainnet.

One extra level of paranoia?

I think this change really is simple enough to approve as-is. It's maybe not the same risk-level as changing standard library major versions, but adjacent to it. If people still object, one idea to improve confidence could be to splice in a new commit before the last one - it could add BlockMerkleRootNew() and BlockWitnessMerkleRootNew() alongside the old ones, and have a fuzz test which compares results between new & old versions. Then the last commit could merge new & old together, keeping the old name but using the new implementations, and removing the fuzz test again.

Benchmarks

Expand

₿ cmake --build build -t bench_bitcoin && build/bin/bench_bitcoin -filter="MerkleRoot" -min-time=10000

`5fd62ed` "bench: make `MerkleRoot` benchmark more representative"

|             ns/leaf |              leaf/s |    err% |        ins/leaf |        cyc/leaf |    IPC |       bra/leaf |   miss% |     total | benchmark
|--------------------:|--------------------:|--------:|----------------:|----------------:|-------:|---------------:|--------:|----------:|:----------
|              115.53 |        8,655,444.89 |    0.0% |        1,216.23 |          425.94 |  2.855 |           2.14 |    0.3% |     11.03 | `MerkleRoot`
|              116.84 |        8,558,882.10 |    0.0% |        1,231.24 |          430.78 |  2.858 |           3.14 |    0.2% |     10.99 | `MerkleRootWithMutation`

`8af0a3a` "validation: pre-reserve leaves to prevent reallocs with odd vtx count"

|             ns/leaf |              leaf/s |    err% |        ins/leaf |        cyc/leaf |    IPC |       bra/leaf |   miss% |     total | benchmark
|--------------------:|--------------------:|--------:|----------------:|----------------:|-------:|---------------:|--------:|----------:|:----------
|              113.25 |        8,830,206.60 |    0.0% |        1,223.17 |          417.50 |  2.930 |           2.63 |    0.2% |     10.99 | `MerkleRoot`
|              114.67 |        8,720,906.94 |    0.0% |        1,238.18 |          422.72 |  2.929 |           3.63 |    0.2% |     11.01 | `MerkleRootWithMutation`

Modified `8af0a3a` which just does `leaves.reserve(hashes.size())`

|             ns/leaf |              leaf/s |    err% |        ins/leaf |        cyc/leaf |    IPC |       bra/leaf |   miss% |     total | benchmark
|--------------------:|--------------------:|--------:|----------------:|----------------:|-------:|---------------:|--------:|----------:|:----------
|              114.81 |        8,709,871.88 |    0.0% |        1,230.23 |          423.26 |  2.907 |           3.64 |    0.2% |     11.01 | `MerkleRoot`
|              116.21 |        8,605,021.23 |    0.0% |        1,245.23 |          428.41 |  2.907 |           4.64 |    0.2% |     11.00 | `MerkleRootWithMutation`

This last one shows that even just switching from resize() to reserve(), without always reserving an even number, does result in a measurable speedup by itself. Explains why I didn't see as big differences in my previous testing (#32497 (comment)) since all those variants used reserve().

src/bench/merkle_root.cpp

vasild

Approach ACK 8af0a3a

src/test/merkle_tests.cpp

src/bench/merkle_root.cpp

vasild · 2025-12-09T13:11:39Z

src/test/fuzz/integer.cpp

@@ -80,7 +81,8 @@ FUZZ_TARGET(integer, .init = initialize_integer)
    }
    constexpr uint256 u256_min{"0000000000000000000000000000000000000000000000000000000000000000"};
    constexpr uint256 u256_max{"ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff"};
-    const std::vector<uint256> v256{u256, u256_min, u256_max};
+    std::vector<uint256> v256{u256, u256_min, u256_max};
+    v256.reserve(RoundUpToEven(v256.size()));


I think it's simpler if the caller does not have to be aware that they should allocate a larger vector to be passed in.

+1

I do not understand why the patch above works :-/ but I like that it is contained inside ComputeMerkleRoot().

Update the integer fuzz test to move the vector into `ComputeMerkleRoot`, matching production usage patterns and avoiding unnecessary copies. Update `merkle_test_BlockWitness` to use an odd number of transactions to ensure the test covers the scenario where leaf duplication occurs. Also switch to `GetWitnessHash` to match `BlockWitnessMerkleRoot` semantics. The manual vector setup retains the exact-size `resize` to explicitly verify the behavior against the calculated root.

hodlinator

re-ACK 9f39a83

Resolved conflict with #33805 and fixed code nit #32497 (comment).

vasild

ACK 9f39a83

achow101 · 2025-12-22T22:54:33Z

src/bench/merkle_root.cpp

+
+            bool mutated{false};
+            const uint256 root{ComputeMerkleRoot(std::move(leaves), mutate ? &mutated : nullptr)};
+            assert(!mutate || mutated == (root.GetUint64(0) & 1));


In 1a768c0 "bench: make MerkleRoot benchmark more representative"

I'm having a hard time understanding why root.GetUint64(0) & 1 is an indicator that the merkle root was mutated.

Yeah, it was a leftover anti-optimization trick since we're in a loop now (meant to confuse the compiler, not the reader). But you're right, it seems to work correctly without it: removed the assert and updated the measurements in the commit messages: https://github.com/bitcoin/bitcoin/compare/9f39a8309cb0a23df03937b0b225aff8ce9e1ec6..3dd815f048c80c9a35f01972e0537eb42531aec7

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. > ./build/bin/bench_bitcoin -filter='MerkleRoot.*' -min-time=1000 | ns/leaf | leaf/s | err% | total | benchmark |--------------------:|--------------------:|--------:|----------:|:---------- | 44.18 | 22,634,858.70 | 0.0% | 1.10 | `MerkleRoot` | 44.66 | 22,390,601.03 | 0.0% | 1.10 | `MerkleRootWithMutation` Massif memory measurements show the excessive memory reservations: MB 1.332^ : | # : | # : | # : | # : | # @ : | # @ : | # @ : | # @ : | # @ : | # @ : | # @ : | # @ : | #::::@::::::::::::::::::::::::::::::::::::::::::::::::::::::@:::::@:::: | #: ::@::::: :::::::: :: ::: :::::: : : :: ::: ::: : : : ::::@:::::@:::: | #: ::@::::: :::::::: :: ::: :::::: : : :: ::: ::: : : : ::::@:::::@:::: | #: ::@::::: :::::::: :: ::: :::::: : : :: ::: ::: : : : ::::@:::::@:::: | #: ::@::::: :::::::: :: ::: :::::: : : :: ::: ::: : : : ::::@:::::@:::: | #: ::@::::: :::::::: :: ::: :::::: : : :: ::: ::: : : : ::::@:::::@:::: | #: ::@::::: :::::::: :: ::: :::::: : : :: ::: ::: : : : ::::@:::::@:::: 0 +----------------------------------------------------------------------->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. ->41.25% (576,064B) 0x969717: allocate (new_allocator.h:151) | ->41.25% (576,064B) 0x969717: allocate (allocator.h:203) | ->41.25% (576,064B) 0x969717: allocate (alloc_traits.h:614) | ->41.25% (576,064B) 0x969717: _M_allocate (stl_vector.h:387) | ->41.25% (576,064B) 0x969717: _M_realloc_append<const uint256&> (vector.tcc:572) | ->41.25% (576,064B) 0x969717: push_back (stl_vector.h:1427) | ->41.25% (576,064B) 0x969717: ComputeMerkleRoot(std::vector<uint256, std::allocator<uint256> >, bool*) (merkle.cpp:55) | ->41.25% (576,064B) 0x2235A7: operator() (merkle_root.cpp:31) | ->41.25% (576,064B) 0x2235A7: ankerl::nanobench::Bench& ankerl::nanobench::Bench::run<MerkleRoot(ankerl::nanobench::Bench&)::{lambda() Co-authored-by: Hodlinator <[email protected]>

`ComputeMerkleRoot` duplicates the last hash when the input size is odd. If the caller provides a `std::vector` whose capacity equals its size, that extra `push_back` forces a reallocation, doubling its capacity (allocating 3x the necessary memory). This affects roughly half of the created blocks (those with odd transaction counts), causing unnecessary memory fragmentation during every block validation. Fix this by pre-reserving the vector capacity to account for the odd-count duplication. The expression `(size + 1) & ~1ULL` adds 1 to the size and clears the last bit, effectively rounding up to the next even number. This syntax produces optimal assembly across x86/ARM and 32/64-bit platforms for gcc/clang, see https://godbolt.org/z/xzscoq7nv. Also switch from `resize` to `reserve` + `push_back` to eliminate the default construction of `uint256` objects that are immediately overwritten. > ./build/bin/bench_bitcoin -filter='MerkleRoot.*' -min-time=1000 | ns/leaf | leaf/s | err% | total | benchmark |--------------------:|--------------------:|--------:|----------:|:---------- | 43.73 | 22,867,350.51 | 0.0% | 1.10 | `MerkleRoot` | 44.17 | 22,640,349.14 | 0.0% | 1.10 | `MerkleRootWithMutation` Massif memory measurements after show 0.8 MB peak memory usage KB 801.4^ # | # | # | # | # | # | # | # :::::@:::::@: | #:::@@@::@:::::::::::::::@::@:@:::@@:::::::::@::::::@:::::@::::@:::::@: | #:::@ @: @:::::::::::::::@::@:@:::@ :::: ::::@::::::@:::::@::::@:::::@: | #:::@ @: @:::::::::::::::@::@:@:::@ :::: ::::@::::::@:::::@::::@:::::@: | #:::@ @: @:::::::::::::::@::@:@:::@ :::: ::::@::::::@:::::@::::@:::::@: | #:::@ @: @:::::::::::::::@::@:@:::@ :::: ::::@::::::@:::::@::::@:::::@: | #:::@ @: @:::::::::::::::@::@:@:::@ :::: ::::@::::::@:::::@::::@:::::@: | #:::@ @: @:::::::::::::::@::@:@:::@ :::: ::::@::::::@:::::@::::@:::::@: | #:::@ @: @:::::::::::::::@::@:@:::@ :::: ::::@::::::@:::::@::::@:::::@: | #:::@ @: @:::::::::::::::@::@:@:::@ :::: ::::@::::::@:::::@::::@:::::@: | #:::@ @: @:::::::::::::::@::@:@:::@ :::: ::::@::::::@:::::@::::@:::::@: | #:::@ @: @:::::::::::::::@::@:@:::@ :::: ::::@::::::@:::::@::::@:::::@: | #:::@ @: @:::::::::::::::@::@:@:::@ :::: ::::@::::::@:::::@::::@:::::@: 0 +----------------------------------------------------------------------->s 0 227.5 and the stacks don't show reallocs anymore: 96.37% (790,809B) (heap allocation functions) malloc/new/new[], --alloc-fns, etc. ->35.10% (288,064B) 0x2234AF: allocate (new_allocator.h:151) | ->35.10% (288,064B) 0x2234AF: allocate (allocator.h:203) | ->35.10% (288,064B) 0x2234AF: allocate (alloc_traits.h:614) | ->35.10% (288,064B) 0x2234AF: _M_allocate (stl_vector.h:387) | ->35.10% (288,064B) 0x2234AF: reserve (vector.tcc:79) | ->35.10% (288,064B) 0x2234AF: ToMerkleLeaves<std::vector<uint256>, MerkleRoot(ankerl::nanobench::Bench&)::<lambda()>::<lambda(bool, const auto:46&)> > (merkle.h:19) | ->35.10% (288,064B) 0x2234AF: operator() (merkle_root.cpp:25) | ->35.10% (288,064B) 0x2234AF: ankerl::nanobench::Bench& ankerl::nanobench::Bench::run<MerkleRoot(ankerl::nanobench::Bench&)::{lambda() Co-authored-by: optout21 <[email protected]> Co-authored-by: Hodlinator <[email protected]>

hodlinator

re-ACK 3dd815f

Changes since previous ACK (#32497 (review)):

Remove confusing assert in benchmark (#32497 (comment)).
Updated benchmark timing results in commit messsages.

luke-jr approved these changes May 20, 2025

View reviewed changes

src/consensus/merkle.cpp Show resolved Hide resolved

src/bench/merkle_root.cpp Outdated Show resolved Hide resolved

src/bench/merkle_root.cpp Outdated Show resolved Hide resolved

l0rinc commented May 20, 2025

View reviewed changes

src/bench/merkle_root.cpp Outdated Show resolved Hide resolved

src/bench/merkle_root.cpp Outdated Show resolved Hide resolved

src/consensus/merkle.cpp Show resolved Hide resolved

DrahtBot mentioned this pull request May 23, 2025

refactor: Txid type safety (parent PR) #32189

Closed

l0rinc mentioned this pull request Jun 12, 2025

[IBD] Tracking PR for speeding up Initial Block Download #32043

Draft

13 tasks

yuvicc reviewed Jun 13, 2025

View reviewed changes

l0rinc force-pushed the l0rinc/pre‑reserve-merkle-leaves-to-max branch from 39b6c13 to 4cc5942 Compare June 15, 2025 09:56

l0rinc requested review from luke-jr and yuvicc June 15, 2025 10:06

yuvicc reviewed Jun 15, 2025

View reviewed changes

maflcko reviewed Jun 20, 2025

View reviewed changes

src/bench/merkle_root.cpp Outdated Show resolved Hide resolved

src/bench/merkle_root.cpp Outdated Show resolved Hide resolved

src/consensus/merkle.cpp Outdated Show resolved Hide resolved

src/consensus/merkle.cpp Outdated Show resolved Hide resolved

l0rinc force-pushed the l0rinc/pre‑reserve-merkle-leaves-to-max branch from 4cc5942 to a1f2a4c Compare June 20, 2025 11:19

l0rinc commented Jun 20, 2025

View reviewed changes

src/bench/merkle_root.cpp Outdated Show resolved Hide resolved

src/bench/merkle_root.cpp Outdated Show resolved Hide resolved

src/consensus/merkle.cpp Outdated Show resolved Hide resolved

src/consensus/merkle.cpp Outdated Show resolved Hide resolved

l0rinc requested review from maflcko and yuvicc June 25, 2025 09:22

l0rinc force-pushed the l0rinc/pre‑reserve-merkle-leaves-to-max branch from a1f2a4c to a73dd45 Compare June 25, 2025 21:30

l0rinc force-pushed the l0rinc/pre‑reserve-merkle-leaves-to-max branch from a73dd45 to be8f305 Compare June 25, 2025 21:36

l0rinc force-pushed the l0rinc/pre‑reserve-merkle-leaves-to-max branch from be8f305 to 6d1950d Compare July 30, 2025 23:55

l0rinc force-pushed the l0rinc/pre‑reserve-merkle-leaves-to-max branch from 6d1950d to 2d1a4e7 Compare July 30, 2025 23:58

DrahtBot added the CI failed label Jul 30, 2025

DrahtBot removed the CI failed label Jul 31, 2025

DrahtBot mentioned this pull request Aug 1, 2025

refactor: Convert uint256 to Txid #33116

Merged

DrahtBot mentioned this pull request Nov 7, 2025

merkle: migrate path arg to reference and drop unused args #33805

Merged

hodlinator reviewed Nov 21, 2025

View reviewed changes

src/test/merkle_tests.cpp Outdated Show resolved Hide resolved

src/consensus/merkle.cpp Outdated Show resolved Hide resolved

src/consensus/merkle.cpp Show resolved Hide resolved

l0rinc commented Nov 22, 2025

View reviewed changes

src/test/merkle_tests.cpp Outdated Show resolved Hide resolved

src/consensus/merkle.cpp Show resolved Hide resolved

l0rinc force-pushed the l0rinc/pre‑reserve-merkle-leaves-to-max branch from de6a283 to e3b02f1 Compare November 22, 2025 13:00

optout21 reviewed Nov 27, 2025

View reviewed changes

src/bench/merkle_root.cpp Outdated Show resolved Hide resolved

optout21 reviewed Nov 27, 2025

View reviewed changes

src/bench/merkle_root.cpp Outdated Show resolved Hide resolved

bitcoin deleted a comment from littledeb77-wq Nov 27, 2025

hodlinator reviewed Nov 27, 2025

View reviewed changes

src/bench/merkle_root.cpp Show resolved Hide resolved

src/test/merkle_tests.cpp Outdated Show resolved Hide resolved

src/consensus/merkle.cpp Show resolved Hide resolved

l0rinc force-pushed the l0rinc/pre‑reserve-merkle-leaves-to-max branch 2 times, most recently from 14a4dca to 8af0a3a Compare December 1, 2025 12:10

hodlinator approved these changes Dec 1, 2025

View reviewed changes

src/bench/merkle_root.cpp Show resolved Hide resolved

DrahtBot requested a review from optout21 December 1, 2025 20:26

vasild reviewed Dec 9, 2025

View reviewed changes

l0rinc force-pushed the l0rinc/pre‑reserve-merkle-leaves-to-max branch from 8af0a3a to 9f39a83 Compare December 11, 2025 13:48

hodlinator approved these changes Dec 11, 2025

View reviewed changes

DrahtBot requested a review from vasild December 11, 2025 14:05

DrahtBot added the CI failed label Dec 11, 2025

l0rinc closed this Dec 11, 2025

l0rinc reopened this Dec 11, 2025

DrahtBot removed the CI failed label Dec 11, 2025

vasild approved these changes Dec 12, 2025

View reviewed changes

achow101 reviewed Dec 22, 2025

View reviewed changes

l0rinc and others added 2 commits December 23, 2025 09:44

l0rinc force-pushed the l0rinc/pre‑reserve-merkle-leaves-to-max branch from 9f39a83 to 3dd815f Compare December 23, 2025 07:45

hodlinator approved these changes Jan 3, 2026

View reviewed changes

DrahtBot requested a review from vasild January 3, 2026 12:52

merkle: pre‑reserve leaves to prevent reallocs with odd vtx count #32497

Are you sure you want to change the base?

merkle: pre‑reserve leaves to prevent reallocs with odd vtx count #32497

Conversation

l0rinc commented May 14, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Summary

Fix

Memory Impact

Validation

Benchmark Performance

Uh oh!

DrahtBot commented May 14, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Code Coverage & Benchmarks

Reviews

Conflicts

Uh oh!

luke-jr left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

l0rinc left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

yuvicc left a comment

Choose a reason for hiding this comment

Uh oh!

yuvicc commented Jun 13, 2025

Uh oh!

yuvicc left a comment

Choose a reason for hiding this comment

Benchmark Testing

Uh oh!

l0rinc commented Jun 15, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

yuvicc left a comment • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Testing

Before Master@9a7eece5a4

After commit@4cc5942895673591de4edceb6dd0c7188c302a72

Uh oh!

maflcko left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

l0rinc left a comment • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

l0rinc commented Jun 25, 2025

Uh oh!

yuvicc commented Jun 27, 2025

Uh oh!

l0rinc commented Jul 30, 2025

Uh oh!

DrahtBot commented Jul 30, 2025

Uh oh!

optout21 commented Aug 7, 2025

Uh oh!

darosior commented Nov 13, 2025

Uh oh!

l0rinc commented Nov 21, 2025

Uh oh!

hodlinator left a comment

Choose a reason for hiding this comment

l0rinc commented May 14, 2025 •

edited

Loading

DrahtBot commented May 14, 2025 •

edited

Loading

l0rinc commented Jun 15, 2025 •

edited

Loading

yuvicc left a comment •

edited

Loading

l0rinc left a comment •

edited

Loading

`5fd62ed` "bench: make `MerkleRoot` benchmark more representative"

`8af0a3a` "validation: pre-reserve leaves to prevent reallocs with odd vtx count"

Modified `8af0a3a` which just does `leaves.reserve(hashes.size())`