ChainCluster No-Large-Chain Trace Baseline

中文版

Overview

To evaluate the ChainCluster optimization when there are no large chain clusters, we generated a no-large-chain trace. This trace is derived from the original by adding extra ADD_DEP edges to eliminate all size ≥ 3 chain-shaped clusters, leaving only size-2 chains and singleton clusters.

The rewrite script only eliminates chains of size≥3; size-2 chains are left unchanged. Therefore the trace still contains hundreds of size-2 chain clusters, from which the chaincluster branch still benefits.

Generation Steps

1. Tool

Use the script contrib/txgraph_tracing/rewrite_trace_no_chain_clusters.py in the bitcoin/bitcoin chaincluster_time_mem_bench branch.

2. Commands

# Single process (default)
python3 contrib/txgraph_tracing/rewrite_trace_no_chain_clusters.py \
  <input_trace> <output_trace>

# Multi-process (recommended for 15–20 cores)
python3 contrib/txgraph_tracing/rewrite_trace_no_chain_clusters.py \
  --jobs 15 \
  <input_trace> <output_trace>

3. Rewrite Strategy

• Chain clusters of size ≥ 3: Add first → third edge (e.g. A→B→C becomes A→B, A→C, B→C) to break the chain
• Chains of size 2: Left unchanged

4. This Run Result

Input: Original trace (~552 MB, 1,763,516 commits)

Output: Rewritten trace

Extra ADD_DEP edges added: 43,074

Verification: python3 contrib/txgraph_tracing/analyze_trace.py <trace_file>

Cluster Distribution (analyze_trace.py)

Peak State (27,512 transactions, 8,582 clusters)

• Transactions in chain clusters: 8,770 (31.9%)
• Transactions in non-chain clusters: 18,742 (68.1%)

Peak Summary

• 582 size-2 chain clusters (1,164 transactions) still use ChainClusterImpl
• All clusters of size≥3 are non-chain (rewrite succeeded)

Comparison Test

The comparison script is available in the bitcoin/bitcoin chaincluster_time_mem_bench branch.

Command

TXGRAPH_TRACE_FILE=/path/to/txgraph.trace.4.5days.final.nochain.copy \
  ./contrib/compare_before_vs_chaincluster.sh getmain

GetMainMemoryUsage (Cluster::TotalMemoryUsage) Results

GetMainMemoryUsage is based on TxGraph’s internal Cluster::TotalMemoryUsage and measures TxGraph memory. See ChainCluster Memory Comparison: Three Methods for measurement details.

Difference: chaincluster uses 92,648 bytes less (~3.2%).

Time Performance Measured Results

The table sums CPU time (μs) per entry point. Wall-clock time (actual elapsed time for the full replay, including I/O) is measured separately: Baseline 10 s, ChainCluster 10 s, difference 0 s (0%). CPU time difference: chaincluster is ~21% faster (TOTAL μs).

Analysis

Why Is There Still ~21% CPU Time Improvement?

The rewrite script only eliminates chains of size≥3; size-2 chains are left unchanged. The 582 size-2 chains use ChainClusterImpl in the chaincluster branch, yielding:

1. O(N) fast path: vs GenericClusterImpl’s O(N²) linearization
2. Lower memory: ~20 bytes/tx vs ~40 bytes/tx

Clear speedups appear on DoWork, CommitStaging, IsOversized, and other paths.

GetMainMemoryUsage on No-Large-Chain Trace

On the no-large-chain trace, chaincluster uses ~3.2% less TxGraph memory (GetMainMemoryUsage) than before_chaincluster. The 582 size-2 chains benefit from ChainClusterImpl’s compact representation (~20 bytes/tx vs ~40 bytes/tx).

Comparison with Original Trace

The original trace has 889 chain clusters of size≥2 at peak; the no-large-chain trace retains only 582 size-2 chains. Eliminating size-2 chains as well would yield a “fully no-chain” baseline.

Summary

The no-large-chain trace eliminates all size≥3 chain clusters by adding 43,074 extra ADD_DEP edges, leaving 582 size-2 chains. Time performance: chaincluster is ~21% faster in CPU time (wall-clock similar); GetMainMemoryUsage: chaincluster uses ~3.2% less TxGraph memory. Size-2 chains provide both time and memory benefits.

Test Environment

The above results were obtained on the test machine.

Hardware

Host OS

Docker Container