txgraph: use PostLinearize less prior to linearizing
What the developer wrote
Authored by Pieter Wuille
txgraph: use PostLinearize less prior to linearizing
With the new SFL algorithm, the process of loading an existing linearization into the
SFL state is very similar to what PostLinearize does. This means there is little benefit
to performing an explicit PostLinearize step before linearizing inside txgraph. Instead,
it seems better to use our allotted CPU time to perform more SFL optimization steps.
What changed, and why it matters
This is a routine internal optimization in Bitcoin Core's transaction graph code. It removes two calls to a helper named PostLinearize and updates comments, replacing an explicit cleanup step with work done by a newer algorithm (SFL). There is no indication this fixes or introduces a security bug.
No security action needed. Treat as normal code review for algorithmic correctness and performance.
Security signals we found
No strong security signals were identified.
Evidence from the diff
The commit modifies GenericClusterImpl::ApplyDependencies in src/txgraph.cpp. It removes an initial PostLinearize(m_depgraph, m_linearization) call and a trailing PostLinearize after FixLinearization. The reasoning given is that the new SFL (set-finding linearization) loading path already does equivalent work, so the explicit PostLinearize steps are redundant and the CPU budget is better spent on more SFL optimization steps. This is a performance/refactoring change in the cluster linearization logic used during mempool operations.
Changed components
src/txgraph.cppGenericClusterImpl::ApplyDependenciestransaction graph cluster linearizationInspect captured patch +1 / −10
diff --git a/src/txgraph.cpp b/src/txgraph.cpp
index 492e13c8..368b5cf7 100644
--- a/src/txgraph.cpp
+++ b/src/txgraph.cpp
@@ -1451,14 +1451,6 @@ void SingletonClusterImpl::Merge(TxGraphImpl&, int, Cluster&) noexcept
void GenericClusterImpl::ApplyDependencies(TxGraphImpl& graph, int level, std::span<std::pair<GraphIndex, GraphIndex>> to_apply) noexcept
{
- // This function is invoked by TxGraphImpl::ApplyDependencies after merging groups of Clusters
- // between which dependencies are added, which simply concatenates their linearizations. Invoke
- // PostLinearize, which has the effect that the linearization becomes a merge-sort of the
- // constituent linearizations. Do this here rather than in Cluster::Merge, because this
- // function is only invoked once per merged Cluster, rather than once per constituent one.
- // This concatenation + post-linearization could be replaced with an explicit merge-sort.
- PostLinearize(m_depgraph, m_linearization);
-
// Sort the list of dependencies to apply by child, so those can be applied in batch.
std::sort(to_apply.begin(), to_apply.end(), [](auto& a, auto& b) { return a.second < b.second; });
// Iterate over groups of to-be-added dependencies with the same child.
@@ -1484,9 +1476,8 @@ void GenericClusterImpl::ApplyDependencies(TxGraphImpl& graph, int level, std::s
}
// Finally fix the linearization, as the new dependencies may have invalidated the
- // linearization, and post-linearize it to fix up the worst problems with it.
+ // linearization.
FixLinearization(m_depgraph, m_linearization);
- PostLinearize(m_depgraph, m_linearization);
Assume(!NeedsSplitting());
Assume(!IsOversized());
if (IsAcceptable()) {
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.