cluster mempool: exploit SFL properties in txgraph #34085
Conversation
|
The following sections might be updated with supplementary metadata relevant to reviewers and maintainers. Code Coverage & BenchmarksFor details see: https://corecheck.dev/bitcoin/bitcoin/pulls/34085. ReviewsSee the guideline for information on the review process.
If your review is incorrectly listed, please copy-paste ConflictsReviewers, 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. LLM Linter (✨ experimental)Possible places where named args for integral literals may be used (e.g.
(No other added lines contain function calls where a third-or-later positional argument is a literal) 2026-01-05 |
d40a7f1 to
159bd23
Compare
|
Rebased after merge of #32545, and marked as ready for review. |
instagibbs
left a comment
There was a problem hiding this comment.
ACK 159bd23
Only a few suggestions
159bd23 to
d9fd076
Compare
|
reACK d9fd076 |
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.
d9fd076 to
1808b5a
Compare
marcofleon
left a comment
There was a problem hiding this comment.
code review ACK 1808b5a
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.
| auto component = m_depgraph.FindConnectedComponent(todo); | ||
| auto component_size = component.Count(); | ||
| auto split_quality = component_size <= 2 ? QualityLevel::OPTIMAL : new_quality; | ||
| auto split_quality = component_size <= 1 ? QualityLevel::OPTIMAL : new_quality; |
There was a problem hiding this comment.
Cluster components of two transactions are no longer guaranteed to be topological while splitting! Nice.
|
|
||
| uint64_t GenericClusterImpl::AppendTrimData(std::vector<TrimTxData>& ret, std::vector<std::pair<GraphIndex, GraphIndex>>& deps) const noexcept | ||
| { | ||
| Assume(IsAcceptable()); |
There was a problem hiding this comment.
nit: Would it make sense to add this check in GenericClusterImpl::AppendChunkFeerates too? Maybe only for consistency.
|
reACK 1808b5a Clean rebase + one comment typo fixed only |
Part of #30289, follow-up to #32545.
This gets rid of
FixLinearization()by integrating the functionality intoLinearize(), 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 toPostLinearize, as the SFL linearization effectively performs something very similar to postlinearization when loading in an existing linearization already.