`BeaconState::apply_pending_mutations` is slow with changes to `validators`

[michaelsproul]

Description

@chong-he and I debugged an issue in BeaconState::apply_pending_mutations where small changes in validators blow out the time required to apply updates.

E.g. for the block at slot 13919998, there are 2 validators that exit, and this creates ~140ms of work in apply_pending_mutations! Gross!

Here's the augmented lcli output:

Mar 19 16:03:42.354 DEBUG Slot processing: 24.12µs                    
Mar 19 16:03:42.354 DEBUG Build all caches (again): 11.26µs           
Mar 19 16:03:42.384 DEBUG Batch verify block signatures: 29.716626ms  
Mar 19 16:03:42.483 DEBUG Process block: 99.235892ms                  
Mar 19 16:03:42.489 DEBUG balances apply updates: 5ms                 
Mar 19 16:03:42.489 DEBUG previous epoch participation apply updates: 0ms
Mar 19 16:03:42.499 DEBUG current epoch participation apply updates: 10ms
Mar 19 16:03:42.500 DEBUG field 0 apply updates: 0ms                  
Mar 19 16:03:42.500 DEBUG field 1 apply updates: 0ms                  
Mar 19 16:03:42.500 DEBUG field 2 apply updates: 0ms                  
Mar 19 16:03:42.500 DEBUG field 3 apply updates: 0ms                  
Mar 19 16:03:42.641 DEBUG field 4 apply updates: 141ms                
Mar 19 16:03:42.642 DEBUG field 5 apply updates: 0ms                  
Mar 19 16:03:42.642 DEBUG field 6 apply updates: 0ms                  
Mar 19 16:03:42.642 DEBUG field 7 apply updates: 0ms                  
Mar 19 16:03:42.642 DEBUG field 8 apply updates: 0ms                  
Mar 19 16:03:42.642 DEBUG field 9 apply updates: 0ms                  
Mar 19 16:03:42.642 DEBUG field 10 apply updates: 0ms                 
Mar 19 16:03:42.642 DEBUG field 11 apply updates: 0ms                 
Mar 19 16:03:42.642 DEBUG field 12 apply updates: 0ms                 
Mar 19 16:03:42.642 DEBUG field 13 apply updates: 0ms                 
Mar 19 16:03:42.642 DEBUG field 14 apply updates: 0ms                 
Mar 19 16:03:42.642 DEBUG field 15 apply updates: 0ms                 
Mar 19 16:03:42.642 DEBUG apply_pending_mutations: 142ms              
Mar 19 16:03:42.644 DEBUG Post-block tree hash: 161.479991ms

Need to do some more digging to optimise this out. Will likely require changes inside milhouse's with_updated_leaves.

[michaelsproul]

The impact of this issue is 10x spikes in tree hashing time when there are changes to state.validators. Credit to @watiem on Discord for raising this and prompting the investigation.

[peter941221]

I dug into this from the Lighthouse side and the hot path does appear to sit upstream in milhouse, exactly around repeated for_each_range(...) calls during apply-time tree rebuilding.

I’ve opened an upstream milhouse PR here:

• Optimize MaxMap sparse range iteration with a lazy realized-key cache milhouse#94

The fix keeps the public API unchanged and makes MaxMap lazily cache realized update keys for range iteration, so repeated sparse range scans stop paying for dense walks across a large logical key space.

Local benchmark summary on List<u64, _> with N = 800_000:

• sparse_two: 3.72-4.08 ms -> 2.93-3.07 ms
• sparse_eight: 4.34-4.58 ms -> 3.03-3.23 ms
• dense_window_512: 14.70-17.89 ms -> 1.98-2.29 ms

I started upstream because Lighthouse currently consumes the published milhouse crate rather than a local path dependency, so this seemed like the cleanest place to fix the root cause instead of layering in a downstream-only workaround.

[michaelsproul]

Yeah great shout! I was planning to do some optimising in Milhouse to fix this. Will take a look at your PR

Thanks!

[michaelsproul]

@peter941221 Found a simpler win, by switching off VecMap for the validators:

• Use BTreeMap for state.validators pending updates #9017

Thank you for this work on this issue though! It's possible we should still fix the VecMap implementation, as we're using it for e.g. balances and other things, but I suspect there's not much more perf to be squeezed out of these changes right now (if you'd like to run some benchmarks that would be cool).

We're planning a release shortly, so we'll likely just include the quick fix, and retain the option to go deeper in future.

[peter941221]

Thanks, that makes sense — the BTreeMap switch for validators seems like the right release-time fix.

I’m happy to run some targeted benchmarks for the remaining VecMap users (e.g. balances / similar large sparse-update paths) and compare that against the validators-only change, so we can tell whether there’s still enough upside to justify the upstream milhouse work. If helpful I can post a small benchmark matrix on the PR.
No pressure on the release path either way — thanks again for taking a look.

[michaelsproul]

Awesome, thanks!

[michaelsproul]

Closing this as resolved. Opened a new issue for further explorations:

• Explore more Milhouse optimisations #9033