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. Like simplex, it does not necessarily make progress in every step, and thus has no upper bound on its runtime, 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 react with 👎 to this comment and the bot will ignore it on the next update.
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:558
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
clusterlin: replace benchmarks with SFL-hard ones (bench)149731fb7e
clusterlin: replace cluster linearization with SFL implementation (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.
See https://delvingbitcoin.org/t/spanning-forest-cluster-linearization/1419
This removes the candidate set finding classes, as well as related tests
and benchmarks for them.
ff164c191d
clusterlin: keep track of the active parents of each transaction (optimization)
This avoids the need for a loop over all parents of a transaction while walking
a chunk, and removes the need to store the set of parent dependencies explicitly.
46f5435908
clusterlin: split chunks based on maximum gain (optimization)
This introduces the notion of gain to the SFL algorithm. Given a chunk c,
an active dependency d in it, and the chunks (t, b) that c would split into
if d were deactivated, the gain is defined as either (they are equivalent):
(feerate(t) - feerate(b)) * size(t) * size(b)
fee(t) * size(b) - fee(b) * size(t)
It happens to also be equal to these:
(feerate(t) - feerate(c)) * size(t) * size(c)
fee(t) * size(c) - fee(c) * size(t)
Its relevance is that this metric is proportional to a lower bound on the area
under the fee-size diagram which would be gained IF a deactivation of d does not
result in a self-merge of t and b again.
This commit adds logic to find, within each chunk, the dependency with the highest
gain. In benchmarks, this appears to be a very good heuristic for deciding which
splits are worth making.
5ffeff626f
clusterlin: use pre-allocated array for dependencies instead of vector (optimization)
This reduces the number of allocations required inside the SFL algorithm, and works
because the number of dependencies per transaction is at most n-1.
To minimize the memory usage from this pre-allocation (which might impact memory locality),
change the data type of DepIdx from uint32_t to uint8_t or uint16_t when possible.
c866cfa1c1
clusterlin: keep child dependencies split into active and inactive (optimization)
Within the per-transaction child dependency list, keep the active ones before all
inactive ones. This improves the complexity over iterating over active dependencies
from O(m) to O(n), as at most n-1 dependencies can be active within any given chunk
at any given time.
191ba3b8b0
clusterlin: keep FIFO queue of improvable chunks (optimization)
This distributes the work over the various chunks fairly, and simultaneously
avoids retrying chunks over and over again which are already known to be optimal.
dde20810bc
clusterlin: randomize merges/splits in SFL (feature)b1b72d147f
clusterlin: use random split in SFL on every 3rd attempt (feature)
Out of an abundance of caution that adversarially-constructed clusters might
reliably result in bad chunk split decisions with the maximum-gain strategy,
make every third consecutive attempt to split the same chunk use a random
strategy instead.
dbf1014a1d
clusterlin: make dependency being active implicit (optimization)
We do not need to actually keep track of whether a dependency is active
or not; it is implied by whether or not it appears within the active
prefix of its parent's child_deps, and its child's parent_deps.
Just remove setting and checking it.
e92b5f7130
clusterlin: add more accurate cost modeling (feature)
This adds a rough estimate of algorithm runtime, so it can be interrupted if no
solution is found in time. Due to inherent differences between platforms, this
will not be extremely accurate, but it is preferable over directly measuring
time for consistency.
a1b8305a1c
sipa force-pushed
on Aug 9, 2025
clusterlin: minimize chunks (feature)
After the normal optimization process finishes, and finds an optimal
spanning forest, run a second process (while computation budget remains)
to split chunks into minimal equal-feerate chunks.
As a side-effect, this also guarantees that the optimal chunk order is
deterministic.
3d2b9b410a
sipa force-pushed
on Aug 9, 2025
DrahtBot removed the label
CI failed
on Aug 9, 2025
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-09-02 18:13 UTC
This site is hosted by @0xB10C More mirrored repositories can be found on mirror.b10c.me
