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, vasild, w0xlt
Concept NACK	darosior
Concept ACK	luke-jr
Stale ACK	yuvicc

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.

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 <172445034+hodlinator@users.noreply.github.com>

`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 <13562139+optout21@users.noreply.github.com> Co-authored-by: Hodlinator <172445034+hodlinator@users.noreply.github.com>

hodlinator

re-ACK 3dd815f

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

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

vasild

ACK 3dd815f

w0xlt

ACK 3dd815f with minor nits.

On my machine, the Massif data clearly shows the improvement.

Benchmark Results

Version	Benchmark	ns/leaf	leaf/s
After (optimized)	MerkleRoot	46.50	21.5M
After (optimized)	MerkleRootWithMutation	45.97	21.8M
Before (master)	MerkleRoot	47.19	21.2M

Massif Memory Results

Metric	Before (master)	After (optimized)	Change
Peak memory	1.34 MB	802 KB	-40%
Reallocation overhead	576 KB (41%)	0	Eliminated

Memory reduction: 1.34 MB → 0.80 MB
Reallocation eliminated: The _M_realloc_insert stack trace is gone entirely
No performance regression: ~47 ns/leaf before and after

w0xlt · 2026-01-15T18:33:50Z

src/test/merkle_tests.cpp

-    hashes.resize(block.vtx.size());
-    hashes[0].SetNull();
-    hashes[1] = block.vtx[1]->GetHash().ToUint256();
+    hashes.resize(vtx_count); // Note: leaving odd count to exercise old behavior


nit: "Old behavior" is not clear to me - leaf duplication for odd counts is the normal merkle tree algorithm, not legacy behavior, isn't it ?.

Suggested change

hashes.resize(vtx_count); // Note: leaving odd count to exercise old behavior

hashes.resize(vtx_count); // Odd count exercises leaf duplication in ComputeMerkleRoot

old behavior = not properly sized.
You're also referring to it as "old": #32497 (comment)
I don't mind adjusting this in a followup

src/test/merkle_tests.cpp

src/test/fuzz/integer.cpp

w0xlt · 2026-01-15T18:41:45Z

src/test/merkle_tests.cpp

-    hashes[0].SetNull();
-    hashes[1] = block.vtx[1]->GetHash().ToUint256();
+    hashes.resize(vtx_count); // Note: leaving odd count to exercise old behavior
+    for (size_t pos{1}; pos < vtx_count; ++pos) {


nit: The old code explicitly had hashes[0].SetNull(). Now hashes[0] relies on implicit zero-initialization from resize(). A brief comment would clarify intent:

Suggested change

for (size_t pos{1}; pos < vtx_count; ++pos) {

// hashes[0] is zero (coinbase witness hash) from resize()

for (size_t pos{1}; pos < vtx_count; ++pos) {

I can do that in a follow-up if you think it's necessarry

src/bench/merkle_root.cpp

src/consensus/merkle.cpp

w0xlt · 2026-01-15T19:05:20Z

src/consensus/merkle.cpp

    std::vector<uint256> leaves;
-    leaves.resize(block.vtx.size());
-    leaves[0].SetNull(); // The witness hash of the coinbase is 0.
+    leaves.reserve((block.vtx.size() + 1) & ~1ULL); // capacity rounded up to even


The pattern (size + 1) & ~1ULL with identical comment appears 4 times across 3 files:

merkle.cpp:69

merkle.cpp:79

signet.cpp:61

merkle_root.cpp:27

A small helper would reduce duplication and can be arguably more readable: "add 1 if odd":

constexpr size_t RoundUpToEven(size_t n) { return n + (n & 1); }

Also: (size + 1) & ~1ULL works but assumes 64-bit arithmetic. assumptions.h explicitly supports 32-bit size_t.

It's what I did originally, but reviewers found it too complicated

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

Closed

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

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

l0rinc mentioned this pull request Jan 14, 2026

Coins Cache Cleanup checklist #34280

Open

24 tasks

l0rinc requested a review from hodlinator January 14, 2026 22:40

vasild approved these changes Jan 15, 2026

View reviewed changes

w0xlt reviewed Jan 15, 2026

View reviewed changes

	hashes.resize(vtx_count); // Note: leaving odd count to exercise old behavior
	hashes.resize(vtx_count); // Odd count exercises leaf duplication in ComputeMerkleRoot

	for (size_t pos{1}; pos < vtx_count; ++pos) {
	// hashes[0] is zero (coinbase witness hash) from resize()
	for (size_t pos{1}; pos < vtx_count; ++pos) {

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!

l0rinc left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

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())`