clusterlin: minor SFL optimizations #35694

sipa commented at 2:37 PM on July 9, 2026: member

These are a few minor and easy-to-review code changes to the SFL algorithm, which net a few % speedup (~2.6% speedup on LinearizeOptimally* benchmarks, ~5% on the Historical ones).

<details><summary>LLM benchmark results:</summary>

Class	Ratio	95% CI
HistoricalTotal	0.9499	[0.9312, 0.9709]
SyntheticTotal	0.9760	[0.9597, 0.9949]
HistoricalPerCost	0.9545	[0.9238, 0.9845]
SyntheticPerCost	0.9934	[0.9688, 1.0175]
All (60)	0.9737	[0.9563, 0.9913]

Methology: One release-mode bench_bitcoin binary (GCC 15.2, -O2) was built for the base commit and one for the branch tip, and run as bench_bitcoin -filter='.*LinearizeOptimally.*' -min-time=100 in 85 strictly alternating pairs of fresh process launches (170 launches, ~20 minutes total), each pinned to the same core of an otherwise idle Zen5 machine. For each of the 60 benchmarks, the per-launch ns/op values were averaged over each binary's 85 launches; the optimized/base ratios of these means were aggregated as a geometric mean per benchmark class, with 95% confidence intervals from 1000 bootstrap resamplings of the launches.

</details>

Disclosure: this code, comments, benchmarks, and selection of optimizations were done by Claude Fable 5. I reviewed the commits, and wrote the PR description.

DrahtBot commented at 2:37 PM on July 9, 2026: 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/35694.

Reviews

See the guideline and AI policy for information on the review process.

Type	Reviewers
ACK	optout21, marcofleon, instagibbs

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

fanquake commented at 9:56 AM on July 10, 2026: member

cc @marcofleon

clusterlin: avoid heap allocations in GetLinearization

Replace GetLinearization's four per-call heap-allocated vectors (the
ready chunk/transaction heaps and both dependency counters) with stack
arrays and explicit size counters. This especially benefits
linearization of small clusters, where the allocations make up a
significant fraction of the total runtime.

e6ca996255

clusterlin: reserve the suboptimal-chunk queue up front

Reserve capacity for one entry per transaction in m_suboptimal_chunks at
construction time, avoiding repeated reallocations while MakeTopological
and StartOptimizing fill the queue.

4b91ad149f

clusterlin: avoid recomputing intersections in MergeChunks

MergeChunks scans the top chunk's transactions twice: once to count
the dependencies on the bottom chunk, and once to locate the randomly
picked one. Remember the per-transaction dependency counts from the
first pass, so the second pass only computes the intersection of the
selected transaction, rather than one per transaction scanned.

efb4eae338

in src/cluster_linearize.h:961 in f5c3ceb627

 953 | @@ -954,23 +954,30 @@ class SpanningForestState
 954 |          Assume(m_chunk_idxs[bottom_idx]);
 955 |          auto& top_chunk_info = m_set_info[top_idx];
 956 |          auto& bottom_chunk_info = m_set_info[bottom_idx];
 957 | -        // Count the number of dependencies between bottom_chunk and top_chunk.
 958 | +        // Count the number of dependencies between bottom_chunk and top_chunk, remembering the
 959 | +        // per-transaction counts so the picking loop below does not need to recompute the
 960 | +        // intersections.
 961 |          unsigned num_deps{0};
 962 | +        std::array<uint8_t, SetType::Size()> counts;

gmaxwell commented at 7:36 PM on July 12, 2026:

Super nitty but maybe:

   static_assert(SetType::Size() <= 0xff, "counts array stores per-transaction Count() results in uint8_t");

just so that it fails cleanly instead of silently if someone tries adding a larger cluster size implementation.

sipa commented at 5:21 PM on July 14, 2026:

I have instead changed the array type to SetIdx, which is always large enough.

sipa force-pushed on Jul 14, 2026

optout21 commented at 9:11 AM on July 18, 2026: contributor

ACK efb4eae33861d3f316d77788f5c83b58dad94a0a

Several minor optimizations. Reviewed by re-creating the changes. All changes seem to be correct, no-behavior-changing, relatively localized. A non-systematic check on benchmark results show improvements or insignificant changes (depending on the specific benchmark). Per commit:

The first commit changes 4 vectors into arrays (to optimize allocations); in two cases a new variable is also introduced for the current size. The four changes are independent.
The second commit adds a missing reserve; it's the simplest change (but possibly the one with the most impact).
The third commit add extra storing of a count that has been computed twice, so there is no need to recompute.

For performance I've cherry-picked a single benchmark case, LinearizeOptimallyHistoricalTotal_63tx_75dep. It shows a 3,9% speedup. The speedup of this benchmark seems to be more pronounced than that of other benchmarks. See a chart with speedups, with a value for each change (cumulative), starting with 0 for the baseline (6 changes, first commit is broken up into 4; commits are from branch https://github.com/optout21/bitcoin/tree/2607-pr35694-reimp).

marcofleon commented at 4:17 PM on July 21, 2026: contributor

crACK efb4eae33861d3f316d77788f5c83b58dad94a0a

instagibbs commented at 8:59 PM on July 22, 2026: member

light review ACK efb4eae33861d3f316d77788f5c83b58dad94a0a

Changes make sense, are limited in scope. Did not directly check if all the commits additively improve performance.

Had gpt run some differential fuzzing with full-size clusters up to count 64 to check that no behavior changed, summary here:

Differential-fuzzed 2d4065d1fe vs efb4eae338 for 1.13M executions, comparing exact linearization, optimal flag, cost, and intermediate SFL states. Coverage included 0–64 transactions, holes, connected/disconnected and dense graphs, all prior-linearization modes, varied budgets/seeds, and up to 1,024 dependencies. The final corpus also passed ASan+UBSan. No mismatches or sanitizer failures found.

fanquake merged this on Jul 23, 2026

fanquake closed this on Jul 23, 2026