commitment: hierarchical branch cache + delayed writes + parallel trie computation

[mh0lt]

Background

Commitment (Patricia trie hashing) is the bottleneck in the parallel execution pipeline. During sync, commitment takes 1.5–2.6x longer than execution per batch. At tip, commitment dominates per-block latency (seconds vs hundreds of ms for exec).

Three techniques exist in various stages of readiness that, combined, can significantly reduce commitment cost:

1. Hierarchical branch cache — from add_execution_context_with_caches branch (branchCache with fixed-size arrays for trie depth < 4, LRU fallback for deeper paths)
2. Delayed trie writes — already in main (SetDeferCommitmentUpdates / FlushPendingUpdates / ApplyDeferredBranchUpdates)
3. Parallel trie computation — already in main (ConcurrentPatriciaHashed / ParallelHashSort with 16-goroutine nibble parallelism), but not activating during sync

These need to be combined into a unified commitment optimization. Currently:

• The branch cache is part of a large breaking change (ExecutionContext replacing SharedDomains) that can't merge yet
• Delayed trie writes exist but are not wired into the main parallel execution flow
• Parallel trie computation exists but the structural condition (CanDoConcurrentNext) never fires during sync, so it runs in mode=direct (single-threaded)

Goal

Extract the specialized commitment cache from add_execution_context_with_caches, wire it with delayed trie writes, and enable parallel trie computation. This is independent of the ExecutionContext refactor — we're extracting the cache as a standalone improvement.

Current branch read path

unfoldBranchNode → readBranchAndCheckForFlushing
  ├── check deferred updates (ApplyDeferredUpdates if prefix is pending)
  └── branchFromCacheOrDB
       ├── WarmupCache.GetBranch (if warmup ran)  ← ephemeral, per-computation
       └── ctx.Branch → SharedDomains.DomainGet → MDBX    ← cold read, expensive

The current WarmupCache is ephemeral — built during warmup phase, consumed during computation, discarded. It does not persist across commitment computations. The new branchCache is persistent and exploits the trie access pattern.

Design: hierarchical persistent branch cache

From add_execution_context_with_caches, the key insight is that trie branch access follows a predictable depth distribution:

Depth (nibbles)	Array size	Description
0 (root state)	1	KeyCommitmentState — most frequently accessed
0 (root branch)	1	Single trie root branch
1 nibble	16	First-level children
2 nibbles	256	Second-level
2.5 nibbles	4096	Third-level
3 nibbles	65536	Fourth-level
> 3 nibbles	LRU	Deep paths — bounded LRU cache

For depths 0–3 (which cover the hottest nodes), lookups are O(1) array index — no hashing, no allocation, no eviction. This matters because:

• Root + level-1 branches are read on every key during unfoldBranchNode
• There are only 16 level-1 branches (one per nibble)
• These hot nodes dominate the MDBX read profile during commitment

type branchCache struct {
    state   ValueWithTxNum[BranchData]         // commitment state (root hash + metadata)
    t0      ValueWithTxNum[BranchData]         // root branch
    t1      [16]ValueWithTxNum[BranchData]     // depth-1 branches
    t2      [256]ValueWithTxNum[BranchData]    // depth-2 branches
    t3      [4096]ValueWithTxNum[BranchData]   // depth-2.5 branches
    t4      [65536]ValueWithTxNum[BranchData]  // depth-3 branches
    deep    *lruCache[Path, BranchData]        // deeper paths — bounded LRU
}

Write-through: when PutBranch is called (either inline or via FlushPendingUpdates), the cache is updated alongside MDBX. The cache is always fresh.

Persistent across computations: unlike WarmupCache, the branchCache lives on SharedDomainsCommitmentContext and persists across batch boundaries. Hot branches stay cached.

Combining the three techniques

Phase A: Extract and wire the hierarchical branch cache

1. Port branchCache from add_execution_context_with_caches into execution/commitment/ as a standalone type
2. Add branchCache to SharedDomainsCommitmentContext (or HexPatriciaHashed)
3. Wire into branchFromCacheOrDB: check branchCache before MDBX read
4. Wire into PutBranch: write-through to branchCache alongside MDBX write
5. Wire into ApplyDeferredBranchUpdates: update cache entries for flushed branches

Expected impact: eliminates MDBX reads for depth 0–3 branches. These are the most frequently accessed nodes — root branch is read O(N) times per computation where N = number of keys. At 300k keys per sync batch, this eliminates ~300k MDBX reads for just the root branch.

Files: execution/commitment/branch_cache.go (new), execution/commitment/hex_patricia_hashed.go, execution/commitment/commitmentdb/commitment_context.go

Phase B: Wire delayed trie writes into the parallel flow

The infrastructure exists (SetDeferCommitmentUpdates, FlushPendingUpdates, ApplyDeferredBranchUpdates) but isn't used in the main parallel execution path.

1. In exec3_parallel.go, enable SetDeferCommitmentUpdates(true) before ComputeCommitment
2. After ComputeCommitment returns the root hash, call FlushPendingUpdates to batch-apply all deferred branch writes
3. FlushPendingUpdates already uses parallel workers (runtime.NumCPU()) for ApplyDeferredBranchUpdates

Expected impact: reduces branch write overhead during trie traversal. Instead of N individual PutBranch calls scattered across the computation, branches accumulate in memory and are flushed in bulk. This reduces MDBX write amplification and improves cache locality.

Key interaction with Phase A: deferred writes update the branchCache at flush time, so subsequent reads within the same computation see fresh data (handled by readBranchAndCheckForFlushing which already checks deferred state).

Files: execution/stagedsync/exec3_parallel.go, db/state/execctx/domain_shared.go

Phase C: Enable parallel trie computation during sync

ConcurrentPatriciaHashed splits the trie into 16 subtries by first nibble and processes them in parallel. Currently gated by CanDoConcurrentNext() which checks a structural condition on the trie root that apparently never fires during sync.

1. Investigate why CanDoConcurrentNext() returns false during sync — is this a fundamental constraint or a configuration issue?
2. If the structural condition can be relaxed (e.g. after the first full computation establishes the root), enable it
3. If not, explore an alternative: use ParallelHashSort (which exists in hex_concurrent_patricia_hashed.go) to process key sorting and warmup in parallel, even if the main hash computation remains single-threaded

Key interaction with Phase A: the branchCache is shared across the 16 subtrie goroutines. Since each subtrie works on a disjoint nibble prefix, cache reads don't conflict. Cache writes need synchronization (per-tier atomics or a lock).

Key interaction with Phase B: deferred writes from 16 parallel subtries must be coordinated. Either each subtrie has its own deferred buffer (merged at the end) or deferred writes use a concurrent map.

Files: execution/commitment/hex_concurrent_patricia_hashed.go, execution/commitment/hex_patricia_hashed.go

Interaction with other work

• perf: pipeline commitment with execution in parallel path (async ComputeCommitment + BAL-driven warmup) #19791 (commitment pipelining): async ComputeCommitment + BAL-driven warmup. Phases A and B here make the commitment computation itself faster; perf: pipeline commitment with execution in parallel path (async ComputeCommitment + BAL-driven warmup) #19791 makes it concurrent with execution. Complementary.
• execution: extract apply loop into event stream with fan-out consumers #19798 (event stream extraction): the commitConsumer in the fan-out dispatcher is where Phases B and C wire in.
• state, stagedsync: IBS 2-cache refactor phase 2+3 — replace StateUpdates with VersionedWrites #19711 (ibs-2cache phase 2+3): must merge first — cleans the write path that feeds TouchKey.
• add_execution_context_with_caches: Phase A extracts the cache without the ExecutionContext breaking change. When ExecutionContext eventually merges, the cache moves to CommitmentDomain.branchCache (already designed there).

Ordering

Phase A (branch cache)  ← standalone, can start after #19711 merges
    │
    ├── Phase B (delayed writes) ← builds on A (cache updated at flush time)
    │
    └── Phase C (parallel trie) ← builds on A (shared cache) + B (deferred coordination)

Phase A is the highest-impact standalone change. Phases B and C build on it incrementally.

Out of scope

• ExecutionContext refactor (big breaking change, separate timeline)
• Serial execution path (unchanged)
• Domain-specific caches for accounts/storage/code (separate from commitment cache)

[VBulikov]

yperbasis added Imp1 as Importance