Explore more Milhouse optimisations

[michaelsproul]

Description

Several Milhouse optimisations might help us achieve faster epoch processing.

E.g. using different update maps, similar to:

• Use BTreeMap for state.validators pending updates #9017

Or optimising within Milhouse:

• Use custom HashCell in place of RwLock milhouse#98
• Optimize MaxMap sparse range iteration with a lazy realized-key cache milhouse#94

We should run lcli skip-slots benchmarks with these changes to see if we can squeeze out some more performance.

[0xMars42]

I ran benchmarks for the two open Milhouse PRs (#98, #94) against current unstable using lcli skip-slots on a mainnet epoch boundary, and profiled where epoch processing time is spent.

Setup

• CPU: AMD Ryzen 7 7800X3D (8C/16T)
• RAM: 32 GB
• Kernel: 6.19.7 (Fedora 42)
• Pre-state: mainnet finalized state at epoch boundary (308 MB, ~931K active validators)
• Test: lcli skip-slots --slots 32 --runs 1 (crosses one epoch boundary)
• Iterations: 5 per variant, page cache dropped between runs
• Baseline: current unstable (includes PR Use BTreeMap for state.validators pending updates #9017 BTreeMap for validators)

Results Epoch Processing

Variant	Median	Min	Max	Spread	Δ vs baseline
Baseline (milhouse 0.9)	867.8ms	858.7ms	875.0ms	16ms
PR #98 (HashCell lock-free)	823.6ms	821.2ms	834.6ms	13ms	-5.0%
PR #94 (lazy key cache)	848.9ms	820.3ms	867.7ms	47ms	-2.2%
PR #98 + #94 (combined)	885.2ms	876.9ms	897.9ms	21ms	within noise

Observations

• PR #98 shows a consistent improvement with low variance (13ms spread). The 44ms median gap vs baseline is well outside the noise band.
• PR #94 has high run-to-run variance (47ms spread). Its best runs match PR #98 (820ms) but its worst runs match baseline (868ms). The improvement signal is there but unreliable on this workload.
• Combined PR #98+#94: the median is 17ms above baseline, but this is within the baseline's own 16ms noise band. I would not call this a regression more likely noise. The two PRs do not appear to produce additive gains, however.

Partial State Advance (no tree hashing)

Variant	Median
Baseline	812ms
PR #98	814ms
PR #94	820ms

All gains disappear with --partial-state-advance (which skips update_tree_hash_cache). This is expected: PR #98 targets lock-free reads in Tree::tree_hash, while PR #94 targets for_each_range in Tree::with_updated_leaves both of which are called inside update_tree_hash_cache (via apply_pending_mutations).

CPU Profile Baseline Epoch Processing

Profiled with perf record on the baseline build (milhouse 0.9 from crates.io):

Category	CPU %
SHA-256 / tree hashing	35.8%
Milhouse iteration	21.7%
Committee shuffling	7.1%
Memory copy (memmove)	6.7%
Memory allocation (malloc/free)	6.2%
RPDS (persistent data structures)	3.2%
State processing logic	2.8%
DefaultHasher	2.7%

Top symbols: sha2::digest_blocks (14.8%), milhouse::iter::Iter::next (13.9%), memmove_avx512 (6.0%), shuffle_list (5.4%).

Over half the CPU is in SHA-256 hashing + Milhouse tree traversal.

Update Map Analysis

After PR #9017 switched validators to BTreeMap, I reviewed which other ValidatorRegistryLimit-sized lists could benefit:

Field	Epoch update pattern	Source
validators	Sparse only exits/slashings	Already on BTreeMap (PR #9017)
balances	Dense all eligible validators receive rewards/penalties via make_mut() (single_pass.rs:630)	VecMap is appropriate
inactivity_scores	Conditional validators participating with score==0 hit early return without make_mut(). During normal operation (no inactivity leak) most active validators should have score 0, making updates sparse. During an inactivity leak, all eligible validators get mutated (dense).	Possible BTreeMap candidate under normal conditions
previous/current_epoch_participation	Read-only during the single-pass loop, then bulk-swapped/reset via mem::take in participation_flag_updates no granular make_mut() updates	N/A

Note: I was not able to empirically verify what fraction of validators currently have non-zero inactivity scores on mainnet. The code analysis shows the update pattern is sparse during normal operation, but I cannot quantify the exact sparsity without inspecting the actual state data.

Summary

1. PR #98 (HashCell lock-free) clear 5% improvement on epoch processing with low variance. Targets lock-free hash reads in Tree::tree_hash.
2. PR #94 (lazy key cache) improvement signal exists but high variance makes it hard to confirm on this workload. May benefit specific scenarios (blocks with many exits, as in BeaconState::apply_pending_mutations is slow with changes to validators #9003) more than epoch transitions.
3. Combined no additive benefit observed. The two optimizations do not appear to stack.
4. Biggest remaining bottleneck SHA-256 at 35.8% of epoch CPU. milhouse::iter::Iter::next at 13.9% is also notable.