txgraph: Add ChainClusterImpl for chain-shaped cluster topologies #34821

HowHsu commented at 1:44 PM on March 13, 2026: contributor

This one replaces #34643

Summary

This PR adds an optimized ChainClusterImpl for chain-shaped transaction topologies (A→B→C→D…). It replaces the generic DepGraph-based cluster with a compact linear representation (m_txdata) and a backward-absorbing chunk algorithm, reducing memory and improving performance for common chain patterns.

Key changes

m_maybe_chain flag on GroupEntry to hint at chain-shaped merges
ChainClusterImpl with m_txdata (chain order) and m_split_segments (contiguous segments after removals)
TryChainMerge in ApplyDependencies to detect and merge chains via the fast path
ApplyRemovals / Split correctly split chains when middle transactions are removed (no spurious dependencies)
Removal of m_linearization from ChainClusterImpl (always [0,1,…,n-1])
ComputeChunks() helper to centralize the backward-absorbing chunk logic
SetFee / Relinearize fix: downgrade to NEEDS_RELINEARIZE on fee change to avoid dereferencing destroyed Refs; Relinearize promotes back to OPTIMAL and recomputes chunks

Testing

Unit tests: txgraph_chain_merge (TryChainMerge), txgraph_chain_split_on_removal (ApplyRemovals/Split)
Benchmarks: ChainCluster merge and BlockBuilder paths

Trace replay comparison

Trace recording (TracingTxGraph) and replay (txgraph-replay, analyze_trace.py) code: git@github.com:HowHsu/bitcoin.git branch before_chaincluster. Usage guide: TxGraph Trace & Replay.

The trace file is on github LFS: https://howhsu.github.io/thinking-in-bitcoin/data/txgraph.trace.4.5days.final.xz Same trace replayed on baseline vs ChainCluster branch. Parameters: max_cluster_count=64, max_cluster_size=404000, acceptable_cost=75000. Total ops: 71,313,272.

Entry point	Baseline Total (μs)	ChainCluster Total (μs)
DoWork	3,595,581	1,297,506
CompareMainOrder	1,445	1,531
GetAncestors	1	0
GetDescendants	8,543	8,361
CountDistinctClusters	575	2,474
GetMainMemoryUsage	157	156
GetMainStagingDiagrams	35,428	15,969
IsOversized	31,732	108,050
StartStaging	128	87
AbortStaging	0	0
CommitStaging	9,300	10,777
TOTAL	3,682,890	1,444,911

Mutations (not timed): ADD_TX 1,764,814, REMOVE_TX 33,050, ADD_DEP 791,630, SET_FEE 0, UNLINK_REF 1,764,814.

Trace analysis

analyze_trace.py on the same trace file (/tmp/txgraph.trace).
Note on oversized clusters: Clusters with size > 64 appear because the trace captures graph state at discrete snapshots (e.g. after each CommitStaging). Split is triggered lazily by DoWork/ApplyDependencies; at snapshot time, some clusters may not yet have been processed and thus exceed max_cluster_count. Note on peak state: Peak state is the snapshot with the most transactions (27,512), not necessarily the one with the most chain clusters.

Trace format version: 1                                                          
Parameters: max_cluster_count=64 max_cluster_size=404000 acceptable_cost=75000   
                                                                                 
Processed 71313273 operations, 1763516 CommitStagings                            
Peak mempool size: 27512 transactions (at op [#51503379](/bitcoin-bitcoin/51503379/))                          
Unstaged mutations: 0 ADD_TX, 0 ADD_DEP, 0 REMOVE_TX, 1764814 UNLINK_REF         
                                                                                 
Edge sanity check (final state): OK - all edges reference live transactions         
Edge sanity check (peak state): OK - all edges reference live transactions

Peak state (27,512 transactions, 8,596 clusters):

Size	Clusters	Chains	Non-chain	Chain%
1	7,628	7,628	0	100.0%
2	575	575	0	100.0%
3	103	72	31	69.9%
4	75	58	17	77.3%
5	21	18	3	85.7%
6	9	4	5	44.4%
7	12	9	3	75.0%
8	4	1	3	25.0%
9	31	30	1	96.8%
10	25	23	2	92.0%
13	1	1	0	100.0%
16	1	0	1	0.0%
20	2	2	0	100.0%
24	10	9	1	90.0%
25	90	87	3	96.7%
26	3	0	3	0.0%
29	1	0	1	0.0%
33	1	0	1	0.0%
48	1	0	1	0.0%
51	1	0	1	0.0%
59	1	0	1	0.0%
14464	1	0	1	0.0%
TOTAL	8,596	8,517	79	99.1%

Transactions in chain clusters: 12,355 (44.9%)
Transactions in non-chain clusters: 15,157 (55.1%)
Transactions with dependencies: 19,884 (72.3%)
Excluding size=1 clusters: 4,727 in chains (23.8%), 15,157 in non-chains (76.2%), of 19,884 txs
1 cluster of size 14,464 exceeds max_cluster_count=64 (oversized)

Final state (6,079 transactions, 4,665 clusters):

Size	Clusters	Chains	Non-chain	Chain%
1	4,269	4,269	0	100.0%
2	285	285	0	100.0%
3	68	44	24	64.7%
4	24	9	15	37.5%
5	6	4	2	66.7%
6	4	1	3	25.0%
7	3	0	3	0.0%
8	1	0	1	0.0%
10	1	0	1	0.0%
26	1	0	1	0.0%
54	1	0	1	0.0%
286	1	0	1	0.0%
481	1	0	1	0.0%
TOTAL	4,665	4,612	53	98.9%

Transactions in chain clusters: 5,033 (82.8%)
Transactions in non-chain clusters: 1,046 (17.2%)
Transactions with dependencies: 1,810 (29.8%)
Excluding size=1 clusters: 764 in chains (42.2%), 1,046 in non-chains (57.8%), of 1,810 txs
2 clusters (sizes 286, 481) exceed max_cluster_count=64

The trace file is about 0.5 GB, I'll find a place to upload it soon.

Memory Analysis

As per @instagibbs 's comment, I make some memory tests, the results are in below article: https://howhsu.github.io/thinking-in-bitcoin/articles/chain-cluster-memory.en.html

No-chain mempool

As @instagibbs points out, mempool usage patterns may evolve over time. We should evaluate the impact of this optimization in the no-chain scenario (i.e., when there are no chains of size ≥ 3; chains of size 2 are typically CPFP cases). Below link is the comparison and results. https://howhsu.github.io/thinking-in-bitcoin/articles/chain-cluster-nochain-baseline.en.html In short, chaincluster is ~21% faster, which is most likely caused by size=2 chains.

Compare with PR #34643

https://howhsu.github.io/thinking-in-bitcoin/articles/chain-linearize-vs-chaincluster.en.html Compare with the previous chain linearize idea. In short, chaincluster branch is about 15.5% faster.

Overhead of `IsOversized` and `CountDistinctClusters`

The increase in overhead for these two components is caused by chunk computation in Updated. This logic was moved from DoWork to IsOversized and CountDistinctClusters as part of the chain cluster design. For more details, see: https://howhsu.github.io/thinking-in-bitcoin/articles/chain-isoversized-chunk-overhead.en.html

Bench Environment

The above results were obtained on the test machine.

Hardware

Item	Value
CPU	Intel Core i5-13600KF (14 cores, 20 threads)
Memory	32 GB

Host OS

Item	Value
OS	Ubuntu 24.04 LTS (Noble Numbat)
Docker	28.4.0

Docker Container

Item	Value
Base OS	Debian 12 (bookworm)
GCC	12.2.0
CMake	3.25.1

Fuzz testing

Check	Result
Crash files	None
Error log	No assert / ERROR / deadly signal
Workers	All 8 finished normally
Total runs	~39.6M
Duration	36001 s (~10 h)

** Fuzz Environment**

Item	Value
Host kernel	Linux 6.17.0-14-generic (Ubuntu)
Container OS	Debian GNU/Linux 12 (bookworm)
Architecture	x86_64
Compiler	Clang 20.1.8
Fuzzer	libFuzzer
Sanitizers	AddressSanitizer, UndefinedBehaviorSanitizer
Target	`txgraph`
Corpus	`fuzz_corpus/txgraph`

DrahtBot commented at 1:45 PM on March 13, 2026: contributor

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

Reviews

See the guideline for information on the review process.

Type	Reviewers
Concept NACK	instagibbs

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

LLM Linter (✨ experimental)

Possible typos and grammar issues:

"where transaction at position i depends on transaction at position i-1." -> "where the transaction at position i depends on the transaction at position i-1." [missing definite article "the" makes the sentence slightly ungrammatical]

HowHsu marked this as a draft on Mar 13, 2026

DrahtBot added the label CI failed on Mar 13, 2026

HowHsu force-pushed on Mar 13, 2026

in src/txgraph.cpp:158 in dd15ced191 outdated

 153 | @@ -154,6 +154,10 @@ class Cluster
 154 |          return m_quality == QualityLevel::NEEDS_SPLIT || m_quality == QualityLevel::NEEDS_SPLIT_FIX;
 155 |      }
 156 |  
 157 | +    /** Whether this Cluster type is compatible with chain topology (Singleton and Chain are,
 158 | +     *  Generic is not). Used to determine if a group of clusters can be optimistically merged

Bodalmalki commented at 9:21 PM on March 13, 2026:

عبدالله جارالله المالكي

Bodalmalki commented at 9:22 PM on March 13, 2026: none

عبدالله جارالله المالكي

Bodalmalki commented at 9:23 PM on March 13, 2026: none

عبدالله جارالله المالكي

HowHsu force-pushed on Mar 14, 2026

DrahtBot removed the label CI failed on Mar 14, 2026

HowHsu marked this as ready for review on Mar 14, 2026

instagibbs commented at 2:28 PM on March 16, 2026: member

Interesting work, thank you for following up on the feedback.

How does this compare directly to #34643 under the same replay system?

did you benchmark memory usage to compare? Would be interested seeing that.

any feeling why CountDistinctClusters and IsOversized took such a hit?

also interested in a pessimal benchmark where no one is making chains beyond say, size 2, and yet we're still trying to optimistically detect and merge chains. (in case people decide other shapes are cooler or whatever)

HowHsu force-pushed on Mar 16, 2026

DrahtBot added the label CI failed on Mar 16, 2026

txgraph: add m_maybe_chain flag to GroupEntry for optimistic chain merge

Add IsChainCompatible() virtual method to Cluster base class. Singleton
returns true (chain-compatible), Generic returns false. During
GroupClusters(), detect whether all clusters in a merge group are
chain-compatible and record this in the new GroupEntry::m_maybe_chain
flag. This will be used by subsequent commits to optimistically merge
groups of Singleton/Chain clusters into a ChainCluster instead of
always falling back to GenericCluster.

deac7fc737

txgraph: add ChainClusterImpl class for chain-shaped cluster topologies

Add ChainClusterImpl, a Cluster implementation optimized for chain-shaped
topologies where transaction at position i only depends on transaction i-1
except position 0. Dependencies are implicit (no DepGraph needed), saving
memory and enabling O(N) operations.

Key design:
- m_txdata: vector of {graph_index, feerate} in chain order
- m_linearization: always [0, 1, 2, ..., n-1] (only valid topological order)
- Chunks computed by greedy merging of consecutive transactions
- Always OPTIMAL quality (no relinearization needed)
- Ancestors/descendants computed trivially from chain position

Also adds CreateEmptyChainCluster() factory method and friend declaration.
ChainClusterImpl is not yet created anywhere; subsequent commits will add
the optimistic merge path that creates ChainClusters during merge.

735eb2410a

txgraph: remove redundant m_linearization from ChainClusterImpl

ChainClusterImpl's m_linearization is always [0, 1, 2, ..., n-1]
since chain transactions have a fixed topological order matching
their array position. Replace all m_linearization usages with
direct index iteration over m_txdata, saving one vector allocation
per chain cluster.

35406f07e9

txgraph: implement optimistic chain merge path in ApplyDependencies

When all clusters in a merge group are chain-compatible (Singletons or
ChainClusters), attempt TryChainMerge() before falling back to the
standard Generic merge path. TryChainMerge() succeeds iff every dep
connects the tail (last tx) of one cluster to the head (first tx) of
another, and the resulting cluster-level graph is itself a linear chain.
On success, a ChainCluster is created directly without going through a
GenericCluster.

Chain detection operates at the cluster level (O(n_clusters + n_deps))
rather than the individual transaction level, since every cluster in
to_merge is already chain-compatible by the m_maybe_chain invariant.

To support the fallback path: ChainCluster is excluded from being
selected as the Merge() target (it cannot absorb arbitrary topologies),
and the largest Generic cluster is preferred as the merge target to
minimise transaction moves.

c3d548d94b

txgraph: add unit tests for TryChainMerge chain detection

10 test cases covering:
- Successful chain merges: two singletons, three singletons, ChainCluster
  extended by a singleton, singleton prepended to a ChainCluster, two
  ChainClusters connected, and duplicate deps.
- Failed merges (fallback to generic): diamond topology (two parents),
  fork topology (two children), dep from a non-tail tx, dep to a
  non-head tx.

efa7230c81

txgraph: add unit tests for ChainCluster split on middle removal

Verify that removing transactions from the interior of a ChainCluster
correctly splits it into disconnected segments:
- Remove one middle tx from a 4-tx chain → singleton + 2-chain
- Remove two alternating middle txs from a 5-tx chain → 3 singletons
- Remove the middle of a 6-tx chain → two separate chains
- Remove head only → single chain preserved
- Remove tail only → single chain preserved

35643a6de4

txgraph: add benchmarks for ChainCluster merge path

- TxGraphChainMergeSingletons: ApplyDependencies merging 64 singletons
  into one chain via TryChainMerge.
- TxGraphChainMergeFromChains: ApplyDependencies merging 64 pre-built
  ChainClusters (10 txs each) into one chain of 640 txs.
- TxGraphChainBlockBuilder: repeated GetBlockBuilder calls on a single
  64-tx ChainCluster.

3491b263e2

HowHsu force-pushed on Mar 16, 2026

DrahtBot removed the label CI failed on Mar 16, 2026

HowHsu commented at 3:28 AM on March 18, 2026: contributor

Interesting work, thank you for following up on the feedback.

How does this compare directly to #34643 under the same replay system?

did you benchmark memory usage to compare? Would be interested seeing that.

No, I'll do these tests in the next days.

any feeling why CountDistinctClusters and IsOversized took such a hit?

have roughly thought about this, no clues yet, will have a deep research on it.

also interested in a pessimal benchmark where no one is making chains beyond say, size 2, and yet we're still trying to optimistically detect and merge chains. (in case people decide other shapes are cooler or whatever)

All great points — I'll make these comparisons.

HowHsu commented at 2:54 PM on March 20, 2026: contributor

Interesting work, thank you for following up on the feedback.

How does this compare directly to #34643 under the same replay system?

did you benchmark memory usage to compare? Would be interested seeing that.

any feeling why CountDistinctClusters and IsOversized took such a hit?

also interested in a pessimal benchmark where no one is making chains beyond say, size 2, and yet we're still trying to optimistically detect and merge chains. (in case people decide other shapes are cooler or whatever)

Hey @instagibbs ,

I did some research on these topic, and add them in the PR description, from section Memory Analysis to Overhead of IsOversized and CountDistinctClusters

instagibbs commented at 7:12 PM on March 27, 2026: member

light concept NACK, from me for now.

It was helpful to me to see what kind of costs we have for now, but modest reduction in already-"trivial" linearization cases isn't very compelling, unless we had quite significant memory savings or similar. It's just enough boilerplate to be too annoying to maintain unless there's a clearer win, to me.

Going forward, I think focusing on reducing the adversarially-bad cases is a more fruitful line of further inquiry.

HowHsu commented at 12:51 PM on March 30, 2026: contributor

light concept NACK, from me for now.

It was helpful to me to see what kind of costs we have for now, but modest reduction in already-"trivial" linearization cases isn't very compelling, unless we had quite significant memory savings or similar. It's just enough boilerplate to be too annoying to maintain unless there's a clearer win, to me.

I see—maintainability is definitely something that needs to be considered.

sipa commented at 1:38 PM on March 30, 2026: member

Is there no way to avoid the std::vector<DepGraphIndex> m_split_segments;? Vectors are relatively expensive for memory usage, with some 32-40 bytes overhead on typical platforms (3 pointers in the std::vector itself, plus 8-16 bytes in allocation overhead). I don't know how much impact it would have here, though.

HowHsu commented at 12:17 PM on March 31, 2026: contributor

Is there no way to avoid the std::vector<DepGraphIndex> m_split_segments;? Vectors are relatively expensive for memory usage, with some 32-40 bytes overhead on typical platforms (3 pointers in the std::vector itself, plus 8-16 bytes in allocation overhead). I don't know how much impact it would have here, though.

I see, I'll look into it.

HowHsu commented at 8:53 AM on April 9, 2026: contributor

Is there no way to avoid the std::vector<DepGraphIndex> m_split_segments;? Vectors are relatively expensive for memory usage, with some 32-40 bytes overhead on typical platforms (3 pointers in the std::vector itself, plus 8-16 bytes in allocation overhead). I don't know how much impact it would have here, though.

I removed m_split_segments from the implementation and ran benchmarks. When the memory ratio $\frac{M_{\text{chain cluster}}}{M_{\text{all clusters}}}$ reaches its peak (around 20%), this PR achieves approximately 13% memory savings.

HowHsu commented at 12:09 PM on April 15, 2026: contributor

light concept NACK, from me for now.

It was helpful to me to see what kind of costs we have for now, but modest reduction in already-"trivial" linearization cases isn't very compelling, unless we had quite significant memory savings or similar. It's just enough boilerplate to be too annoying to maintain unless there's a clearer win, to me.

Going forward, I think focusing on reducing the adversarially-bad cases is a more fruitful line of further inquiry.

as per offline talking, I wrote some script to tracing the transaction lifecycle, DoWork does play just a small role of the total latency, while the TX script check is the main part. Thanks for pointing out this. @instagibbs

tx 69e44e07  total=  441  deser=   0  recv=  15  pre=  79 [chktx=6 std=8 utxo=53 inputs=5 stage=7]  rbf=   0  policy= 155 [scripts=147]  consens=  19 [scripts=12]  final=  51 [apply=44 commit=11 dowork=5]  limit=   4  post=  41 [validtx=25 bcast=16] 
tx 6bb2ce7e  total=  332  deser=   0  recv=  10  pre=  57 [chktx=4 std=6 utxo=37 inputs=4 stage=6]  rbf=   0  policy= 133 [scripts=128]  consens=  16 [scripts=10]  final=  32 [apply=27 commit=6 dowork=4]  limit=   2  post=  30 [validtx=18 bcast=11] 
tx 3f99ebbb  total=  469  deser=   0  recv=  14  pre= 108 [chktx=6 std=8 utxo=82 inputs=5 stage=7]  rbf=   0  policy= 153 [scripts=145]  consens=  20 [scripts=12]  final=  44 [apply=38 commit=12 dowork=4]  limit=   4  post=  43 [validtx=26 bcast=17] 
tx f926faca  total=  334  deser=   0  recv=   8  pre=  62 [chktx=5 std=7 utxo=39 inputs=4 stage=7]  rbf=   0  policy= 130 [scripts=125]  consens=  16 [scripts=11]  final=  32 [apply=27 commit=7 dowork=4]  limit=   2  post=  32 [validtx=19 bcast=12] 
tx 96af4893  total=  527  deser=   0  recv=   7  pre=  57 [chktx=4 std=6 utxo=38 inputs=4 stage=5]  rbf=   0  policy= 232 [scripts=227]  consens=  92 [scripts=87]  final=  54 [apply=50 commit=8 dowork=26]  limit=   2  post=  28 [validtx=17 bcast=11] 
tx bed10cc2  total=  485  deser=   0  recv=   8  pre=  52 [chktx=4 std=5 utxo=34 inputs=4 stage=5]  rbf=   0  policy= 202 [scripts=197]  consens=  91 [scripts=86]  final=  45 [apply=40 commit=6 dowork=19]  limit=   2  post=  27 [validtx=16 bcast=10] 
tx d4e47eea  total=  630  deser=   0  recv=  15  pre=  82 [chktx=6 std=9 utxo=55 inputs=5 stage=7]  rbf=   0  policy= 236 [scripts=228]  consens=  95 [scripts=87]  final=  68 [apply=61 commit=12 dowork=29]  limit=   4  post=  41 [validtx=25 bcast=16] 
tx 6645c474  total=  513  deser=   0  recv=   9  pre=  58 [chktx=5 std=6 utxo=36 inputs=4 stage=7]  rbf=   0  policy= 210 [scripts=205]  consens=  90 [scripts=84]  final=  52 [apply=47 commit=6 dowork=25]  limit=   2  post=  30 [validtx=18 bcast=11] 
tx 54c3d55d  total=  479  deser=   0  recv=   8  pre=  53 [chktx=4 std=5 utxo=35 inputs=4 stage=5]  rbf=   0  policy= 199 [scripts=194]  consens=  90 [scripts=85]  final=  46 [apply=41 commit=5 dowork=20]  limit=   2  post=  37 [validtx=21 bcast=15] 
tx ad0efc5d  total=  638  deser=   0  recv=  15  pre=  80 [chktx=6 std=9 utxo=53 inputs=5 stage=7]  rbf=   0  policy= 236 [scripts=228]  consens=  94 [scripts=86]  final=  75 [apply=68 commit=12 dowork=35]  limit=   4  post=  45 [validtx=27 bcast=18] 
tx dd379bf8  total=  511  deser=   0  recv=   9  pre=  60 [chktx=5 std=6 utxo=39 inputs=4 stage=6]  rbf=   0  policy= 203 [scripts=198]  consens=  90 [scripts=85]  final=  53 [apply=48 commit=6 dowork=25]  limit=   2  post=  34 [validtx=20 bcast=13] 
tx 1dbf7cbd  total=  492  deser=   0  recv=   7  pre=  50 [chktx=4 std=5 utxo=32 inputs=4 stage=5]  rbf=   0  policy= 204 [scripts=199]  consens= 104 [scripts=98]  final=  49 [apply=44 commit=6 dowork=23]  limit=   2  post=  28 [validtx=17 bcast=11] 
tx b079c703  total=  475  deser=   0  recv=   8  pre=  54 [chktx=4 std=5 utxo=36 inputs=4 stage=5]  rbf=   0  policy= 199 [scripts=194]  consens=  89 [scripts=84]  final=  47 [apply=43 commit=5 dowork=23]  limit=   2  post=  29 [validtx=17 bcast=11] 
tx 754b658c  total=  658  deser=   0  recv=  13  pre=  82 [chktx=6 std=9 utxo=54 inputs=5 stage=8]  rbf=   0  policy= 235 [scripts=228]  consens=  95 [scripts=87]  final=  79 [apply=73 commit=12 dowork=39]  limit=   4  post=  45 [validtx=27 bcast=17] 
tx ccd393fa  total=  526  deser=   0  recv=   8  pre=  66 [chktx=5 std=6 utxo=44 inputs=4 stage=7]  rbf=   0  policy= 213 [scripts=208]  consens=  90 [scripts=84]  final=  59 [apply=54 commit=6 dowork=32]  limit=   2  post=  36 [validtx=22 bcast=14] 
tx 373d8676  total=  486  deser=   0  recv=   9  pre=  51 [chktx=4 std=5 utxo=33 inputs=4 stage=5]  rbf=   0  policy= 201 [scripts=197]  consens=  90 [scripts=85]  final=  56 [apply=51 commit=5 dowork=30]  limit=   2  post=  30 [validtx=18 bcast=12] 
tx 176e3113  total=  655  deser=   0  recv=  15  pre= 170 [chktx=7 std=8 utxo=122 inputs=5 stage=28]  rbf=   0  policy= 274 [scripts=266]  consens=  22 [scripts=14]  final=  47 [apply=40 commit=11 dowork=5]  limit=   4  post=  40 [validtx=24 bcast=15] 
tx 7956a62f  total=  457  deser=   0  recv=  14  pre=  79 [chktx=6 std=8 utxo=53 inputs=5 stage=7]  rbf=   0  policy= 150 [scripts=143]  consens=  25 [scripts=12]  final=  44 [apply=37 commit=11 dowork=4]  limit=   4  post=  39 [validtx=23 bcast=15] 
tx ec29cdb0  total=  726  deser=   0  recv=   8  pre= 115 [chktx=4 std=6 utxo=95 inputs=4 stage=6]  rbf=   0  policy= 360 [scripts=355]  consens= 119 [scripts=113]  final=  38 [apply=27 commit=7 dowork=4]  limit=   2  post=  29 [validtx=18 bcast=11]