This replaces the cluster linearization algorithm introduced in #30126 and #30286 (a combination of LIMO with candidate-set search), with a completely different algorithm: spanning-forest linearization, which appears to have much better performance for hard clusters. See this post for a comparison between various linearization algorithms, and this post for benchmarks comparing them. Replaying historical mempool data on it shows that it can effectively linearize every observed cluster up to 64 transactions optimally within tens of microseconds, though pathological examples can be created which take longer.
The algorithm is effectively a very specialized version of the simplex algorithm to the problem of finding high-feerate topological subsets of clusters, but modified to find all consecutive such subsets concurrently rather than just the first one. See the post above for how it is related.
It represents the cluster as partitioned into a set of chunks, each with a spanning tree of its internal dependencies connecting the transactions. Randomized improvements are made by selecting dependencies to add and remove to these spanning trees, merging and splitting chunks, until no more improvements are possible, or a computation budget is reached. Like simplex, it does not necessarily make progress in every step, and thus has no upper bound on its runtime to find optimal, but randomization makes long runtimes very unlikely, and additionally makes it hard to adversarially construct clusters in which the algorithm reliably makes bad choices.
DrahtBot
commented at 11:24 pm on May 17, 2025:
contributor
The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.
If your review is incorrectly listed, please copy-paste <!–meta-tag:bot-skip–> into the comment that the bot should ignore.
Conflicts
No conflicts as of last run.
sipa force-pushed
on May 17, 2025
DrahtBot added the label
CI failed
on May 17, 2025
DrahtBot
commented at 11:40 pm on May 17, 2025:
contributor
🚧 At least one of the CI tasks failed.
Task ARM, unit tests, no functional tests: https://github.com/bitcoin/bitcoin/runs/42417371062
LLM reason (✨ experimental): The CI failure is due to a build error during the compilation of txgraph.cpp.o.
Try to run the tests locally, according to the documentation. However, a CI failure may still
happen due to a number of reasons, for example:
Possibly due to a silent merge conflict (the changes in this pull request being
incompatible with the current code in the target branch). If so, make sure to rebase on the latest
commit of the target branch.
A sanitizer issue, which can only be found by compiling with the sanitizer and running the
affected test.
An intermittent issue.
Leave a comment here, if you need help tracking down a confusing failure.
sipa force-pushed
on May 18, 2025
sipa force-pushed
on May 18, 2025
DrahtBot removed the label
CI failed
on May 18, 2025
sipa force-pushed
on May 18, 2025
sipa force-pushed
on May 19, 2025
DrahtBot added the label
CI failed
on May 19, 2025
DrahtBot
commented at 3:39 am on May 19, 2025:
contributor
🚧 At least one of the CI tasks failed.
Task ARM, unit tests, no functional tests: https://github.com/bitcoin/bitcoin/runs/42447412610
LLM reason (✨ experimental): The CI failure is due to a failed CTest test: cluster_linearize_tests.
Try to run the tests locally, according to the documentation. However, a CI failure may still
happen due to a number of reasons, for example:
Possibly due to a silent merge conflict (the changes in this pull request being
incompatible with the current code in the target branch). If so, make sure to rebase on the latest
commit of the target branch.
A sanitizer issue, which can only be found by compiling with the sanitizer and running the
affected test.
An intermittent issue.
Leave a comment here, if you need help tracking down a confusing failure.
sipa force-pushed
on May 20, 2025
sipa force-pushed
on May 20, 2025
DrahtBot removed the label
CI failed
on May 20, 2025
sipa added the label
Mempool
on May 20, 2025
in
src/cluster_linearize.h:464
in
23072f2b0eoutdated
554@@ -539,492 +555,651 @@ class LinearizationChunking
555 }
556 };
557558-/** Class encapsulating the state needed to find the best remaining ancestor set.
559+/** Class to represent the internal state of the spanning-forest linearization algorithm.
Appreciate the excellent doxygen documentation here.
jonatack
commented at 4:09 pm on May 22, 2025:
member
Concept ACK
sipa force-pushed
on May 23, 2025
sipa force-pushed
on May 23, 2025
sipa force-pushed
on May 24, 2025
sipa force-pushed
on May 25, 2025
sipa force-pushed
on May 25, 2025
DrahtBot added the label
CI failed
on May 25, 2025
DrahtBot
commented at 4:44 pm on May 25, 2025:
contributor
🚧 At least one of the CI tasks failed.
Task CentOS, depends, gui: https://github.com/bitcoin/bitcoin/runs/42858330826
LLM reason (✨ experimental): The CI failure is due to assertion failures within the cluster_linearize_tests and bench_sanity_check tests.
Try to run the tests locally, according to the documentation. However, a CI failure may still
happen due to a number of reasons, for example:
Possibly due to a silent merge conflict (the changes in this pull request being
incompatible with the current code in the target branch). If so, make sure to rebase on the latest
commit of the target branch.
A sanitizer issue, which can only be found by compiling with the sanitizer and running the
affected test.
An intermittent issue.
Leave a comment here, if you need help tracking down a confusing failure.
DrahtBot removed the label
CI failed
on May 25, 2025
I’m interested in seeing benchmarks of this on various systems, especially high-end/modern ones (as their performance is likely most predictive of what future hardware will be like).
ismaelsadeeq
commented at 1:51 pm on May 29, 2025:
member
I’m interested in seeing benchmarks of this on various systems, especially high-end/modern ones (as their performance is likely most predictive of what future hardware will be like).
Below are benchmarks on MacBook M2 PRO 2023.
Compiled using clang with only build bench cmake option.
@ismaelsadeeq Not an apples-to-apples comparison I’m afraid, because the benchmark cases are changed in this PR too. Can you run the LinearizeBoundedExample? benchmarks too?
ismaelsadeeq
commented at 2:35 pm on May 29, 2025:
member
@ismaelsadeeq Not an apples-to-apples comparison I’m afraid, because the benchmark cases are changed in this PR too
Oops sorry haven’t take a look, I was hoping I can compare locally myself. I saw a link to the bench results comparing them in the description 👍🏾
Can you run the LinearizeBoundedExample? benchmarks too?
Yep I did and updated the bench results. previous one was not pointing to your latest push.
instagibbs
commented at 4:28 pm on May 29, 2025:
member
Ran apples to apples out of curiosity. One example ran marginally slower on this PR (but still very fast), many are many multiples faster and some see 500x+ improvements.
gmaxwell
commented at 6:47 pm on May 29, 2025:
contributor
@instagibbs I believe the only cases that should be slower with SFL are either very small examples (where their time is irrelevant because its very low per tx compared to bigger clusters) and ones with huge numbers of dependencies. Beyond huge dependencies being generally unrepresentative they’re also expensive to generate because every dependency needs a vin, they also tend to be so slow with both that I guess neither will run to completion in practice.
A better way to compare across implementations might be some kind of optimization time vs amount of fee required to create a cluster with that dependency geometry (just assuming a 1s/vb feerate or something, not adding up the actual costs in the cluster because another cluster could exist with the same topology but different fees/size). like fee = 16*txn + 41*inputs_consumed + 9*outputs_consumed_within_cluster – so I’d hope to find that SFL always beats the current exponential algorithm on this kind of metric (except for very small inputs).
The exponential algorithm gets faster with dependency rich clusters because the linearization essentially becomes topologically forced, so the current algorithm doesn’t have many options to consider. If it massive high dependency clusters became common on the network in the future it might make sense to bring back the exponential algorithm for them. :P but I doubt that would happen.
fjahr
commented at 8:26 pm on May 30, 2025:
contributor
I’m interested in seeing benchmarks of this on various systems
@instagibbs@ismaelsadeeq@gmaxwell FWIW, I didn’t include apples-to-apples comparison because the large-scale comparison benchmarks I did (especially, this one) were just overwhelmingly in favor of SFL over the existing one. The benchmarks were mostly done to decide between SFL and another replacement algorithm, GGT, but see the reasons for choosing SFL here.
A fair apples-to-apples comparison I think needs to use a dataset large enough to encompass both good and bad cases for each of the algorithms, and not be specifically biased for one of them, which is hard in a benchmark I can include in the PR directly. If people are interested, I can try to clean up the branch I used to create the graphs above, however.
l0rinc
commented at 10:21 am on June 4, 2025:
contributor
I’ve run the command on a Raspberry Pi 4 Model B - Cortex-A72 4-Core ARM with SanDisk SSD PLUS 1TB (USB 3.0) with to have data about lower-end hardware as well.
l0rinc
commented at 1:22 pm on June 4, 2025:
contributor
Also, is this with 32-bit or 64-bit userspace?
64-bit userspace (AArch64)
0$ file bitcoind
1bitcoind: ELF 64-bit LSB pie executable, ARM aarch64, version 1(GNU/Linux), dynamically linked, interpreter /lib/ld-linux-aarch64.so.1, BuildID[sha1]=7e059ec01f7460042910ca4ed15270382269c9d5, for GNU/Linux 3.7.0, with debug_info, not stripped
DrahtBot added the label
Needs rebase
on Jul 29, 2025
sipa force-pushed
on Aug 9, 2025
DrahtBot added the label
CI failed
on Aug 9, 2025
DrahtBot
commented at 4:45 am on August 9, 2025:
contributor
🚧 At least one of the CI tasks failed.
Task no wallet, libbitcoinkernel: https://github.com/bitcoin/bitcoin/runs/47723469045
LLM reason (✨ experimental): The build failed due to compilation errors in cluster_linearize.cpp caused by incorrect member access of a tuple, leading to a build error.
Try to run the tests locally, according to the documentation. However, a CI failure may still
happen due to a number of reasons, for example:
Possibly due to a silent merge conflict (the changes in this pull request being
incompatible with the current code in the target branch). If so, make sure to rebase on the latest
commit of the target branch.
A sanitizer issue, which can only be found by compiling with the sanitizer and running the
affected test.
An intermittent issue.
Leave a comment here, if you need help tracking down a confusing failure.
DrahtBot removed the label
Needs rebase
on Aug 9, 2025
sipa force-pushed
on Aug 9, 2025
sipa force-pushed
on Aug 9, 2025
DrahtBot removed the label
CI failed
on Aug 9, 2025
sipa marked this as a draft
on Sep 11, 2025
sipa
commented at 3:32 pm on September 11, 2025:
member
I’m working on some improvements and reorganization of the commit here, so marking it as draft for now.
sipa force-pushed
on Sep 11, 2025
sipa force-pushed
on Oct 16, 2025
sipa marked this as ready for review
on Oct 16, 2025
sipa force-pushed
on Oct 16, 2025
sipa force-pushed
on Oct 16, 2025
sipa
commented at 7:01 pm on October 16, 2025:
member
Rebased, and made a significant change to the SFL algorithm itself:
Switched to a different technique for making the initial state topological. The big advantage is that this approach also works when one already has a linearization which is not entirely topological already.
Also the following changes to the cluster_linearize.h code in general:
Using SFL gaining the ability to fix existing linearizations, replaced FixLinearization with just making this feature part of Linearize.
With the LIMO-based Linearize, and MergeLinearizations (see below), gone, there is no more need for the LinearizationChunking class.
And as a result some changes in TxGraph are possible too:
Removed the need for FixLinearization by introducing QualityLevel states to represent “may be non-topological”, which makes the next call to Linearize() do the fixing instead.
Removed MergeLinearizations, as it was never used.
As SFL, upon being fed an existing linearization, runs through an initialization procedure that is pretty much equivalent to PostLinearize, drop all calls to PostLinearize()prior to Linearize() calls.
Because the new algorithm randomizes output linearization order (within equal-chunk-feerate parts), undo some of the non-determinism that introduces by always calling PostLinearize()afterLinearize() calls (before it would only do this if non-optimal).
sipa
commented at 7:10 pm on October 16, 2025:
member
This PR has grown quite a bit in scope (despite still being a net negative in LoC!), so I don’t think it’s unreasonable to split it up into an SFL-specific one, and one with follow-up changes to txgraph, or even further. I’ll wait for reviewer comments.
sipa requested review from Copilot
on Oct 20, 2025
in
src/cluster_linearize.h:1496
in
52b983bf90outdated
The new is_topological parameter defaults to true, but when old_linearization is empty, this parameter is ignored. This could be confusing for API consumers. Consider documenting this behavior more explicitly in the function comment, or validate that when old_linearization is empty, is_topological is not set to false.
Copilot
commented at 0:30 am on October 20, 2025:
none
Pull Request Overview
This PR replaces the existing cluster linearization algorithm (LIMO with candidate-set search) with a new spanning-forest linearization (SFL) algorithm that offers significantly better performance for complex clusters. The new algorithm uses a fundamentally different approach based on maintaining spanning trees within chunks and performing split/merge operations.
Key Changes:
Replaces search-based linearization with spanning-forest based approach
Simplifies quality level management by introducing NEEDS_FIX and NEEDS_SPLIT_FIX states
Updates the ExtractTransactions interface to use two separate visitor callbacks
Reviewed Changes
Copilot reviewed 6 out of 7 changed files in this pull request and generated 2 comments.
File
Description
src/txgraph.cpp
Implements quality level changes, updates transaction extraction to use two-pass visitors, modifies merging/splitting logic to work with new algorithm
src/test/util/cluster_linearize.h
Adjusts test utilities for changed type parameters and updated iteration bounds
src/test/fuzz/txgraph.cpp
Updates fuzz tests to use new chunking API
src/test/fuzz/cluster_linearize.cpp
Removes tests for deprecated algorithm components, adds tests for new chunking functions
src/cluster_linearize.h
Replaces entire linearization algorithm implementation with spanning-forest approach, adds ChunkLinearizationInfo function
src/bench/cluster_linearize.cpp
Updates benchmarks to test new algorithm with historical and random cluster examples
src/test/fuzz/cluster_linearize.cpp:1
[nitpick] The variable name done changed from TestBitSet to SetType. While this makes the code more generic, verify that this change aligns with the intended test coverage, as the original code may have been explicitly testing with TestBitSet for specific reasons.
0// Copyright (c) The Bitcoin Core developers
Tip: Customize your code reviews with copilot-instructions.md. Create the file or learn how to get started.
in
src/bench/cluster_linearize.cpp:47
in
52b983bf90outdated
[nitpick] The function signature changed from accepting const std::array<uint8_t, N>& to const std::vector<uint8_t>&. This removes compile-time size checking. While this makes the function more flexible, it also removes a safety guarantee. Consider if the added flexibility is worth the loss of compile-time size verification.
sipa
commented at 8:35 am on October 27, 2025:
member
I have added an additional fuzz test (clusterlin_sfl) which verifies properties of the underlying data structure (SpanningForestState) plus sanity checks on it (as opposed to clusterlin_linearize which only tests the higher-level Linearize() function implemented in function of it).
It’s no longer a net reduction in LoC now :(
sipa force-pushed
on Oct 27, 2025
sipa force-pushed
on Nov 3, 2025
sipa force-pushed
on Nov 4, 2025
sipa force-pushed
on Nov 23, 2025
sipa
commented at 3:42 pm on November 23, 2025:
member
DrahtBot removed the label
Needs rebase
on Nov 25, 2025
fanquake added this to the milestone 31.0
on Nov 27, 2025
fanquake requested review from instagibbs
on Dec 2, 2025
fanquake requested review from sdaftuar
on Dec 2, 2025
fanquake requested review from glozow
on Dec 2, 2025
in
src/cluster_linearize.h:399
in
060e1856b1
394+ feerate -= other.feerate;
395+ return *this;
396+ }
397+
398+ /** Compute the difference between this and other SetInfo (which must be a subset). */
399+ SetInfo operator-(const SetInfo& other) noexcept
marcofleon
commented at 6:36 pm on December 3, 2025:
marcofleon
commented at 6:50 pm on December 3, 2025:
nit: Is there a reason we recalculate here vs just using chunk_rep from the line above?
Also additional nit: The local chunk_rep is named the same as the function parameter and both are TxIdx I believe. Could be worth having different names?
marcofleon
commented at 7:10 pm on December 3, 2025:
contributor
Did a first pass of the changes in cluster_linearize.h, left a couple small comments. I’m running a few of the fuzz targets, including the new one, and I’ll leave those going for a while.
Still need to look at the tests thoroughly. Let me know if there’s anything specific you think reviewers can do that would be useful.
sipa
commented at 10:35 pm on December 3, 2025:
member
FWIW, I’m writing a Python version of SFL with simpler data structures and less optimizations. It needs some polishing, but I’ll post it here. It could be used as a form of documentation, or live in the functional test framework.
instagibbs
commented at 2:32 pm on December 4, 2025:
member
glancing through the PR now
how bad would it be to merge all the way through “clusterlin: replace cluster linearization with SFL implementation (feature)”, maybe some of the commits that drops unused things (ala “clusterlin: remove unused MergeLinearizations (cleanup)”) and defer the other optimisations for next PR?
in
src/cluster_linearize.h:474
in
f81f72a11eoutdated
677+ * dependencies cannot all simultaneously be active.
678+ *
679+ * The sets of transactions that are internally connected by active dependencies are called chunks.
680+ * Each chunk of N transactions contains exactly N-1 active dependencies (an additional one would
681+ * necessarily form a cycle), and thus those active dependencies form a spanning tree for the chunk.
682+ * The collection of all spanning trees for the entire cluster form a spanning forest. Each
instagibbs
commented at 7:31 pm on December 4, 2025:
0 * The collection of all spanning trees for the entire cluster form a spanning forest. In the extreme each
in
src/cluster_linearize.h:481
in
f81f72a11eoutdated
683+ * transaction may be in its own chunk (and thus 0 dependencies are active), or all transactions
684+ * may form a single chunk (and thus N-1 dependencies are active).
685+ *
686+ * Each chunk has a feerate: the total fee of all transactions in it divided by the total size of
687+ * all transactions in it. We say the spanning forest is topological whenever no inactive
688+ * dependencies exist from one chunk to another chunk with lower or equal feerate. The algorithm
instagibbs
commented at 7:35 pm on December 4, 2025:
or equal
Need to understand why, delving seems to suggest the more “natural” choice https://delvingbitcoin.org/t/spanning-forest-cluster-linearization/1419 “If there is an inactive dependency, where the parent and child are in distinct chunks, and the child chunk has higher feerate than the parent chunk, make the dependency active, merging the two chunks.”
The solution is an initial phase where you don’t care about splitting equal-feerate parts from one another (this PR), and then a secondary phase where you split up chunks in their minimal components (added in #34023).
instagibbs
commented at 2:43 pm on December 9, 2025:
makes sense, I am just noting it’s not clear at all from the writeup
Do you mean the write-up in the code comment added here, on the one on Delving?
Do you think it’s worth elaborating on here?
instagibbs
commented at 2:57 pm on December 9, 2025:
sorry, I meant the one on delving. I think it’s worth mentioning in the code itself actually.
in
src/cluster_linearize.h:525
in
f81f72a11eoutdated
727+ * In addition, this allows refining the algorithm flow into:
728+ *
729+ * - Construct an initial topological spanning forest for the graph:
730+ * - Start with graph with all dependencies inactive (i.e., each transaction is a singleton
731+ * chunk).
732+ * - Make the graph topological by randomly picking chunks, and merging them (with their
instagibbs
commented at 8:07 pm on December 4, 2025:
do you mean pick a chunk randomly, then observer the dependency/dependee list, and pick the corresponding lowers/highest feerate one for activation?
Pick a random chunk (from the list you maintain of chunks that need to be considered still)
See if it can be merged upwards or downwards, and:
If so, merge with its max-feerate-difference dependency/depender, and add the resulting chunk to list.
If not, remove the chunk from the list.
in
src/test/fuzz/cluster_linearize.cpp:930
in
f81f72a11eoutdated
1208+ //
1209+ if (is_topological) {
1210+ auto lin = sfl.GetLinearization();
1211+ // Which must be valid.
1212+ SanityCheck(depgraph, lin);
1213+ // If we started from a topological input, the resulting feerate diagram cannot be worse.
instagibbs
commented at 8:40 pm on December 4, 2025:
0 // If we started from a topological input, the resulting feerate diagram cannot be worse or incomparable.
in
src/cluster_linearize.h:1124
in
f81f72a11eoutdated
1119+ const auto& dep_data = m_dep_data[dep_idx];
1120+ if (!dep_data.active) continue;
1121+ // Skip if this dependency is ineligible (the top chunk that would be created
1122+ // does not have higher feerate than the chunk it is currently part of).
1123+ if (!(dep_data.top_setinfo.feerate >> chunk_data.chunk_setinfo.feerate)) continue;
1124+ // Activate it otherwise.
instagibbs
commented at 6:55 pm on December 5, 2025:
DrahtBot
commented at 8:52 pm on December 6, 2025:
contributor
🚧 At least one of the CI tasks failed.
Task Windows native, fuzz, VS 2022: https://github.com/bitcoin/bitcoin/actions/runs/19993713242/job/57338160248
LLM reason (✨ experimental): Fuzz txgraph failed due to an assertion failure in cluster_linearize (transactions overlapping in SetInfo|=), causing exit code 1.
Try to run the tests locally, according to the documentation. However, a CI failure may still
happen due to a number of reasons, for example:
Possibly due to a silent merge conflict (the changes in this pull request being
incompatible with the current code in the target branch). If so, make sure to rebase on the latest
commit of the target branch.
A sanitizer issue, which can only be found by compiling with the sanitizer and running the
affected test.
An intermittent issue.
Leave a comment here, if you need help tracking down a confusing failure.
sipa force-pushed
on Dec 6, 2025
sipa force-pushed
on Dec 7, 2025
sipa force-pushed
on Dec 7, 2025
sipa force-pushed
on Dec 7, 2025
DrahtBot removed the label
CI failed
on Dec 7, 2025
sipa
commented at 10:52 pm on December 7, 2025:
member
clusterlin: replace benchmarks with SFL-hard ones (bench)
This also adds a per-cost variant of each.
84fa6ff310
clusterlin: add class implementing SFL state (preparation)
This adds a data structure representing the optimization state for the spanning-forest
linearization algorithm (SFL), plus a fuzz test for its correctness.
This is preparation for switching over Linearize() to use this algorithm.
See https://delvingbitcoin.org/t/spanning-forest-cluster-linearization/1419 for
a description of the algorithm.
a21a2451c6
clusterlin: replace cluster linearization with SFL (feature)
This replaces the existing LIMO linearization algorithm (which internally uses
ancestor set finding and candidate set finding) with the much more performant
spanning-forest linearization algorithm.
This removes the old candidate-set search algorithm, and several of its tests,
benchmarks, and needed utility code.
8f0828ea51
clusterlin: keep FIFO queue of improvable chunks (preparation)
This introduces a queue of chunks that still need processing, in both
MakeTopological() and OptimizationStep(). This is simultaneously:
* A preparation for introducing randomization, by allowing permuting the
queue.
* An improvement to the fairness of suboptimal solutions, by distributing
the work more fairly over chunks.
* An optimization, by avoiding retrying chunks over and over again which
are already known to be optimal.
7e299020e2
clusterlin: randomize various decisions in SFL (feature)
This introduces a local RNG inside the SFL state, which is used to randomize
various decisions inside the algorithm, in order to make it hard to create
pathological clusters which predictably have bad performance.
The decisions being randomized are:
* When deciding what chunk to attempt to split, the queue order is
randomized.
* When deciding which dependency to split on, a uniformly random one is
chosen among those with higher top feerate than bottom feerate within
the chosen chunk.
* When deciding which chunks to merge, a uniformly random one among those
with the higher feerate difference is picked.
* When merging two chunks, a uniformly random dependency between them is
now activated.
* When making the state topological, the queue of chunks to process is
randomized.
490a296640
clusterlin: randomize equal-feerate parts of linearization (privacy)
This places equal-feerate chunks (with no dependencies between them) in random
order in the linearization output, hiding information about DepGraph insertion
order from the output. Likewise, it randomizes the order of transactions within
chunks for the same reason.
clusterlin: drop support for improvable chunking (simplification)
With MergeLinearizations() gone and the LIMO-based Linearize() replaced by SFL, we do not
need a class (LinearizationChunking) that can maintain an incrementally-improving chunk
set anymore.
Replace it with a function (ChunkLinearizationInfo) that just computes the chunks as
SetInfos once, and returns them as a vector. This simplifies several call sites too.
This is a metadata mirror of the GitHub repository
bitcoin/bitcoin.
This site is not affiliated with GitHub.
Content is generated from a GitHub metadata backup.
generated: 2025-12-10 03:13 UTC
This site is hosted by @0xB10C More mirrored repositories can be found on mirror.b10c.me
