clusterlin: avoid recomputing intersections in MergeChunks
What the developer wrote
Authored by Pieter Wuille
clusterlin: avoid recomputing intersections in MergeChunks
MergeChunks scans the top chunk's transactions twice: once to count
the dependencies on the bottom chunk, and once to locate the randomly
picked one. Remember the per-transaction dependency counts from the
first pass, so the second pass only computes the intersection of the
selected transaction, rather than one per transaction scanned.
What changed, and why it matters
This is a small internal performance improvement in Bitcoin Core's transaction clustering code. It avoids doing the same bit-set intersection twice by saving the result of the first pass. There is no security-relevant change: no new behavior, no bounds check changes, no memory safety changes, and no externally reachable input handling.
No security action required. Treat as a normal performance refactor.
Security signals we found
No strong security signals were identified.
Evidence from the diff
In src/cluster_linearize.h, MergeChunks previously iterated top_chunk_info.transactions twice: first to count dependencies on bottom_chunk, then again to find a randomly selected dependency. The patch caches per-transaction dependency counts from the first loop (std::array
Changed components
src/cluster_linearize.hMergeChunks functionInspect captured patch +10 / −5
diff --git a/src/cluster_linearize.h b/src/cluster_linearize.h
index aa28d046..7b262edb 100644
--- a/src/cluster_linearize.h
+++ b/src/cluster_linearize.h
@@ -954,11 +954,16 @@ private:
Assume(m_chunk_idxs[bottom_idx]);
auto& top_chunk_info = m_set_info[top_idx];
auto& bottom_chunk_info = m_set_info[bottom_idx];
- // Count the number of dependencies between bottom_chunk and top_chunk.
+ // Count the number of dependencies between bottom_chunk and top_chunk, remembering the
+ // per-transaction counts so the picking loop below does not need to recompute the
+ // intersections.
unsigned num_deps{0};
+ std::array<SetIdx, SetType::Size()> counts;
for (auto tx_idx : top_chunk_info.transactions) {
auto& tx_data = m_tx_data[tx_idx];
- num_deps += (tx_data.children & bottom_chunk_info.transactions).Count();
+ auto count = (tx_data.children & bottom_chunk_info.transactions).Count();
+ counts[tx_idx] = count;
+ num_deps += count;
}
m_cost.MergeChunksMid(/*num_txns=*/top_chunk_info.transactions.Count());
Assume(num_deps > 0);
@@ -967,10 +972,10 @@ private:
unsigned num_steps = 0;
for (auto tx_idx : top_chunk_info.transactions) {
++num_steps;
- auto& tx_data = m_tx_data[tx_idx];
- auto intersect = tx_data.children & bottom_chunk_info.transactions;
- auto count = intersect.Count();
+ auto count = counts[tx_idx];
if (pick < count) {
+ auto& tx_data = m_tx_data[tx_idx];
+ auto intersect = tx_data.children & bottom_chunk_info.transactions;
for (auto child_idx : intersect) {
if (pick == 0) {
m_cost.MergeChunksEnd(/*num_steps=*/num_steps);
Why this scored 15/100
Community notes
Notes can correct, qualify, or add evidence to the AI analysis. Every note shown here has been validated by a human moderator.
The AI analysis stands alone for now. Submit a note if you can add evidence or important context.