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.

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.

2028be15e3

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.

0e2ae7d686

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.

f5c3ceb627

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. A summary of reviews will appear here.