Part of #30289, follow-up to #32545.
This gets rid of FixLinearization() by integrating the functionality into Linearize(), and makes txgraph exploit that (by delaying fixing of clusters until their first re-linearization). It also reduces (but does not eliminate) the number of calls to PostLinearize, as the SFL linearization effectively performs something very similar to postlinearization when loading in an existing linearization already.
The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.
For details see: https://corecheck.dev/bitcoin/bitcoin/pulls/34085.
See the guideline for information on the review process.
| Type | Reviewers |
|---|---|
| ACK | marcofleon, instagibbs |
If your review is incorrectly listed, please copy-paste <!–meta-tag:bot-skip–> into the comment that the bot should ignore.
Reviewers, this pull request conflicts with the following ones:
If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.
Possible places where named args for integral literals may be used (e.g. func(x, /*named_arg=*/0) in C++, and func(x, named_arg=0) in Python):
(No other added lines contain function calls where a third-or-later positional argument is a literal)
2026-01-05
1578@@ -1577,32 +1579,10 @@ void PostLinearize(const DepGraph<SetType>& depgraph, std::span<DepGraphIndex> l
1579 template<typename SetType>
a5067dbc7f5189848e02574f8f889c5a26fd3ceb
retaining its ordering where possible
micro nit: I know it’s going to get nuked later, but seems misleading at this commit IIUC
1193- quality = QualityLevel::NEEDS_SPLIT_ACCEPTABLE;
1194- } else {
1195- quality = QualityLevel::NEEDS_SPLIT;
1196- }
1197- } else {
1198+ if (todo.Any()) {
1b2c53ae0c9020791d39c85b032f7f907b468c99
Could we go another step further and delete the
// First remove all removals at the end of the linearization
Stuff, drop this specific conditional and just filter or is this still a performance win
3272@@ -3253,6 +3273,7 @@ std::vector<TxGraph::Ref*> TxGraphImpl::Trim() noexcept
3273 .subspan(group_data.m_cluster_offset, group_data.m_cluster_count);
3274 uint64_t size{0};
3275 for (Cluster* cluster : cluster_span) {
3276+ MakeAcceptable(*cluster, cluster->GetLevel(*this));
28ff1be7b5cae0f0674e0d0045da0eee5e9adc6a
Let’s me be more confident the cluster wasnt in a needs split state or something.
0 MakeAcceptable(*cluster, cluster->GetLevel(*this));
1 Assume(cluster->IsAcceptable());
GenericClusterImpl::AppendTrimData(), as I think it may otherwise result in a non-optimizable dynamic call. Ok?
1485@@ -1494,7 +1486,6 @@ void GenericClusterImpl::ApplyDependencies(TxGraphImpl& graph, int level, std::s
1486 // Finally fix the linearization, as the new dependencies may have invalidated the
1487 // linearization, and post-linearize it to fix up the worst problems with it.
ad895c9fd7f70e435aa7e478a8054c31f7b2d2e3
Stale comment about “post-linearize”
28ff1be7b5cae0f0674e0d0045da0eee5e9adc6a
stale comment about fixing + post-linearization
ACK 159bd23bcc8dca4d5e7029ee25c312c4ef78b0eb
Only a few suggestions
This also updates FixLinearization to just be a thin wrapper around Linearize.
In a future commit, FixLinearization will be removed entirely.
With the SFL algorithm, we will practically be capable of keeping
most if not all clusters optimal. With that, it seems less valuable
to avoid doing work after splitting an acceptable cluster, because by
doing some work we may get it to OPTIMAL.
This reduces the complexity of the code a bit as well.
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.
1360@@ -1345,7 +1361,7 @@ bool GenericClusterImpl::Split(TxGraphImpl& graph, int level) noexcept
1361 while (todo.Any()) {
1362 auto component = m_depgraph.FindConnectedComponent(todo);
1363 auto component_size = component.Count();
1364- auto split_quality = component_size <= 2 ? QualityLevel::OPTIMAL : new_quality;
1365+ auto split_quality = component_size <= 1 ? QualityLevel::OPTIMAL : new_quality;
1304@@ -1290,6 +1305,7 @@ void SingletonClusterImpl::AppendChunkFeerates(std::vector<FeeFrac>& ret) const
1305
1306 uint64_t GenericClusterImpl::AppendTrimData(std::vector<TrimTxData>& ret, std::vector<std::pair<GraphIndex, GraphIndex>>& deps) const noexcept
1307 {
1308+ Assume(IsAcceptable());
GenericClusterImpl::AppendChunkFeerates too? Maybe only for consistency.
code review ACK 1808b5aaf7c4910122fcd088e03d790189907438
Makes sense to defer making a cluster topological until the linearization is actually needed.
I also ran the new clusterlin_linearize fuzz target for a while, no issues.
reACK 1808b5aaf7c4910122fcd088e03d790189907438
Clean rebase + one comment typo fixed only