Summary
This PR adds correctness tests and benchmarks specifically targeting chain and tree-shaped
cluster topologies, which are both common in real-world mempools and structurally special
with respect to PostLinearize.
Commits:
a11760f9cluster_linearize: add chain cluster benchmarks for PostLinearize and Linearize4b7e2b28cluster_linearize: test PostLinearize optimality on random tree-shaped clusters0725aa05cluster_linearize: test PostLinearize optimality on random chain clusters
Motivation
PostLinearize gives an optimality guarantee for clusters with a tree shape: if every
transaction has at most one direct parent, or every transaction has at most one direct child,
the result is provably optimal. A chain (tx_0 → tx_1 → … → tx_{N-1}) satisfies both
conditions simultaneously.
These structural guarantees lacked dedicated test coverage and chain-specific benchmarks, making it hard to observe the effect of topology-aware optimizations on linearization performance.
Changes
Tests (src/test/cluster_linearize_tests.cpp)
postlinearize_tree_optimal_tests
Adds MakeRandomTreeGraph(), which generates random tree-shaped dependency graphs in two
orientations:
- Upright tree: transaction i picks a random parent from [0, i), so every node has at most one direct parent.
- Reverse tree: transaction i picks a random child from [0, i), so every node has at most one direct child.
For random trees of sizes 5..30, the test verifies:
PostLinearizeproduces a linearization of equal quality to the exhaustiveLinearize()result (as guaranteed byPostLinearize’s interface for tree-shaped inputs).- Idempotency: a second
PostLinearizepass produces no change.
postlinearize_chain_optimal_tests
Adds MakeRandomChainGraph(), which generates random linear chain dependency graphs
(tx_0 → tx_1 → … → tx_{N-1}) with randomized feerates.
For chains of sizes 5..50, the test verifies:
PostLinearizeproduces a linearization of equal quality to the exhaustiveLinearize()result. A chain satisfies both tree-shape conditions simultaneously, so optimality is guaranteed.- Idempotency: a second
PostLinearizepass produces no change.
Benchmarks (src/bench/cluster_linearize.cpp)
Adds MakeChainGraph() to build deterministic random chain dependency graphs
(tx_0 → tx_1 → … → tx_{N-1}) with randomized feerates seeded deterministically from the
cluster size, and two sets of chain-specific benchmarks:
PostLinearizeChain{16,32,48,64,75,99}Tx: measurePostLinearizethroughput on chain-shaped clusters across a range of sizes.LinearizeOptimallyChainTotal_{9,16,32,48,63}tx: measure the total time forLinearizeto reach an optimal result on chain-shaped clusters.
Chain clusters are a common real-world mempool pattern (each transaction spending an output of the previous one). Dedicated benchmarks make it easy to observe the effect of topology-specific linearization optimizations as they are developed.
