validation: pre-reserve leaves to prevent reallocs with odd vtx count

l0rinc · optout21 · hodlinator · l0rinc · commit 3dd815f048c8 · 2025-12-23T09:44:59.000+02:00
`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>
diff --git a/src/bench/merkle_root.cpp b/src/bench/merkle_root.cpp
@@ -24,9 +24,9 @@ static void MerkleRoot(benchmark::Bench& bench)
     for (bool mutate : {false, true}) {
         bench.name(mutate ? "MerkleRootWithMutation" : "MerkleRoot").batch(hashes.size()).unit("leaf").run([&] {
             std::vector<uint256> leaves;
-            leaves.resize(hashes.size());
+            leaves.reserve((hashes.size() + 1) & ~1ULL); // capacity rounded up to even
             for (size_t s = 0; s < hashes.size(); s++) {
-                leaves[s] = hashes[s];
+                leaves.push_back(hashes[s]);
             }
 
             bool mutated{false};
diff --git a/src/consensus/merkle.cpp b/src/consensus/merkle.cpp
@@ -66,20 +66,20 @@ uint256 ComputeMerkleRoot(std::vector<uint256> hashes, bool* mutated) {
 uint256 BlockMerkleRoot(const CBlock& block, bool* mutated)
 {
     std::vector<uint256> leaves;
-    leaves.resize(block.vtx.size());
+    leaves.reserve((block.vtx.size() + 1) & ~1ULL); // capacity rounded up to even
     for (size_t s = 0; s < block.vtx.size(); s++) {
-        leaves[s] = block.vtx[s]->GetHash().ToUint256();
+        leaves.push_back(block.vtx[s]->GetHash().ToUint256());
     }
     return ComputeMerkleRoot(std::move(leaves), mutated);
 }
 
 uint256 BlockWitnessMerkleRoot(const CBlock& block)
 {
     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
+    leaves.emplace_back(); // The witness hash of the coinbase is 0.
     for (size_t s = 1; s < block.vtx.size(); s++) {
-        leaves[s] = block.vtx[s]->GetWitnessHash().ToUint256();
+        leaves.push_back(block.vtx[s]->GetWitnessHash().ToUint256());
     }
     return ComputeMerkleRoot(std::move(leaves));
 }
diff --git a/src/signet.cpp b/src/signet.cpp
@@ -58,10 +58,10 @@ static bool FetchAndClearCommitmentSection(const std::span<const uint8_t> header
 static uint256 ComputeModifiedMerkleRoot(const CMutableTransaction& cb, const CBlock& block)
 {
     std::vector<uint256> leaves;
-    leaves.resize(block.vtx.size());
-    leaves[0] = cb.GetHash().ToUint256();
+    leaves.reserve((block.vtx.size() + 1) & ~1ULL); // capacity rounded up to even
+    leaves.push_back(cb.GetHash().ToUint256());
     for (size_t s = 1; s < block.vtx.size(); ++s) {
-        leaves[s] = block.vtx[s]->GetHash().ToUint256();
+        leaves.push_back(block.vtx[s]->GetHash().ToUint256());
     }
     return ComputeMerkleRoot(std::move(leaves));
 }

Original file line number	Diff line number	Diff line change
`@@ -66,20 +66,20 @@ uint256 ComputeMerkleRoot(std::vector<uint256> hashes, bool* mutated) {`
`66`	`66`	`uint256 BlockMerkleRoot(const CBlock& block, bool* mutated)`
`67`	`67`	`{`
`68`	`68`	`std::vector<uint256> leaves;`
`69`		`- leaves.resize(block.vtx.size());`
	`69`	`+ leaves.reserve((block.vtx.size() + 1) & ~1ULL); // capacity rounded up to even`
`70`	`70`	`for (size_t s = 0; s < block.vtx.size(); s++) {`
`71`		`- leaves[s] = block.vtx[s]->GetHash().ToUint256();`
	`71`	`+ leaves.push_back(block.vtx[s]->GetHash().ToUint256());`
`72`	`72`	`}`
`73`	`73`	`return ComputeMerkleRoot(std::move(leaves), mutated);`
`74`	`74`	`}`
`75`	`75`
`76`	`76`	`uint256 BlockWitnessMerkleRoot(const CBlock& block)`
`77`	`77`	`{`
`78`	`78`	`std::vector<uint256> leaves;`
`79`		`- leaves.resize(block.vtx.size());`
`80`		`- leaves[0].SetNull(); // The witness hash of the coinbase is 0.`
	`79`	`+ leaves.reserve((block.vtx.size() + 1) & ~1ULL); // capacity rounded up to even`
	`80`	`+ leaves.emplace_back(); // The witness hash of the coinbase is 0.`
`81`	`81`	`for (size_t s = 1; s < block.vtx.size(); s++) {`
`82`		`- leaves[s] = block.vtx[s]->GetWitnessHash().ToUint256();`
	`82`	`+ leaves.push_back(block.vtx[s]->GetWitnessHash().ToUint256());`
`83`	`83`	`}`
`84`	`84`	`return ComputeMerkleRoot(std::move(leaves));`
`85`	`85`	`}`
Original file line number	Diff line number	Diff line change
`@@ -58,10 +58,10 @@ static bool FetchAndClearCommitmentSection(const std::span<const uint8_t> header`
`58`	`58`	`static uint256 ComputeModifiedMerkleRoot(const CMutableTransaction& cb, const CBlock& block)`
`59`	`59`	`{`
`60`	`60`	`std::vector<uint256> leaves;`
`61`		`- leaves.resize(block.vtx.size());`
`62`		`- leaves[0] = cb.GetHash().ToUint256();`
	`61`	`+ leaves.reserve((block.vtx.size() + 1) & ~1ULL); // capacity rounded up to even`
	`62`	`+ leaves.push_back(cb.GetHash().ToUint256());`
`63`	`63`	`for (size_t s = 1; s < block.vtx.size(); ++s) {`
`64`		`- leaves[s] = block.vtx[s]->GetHash().ToUint256();`
	`64`	`+ leaves.push_back(block.vtx[s]->GetHash().ToUint256());`
`65`	`65`	`}`
`66`	`66`	`return ComputeMerkleRoot(std::move(leaves));`
`67`	`67`	`}`