clusterlin: inline GetReachable into Deactivate (optimization)
What the developer wrote
Authored by Pieter Wuille
clusterlin: inline GetReachable into Deactivate (optimization)
Avoid two full iterations over all of a chunks' transactions to
recompute the reachable sets, by inlining them into the
dependency-updating loops.
Note that there is no need to do the same for Activate, because the
reachable sets after merging can be computed directly from the input
chunks' reachable sets. Deactivate needs to recompute them, however.
What changed, and why it matters
This is a routine code optimization in Bitcoin Core's transaction clustering logic. It rewrites how one internal data structure (reachable transaction sets) is maintained when chunks of related transactions are split apart. The change is described by the author as a performance improvement and includes no indication of a security fix.
No security action required. Treat as normal code-review/optimization change. If reviewing, verify the inlined aggregation covers the same transaction parent/child sets as the original GetReachable computation and that SanityCheck still catches any divergence.
Security signals we found
No strong security signals were identified.
Evidence from the diff
The commit inlines the GetReachable helper into the Deactivate method of the cluster linearization data structure. Previously Deactivate recomputed reachable parent/child sets by two full passes over all chunk transactions via GetReachable. The patch instead accumulates top_parents/top_children and bottom_parents/bottom_children during the existing dependency-update loops, then derives the new reachable sets by subtracting the chunk’s own transactions. GetReachable is retained only for SanityCheck validation. The logic is functionally equivalent to the prior implementation if the loops correctly aggregate all parents/children of the split chunks.
Changed components
src/cluster_linearize.hCluster linearization reachable-set maintenanceDeactivate() methodInspect captured patch +17 / −8
diff --git a/src/cluster_linearize.h b/src/cluster_linearize.h
index a53edf77..1fe737a7 100644
--- a/src/cluster_linearize.h
+++ b/src/cluster_linearize.h
@@ -724,7 +724,8 @@ private:
}
/** Find the set of out-of-chunk transactions reachable from tx_idxs, both in upwards and
- * downwards direction. */
+ * downwards direction. Only used by SanityCheck to verify the precomputed reachable sets in
+ * m_reachable that are maintained by Activate/Deactivate. */
std::pair<SetType, SetType> GetReachable(const SetType& tx_idxs) const noexcept
{
SetType parents, children;
@@ -794,9 +795,8 @@ private:
// Merge top_info into bottom_info, which becomes the merged chunk.
bottom_info |= top_info;
m_cost += bottom_info.transactions.Count();
- // Compute merged sets of reachable transactions from the new chunk. There is no need to
- // call GetReachable here, because they can be computed directly from the input chunks'
- // reachable sets.
+ // Compute merged sets of reachable transactions from the new chunk, based on the input
+ // chunks' reachable sets.
m_reachable[child_chunk_idx].first |= m_reachable[parent_chunk_idx].first;
m_reachable[child_chunk_idx].second |= m_reachable[parent_chunk_idx].second;
m_reachable[child_chunk_idx].first -= bottom_info.transactions;
@@ -834,25 +834,34 @@ private:
// Subtract the top_info from the bottom_info, as it will become the child chunk.
bottom_info -= top_info;
// See the comment above in Activate(). We perform the opposite operations here, removing
- // instead of adding.
+ // instead of adding. Simultaneously, aggregate the top/bottom's union of parents/children.
+ SetType top_parents, top_children;
for (auto tx_idx : top_info.transactions) {
auto& tx_data = m_tx_data[tx_idx];
tx_data.chunk_idx = parent_chunk_idx;
+ top_parents |= tx_data.parents;
+ top_children |= tx_data.children;
for (auto dep_child_idx : tx_data.active_children) {
auto& dep_top_info = m_set_info[tx_data.dep_top_idx[dep_child_idx]];
if (dep_top_info.transactions[parent_idx]) dep_top_info -= bottom_info;
}
}
+ SetType bottom_parents, bottom_children;
for (auto tx_idx : bottom_info.transactions) {
auto& tx_data = m_tx_data[tx_idx];
+ bottom_parents |= tx_data.parents;
+ bottom_children |= tx_data.children;
for (auto dep_child_idx : tx_data.active_children) {
auto& dep_top_info = m_set_info[tx_data.dep_top_idx[dep_child_idx]];
if (dep_top_info.transactions[child_idx]) dep_top_info -= top_info;
}
}
- // Compute the new sets of reachable transactions for each new chunk.
- m_reachable[child_chunk_idx] = GetReachable(bottom_info.transactions);
- m_reachable[parent_chunk_idx] = GetReachable(top_info.transactions);
+ // Compute the new sets of reachable transactions for each new chunk, based on the
+ // top/bottom parents and children computed above.
+ m_reachable[parent_chunk_idx].first = top_parents - top_info.transactions;
+ m_reachable[parent_chunk_idx].second = top_children - top_info.transactions;
+ m_reachable[child_chunk_idx].first = bottom_parents - bottom_info.transactions;
+ m_reachable[child_chunk_idx].second = bottom_children - bottom_info.transactions;
// Return the two new set idxs.
return {parent_chunk_idx, child_chunk_idx};
}
Why this scored 12/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.