Replace cluster linearization algorithm with SFL #32545

sipa commented at 11:24 PM on May 17, 2025: member

Part of cluster mempool: #30289.

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.

Code Coverage & Benchmarks

For details see: https://corecheck.dev/bitcoin/bitcoin/pulls/32545.

Reviews

See the guideline for information on the review process.

Type	Reviewers
ACK	instagibbs, marcofleon
Concept ACK	jonatack

If your review is incorrectly listed, please copy-paste <code></code> into the comment that the bot should ignore.

Conflicts

Reviewers, this pull request conflicts with the following ones:

#34085 (cluster mempool: exploit SFL properties in txgraph by sipa)

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.

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.

<details><summary>Hints</summary>

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.

</details>

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.

<details><summary>Hints</summary>

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.

</details>

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 23072f2b0e outdated

 554 | @@ -539,492 +555,651 @@ class LinearizationChunking
 555 |      }
 556 |  };
 557 |  
 558 | -/** 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.

jonatack commented at 4:09 PM on May 22, 2025:

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 24, 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.

<details><summary>Hints</summary>

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.

</details>

DrahtBot removed the label CI failed on May 25, 2025

sipa force-pushed on May 25, 2025

sipa force-pushed on May 28, 2025

sipa commented at 2:57 PM on May 28, 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).

./build_dev_mode/bin/bench_bitcoin --filter="Linearize.*Example.*" -min-time=10000

Here are some I have gathered:

<details> <summary>AMD Ryzen 9 5950X 16-Core Processor</summary>

| ns/cost | cost/s | err% | total | benchmark |--------------------:|--------------------:|--------:|----------:|:---------- | 1.68 | 595,052,476.10 | 0.4% | 11.01 | LinearizeBoundedExample0 | 1.92 | 521,264,873.78 | 0.1% | 11.01 | LinearizeBoundedExample1 | 1.79 | 557,860,504.16 | 0.3% | 10.58 | LinearizeBoundedExample2 | 1.89 | 528,599,597.23 | 0.1% | 10.97 | LinearizeBoundedExample3 | 1.81 | 552,507,201.82 | 0.4% | 10.81 | LinearizeBoundedExample4 | 1.97 | 508,721,677.18 | 1.0% | 11.05 | LinearizeBoundedExample5 | 1.89 | 528,912,231.85 | 0.4% | 11.06 | LinearizeBoundedExample6 | 1.79 | 557,221,394.89 | 0.8% | 11.01 | LinearizeBoundedExample7 | 1.79 | 557,162,554.42 | 0.3% | 11.05 | LinearizeBoundedExample8 | 1.84 | 543,573,897.10 | 0.3% | 10.99 | LinearizeBoundedExample9

| ns/op | |--------------------:| | 1,576.22 | | 3,010.14 | | 5,871.01 | | 6,321.90 | | 15,081.30 | | 12,227.15 | | 12,703.52 | | 11,519.71 | | 14,768.84 | | 19,655.67 | | 11,776.61 | | 17,396.59 | | 25,232.95 | | 28,941.27 | | 36,964.92 | | 37,103.54 | | 43,747.38 | | 59,132.17 | | 61,824.04 | | 73,274.33 | op/s | err% | total | benchmark --------------------:|--------:|----------:|:---------- 634,428.95 | 0.4% | 10.95 | LinearizeOptimallyExample00 332,209.92 | 0.3% | 10.99 | LinearizeOptimallyExample01 170,328.44 | 0.4% | 11.09 | LinearizeOptimallyExample02 158,180.35 | 0.6% | 10.55 | LinearizeOptimallyExample03 66,307.30 | 0.4% | 10.99 | LinearizeOptimallyExample04 81,785.18 | 0.2% | 11.01 | LinearizeOptimallyExample05 78,718.34 | 0.4% | 11.02 | LinearizeOptimallyExample06 86,807.71 | 0.3% | 11.01 | LinearizeOptimallyExample07 67,710.11 | 0.5% | 10.93 | LinearizeOptimallyExample08 50,875.90 | 0.3% | 11.03 | LinearizeOptimallyExample09 84,914.06 | 0.1% | 10.97 | LinearizeOptimallyExample10 57,482.51 | 0.5% | 10.97 | LinearizeOptimallyExample11 39,630.72 | 0.3% | 11.04 | LinearizeOptimallyExample12 34,552.73 | 0.2% | 10.98 | LinearizeOptimallyExample13 27,052.68 | 0.7% | 11.00 | LinearizeOptimallyExample14 26,951.61 | 0.3% | 11.02 | LinearizeOptimallyExample15 22,858.51 | 0.3% | 10.98 | LinearizeOptimallyExample16 16,911.27 | 0.8% | 11.04 | LinearizeOptimallyExample17 16,174.94 | 0.2% | 10.54 | LinearizeOptimallyExample18 13,647.34 | 0.6% | 10.65 | LinearizeOptimallyExample19

</details>

<details> <summary>AMD Ryzen Threadripper PRO 7995WX 96-Cores</summary>

| ns/cost | cost/s | err% | total | benchmark |--------------------:|--------------------:|--------:|----------:|:---------- | 1.31 | 763,277,399.95 | 0.0% | 10.99 | LinearizeBoundedExample0 | 1.53 | 652,463,095.02 | 0.1% | 11.00 | LinearizeBoundedExample1 | 1.49 | 672,057,837.39 | 0.0% | 11.00 | LinearizeBoundedExample2 | 1.66 | 602,362,799.74 | 0.0% | 10.69 | LinearizeBoundedExample3 | 1.52 | 656,146,353.18 | 0.1% | 10.71 | LinearizeBoundedExample4 | 1.65 | 607,795,039.45 | 0.0% | 10.76 | LinearizeBoundedExample5 | 1.59 | 628,108,657.72 | 0.0% | 10.82 | LinearizeBoundedExample6 | 1.50 | 668,384,115.59 | 0.1% | 11.00 | LinearizeBoundedExample7 | 1.51 | 663,161,838.88 | 0.0% | 11.01 | LinearizeBoundedExample8 | 1.53 | 654,682,223.87 | 0.1% | 10.99 | LinearizeBoundedExample9

| ns/op | op/s | err% | total | benchmark |--------------------:|--------------------:|--------:|----------:|:---------- | 1,209.24 | 826,967.78 | 0.3% | 10.98 | LinearizeOptimallyExample00 | 2,393.97 | 417,716.84 | 0.0% | 11.01 | LinearizeOptimallyExample01 | 4,764.63 | 209,879.68 | 0.0% | 11.01 | LinearizeOptimallyExample02 | 5,067.95 | 197,318.41 | 0.1% | 11.01 | LinearizeOptimallyExample03 | 12,716.36 | 78,638.87 | 0.0% | 11.01 | LinearizeOptimallyExample04 | 10,231.29 | 97,739.43 | 0.0% | 11.01 | LinearizeOptimallyExample05 | 10,649.64 | 93,899.84 | 0.0% | 11.01 | LinearizeOptimallyExample06 | 9,564.17 | 104,556.95 | 0.1% | 11.01 | LinearizeOptimallyExample07 | 11,884.47 | 84,143.41 | 0.3% | 11.00 | LinearizeOptimallyExample08 | 16,436.12 | 60,841.62 | 0.1% | 11.00 | LinearizeOptimallyExample09 | 9,937.05 | 100,633.51 | 0.1% | 11.00 | LinearizeOptimallyExample10 | 14,575.73 | 68,607.20 | 0.2% | 11.02 | LinearizeOptimallyExample11 | 21,355.98 | 46,825.28 | 0.1% | 11.01 | LinearizeOptimallyExample12 | 24,439.13 | 40,917.99 | 0.0% | 11.00 | LinearizeOptimallyExample13 | 31,407.36 | 31,839.67 | 0.1% | 11.00 | LinearizeOptimallyExample14 | 31,366.41 | 31,881.24 | 0.1% | 11.01 | LinearizeOptimallyExample15 | 37,182.88 | 26,894.10 | 0.1% | 11.00 | LinearizeOptimallyExample16 | 50,528.12 | 19,790.96 | 0.3% | 11.02 | LinearizeOptimallyExample17 | 52,714.16 | 18,970.24 | 0.1% | 11.00 | LinearizeOptimallyExample18 | 62,357.87 | 16,036.47 | 0.1% | 10.57 | LinearizeOptimallyExample19

</details>

<details> <summary>Apple 2023 MacBook Pro - M2 Max</summary>

| ns/cost | cost/s | err% | total | benchmark |--------------------:|--------------------:|--------:|----------:|:---------- | 1.53 | 655,436,526.57 | 0.7% | 1.10 | LinearizeBoundedExample0 | 1.81 | 552,194,379.23 | 0.2% | 1.10 | LinearizeBoundedExample1 | 1.52 | 656,148,852.84 | 0.4% | 1.09 | LinearizeBoundedExample2 | 1.75 | 572,294,606.97 | 0.7% | 1.06 | LinearizeBoundedExample3 | 1.62 | 615,593,105.29 | 0.3% | 1.07 | LinearizeBoundedExample4 | 1.78 | 561,989,024.83 | 1.2% | 1.08 | LinearizeBoundedExample5 | 1.69 | 592,612,447.36 | 0.2% | 1.10 | LinearizeBoundedExample6 | 1.58 | 633,450,827.45 | 0.3% | 1.10 | LinearizeBoundedExample7 | 1.56 | 640,690,050.49 | 0.1% | 1.10 | LinearizeBoundedExample8 | 1.59 | 628,148,004.87 | 0.2% | 1.09 | LinearizeBoundedExample9

| ns/op | op/s | err% | total | benchmark |--------------------:|--------------------:|--------:|----------:|:---------- | 1,499.94 | 666,693.94 | 0.4% | 1.09 | LinearizeOptimallyExample00 | 2,884.51 | 346,679.16 | 0.2% | 1.10 | LinearizeOptimallyExample01 | 5,815.27 | 171,961.12 | 0.1% | 1.10 | LinearizeOptimallyExample02 | 6,097.37 | 164,005.14 | 0.2% | 1.05 | LinearizeOptimallyExample03 | 13,502.59 | 74,059.89 | 0.1% | 1.10 | LinearizeOptimallyExample04 | 11,447.25 | 87,357.24 | 0.1% | 1.10 | LinearizeOptimallyExample05 | 11,639.59 | 85,913.71 | 0.1% | 1.10 | LinearizeOptimallyExample06 | 9,557.65 | 104,628.26 | 0.1% | 1.10 | LinearizeOptimallyExample07 | 12,139.84 | 82,373.43 | 0.1% | 1.10 | LinearizeOptimallyExample08 | 18,237.62 | 54,831.73 | 0.1% | 1.10 | LinearizeOptimallyExample09 | 11,806.18 | 84,701.39 | 0.1% | 1.10 | LinearizeOptimallyExample10 | 17,519.95 | 57,077.80 | 0.2% | 1.09 | LinearizeOptimallyExample11 | 24,397.16 | 40,988.37 | 0.2% | 1.10 | LinearizeOptimallyExample12 | 28,264.97 | 35,379.48 | 0.1% | 1.10 | LinearizeOptimallyExample13 | 36,230.91 | 27,600.74 | 0.5% | 1.10 | LinearizeOptimallyExample14 | 36,251.16 | 27,585.33 | 0.3% | 1.10 | LinearizeOptimallyExample15 | 42,480.07 | 23,540.45 | 0.3% | 1.10 | LinearizeOptimallyExample16 | 59,497.62 | 16,807.39 | 0.4% | 1.10 | LinearizeOptimallyExample17 | 62,192.70 | 16,079.06 | 0.2% | 1.06 | LinearizeOptimallyExample18 | 73,604.11 | 13,586.20 | 0.7% | 1.06 | LinearizeOptimallyExample19

</details>

<details> <summary>Intel Core Processor (Haswell, no TSX) [VPS]</summary>

| ns/cost | cost/s | err% | total | benchmark |--------------------:|--------------------:|--------:|----------:|:---------- | 4.39 | 227,695,874.58 | 0.4% | 10.99 | LinearizeBoundedExample0 | 5.32 | 187,925,655.80 | 2.3% | 11.09 | LinearizeBoundedExample1 | 4.96 | 201,470,069.83 | 1.6% | 11.13 | LinearizeBoundedExample2 | 5.47 | 182,878,034.13 | 1.9% | 10.75 | LinearizeBoundedExample3 | 5.02 | 199,278,377.58 | 2.6% | 10.73 | LinearizeBoundedExample4 | 5.69 | 175,678,783.21 | 2.7% | 11.08 | LinearizeBoundedExample5 | 5.53 | 180,751,956.64 | 4.1% | 11.00 | LinearizeBoundedExample6 | 5.80 | 172,338,240.84 | 2.0% | 10.81 | LinearizeBoundedExample7 | 5.24 | 190,865,678.33 | 3.1% | 10.63 | LinearizeBoundedExample8 | 5.51 | 181,564,438.26 | 2.9% | 11.38 | LinearizeBoundedExample9

| ns/op | op/s | err% | total | benchmark |--------------------:|--------------------:|--------:|----------:|:---------- | 4,399.38 | 227,304.78 | 1.9% | 11.18 | LinearizeOptimallyExample00 | 8,789.91 | 113,766.77 | 0.9% | 10.84 | LinearizeOptimallyExample01 | 15,890.75 | 62,929.71 | 1.6% | 11.07 | LinearizeOptimallyExample02 | 19,082.82 | 52,403.17 | 2.2% | 11.00 | LinearizeOptimallyExample03 | 44,627.25 | 22,407.83 | 1.8% | 11.20 | LinearizeOptimallyExample04 | 33,718.11 | 29,657.66 | 1.1% | 11.03 | LinearizeOptimallyExample05 | 35,473.62 | 28,189.96 | 1.1% | 11.05 | LinearizeOptimallyExample06 | 33,162.95 | 30,154.13 | 1.5% | 10.88 | LinearizeOptimallyExample07 | 45,473.12 | 21,991.01 | 0.9% | 11.12 | LinearizeOptimallyExample08 | 57,919.95 | 17,265.21 | 1.1% | 11.04 | LinearizeOptimallyExample09 | 32,640.19 | 30,637.08 | 2.1% | 11.16 | LinearizeOptimallyExample10 | 46,559.58 | 21,477.86 | 1.5% | 10.98 | LinearizeOptimallyExample11 | 66,614.50 | 15,011.75 | 1.4% | 10.55 | LinearizeOptimallyExample12 | 76,783.09 | 13,023.70 | 0.5% | 10.74 | LinearizeOptimallyExample13 | 97,635.10 | 10,242.22 | 1.7% | 11.00 | LinearizeOptimallyExample14 | 99,854.80 | 10,014.54 | 0.8% | 11.00 | LinearizeOptimallyExample15 | 119,444.66 | 8,372.08 | 1.2% | 11.11 | LinearizeOptimallyExample16 | 156,160.25 | 6,403.68 | 0.9% | 10.98 | LinearizeOptimallyExample17 | 163,364.57 | 6,121.28 | 0.8% | 10.90 | LinearizeOptimallyExample18 | 193,524.10 | 5,167.32 | 1.2% | 11.14 | LinearizeOptimallyExample19

</details>

<details> <summary>12th Gen Intel(R) Core(TM) i5-12500H [laptop]</summary>

| ns/cost | cost/s | err% | total | benchmark |--------------------:|--------------------:|--------:|----------:|:---------- | 1.75 | 571,671,353.08 | 0.1% | 10.99 | LinearizeBoundedExample0 | 2.05 | 487,547,934.48 | 0.1% | 11.00 | LinearizeBoundedExample1 | 1.97 | 506,752,217.57 | 0.1% | 10.64 | LinearizeBoundedExample2 | 2.24 | 447,162,026.45 | 0.1% | 11.00 | LinearizeBoundedExample3 | 2.08 | 480,557,495.14 | 0.1% | 11.01 | LinearizeBoundedExample4 | 2.30 | 434,505,839.40 | 0.1% | 11.12 | LinearizeBoundedExample5 | 2.21 | 451,557,580.61 | 0.0% | 11.00 | LinearizeBoundedExample6 | 2.25 | 444,374,372.72 | 0.0% | 11.00 | LinearizeBoundedExample7 | 2.12 | 471,017,980.18 | 0.1% | 10.93 | LinearizeBoundedExample8 | 2.22 | 450,256,469.71 | 1.1% | 11.07 | LinearizeBoundedExample9

| ns/op | op/s | err% | total | benchmark |--------------------:|--------------------:|--------:|----------:|:---------- | 1,586.71 | 630,233.45 | 0.1% | 10.98 | LinearizeOptimallyExample00 | 3,268.23 | 305,976.43 | 0.0% | 11.00 | LinearizeOptimallyExample01 | 6,858.84 | 145,797.34 | 0.2% | 10.54 | LinearizeOptimallyExample02 | 7,873.51 | 127,008.11 | 0.1% | 10.73 | LinearizeOptimallyExample03 | 17,277.23 | 57,879.64 | 0.1% | 11.00 | LinearizeOptimallyExample04 | 14,178.66 | 70,528.55 | 0.1% | 11.00 | LinearizeOptimallyExample05 | 16,009.26 | 62,463.84 | 0.0% | 10.99 | LinearizeOptimallyExample06 | 12,586.44 | 79,450.57 | 1.6% | 10.87 | LinearizeOptimallyExample07 | 15,396.54 | 64,949.64 | 0.0% | 11.00 | LinearizeOptimallyExample08 | 24,369.54 | 41,034.82 | 0.0% | 11.00 | LinearizeOptimallyExample09 | 13,610.19 | 73,474.38 | 0.1% | 10.99 | LinearizeOptimallyExample10 | 20,073.90 | 49,815.92 | 0.1% | 11.01 | LinearizeOptimallyExample11 | 30,462.32 | 32,827.44 | 0.3% | 11.12 | LinearizeOptimallyExample12 | 34,713.56 | 28,807.18 | 0.3% | 10.93 | LinearizeOptimallyExample13 | 44,015.70 | 22,719.17 | 0.1% | 11.00 | LinearizeOptimallyExample14 | 43,492.08 | 22,992.69 | 0.1% | 11.00 | LinearizeOptimallyExample15 | 51,596.62 | 19,381.12 | 0.1% | 11.01 | LinearizeOptimallyExample16 | 71,384.39 | 14,008.67 | 0.2% | 10.69 | LinearizeOptimallyExample17 | 73,714.84 | 13,565.79 | 0.1% | 10.69 | LinearizeOptimallyExample18 | 87,910.27 | 11,375.24 | 0.0% | 10.82 | LinearizeOptimallyExample19

</details>

davidgumberg commented at 3:16 AM on May 29, 2025: contributor

(built with Clang)

AMD Ryzen 9 9950X 16-Core Processor </summary>

./build/bin/bench_bitcoin --filter="Linearize.*Example.*" -min-time=10000

| ns/cost | cost/s | err% | ins/cost | cyc/cost | IPC | bra/cost | miss% | total | benchmark |--------------------:|--------------------:|--------:|----------------:|----------------:|-------:|---------------:|--------:|----------:|:---------- | 1.19 | 836,855,166.72 | 0.4% | 20.42 | 5.13 | 3.984 | 2.29 | 2.4% | 11.05 | LinearizeBoundedExample0 | 1.44 | 695,776,928.37 | 0.1% | 24.33 | 6.17 | 3.945 | 2.74 | 2.4% | 10.99 | LinearizeBoundedExample1 | 1.17 | 852,566,861.36 | 0.2% | 18.78 | 5.03 | 3.733 | 2.33 | 3.2% | 11.04 | LinearizeBoundedExample2 | 1.36 | 735,968,415.25 | 0.1% | 19.54 | 5.83 | 3.349 | 2.36 | 4.6% | 10.57 | LinearizeBoundedExample3 | 1.24 | 805,653,703.91 | 0.0% | 18.58 | 5.33 | 3.487 | 2.27 | 4.2% | 10.56 | LinearizeBoundedExample4 | 1.34 | 745,442,570.61 | 0.1% | 20.46 | 5.76 | 3.553 | 2.50 | 4.1% | 10.62 | LinearizeBoundedExample5 | 1.27 | 784,639,270.59 | 0.0% | 19.10 | 5.47 | 3.490 | 2.35 | 4.3% | 10.65 | LinearizeBoundedExample6 | 1.18 | 847,347,367.90 | 0.2% | 18.45 | 5.07 | 3.642 | 2.23 | 3.6% | 10.70 | LinearizeBoundedExample7 | 1.19 | 841,752,012.32 | 0.2% | 18.65 | 5.10 | 3.657 | 2.29 | 3.5% | 10.70 | LinearizeBoundedExample8 | 1.20 | 833,486,862.05 | 0.1% | 19.07 | 5.15 | 3.703 | 2.31 | 3.2% | 10.79 | LinearizeBoundedExample9

| ns/op | op/s | err% | ins/op | cyc/op | IPC | bra/op | miss% | total | benchmark |--------------------:|--------------------:|--------:|----------------:|----------------:|-------:|---------------:|--------:|----------:|:---------- | 1,062.27 | 941,380.47 | 0.2% | 23,154.64 | 4,561.62 | 5.076 | 2,732.15 | 1.1% | 10.99 | LinearizeOptimallyExample00 | 2,199.32 | 454,686.52 | 0.1% | 44,955.91 | 9,443.49 | 4.761 | 5,125.75 | 1.2% | 11.01 | LinearizeOptimallyExample01 | 4,655.43 | 214,803.15 | 0.1% | 76,020.42 | 19,989.80 | 3.803 | 8,376.75 | 2.7% | 11.01 | LinearizeOptimallyExample02 | 4,687.57 | 213,330.01 | 0.2% | 79,606.35 | 20,125.95 | 3.955 | 8,838.43 | 2.7% | 10.99 | LinearizeOptimallyExample03 | 11,198.28 | 89,299.41 | 0.1% | 180,121.05 | 48,080.45 | 3.746 | 21,333.25 | 2.9% | 11.01 | LinearizeOptimallyExample04 | 8,806.12 | 113,557.33 | 0.0% | 148,315.36 | 37,809.30 | 3.923 | 17,597.94 | 2.9% | 10.83 | LinearizeOptimallyExample05 | 8,881.81 | 112,589.68 | 0.0% | 129,414.56 | 38,127.56 | 3.394 | 15,799.78 | 4.3% | 10.83 | LinearizeOptimallyExample06 | 7,396.23 | 135,204.04 | 0.0% | 139,880.41 | 31,756.73 | 4.405 | 16,345.08 | 2.7% | 10.67 | LinearizeOptimallyExample07 | 9,691.58 | 103,182.40 | 0.0% | 201,859.77 | 41,612.38 | 4.851 | 23,957.84 | 1.1% | 11.01 | LinearizeOptimallyExample08 | 13,912.45 | 71,878.08 | 0.1% | 205,829.89 | 59,733.52 | 3.446 | 25,060.12 | 4.2% | 11.00 | LinearizeOptimallyExample09 | 9,799.39 | 102,047.14 | 0.1% | 131,704.66 | 42,074.45 | 3.130 | 13,959.94 | 5.7% | 11.00 | LinearizeOptimallyExample10 | 14,178.88 | 70,527.42 | 0.1% | 181,891.98 | 60,879.32 | 2.988 | 18,797.61 | 5.9% | 11.02 | LinearizeOptimallyExample11 | 19,417.52 | 51,499.89 | 0.1% | 231,655.76 | 83,370.63 | 2.779 | 26,582.04 | 6.6% | 11.01 | LinearizeOptimallyExample12 | 21,875.47 | 45,713.31 | 0.1% | 262,258.87 | 93,911.73 | 2.793 | 30,218.20 | 6.7% | 11.00 | LinearizeOptimallyExample13 | 28,875.31 | 34,631.67 | 0.1% | 336,971.73 | 123,981.98 | 2.718 | 38,520.06 | 6.5% | 11.01 | LinearizeOptimallyExample14 | 27,860.30 | 35,893.37 | 0.1% | 334,160.29 | 119,619.93 | 2.794 | 37,727.10 | 6.5% | 11.00 | LinearizeOptimallyExample15 | 33,495.46 | 29,854.79 | 0.1% | 395,850.86 | 143,808.78 | 2.753 | 45,419.38 | 6.8% | 11.00 | LinearizeOptimallyExample16 | 46,820.27 | 21,358.27 | 0.2% | 527,868.16 | 201,024.15 | 2.626 | 60,683.66 | 7.4% | 11.01 | LinearizeOptimallyExample17 | 47,420.53 | 21,087.91 | 0.1% | 549,255.39 | 203,589.67 | 2.698 | 62,108.84 | 7.0% | 11.01 | LinearizeOptimallyExample18 | 56,870.07 | 17,583.94 | 0.2% | 665,564.77 | 244,167.60 | 2.726 | 75,210.75 | 6.7% | 10.98 | LinearizeOptimallyExample19

</details> <details> <summary>

AMD Ryzen 9 7900X 12-Core Processor </summary>

./build/bin/bench_bitcoin --filter="Linearize.*Example.*" -min-time=10000

| ns/cost | cost/s | err% | ins/cost | cyc/cost | IPC | bra/cost | miss% | total | benchmark |--------------------:|--------------------:|--------:|----------------:|----------------:|-------:|---------------:|--------:|----------:|:---------- | 1.36 | 737,410,406.03 | 0.2% | 20.58 | 6.34 | 3.247 | 2.34 | 2.5% | 11.02 | LinearizeBoundedExample0 | 1.65 | 606,854,042.04 | 0.1% | 24.57 | 7.70 | 3.190 | 2.76 | 2.5% | 10.99 | LinearizeBoundedExample1 | 1.31 | 760,547,140.52 | 0.1% | 18.87 | 6.14 | 3.071 | 2.36 | 3.4% | 11.02 | LinearizeBoundedExample2 | 1.52 | 657,532,700.47 | 0.0% | 19.61 | 7.11 | 2.758 | 2.38 | 4.9% | 10.63 | LinearizeBoundedExample3 | 1.39 | 718,444,894.17 | 0.1% | 18.63 | 6.51 | 2.864 | 2.30 | 4.3% | 10.63 | LinearizeBoundedExample4 | 1.52 | 656,965,976.43 | 0.1% | 20.51 | 7.11 | 2.882 | 2.53 | 4.1% | 10.71 | LinearizeBoundedExample5 | 1.44 | 694,175,863.25 | 0.1% | 19.12 | 6.73 | 2.839 | 2.39 | 4.5% | 10.72 | LinearizeBoundedExample6 | 1.34 | 745,455,006.56 | 0.0% | 18.49 | 6.27 | 2.948 | 2.27 | 3.8% | 10.81 | LinearizeBoundedExample7 | 1.35 | 740,869,763.95 | 0.2% | 18.70 | 6.31 | 2.965 | 2.32 | 3.7% | 10.83 | LinearizeBoundedExample8 | 1.36 | 733,610,430.06 | 0.0% | 19.17 | 6.37 | 3.009 | 2.34 | 3.4% | 11.00 | LinearizeBoundedExample9

| ns/op | op/s | err% | ins/op | cyc/op | IPC | bra/op | miss% | total | benchmark |--------------------:|--------------------:|--------:|----------------:|----------------:|-------:|---------------:|--------:|----------:|:---------- | 1,231.66 | 811,912.24 | 0.0% | 23,357.46 | 5,757.88 | 4.057 | 2,788.34 | 1.0% | 11.01 | LinearizeOptimallyExample00 | 2,608.32 | 383,388.20 | 0.1% | 44,890.34 | 12,192.83 | 3.682 | 5,176.76 | 1.2% | 11.02 | LinearizeOptimallyExample01 | 5,129.41 | 194,954.12 | 0.1% | 76,112.07 | 23,977.96 | 3.174 | 8,574.18 | 2.6% | 10.99 | LinearizeOptimallyExample02 | 5,283.32 | 189,274.88 | 0.1% | 79,355.44 | 24,692.88 | 3.214 | 8,960.39 | 2.7% | 11.01 | LinearizeOptimallyExample03 | 12,510.48 | 79,933.00 | 0.1% | 178,410.73 | 58,475.18 | 3.051 | 21,948.73 | 3.0% | 11.00 | LinearizeOptimallyExample04 | 9,699.21 | 103,101.15 | 0.1% | 147,263.70 | 45,334.12 | 3.248 | 18,517.16 | 2.7% | 10.99 | LinearizeOptimallyExample05 | 9,890.03 | 101,111.94 | 0.1% | 128,779.01 | 46,228.98 | 2.786 | 16,175.51 | 4.5% | 11.00 | LinearizeOptimallyExample06 | 8,853.35 | 112,951.56 | 0.1% | 138,404.58 | 41,381.10 | 3.345 | 16,972.04 | 2.6% | 10.83 | LinearizeOptimallyExample07 | 11,429.49 | 87,493.00 | 0.0% | 199,933.47 | 53,426.08 | 3.742 | 24,782.93 | 1.0% | 11.00 | LinearizeOptimallyExample08 | 15,278.31 | 65,452.27 | 0.1% | 203,844.43 | 71,404.74 | 2.855 | 25,811.52 | 4.2% | 10.98 | LinearizeOptimallyExample09 | 10,430.03 | 95,877.04 | 0.1% | 130,835.87 | 48,749.71 | 2.684 | 14,322.22 | 5.7% | 11.01 | LinearizeOptimallyExample10 | 14,955.33 | 66,865.78 | 0.1% | 181,388.73 | 69,905.18 | 2.595 | 19,826.07 | 5.7% | 11.01 | LinearizeOptimallyExample11 | 20,192.09 | 49,524.34 | 0.1% | 229,811.63 | 94,374.34 | 2.435 | 27,200.27 | 6.6% | 11.01 | LinearizeOptimallyExample12 | 23,265.71 | 42,981.71 | 0.3% | 260,056.43 | 108,734.94 | 2.392 | 30,956.74 | 6.7% | 10.99 | LinearizeOptimallyExample13 | 29,690.95 | 33,680.30 | 0.1% | 334,363.41 | 138,778.90 | 2.409 | 39,510.12 | 6.4% | 10.99 | LinearizeOptimallyExample14 | 29,188.83 | 34,259.68 | 0.1% | 331,541.94 | 136,412.59 | 2.430 | 38,603.88 | 6.3% | 10.99 | LinearizeOptimallyExample15 | 35,084.30 | 28,502.78 | 0.0% | 391,658.97 | 163,986.36 | 2.388 | 46,505.21 | 6.6% | 11.00 | LinearizeOptimallyExample16 | 47,904.99 | 20,874.65 | 0.1% | 521,828.04 | 223,869.99 | 2.331 | 62,246.01 | 7.0% | 11.01 | LinearizeOptimallyExample17 | 49,498.85 | 20,202.49 | 0.1% | 543,459.92 | 231,331.22 | 2.349 | 63,630.07 | 6.7% | 11.01 | LinearizeOptimallyExample18 | 59,173.83 | 16,899.36 | 0.1% | 658,965.47 | 276,557.48 | 2.383 | 77,128.66 | 6.3% | 11.00 | LinearizeOptimallyExample19

</details>

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.

cmake -B build -DBUILD_BENCH=ON && cmake --build build

<details> <summary> origin/pr/32545 47bdf8faafc550bf673b4affadc73415160f9ff2</summary>

abubakarismail@Abubakars-MacBook-Pro ~/D/W/b/bitcoin ((47bdf8fa))> ./build/bin/bench_bitcoin --filter="Linearize.*Example.*" -min-ti
me=1000

| ns/cost | cost/s | err% | total | benchmark |--------------------:|--------------------:|--------:|----------:|:---------- | 1.85 | 539,881,102.87 | 6.1% | 10.64 | :wavy_dash: LinearizeBoundedExample0 (Unstable with ~171,993.8 iters. Increase minEpochIterations to e.g. 1719938) | 2.16 | 463,765,560.64 | 1.9% | 11.52 | LinearizeBoundedExample1 | 1.89 | 529,370,444.85 | 3.4% | 11.88 | LinearizeBoundedExample2 | 2.09 | 478,266,850.10 | 2.1% | 10.69 | LinearizeBoundedExample3 | 2.00 | 500,459,378.92 | 3.4% | 10.99 | LinearizeBoundedExample4 | 2.23 | 448,896,053.69 | 4.1% | 12.62 | LinearizeBoundedExample5 | 2.21 | 453,201,053.94 | 6.2% | 9.74 | :wavy_dash: LinearizeBoundedExample6 (Unstable with ~70,645.3 iters. Increase minEpochIterations to e.g. 706453) | 1.88 | 531,282,530.06 | 1.7% | 11.59 | LinearizeBoundedExample7 | 1.82 | 550,292,679.97 | 1.5% | 11.85 | LinearizeBoundedExample8 | 1.81 | 553,506,180.26 | 1.1% | 10.68 | LinearizeBoundedExample9

| ns/op | op/s | err% | total | benchmark |--------------------:|--------------------:|--------:|----------:|:---------- | 1,927.91 | 518,696.06 | 1.2% | 11.39 | LinearizeOptimallyExample00 | 3,227.99 | 309,790.35 | 1.0% | 10.99 | LinearizeOptimallyExample01 | 6,619.50 | 151,068.72 | 2.3% | 10.17 | LinearizeOptimallyExample02 | 6,648.74 | 150,404.54 | 1.1% | 10.67 | LinearizeOptimallyExample03 | 15,989.38 | 62,541.52 | 1.7% | 11.11 | LinearizeOptimallyExample04 | 13,491.31 | 74,121.78 | 4.1% | 12.15 | LinearizeOptimallyExample05 | 12,958.96 | 77,166.66 | 1.0% | 10.63 | LinearizeOptimallyExample06 | 11,525.25 | 86,766.02 | 3.7% | 11.77 | LinearizeOptimallyExample07 | 14,095.38 | 70,945.21 | 0.6% | 10.80 | LinearizeOptimallyExample08 | 21,410.11 | 46,706.90 | 1.1% | 11.46 | LinearizeOptimallyExample09 | 13,372.29 | 74,781.50 | 1.5% | 11.06 | LinearizeOptimallyExample10 | 19,803.65 | 50,495.75 | 3.2% | 10.79 | LinearizeOptimallyExample11 | 26,699.86 | 37,453.38 | 1.1% | 11.15 | LinearizeOptimallyExample12 | 36,106.95 | 27,695.50 | 8.0% | 11.03 | :wavy_dash: LinearizeOptimallyExample13 (Unstable with ~24,184.5 iters. Increase minEpochIterations to e.g. 241845) | 41,346.30 | 24,185.96 | 3.3% | 10.49 | LinearizeOptimallyExample14 | 41,673.85 | 23,995.86 | 1.6% | 9.89 | LinearizeOptimallyExample15 | 47,425.14 | 21,085.87 | 1.1% | 11.07 | LinearizeOptimallyExample16 | 66,540.78 | 15,028.38 | 2.4% | 11.26 | LinearizeOptimallyExample17 | 66,934.73 | 14,939.93 | 1.4% | 10.54 | LinearizeOptimallyExample18 | 81,828.99 | 12,220.61 | 1.8% | 11.44 | LinearizeOptimallyExample19

</details>

~Almost 10x speedup~ edit: bench cases changed, so not comparable with master.

sipa commented at 1:54 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. 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

<details> <summary>Macbook Pro M4</summary>

$ build/bin/bench_bitcoin --filter="Linearize.Example." -min-time=10000

| ns/cost | cost/s | err% | total | benchmark |--------------------:|--------------------:|--------:|----------:|:---------- | 1.12 | 893,382,447.85 | 0.5% | 11.06 | LinearizeBoundedExample0 | 1.34 | 743,601,759.92 | 0.7% | 11.07 | LinearizeBoundedExample1 | 1.14 | 880,692,144.98 | 0.3% | 10.99 | LinearizeBoundedExample2 | 1.33 | 749,663,261.00 | 0.3% | 10.98 | LinearizeBoundedExample3 | 1.24 | 807,545,779.18 | 0.5% | 10.57 | LinearizeBoundedExample4 | 1.37 | 730,046,090.82 | 0.4% | 10.64 | LinearizeBoundedExample5 | 1.28 | 779,862,831.19 | 0.4% | 10.66 | LinearizeBoundedExample6 | 1.17 | 856,937,081.55 | 0.4% | 10.71 | LinearizeBoundedExample7 | 1.19 | 840,624,085.43 | 0.2% | 10.74 | LinearizeBoundedExample8 | 1.19 | 840,938,970.51 | 0.4% | 10.74 | LinearizeBoundedExample9

| ns/op | op/s | err% | total | benchmark |--------------------:|--------------------:|--------:|----------:|:---------- | 1,155.37 | 865,524.35 | 0.2% | 11.00 | LinearizeOptimallyExample00 | 2,170.00 | 460,828.59 | 0.2% | 11.04 | LinearizeOptimallyExample01 | 4,507.21 | 221,866.90 | 0.2% | 11.01 | LinearizeOptimallyExample02 | 4,435.85 | 225,435.87 | 0.3% | 10.96 | LinearizeOptimallyExample03 | 10,189.93 | 98,136.12 | 0.2% | 11.02 | LinearizeOptimallyExample04 | 8,854.57 | 112,936.09 | 0.4% | 10.79 | LinearizeOptimallyExample05 | 8,685.08 | 115,140.05 | 0.1% | 10.82 | LinearizeOptimallyExample06 | 7,162.17 | 139,622.57 | 0.0% | 10.64 | LinearizeOptimallyExample07 | 9,120.88 | 109,638.49 | 0.0% | 11.00 | LinearizeOptimallyExample08 | 12,780.73 | 78,242.79 | 0.1% | 11.00 | LinearizeOptimallyExample09 | 9,242.70 | 108,193.53 | 0.1% | 10.98 | LinearizeOptimallyExample10 | 13,653.81 | 73,239.62 | 0.3% | 11.04 | LinearizeOptimallyExample11 | 19,211.80 | 52,051.34 | 0.2% | 11.00 | LinearizeOptimallyExample12 | 22,243.75 | 44,956.45 | 0.1% | 11.00 | LinearizeOptimallyExample13 | 28,409.81 | 35,199.11 | 0.2% | 10.99 | LinearizeOptimallyExample14 | 28,265.23 | 35,379.16 | 0.1% | 10.99 | LinearizeOptimallyExample15 | 33,767.58 | 29,614.20 | 0.3% | 11.02 | LinearizeOptimallyExample16 | 46,851.80 | 21,343.90 | 0.4% | 11.03 | LinearizeOptimallyExample17 | 48,470.35 | 20,631.17 | 0.1% | 10.98 | LinearizeOptimallyExample18 | 57,668.81 | 17,340.40 | 0.4% | 10.98 | LinearizeOptimallyExample19

</details>

sipa force-pushed on May 31, 2025

sipa commented at 1:24 PM on May 31, 2025: member

@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.

sipa commented at 9:25 PM on May 31, 2025: member

Thanks for all the benchmarks, here are some graphs created from them to show their relative performance:

(code & data to generate them is here)

sipa commented at 1:43 AM on June 2, 2025: member

If people are interested in a much larger scale comparison between the old and the new algorithm, checkout https://github.com/sipa/bitcoin/commits/bench_sfl_css, build its bin/bench_bitcoin, and:

wget https://bitcoin.sipa.be/clusters/clusters.tgz
tar -xzf clusters.tgz
for F in clusters_sim2023_large clusters_medium clusters_spanning clusters_bipartite; do time ./build/bin/bench_bitcoin --filter="LinearizeDataSet" <$F >$F.out; done
zstd -19 clusters_*.out

And then PR the resulting *.out.zst files to https://github.com/sipa/lin-benches/tree/main/data.

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.

<details> <summary>full command</summary>

git remote add sipa https://github.com/sipa/bitcoin.git || true && git fetch sipa bench_sfl_css && git switch -C bench_sfl_css sipa/bench_sfl_css && \
git clean -fxd && git reset --hard && \
cmake -B build -DBUILD_BENCH=ON -DCMAKE_BUILD_TYPE=Release && cmake --build build -j"$(nproc)" && \
wget -q https://bitcoin.sipa.be/clusters/clusters.tgz && tar -xzf clusters.tgz && \
for F in clusters_sim2023_large clusters_medium clusters_spanning clusters_bipartite; do \
    time build/bin/bench_bitcoin --filter="LinearizeDataSet" <"$F" >"$F.out"; \
done && \
tar -czf clusters.out.tgz clusters_*.out

</details>

It took considerably longer than expected (~13h):

clusters_sim2023_large: 11h 39m
clusters_medium: 26m 33s
clusters_spanning: 19m 37s
clusters_bipartite: 37m 17s

Let's see if I can attach it here: clusters.out.tgz

sipa commented at 12:44 PM on June 4, 2025: member

I've created a repo for benchmark data, and added my results plus @l0rinc's: https://github.com/sipa/lin-benches/tree/main/data.

Also, is this with 32-bit or 64-bit userspace?

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)

$ file bitcoind
bitcoind: 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

<details> <summary>additional details</summary>

$ getconf LONG_BIT
64
$ dpkg --print-architecture
arm64
$ uname -m
aarch64

</details>

sipa force-pushed on Jun 12, 2025

sipa commented at 5:28 PM on June 12, 2025: member

Rebased on top of #30605.

sipa force-pushed on Jun 12, 2025

sipa force-pushed on Jun 14, 2025

sipa force-pushed on Jul 11, 2025

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.

<details><summary>Hints</summary>

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.

</details>

DrahtBot removed the label Needs rebase 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 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() after Linearize() 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 52b983bf90 outdated

1896 | - *
1897 | - * Complexity: possibly O(N * min(max_iterations + N, sqrt(2^N))) where N=depgraph.TxCount().
1898 |   */
1899 |  template<typename SetType>
1900 | -std::tuple<std::vector<DepGraphIndex>, bool, uint64_t> Linearize(const DepGraph<SetType>& depgraph, uint64_t max_iterations, uint64_t rng_seed, std::span<const DepGraphIndex> old_linearization = {}) noexcept
1901 | +std::tuple<std::vector<DepGraphIndex>, bool, uint64_t> Linearize(const DepGraph<SetType>& depgraph, uint64_t max_iterations, uint64_t rng_seed, std::span<const DepGraphIndex> old_linearization = {}, bool is_topological = true) noexcept

Copilot commented at 12:30 AM on October 20, 2025:

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 12: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.

<details> <summary>Show a summary per file</summary>

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

</details>

<details> <summary>Comments suppressed due to low confidence (1)</summary>

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.

// Copyright (c) The Bitcoin Core developers

</details>

Tip: Customize your code reviews with copilot-instructions.md. <a href="/bitcoin/bitcoin/new/master/.github?filename=copilot-instructions.md" class="Link--inTextBlock" target="_blank" rel="noopener noreferrer">Create the file</a> or <a href="https://docs.github.com/en/copilot/customizing-copilot/adding-repository-custom-instructions-for-github-copilot" class="Link--inTextBlock" target="_blank" rel="noopener noreferrer">learn how to get started</a>.

in src/bench/cluster_linearize.cpp:47 in 52b983bf90 outdated

  65 | -    });
  66 | -}
  67 | -
  68 | -template<size_t N>
  69 | -void BenchLinearizeOptimally(benchmark::Bench& bench, const std::array<uint8_t, N>& serialized)
  70 | +void BenchLinearizeOptimally(benchmark::Bench& bench, const std::vector<uint8_t>& serialized)

Copilot commented at 12:30 AM on October 20, 2025:

[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.

template <size_t N>
void BenchLinearizeOptimally(benchmark::Bench& bench, const std::array<uint8_t, N>& serialized)

sipa force-pushed on Oct 26, 2025

sipa force-pushed on Oct 27, 2025

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

Rebased on top of #33629.

DrahtBot added the label Needs rebase on Nov 25, 2025

sipa force-pushed on Nov 25, 2025

sipa commented at 12:39 PM on November 25, 2025: member

Rebased after merge of #33629.

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:

    SetInfo operator-(const SetInfo& other) const noexcept

sipa commented at 8:16 PM on December 6, 2025:

Done.

in src/cluster_linearize.h:850 in 060e1856b1

 946 | +            auto& tx_data = m_tx_data[tx];
 947 | +            auto unreached = (DownWard ? tx_data.children : tx_data.parents) - explored;
 948 | +            while (unreached.Any()) {
 949 | +                m_cost += 3;
 950 | +                auto chunk_rep = m_tx_data[unreached.First()].chunk_rep;
 951 | +                auto& reached = m_tx_data[m_tx_data[unreached.First()].chunk_rep].chunk_setinfo;

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?

sipa commented at 8:16 PM on December 6, 2025:

Nice catch, done both.

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 f81f72a11e outdated

 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:

 * The collection of all spanning trees for the entire cluster form a spanning forest. In the extreme each

sipa commented at 2:22 PM on December 9, 2025:

Done.

in src/cluster_linearize.h:481 in f81f72a11e outdated

 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."

sipa commented at 7:38 PM on December 8, 2025:

If you don't merge along equal-feerate dependencies, you can end up in a situation with two equal-feerate "chunks" that depend on each other.

E.g. the AC and BD "chunks" in:

graph BT;
A["A: 1/1"];
B["B: 1/1"];
C["C: 2/1"];
D["D: 2/1"];
C --> A;
C -.-> B;
D -.-> A;
D --> B;

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

sipa commented at 2:48 PM on December 9, 2025:

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 f81f72a11e outdated

 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?

sipa commented at 7:50 PM on December 8, 2025:

Yeah, exactly.

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 f81f72a11e outdated

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:

        // If we started from a topological input, the resulting feerate diagram cannot be worse or incomparable.

sipa commented at 2:22 PM on December 9, 2025:

Done.

in src/test/fuzz/cluster_linearize.cpp:745 in 85cff48b78 outdated

 738 | @@ -799,14 +739,11 @@ FUZZ_TARGET(clusterlin_simple_finder)
 739 |      // AncestorCandidateFinder it is being tested against.

instagibbs commented at 8:44 PM on December 4, 2025:

85cff48b782538ed5a1c980015dd01cb32986b66

straggling AncestorCandidateFinder reference

sipa commented at 2:22 PM on December 9, 2025:

Fixed.

in src/cluster_linearize.h:1124 in f81f72a11e outdated

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:

                    // De-activate it otherwise.

sipa commented at 2:22 PM on December 9, 2025:

Done.

sipa force-pushed on Dec 6, 2025

sipa commented at 8:18 PM on December 6, 2025: member

I have reorganized this PR, dropping most optimizations in favor of a future follow-up.

Addressed comments, added more explanations, and made a few code simplifications.

A python version of the algorithm, lacking most optimizations and using simpler data structures than the C++ version, can be found in https://gist.github.com/sipa/822f60db6608a26bb4aae75fd31bcb12 (in sfl.py).

sipa force-pushed on Dec 6, 2025

DrahtBot added the label CI failed on Dec 6, 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.

<details><summary>Hints</summary>

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.

</details>

sipa force-pushed on Dec 6, 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

Now a proper repository for the Python version: https://github.com/sipa/pyclusterlin

sipa force-pushed on Dec 9, 2025

sipa commented at 2:04 PM on December 10, 2025: member

I have pushed an additional WIP commit which rewords and expands the big SpanningForestState comment. LMK what you think. If reviewers think it's an improvement, I'll squash it into the individual commits.

in src/cluster_linearize.h:502 in 8c990cc2f5 outdated

 531 | + *
 532 | + * - topological: We say the state is topological whenever no inactive dependency exists between
 533 | + *                two distinct chunks such that the child chunk has higher or equal feerate than
 534 | + *                the parent chunk.
 535 | + *
 536 | + *                The relevance is that whenever the state is topological, the produced output

instagibbs commented at 2:30 PM on December 10, 2025:

8c990cc2f5a7e93a5debb7eaf20e7f2c887df70d

might be worth noting this is an if and only if situation.

sipa commented at 3:28 PM on December 10, 2025:

It's not, but it's pretty subtle.

You could have two equal-feerate chunks that depend on each other in one way but not the other one. If so, it doesn't matter whether they're merged or not.

Worth elaborating on?

instagibbs commented at 3:39 PM on December 10, 2025:

actually not sure what I meant here on second read, ignore

instagibbs commented at 3:54 PM on December 10, 2025:

ok, so I just "forgot" again that "or equal" means you can clearly have same feerate chunks that can be merged, hence not topological in the SFL state sense

in src/cluster_linearize.h:479 in 8c990cc2f5

 493 | - * consists of each of the chunks, from high to low feerate, each internally ordered in an
 494 | - * arbitrary but topologically-valid way. If the spanning forest is topological, then the output
 495 | - * linearization is also topological.
 496 | + * The algorithm consists of switching dependencies between active and inactive. The final
 497 | + * linearization that is produced at the end consists of these chunks, sorted from high to low
 498 | + * feerate, each individually sorted in an arbitrary but topological (= no parent before child)

marcofleon commented at 2:51 PM on December 10, 2025:

topological = no child before parent yes? Or could be (= parents before children), put another way

sipa commented at 3:32 PM on December 10, 2025:

Thanks, fixed!

in src/cluster_linearize.h:488 in 8c990cc2f5

 517 | + *
 518 | + * - acyclic: The state is acyclic whenever no cycle of active dependencies exists within the
 519 | + *            graph, ignoring the parent/child direction. This is equivalent to saying that within
 520 | + *            each chunk the set of active dependencies form a tree, and thus the overall set of
 521 | + *            active dependencies in the graph form a spanning forest, giving the algorithm its
 522 | + *            name. Being acylic is also equivalent to every chunk of N transactions having exactly

marcofleon commented at 2:52 PM on December 10, 2025:

typo: acyclic

sipa commented at 3:32 PM on December 10, 2025:

Fixed.

in src/cluster_linearize.h:574 in 8c990cc2f5

 634 | - * This guarantees an initial topological state whose output linearization is at least as good
 635 | - * (in the convexified feerate diagram sense) as the input existing linearization bootstrapped from.
 636 | + * What remains to be specified are three heuristics:
 637 | + *
 638 | + * - How to decide what dependency to activate (when merging chunks):
 639 | + *   - A uniformly random dependency between the two maximum-feerate-difference chunks is activated.

instagibbs commented at 2:56 PM on December 10, 2025:

8c990cc2f5a7e93a5debb7eaf20e7f2c887df70d

to make sure I'm understanding, the two chunks being chosen to be merged are described here, correct? https://github.com/bitcoin/bitcoin/pull/32545/commits/8c990cc2f5a7e93a5debb7eaf20e7f2c887df70d#diff-1433c1fc4926a466291656ba67cf6b029523e4bd5da177ade812f25edf07343cR543

top or bottom chunk along with highest/lowest feerate difference which is maximally different

in effect the new info here is just "uniformly random"

sipa commented at 3:32 PM on December 10, 2025:

I have pushed another updated which drops the "maximum feerate difference" explanation entirely. I think encapsulating all of that within "merge upwards" and "merge downwards" rules is more concrete.

To be clear, the "uniformly random" aspect is something that doesn't exist in the initial "add class implementing SFL state" PR, it's added in a slightly later commit. The reword commit is at the end, so it's just the final state of the explainer comment.

instagibbs commented at 3:38 PM on December 10, 2025:

ok then I'm reading it correctly and agree to drop the language (I couldn't tell if it was new info or a restatement of prior)

instagibbs commented at 3:01 PM on December 10, 2025: member

8c990cc2f5a7e93a5debb7eaf20e7f2c887df70d seems like an improvement, only a couple comments

marcofleon commented at 3:06 PM on December 10, 2025: contributor

I think this new comment is better.

sipa force-pushed on Dec 10, 2025

sipa commented at 8:13 PM on December 10, 2025: member

I've squashed in the new explainer comment, plus a number of other changes:

Split out loading of an existing linearization into a separate commit.
Split out adding support for reading non-topological inputs to ReadLinearization into a separate commit.
Various small improvements to benchmarks, tests, comments.

in src/txmempool.h:56 in 9a22b41a79 outdated

  52 | @@ -53,7 +53,7 @@ static const uint32_t MEMPOOL_HEIGHT = 0x7FFFFFFF;
  53 |  /** How many linearization iterations required for TxGraph clusters to have
  54 |   * "acceptable" quality, if they cannot be optimally linearized with fewer
  55 |   * iterations. */
  56 | -static constexpr uint64_t ACCEPTABLE_ITERS = 1'700;
  57 | +static constexpr uint64_t ACCEPTABLE_ITERS = 1'000;

instagibbs commented at 8:59 PM on December 10, 2025:

8f0828ea5144f261ff5e0cc39ee5eed17d0eec57

why this reduction? commit message commenting on it could be helpful

sipa commented at 10:55 PM on December 12, 2025:

I have reverted this change. My benchmarks show that the time per cost is quite similar to before, which I'm now mentioning in the commit message. This will be overhauled in #34023.

in src/test/cluster_linearize_tests.cpp:57 in 1c008c063d outdated

  53 | @@ -52,6 +54,63 @@ void TestDepGraphSerialization(const std::vector<std::pair<FeeFrac, SetType>>& c
  54 |      BOOST_CHECK(depgraph == depgraph_read);
  55 |  }
  56 |  
  57 | +void TestOptimalLinearization(const std::vector<uint8_t>& enc, const std::vector<FeeFrac>& diagram)

instagibbs commented at 3:38 PM on December 11, 2025:

1c008c063df383aff64c564b116802b427a228ce

void TestOptimalLinearization(const std::vector<uint8_t>& enc, const std::vector<FeeFrac>& optimal_diagram)

sipa commented at 10:55 PM on December 12, 2025:

Done.

in src/test/cluster_linearize_tests.cpp:85 in 1c008c063d outdated

  80 | +                // Construct random input linearization.
  81 | +                std::shuffle(lin.begin(), lin.end(), rng);
  82 | +                FixLinearization(depgraph, lin);
  83 | +                break;
  84 | +            }
  85 | +            std::tie(lin, opt, cost) = Linearize(depgraph, 1000000, rng.rand64(), lin);

instagibbs commented at 3:45 PM on December 11, 2025:

1c008c063df383aff64c564b116802b427a228ce

Please leave a note that 1M iterations is enough for all given dependency graphs but often a lot less than MaxOptimalLinearizationIters

sipa commented at 10:55 PM on December 12, 2025:

I have just increased it to 1T iterations, which ought to be enough for anyone.

in src/bench/cluster_linearize.cpp:79 in 094e845f73 outdated

 266 | +        for (uint64_t iter = 0; iter < 100; ++iter) {
 267 | +            auto [_lin, optimal, cost] = Linearize(depgraph, /*max_iterations=*/10000000, /*rng_seed=*/iter);
 268 | +            total_cost += cost;
 269 | +        }
 270 | +
 271 | +        // Benchmark the time per cost.

instagibbs commented at 4:04 PM on December 11, 2025:

094e845f7309c8cf4e172c8fe07e200e054ca2db

TIL, nice

in src/cluster_linearize.h:639 in c2eaf22503 outdated

 836 | +         *  be formed if this dependency were to be deactivated. */
 837 | +        SetInfo<SetType> top_setinfo;
 838 | +    };
 839 | +
 840 | +    /** The set of all transactions in the cluster. */
 841 | +    SetType m_transactions;

instagibbs commented at 6:49 PM on December 11, 2025:

c2eaf22503f7af057599f02ecb5f24a267ea33e2

suggestion:

-    /** The set of all transactions in the cluster. */
-    SetType m_transactions;
-    /** Information about each transaction (and chunks). Indexed by TxIdx. */
+    /** The set of all TxIdx's of transactions in the cluster indexing into m_tx_data. */
+    SetType m_transaction_idxs;
+    /** Information about each transaction (and chunks). Keeps the "holes" from DepGraph
+        during construction. Indexed by TxIdx. */
     std::vector<TxData> m_tx_data;

sipa commented at 10:56 PM on December 12, 2025:

Done, except renaming to m_transaction_idxs, because I'm too lazy to update all the affected commits right now. Will leave this open.

sipa commented at 9:21 PM on December 15, 2025:

Renamed now.

in src/cluster_linearize.h:916 in c2eaf22503 outdated

1065 | +    explicit SpanningForestState(const DepGraph<SetType>& depgraph) noexcept
1066 | +    {
1067 | +        m_transactions = depgraph.Positions();
1068 | +        auto num_transactions = m_transactions.Count();
1069 | +        m_tx_data.resize(depgraph.PositionRange());
1070 | +        m_dep_data.reserve(((num_transactions + 1) / 2) * (num_transactions / 2));

instagibbs commented at 6:56 PM on December 11, 2025:

c2eaf22503f7af057599f02ecb5f24a267ea33e2

Exposing my ignorance here, but why reserve this value? Deserves a comment.

sipa commented at 10:56 PM on December 12, 2025:

It's to avoid reallocating; this formula gives the maximum number of dependencies a cluster with a given number of transactions can have. I have added a comment. Does this suffice?

instagibbs commented at 1:18 PM on December 15, 2025:

I was more asking about the specific number; I'm guessing it's related to the maximum number of "reduced" relations with their transitive reductions.

The "worst" I can naively do is split up N into two sets of nodes, half each, then fully connect the two sets -> floor(N^2 / 4) , I think

sipa commented at 1:21 PM on December 15, 2025:

That's exactly it.

If the graph has an odd number of elements, you need to divide it into a group of size (n-1)/2 and a group of (n+1)/2, though. This formula covers both even and odd cases.

sipa commented at 9:21 PM on December 15, 2025:

I added a comment explaining the formula. Also, simplified it to N^2 / 4, which is actually also correct for the odd-numbered case.

in src/cluster_linearize.h:965 in c2eaf22503 outdated

 960 | +        auto& bottom_chunk = m_tx_data[bottom_rep];
 961 | +        Assume(bottom_chunk.chunk_rep == bottom_rep);
 962 | +        // Activate the first dependency between bottom_chunk and top_chunk.
 963 | +        for (auto tx : top_chunk.chunk_setinfo.transactions) {
 964 | +            auto& tx_data = m_tx_data[tx];
 965 | +            if (tx_data.children.Overlaps(bottom_chunk.chunk_setinfo.transactions)) {

instagibbs commented at 7:43 PM on December 11, 2025:

c2eaf22503f7af057599f02ecb5f24a267ea33e2

just making sure this is a quick check to avoid looping over deps, not a correctness requirement

sipa commented at 10:57 PM on December 12, 2025:

Indeed! Added as comment.

sipa force-pushed on Dec 11, 2025

DrahtBot added the label CI failed on Dec 11, 2025

DrahtBot removed the label CI failed on Dec 11, 2025

sipa commented at 3:02 AM on December 12, 2025: member

I have added an extensive comment inside the SpanningForestState::Activate() function.

sipa force-pushed on Dec 12, 2025

sipa commented at 4:43 PM on December 12, 2025: member

I have rewritten SpanningForestState::UpdateChunk to no longer traverse the chunk by walking dependencies, but by looping over all dependencies of the chunk directly, and using the top_setinfo to figure out which ones to update. It's a few percent faster, simpler, and additionally allowed dropping the tracking of parent dependencies of a transaction entirely.

in src/cluster_linearize.h:920 in a0cb73b425 outdated

 915 | +        //
 916 | +        // Let UpdateChunk traverse the old parent chunk top_part (ABC in example), and add
 917 | +        // bottom_part (DEF) to every dependency's top_set which has the parent (C) in it. The
 918 | +        // representative of each of these transactions was already top_rep, so that is not being
 919 | +        // changed here.
 920 | +        UpdateChunk<false>(top_part.transactions, dep_data.parent, top_rep, bottom_part);

instagibbs commented at 4:58 PM on December 12, 2025:

a0cb73b4257f771353f6732e7afdaf2d03b51efe

now that UpdateChunk has two TxIdx args let's annotate themhere and other three spots

sipa commented at 10:57 PM on December 12, 2025:

I was considering that already, done.

in src/test/fuzz/cluster_linearize.cpp:999 in ab1416bb47 outdated

1053 | @@ -1230,6 +1054,13 @@ FUZZ_TARGET(clusterlin_sfl)
1054 |              }
1055 |          }
1056 |      }
1057 | +
1058 | +    //
1059 | +    // Verify that optimality is reached within an expected amount of work.
1060 | +    //
1061 | +    if (sfl.GetCost() > MaxOptimalLinearizationIters(depgraph.TxCount())) {
1062 | +        assert(is_optimal);

instagibbs commented at 5:33 PM on December 12, 2025:

ab1416bb471c9326bb77ee464be6aeebf663e024

Feels like dead code to me here considering it's double of whatever you've seen in a large randomized trial.

sipa commented at 10:58 PM on December 12, 2025:

The point here is to prevent against potential bugs added in the future, which result in optimality just never being reached anymore. Absent bounds on expected iteration count, this would render a large portion of this test powerless (because anything in is_optimal, which includes all quality checks, won't be reached anymore).

Added a comment. Does this explain it?

instagibbs commented at 1:21 PM on December 15, 2025:

The new assert is more in-line with my expectations, yes

in src/test/fuzz/cluster_linearize.cpp:1155 in a0cb73b425 outdated

1150 | +    //
1151 | +    // Construct the depgraph and SFL state for it.
1152 | +    //
1153 | +    bool is_topological = false;
1154 | +    if (make_connected) MakeConnected(depgraph);
1155 | +    SpanningForestState sfl(depgraph);

instagibbs commented at 5:57 PM on December 12, 2025:

suggestion:

for each of the operations, we could check that the GetCost() doesn't return an unexpectedly high jump. Cost should be bounded by series of merges, or a single split and series of merges.

sipa commented at 10:59 PM on December 12, 2025:

I have not done this (yet), because it's hard to maintain in #34023, where the cost function becomes a lot more complicated.

in src/cluster_linearize.h:1154 in a0cb73b425 outdated

1149 | +                    const auto& dep_data = m_dep_data[dep_idx];
1150 | +                    if (!dep_data.active) continue;
1151 | +                    // Skip if this dependency is ineligible (the top chunk that would be created
1152 | +                    // does not have higher feerate than the chunk it is currently part of).
1153 | +                    if (!(dep_data.top_setinfo.feerate >> chunk_data.chunk_setinfo.feerate)) continue;
1154 | +                    // Deactivate it otherwise.

instagibbs commented at 6:08 PM on December 12, 2025:

                    // Deactivate it otherwise and then make it topological with a series of merges.

sipa commented at 10:59 PM on December 12, 2025:

Done.

in src/cluster_linearize.h:901 in a0cb73b425 outdated

1063 | +        // Deactivate the specified dependency, splitting it into two new chunks: a top containing
1064 | +        // the parent, and a bottom containing the child. The top should have a higher feerate.
1065 | +        Deactivate(dep_idx);
1066 | +        // Merge the top chunk with lower-feerate chunks it depends on (which may be the bottom it
1067 | +        // was just split from, or other pre-existing chunks).
1068 | +        MergeSequence<false>(dep_data.parent);

instagibbs commented at 6:17 PM on December 12, 2025:

a0cb73b4257f771353f6732e7afdaf2d03b51efe

IIUC these two invocations are optimizations we can use since we know where things are potentially mergable next instead of MakeTopological?

sipa commented at 11:00 PM on December 12, 2025:

Good observation, I have added a comment.

(historically, MakeTopological was actually using MergeSequence before an overhaul, which may explain why this wasn't explained already)

in src/test/fuzz/cluster_linearize.cpp:336 in 9f7f80f940 outdated

 345 | +                if ((depgraph.Ancestors(j) & todo) == TestBitSet::Singleton(j)) {
 346 | +                    potential_next.Set(j);
 347 | +                }
 348 |              }
 349 | +        } else {
 350 | +            potential_next = todo;

instagibbs commented at 8:29 PM on December 12, 2025:

9f7f80f9407d10c95c2690e34dfa918c6a361f21

nit

            // Allow any element to be selected next, regardless of topology
            potential_next = todo;

sipa commented at 11:00 PM on December 12, 2025:

Done.

in src/test/fuzz/cluster_linearize.cpp:1195 in 9f7f80f940 outdated

1195 | @@ -1192,13 +1196,11 @@ FUZZ_TARGET(clusterlin_sfl)
1196 |          auto lin = sfl.GetLinearization();
1197 |          // Which must be valid.
1198 |          SanityCheck(depgraph, lin);
1199 | -        // If we started from a topological input, the resulting feerate diagram must be at least

instagibbs commented at 8:33 PM on December 12, 2025:

9f7f80f9407d10c95c2690e34dfa918c6a361f21

Unnecessary code movement? This moves right back after f7e0857b97afe30d9a2c0a9ceb49ddd798ad5642

sipa commented at 11:00 PM on December 12, 2025:

This was a result of commit surgery gone wrong. Fixed.

instagibbs commented at 8:56 PM on December 12, 2025: member

reviewed through ab1416bb471c9326bb77ee464be6aeebf663e024

continuing on with optimizations next

only minor quibbles after the nice reworkings of comments and UpdateChunk

sipa force-pushed on Dec 12, 2025

DrahtBot added the label CI failed on Dec 12, 2025

sipa commented at 11:07 PM on December 12, 2025: member

I have addressed most of @instagibbs's comments above, and also rewritten SpanningForestState::SanityCheck to no longer rely on walking clusters. It's a bit more verbose now, but maybe easier to follow.

DrahtBot commented at 11:07 PM on December 12, 2025: contributor

🚧 At least one of the CI tasks failed. Task Windows-cross to x86_64, ucrt: https://github.com/bitcoin/bitcoin/actions/runs/20182170466/job/57944882529 LLM reason (✨ experimental): Compilation failed: -Werror treats a range-for loop copying a tuple in cluster_linearize.h as an error.

<details><summary>Hints</summary>

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.

</details>

DrahtBot removed the label CI failed on Dec 13, 2025

sipa force-pushed on Dec 13, 2025

sipa force-pushed on Dec 14, 2025

DrahtBot added the label CI failed on Dec 14, 2025

DrahtBot commented at 10:48 PM on December 14, 2025: contributor

🚧 At least one of the CI tasks failed. Task Windows-cross to x86_64, ucrt: https://github.com/bitcoin/bitcoin/actions/runs/20215030449/job/58026651059 LLM reason (✨ experimental): Compilation failed due to a treated-as-error warning: a boolean expression is being compared to 0 in cluster_linearize.cpp, causing the build to fail.

<details><summary>Hints</summary>

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.

</details>

DrahtBot removed the label CI failed on Dec 15, 2025

sipa force-pushed on Dec 15, 2025

sipa commented at 1:24 PM on December 15, 2025: member

I have made a number of changes here since my last comment:

Made a few more improvements/simplifications to SpanningForestState::SanityCheck.
Simplified the sub-chunk transaction order randomization in SpanningForestState::GetLinearization
Rewrote the clusterlin_sfl fuzz test to verify properties of every step of the algorithm, rather than a single final state. It's slower now, but more closely tracks properties like every split+merge improving the diagram, etc.

I won't make substantial changes like these anymore unless requested by review.

in src/cluster_linearize.h:986 in 26661a6c65 outdated

1143 | +            auto& chunk_data = m_tx_data[chunk];
1144 | +            // If what was popped is not currently a chunk representative, continue. This may
1145 | +            // happen when it was merged with something else since being added.
1146 | +            if (chunk_data.chunk_rep != chunk) continue;
1147 | +            int flip = m_rng.randbool();
1148 | +            for (int i = 0; i < 2; ++i) {

brunoerg commented at 2:02 PM on December 15, 2025:

Unkilled mutant:

diff --git a/src/cluster_linearize.h b/src/cluster_linearize.h
index dc7d0e8495..1a894033e8 100644
--- a/src/cluster_linearize.h
+++ b/src/cluster_linearize.h
@@ -983,7 +983,7 @@ public:
             // happen when it was merged with something else since being added.
             if (chunk_data.chunk_rep != chunk) continue;
             int flip = m_rng.randbool();
-            for (int i = 0; i < 2; ++i) {
+            for (int i = 0; i <= 2; ++i) {
                 if (i ^ flip) {
                     // Attempt to merge the chunk upwards.
                     auto result_up = MergeStep<false>(chunk);

sipa commented at 4:08 PM on December 15, 2025:

That's expected; the loop is there to try merging both upwards and downwards, but more iterations will just cause it to re-attempt the same direction again.

brunoerg commented at 4:10 PM on December 15, 2025:

Cool, thanks.

in src/cluster_linearize.h:1249 in 26661a6c65 outdated

1625 | +                // Verify the chunk's transaction set: it must contain the representative, and for
1626 | +                // every active dependency, if it contains the parent or child, it must contain
1627 | +                // both. It must have exactly N-1 active dependencies in it, guaranteeing it is
1628 | +                // acyclic.
1629 | +                SetType expected_chunk = SetType::Singleton(tx_idx);
1630 | +                while (true) {

brunoerg commented at 2:27 PM on December 15, 2025:

Unkilled mutant:

diff --git a/src/cluster_linearize.h b/src/cluster_linearize.h
index 8f5b099ef2..f7d87f048c 100644
--- a/src/cluster_linearize.h
+++ b/src/cluster_linearize.h
@@ -1240,7 +1240,7 @@ public:
                 // both. It must have exactly N-1 active dependencies in it, guaranteeing it is
                 // acyclic.
                 SetType expected_chunk = SetType::Singleton(tx_idx);
-                while (true) {
+                while (1==0) {
                     auto old = expected_chunk;
                     size_t active_dep_count{0};
                     for (const auto& [par, chl, _dep] : active_dependencies) {

sipa commented at 3:59 PM on December 15, 2025:

This instantly (~2000 fuzz iterations from empty corpus) crashes for me.

brunoerg commented at 4:07 PM on December 15, 2025:

Which target?

sipa commented at 4:10 PM on December 15, 2025:

clusterlin_sfl, which is the only one that invokes SpanningForestState::SanityCheck.

brunoerg commented at 4:12 PM on December 15, 2025:

Yes, confirmed. Not sure what happened during the analysis, but anyway, it's resolved.

[#1703](/bitcoin-bitcoin/1703/)	NEW    cov: 524 ft: 678 corp: 27/330b lim: 14 exec/s: 0 rss: 75Mb L: 14/14 MS: 1 ChangeBit-
[#1711](/bitcoin-bitcoin/1711/)	NEW    cov: 524 ft: 681 corp: 28/344b lim: 14 exec/s: 0 rss: 75Mb L: 14/14 MS: 3 ShuffleBytes-PersAutoDict-CrossOver- DE: "\377\377\377\377\377\377\377\000"-
[#1722](/bitcoin-bitcoin/1722/)	NEW    cov: 524 ft: 683 corp: 29/358b lim: 14 exec/s: 0 rss: 75Mb L: 14/14 MS: 1 ChangeBinInt-
Assertion failed: (chunk_data.chunk_setinfo.transactions == expected_chunk), function SanityCheck, file cluster_linearize.h, line 1258.
==41593== ERROR: libFuzzer: deadly signal
    [#0](/bitcoin-bitcoin/0/) 0x0001060facd4 in __sanitizer_print_stack_trace+0x28 (libclang_rt.asan_osx_dynamic.dylib:arm64+0x5ecd4)
    [#1](/bitcoin-bitcoin/1/) 0x000103de12a4 in fuzzer::PrintStackTrace()+0x2c (fuzz:arm64+0x101d5d2a4)
    [#2](/bitcoin-bitcoin/2/) 0x000103dd4590 in fuzzer::Fuzzer::CrashCallback()+0x54 (fuzz:arm64+0x101d50590)
    [#3](/bitcoin-bitcoin/3/) 0x000186575a20 in _sigtramp+0x34 (libsystem_platform.dylib:arm64+0x3a20)
    [#4](/bitcoin-bitcoin/4/) 0xfa78800186545cbc  (<unknown module>)
    [#5](/bitcoin-bitcoin/5/) 0xcf04800186451a3c  (<unknown module>)
    [#6](/bitcoin-bitcoin/6/) 0x9f16800186450d2c  (<unknown module>)
    [#7](/bitcoin-bitcoin/7/) 0x5c2f0001021e39bc  (<unknown module>)
    [#8](/bitcoin-bitcoin/8/) 0x0001021d6564 in clusterlin_sfl_fuzz_target(std::__1::span<unsigned char const, 18446744073709551615ul>)::$_0::operator()(bool) const+0x29c (fuzz:arm64+0x100152564)
    [#9](/bitcoin-bitcoin/9/) 0x0001021d437c in clusterlin_sfl_fuzz_target(std::__1::span<unsigned char const, 18446744073709551615ul>)+0x6d4 (fuzz:arm64+0x10015037c)
    [#10](/bitcoin-bitcoin/10/) 0x0001027bed70 in LLVMFuzzerTestOneInput+0x1d4 (fuzz:arm64+0x10073ad70)
    [#11](/bitcoin-bitcoin/11/) 0x000103dd5c24 in fuzzer::Fuzzer::ExecuteCallback(unsigned char const*, unsigned long)+0x134 (fuzz:arm64+0x101d51c24)
    [#12](/bitcoin-bitcoin/12/) 0x000103dd53b0 in fuzzer::Fuzzer::RunOne(unsigned char const*, unsigned long, bool, fuzzer::InputInfo*, bool, bool*)+0x3c (fuzz:arm64+0x101d513b0)
    [#13](/bitcoin-bitcoin/13/) 0x000103dd6d10 in fuzzer::Fuzzer::MutateAndTestOne()+0x1f0 (fuzz:arm64+0x101d52d10)
    [#14](/bitcoin-bitcoin/14/) 0x000103dd79a0 in fuzzer::Fuzzer::Loop(std::__1::vector<fuzzer::SizedFile, std::__1::allocator<fuzzer::SizedFile>>&)+0x3c4 (fuzz:arm64+0x101d539a0)
    [#15](/bitcoin-bitcoin/15/) 0x000103dcdf78 in fuzzer::FuzzerDriver(int*, char***, int (*)(unsigned char const*, unsigned long))+0x1ee8 (fuzz:arm64+0x101d49f78)
    [#16](/bitcoin-bitcoin/16/) 0x000103de1ca4 in main+0x24 (fuzz:arm64+0x101d5dca4)
    [#17](/bitcoin-bitcoin/17/) 0x0001861c50dc  (<unknown module>)
    [#18](/bitcoin-bitcoin/18/) 0x5c35fffffffffffc  (<unknown module>)

NOTE: libFuzzer has rudimentary signal handlers.
      Combine libFuzzer with AddressSanitizer or similar for better crash reports.
SUMMARY: libFuzzer: deadly signal
MS: 1 CopyPart-; base unit: 099984ad01f124eca6b78d4273cfc601591ca6b3
0x1f,0xb5,0x0,0x0,0x0,0x0,0x0,0x0,0x5d,0x1f,0x1f,0xd,0x1f,0x26,
\037\265\000\000\000\000\000\000]\037\037\015\037&
artifact_prefix='./'; Test unit written to ./crash-6f59a9d6a7f236e8a4a6da57b7c1b2426b7fec10
Base64: H7UAAAAAAABdHx8NHyY=

brunoerg commented at 3:06 PM on December 15, 2025: contributor

I ran an incremental mutation test for this PR, specifically for src/cluster_linearize.h (which generated 222 mutants), considering unit (cluster_linearize_tests), functional (mempool_packages), and fuzzing.

For fuzzing, existing targets were run with qa-assets inputs. For the clusterlin_sfl target, I created a simple corpus from a few hours of executions (not very reliable).

Overall, the tests are excellent, achieving a mutation rate of over 98% (excluding equivalent mutants and some useless ones). I've commented out some unkilled mutants here; feel free to ignore them or add tests to eliminate them if it makes sense.

Happy to run it again if any relevant changes are made.

in src/cluster_linearize.h:1161 in 7b2a7106b1 outdated

1161 | +            // If a candidate with positive gain was found, deactivate it and then make the state
1162 | +            // topological again with a sequence of merges.
1163 | +            if (candidate_dep != DepIdx(-1)) Improve(candidate_dep);
1164 | +            // Stop processing for now, even if nothing was activated, as the loop above may have
1165 | +            // had a nontrivial cost.
1166 | +            return true;

instagibbs commented at 5:39 PM on December 15, 2025:

7b2a7106b12a8eb9d0c7a345c275dc3e4b919a5f

nit: probably not worth doing but noting that if m_suboptimal_chunks is empty here then we should be optimal and could return false

sipa commented at 9:22 PM on December 15, 2025:

Doesn't hurt. Done.

in src/test/fuzz/cluster_linearize.cpp:1056 in 7b2a7106b1 outdated

1052 | @@ -1053,7 +1053,6 @@ FUZZ_TARGET(clusterlin_sfl)
1053 |      if (load_linearization) {
1054 |          auto input_lin = ReadLinearization(depgraph, reader, load_topological);
1055 |          sfl.LoadLinearization(input_lin);
1056 | -        sfl.SanityCheck(depgraph);

instagibbs commented at 6:01 PM on December 15, 2025:

7b2a7106b12a8eb9d0c7a345c275dc3e4b919a5f

Why is this removed?

sipa commented at 9:22 PM on December 15, 2025:

I've moved it to remove it in the initial commit now.

in src/test/fuzz/cluster_linearize.cpp:55 in 26661a6c65

  53 | @@ -54,7 +54,6 @@
  54 |   *   - clusterlin_components
  55 |   * - ChunkLinearization and LinearizationChunking tests:

instagibbs commented at 8:20 PM on December 15, 2025:

dangling LinearizationChunking

sipa commented at 9:22 PM on December 15, 2025:

Fixed.

in src/txgraph.cpp:1319 in 26661a6c65

1317 |      uint64_t size{0};
1318 |      auto prev_index = GraphIndex(-1);
1319 |      // Iterate over the chunks of this cluster's linearization.
1320 | -    for (unsigned i = 0; i < linchunking.NumChunksLeft(); ++i) {
1321 | -        const auto& [chunk, chunk_feerate] = linchunking.GetChunk(i);
1322 | +    for (unsigned i = 0; i < linchunking.size(); ++i) {

instagibbs commented at 9:04 PM on December 15, 2025:

26661a6c655ad148d3ecf200c64b89c439b6d44a

nit: while we're here (we also arent using j below anywhere, but meh)

    for (const auto& [chunk, chunk_feerate] : linchunking) {

sipa commented at 9:22 PM on December 15, 2025:

Done.

instagibbs commented at 9:08 PM on December 15, 2025: member

reviewed through 26661a6c655ad148d3ecf200c64b89c439b6d44a

sorry all I have is ticky-tacky, will go one more pass over before finishing

sipa force-pushed on Dec 15, 2025

in src/test/fuzz/cluster_linearize.cpp:904 in 382cf0ed5f outdated

 899 | +    uint8_t flags{1};
 900 | +    uint64_t rng_seed{0};
 901 | +    try {
 902 | +        reader >> rng_seed >> flags >> Using<DepGraphFormatter>(depgraph);
 903 | +    } catch (const std::ios_base::failure&) {}
 904 | +    if (depgraph.TxCount() <= 1) return;

instagibbs commented at 9:21 PM on December 15, 2025:

Feel like we should still cover size 1, even if it's trivial. Thoughts?

sipa commented at 9:23 PM on December 15, 2025:

Clusters of size 1 only have one possible linearization, and TxGraphImpl doesn't even invoke Linearize for them. But happy to keep them in if you feel strongly.

instagibbs commented at 9:25 PM on December 15, 2025:

TxGraphImpl doesn't even invoke Linearize for them

compelling, mark as resolved

sipa force-pushed on Dec 16, 2025

instagibbs approved

instagibbs commented at 4:27 PM on December 16, 2025: member

ACK edc64813b221598994da52cc5b7124a02ab7e042

Much more straightforward than the in-master linearization approach, even ignoring its clear performance benefits.

DrahtBot requested review from jonatack on Dec 16, 2025

in src/test/fuzz/cluster_linearize.cpp:335 in e2ae52b523

 327 | @@ -328,18 +328,24 @@ SetType ReadTopologicalSet(const DepGraph<SetType>& depgraph, const SetType& tod
 328 |  
 329 |  /** Given a dependency graph, construct any valid linearization for it, reading from a SpanReader. */
 330 |  template<typename BS>
 331 | -std::vector<DepGraphIndex> ReadLinearization(const DepGraph<BS>& depgraph, SpanReader& reader)
 332 | +std::vector<DepGraphIndex> ReadLinearization(const DepGraph<BS>& depgraph, SpanReader& reader, bool topological=true)
 333 |  {
 334 |      std::vector<DepGraphIndex> linearization;
 335 |      TestBitSet todo = depgraph.Positions();
 336 |      // In every iteration one topologically-valid transaction is appended to linearization.

marcofleon commented at 6:30 PM on December 18, 2025:

nit: This comment isn't accurate anymore if topological=false.

sipa commented at 7:27 PM on December 18, 2025:

Fixed.

in src/cluster_linearize.h:951 in 2446fc6878 outdated

1132 | @@ -1124,7 +1133,22 @@ class SpanningForestState
1133 |          }
1134 |      }
1135 |  
1136 | -    /** Make state topological. Can be called after constructing. */
1137 | +    /** Load an existing linearization. Must be called immediately after constructor. The result is
1138 | +     *  topological if the linearization is valid. Otherwise, MakeTopological still needs to be
1139 | +     *  called. */
1140 | +    void LoadLinearization(std::span<const DepGraphIndex> old_linearization) noexcept
1141 | +    {

marcofleon commented at 6:43 PM on December 18, 2025:

To enforce the "must be called immediately after constructor", could add an assume here checking that we're in the initial state (no dependencies active or something like that). It's only called in two places right now so it's not critical, but could serve as a defensive check.

sipa commented at 7:28 PM on December 18, 2025:

Good point, and actually this also allows a tiny optimization, as m_tx_data[tx].chunk_rep == tx for every iteration in the loop. Made use of that, and added an Assume.

marcofleon commented at 7:04 PM on December 18, 2025: contributor

ACK edc64813b221598994da52cc5b7124a02ab7e042

This implementation was easier for me to review/understand than the current one on master, which I spent some time with when reviewing #30605. We'll see if I still feel that way after looking at the optimizations.

I ran the clusterlin_sfl and clusterlin_linearize fuzz targets for a while and no issues came up. Here's the coverage: sfl and linearize.

I also verified that the test vectors in the python repo are the same ones in the unit test. Both tests pass and arrive at optimal linearizations for the chosen mempool clusters.

Left a couple non-blocking comments that can be addressed in the follow up, if desired.

clusterlin: add known-correct optimal linearization tests (tests) 86dd550a9b

clusterlin: replace benchmarks with SFL-hard ones (bench)

This also adds a per-cost variant of each.

95bfe7d574

sipa force-pushed on Dec 18, 2025

sipa commented at 7:29 PM on December 18, 2025: member

Addressing review comments:

diff --git a/src/cluster_linearize.h b/src/cluster_linearize.h
index 817d7d52cd3..7b74d433722 100644
--- a/src/cluster_linearize.h
+++ b/src/cluster_linearize.h
@@ -951,7 +951,12 @@ public:
     {
         // Add transactions one by one, in order of existing linearization.
         for (DepGraphIndex tx : old_linearization) {
-            auto chunk_rep = m_tx_data[tx].chunk_rep;
+            // Since this function must be called after construction, each new transaction added
+            // is in its own singleton chunk still.
+            auto chunk_rep = tx;
+            // Verify that it is indeed in its own chunk.
+            Assume(m_tx_data[tx].chunk_rep == chunk_rep);
+            // Merge the chunk upwards, as long as merging succeeds.
             while (true) {
                 chunk_rep = MergeStep<false>(chunk_rep);
                 if (chunk_rep == TxIdx(-1)) break;
diff --git a/src/test/fuzz/cluster_linearize.cpp b/src/test/fuzz/cluster_linearize.cpp
index 5244fb840cd..ccf1be68768 100644
--- a/src/test/fuzz/cluster_linearize.cpp
+++ b/src/test/fuzz/cluster_linearize.cpp
@@ -320,7 +320,7 @@ std::vector<DepGraphIndex> ReadLinearization(const DepGraph<BS>& depgraph, SpanR
 {
     std::vector<DepGraphIndex> linearization;
     TestBitSet todo = depgraph.Positions();
-    // In every iteration one topologically-valid transaction is appended to linearization.
+    // In every iteration one transaction is appended to linearization.
     while (todo.Any()) {
         // Compute the set of transactions to select from.
         TestBitSet potential_next;

DrahtBot added the label CI failed on Dec 18, 2025

DrahtBot commented at 8:45 PM on December 18, 2025: contributor

🚧 At least one of the CI tasks failed. Task fuzzer,address,undefined,integer: https://github.com/bitcoin/bitcoin/actions/runs/20348793658/job/58467736369 LLM reason (✨ experimental): Fuzz target crashed with a deadly signal during libFuzzer run (exit code 77).

<details><summary>Hints</summary>

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.

</details>

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.

c461259fb6

clusterlin: ReadLinearization for non-topological (tests)

Rather than using an ad-hoc no-dependency copy of the graph when a potentially
non-topological linearization is needed in the clusterlin fuzz test, add this
directly as a feature in ReadLinearization().

This is preparation for a later commit where another use for such a function
is added.

da48ed9f34

clusterlin: add support for loading existing linearization (feature) 6a8fa821b8

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.

The worst case time per cost is similar to the previous algorithm, so
ACCEPTABLE_ITERS is unchanged.

3efc94d656

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.

ddbfa4dfac

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.

13aad26b78

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.

5ce2800745

clusterlin: remove unused MergeLinearizations (cleanup)

This ended up never being used in txgraph.

91399a7912

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.

75bdb925f4

sipa force-pushed on Dec 18, 2025

sipa commented at 9:03 PM on December 18, 2025: member

Oops, sorry, I had to revert this last change because the property I claimed (each new transaction traversed in LoadLinearization() is in its own chunk still) only holds if the input linearization is topological. With that, I don't see an effectively way of asserting that LoadLinearization() is called in the right state, without introducing a performance penalty.

diff --git a/src/cluster_linearize.h b/src/cluster_linearize.h
index 7b74d433722..d65e61d4458 100644
--- a/src/cluster_linearize.h
+++ b/src/cluster_linearize.h
@@ -395,7 +395,7 @@ struct SetInfo
         return *this;
     }
 
-    /** Remove the transactions of other from this SetInfo (must be subset). */
+    /** Remove the transactions of other from this SetInfo (which must be a subset). */
     SetInfo& operator-=(const SetInfo& other) noexcept
     {
         Assume(other.transactions.IsSubsetOf(transactions));
@@ -951,11 +951,7 @@ public:
     {
         // Add transactions one by one, in order of existing linearization.
         for (DepGraphIndex tx : old_linearization) {
-            // Since this function must be called after construction, each new transaction added
-            // is in its own singleton chunk still.
-            auto chunk_rep = tx;
-            // Verify that it is indeed in its own chunk.
-            Assume(m_tx_data[tx].chunk_rep == chunk_rep);
+            auto chunk_rep = m_tx_data[tx].chunk_rep;
             // Merge the chunk upwards, as long as merging succeeds.
             while (true) {
                 chunk_rep = MergeStep<false>(chunk_rep);

DrahtBot removed the label CI failed on Dec 18, 2025

instagibbs commented at 2:21 PM on December 19, 2025: member

reACK 75bdb925f404f41874adf0fcefca0f1641fcb4e6

Comment cleanups only

git range-diff master edc64813b221598994da52cc5b7124a02ab7e042 75bdb925f404f41874adf0fcefca0f1641fcb4e6

DrahtBot requested review from marcofleon on Dec 19, 2025

marcofleon commented at 2:33 PM on December 19, 2025: contributor

reACK 75bdb925f404f41874adf0fcefca0f1641fcb4e6

I don't see an effectively way of asserting that LoadLinearization() is called in the right state, without introducing a performance penalty.

Yeah I was thinking Assume(m_cost == 0) could potentially work, but that wouldn't work for the optimized sfl branch.

fanquake merged this on Dec 19, 2025

fanquake closed this on Dec 19, 2025