yk/batch-multiproof-v2 - Branch - paradigmxyz/reth

perf(multiproof): batch consecutive state updates

#20475

Comparing

yk/batch-multiproof-v2

(

21829c2

) with

main

(

98a7095

)

Untouched: 110

Skipped: 7

Benchmarks

Skipped (7)

Passed

V2[dataset_128/targets_512]

crates/trie/trie/benches/proof_v2.rs::proof_comparison::bench_proof_algos::Proof

+3%

848.4 µs824.3 µs

Legacy[dataset_128/targets_2048]

crates/trie/trie/benches/proof_v2.rs::proof_comparison::bench_proof_algos::Proof

+3%

1.2 ms1.2 ms

size 100000 | updated 0.1% | depth 2

crates/trie/sparse/benches/rlp_node.rs::rlp_node::update_rlp_node_level::update rlp node level

+2%

3.5 ms3.4 ms

size 100000 | updated 0.1% | depth 0

crates/trie/sparse/benches/rlp_node.rs::rlp_node::update_rlp_node_level::update rlp node level

+2%

3.6 ms3.6 ms

size 100000 | updated 0.1% | depth 1

crates/trie/sparse/benches/rlp_node.rs::rlp_node::update_rlp_node_level::update rlp node level

+2%

3.6 ms3.6 ms

size 100000 | updated 0.1% | depth 3

crates/trie/sparse/benches/rlp_node.rs::rlp_node::update_rlp_node_level::update rlp node level

+2%

2.5 ms2.4 ms

prefix set | size: 10 | `BTreeSet` with `Iterator:any` lookup

crates/trie/common/benches/prefix_set.rs::prefix_set::prefix_set_lookups::Prefix Set Lookups

+1%

4 µs3.9 µs

prefix set | size: 10 | `Vec` with custom cursor lookup

crates/trie/common/benches/prefix_set.rs::prefix_set::prefix_set_lookups::Prefix Set Lookups

+1%

3.3 µs3.3 µs

hash builder[init size 1000 | update size 1000 | num updates 1]

crates/trie/sparse/benches/root.rs::root::calculate_root_from_leaves_repeated::calculate root from leaves repeated

+1%

5.8 ms5.8 ms

hash builder[init size 1000 | update size 100 | num updates 3]

crates/trie/sparse/benches/root.rs::root::calculate_root_from_leaves_repeated::calculate root from leaves repeated

+1%

7.5 ms7.5 ms

hash builder[init size 10000 | update size 100 | num updates 1]

crates/trie/sparse/benches/root.rs::root::calculate_root_from_leaves_repeated::calculate root from leaves repeated

9.6 ms9.5 ms

Legacy[dataset_128/targets_128]

crates/trie/trie/benches/proof_v2.rs::proof_comparison::bench_proof_algos::Proof

860.1 µs856.6 µs

V2[dataset_1024/targets_512]

crates/trie/trie/benches/proof_v2.rs::proof_comparison::bench_proof_algos::Proof

11 ms11 ms

Legacy[dataset_128/targets_64]

crates/trie/trie/benches/proof_v2.rs::proof_comparison::bench_proof_algos::Proof

809.2 µs806.7 µs

sparse trie[init size 1000 | update size 1000 | num updates 1]

crates/trie/sparse/benches/root.rs::root::calculate_root_from_leaves_repeated::calculate root from leaves repeated

5.1 ms5.1 ms

validate_blob | num blobs: 5 | ValidateBlob

crates/primitives/benches/validate_blob_tx.rs::validate_blob::blob_validation::Blob Transaction KZG validation

153.5 µs153.2 µs

hash builder[init size 10000 | update size 1000 | num updates 1]

crates/trie/sparse/benches/root.rs::root::calculate_root_from_leaves_repeated::calculate root from leaves repeated

26.5 ms26.4 ms

hash builder[1000]

crates/trie/sparse/benches/root.rs::root::calculate_root_from_leaves::calculate root from leaves

4.5 ms4.5 ms

Legacy[dataset_1024/targets_512]

crates/trie/trie/benches/proof_v2.rs::proof_comparison::bench_proof_algos::Proof

15.4 ms15.4 ms

hash builder[5000]

crates/trie/sparse/benches/root.rs::root::calculate_root_from_leaves::calculate root from leaves

22.3 ms22.3 ms

hash builder[init size 1000 | update size 100 | num updates 1]

crates/trie/sparse/benches/root.rs::root::calculate_root_from_leaves_repeated::calculate root from leaves repeated

2.5 ms2.5 ms

hash builder[init size 10000 | update size 100 | num updates 10]

crates/trie/sparse/benches/root.rs::root::calculate_root_from_leaves_repeated::calculate root from leaves repeated

86.1 ms86 ms

hash builder[init size 1000 | update size 1000 | num updates 3]

crates/trie/sparse/benches/root.rs::root::calculate_root_from_leaves_repeated::calculate root from leaves repeated

17.3 ms17.3 ms

validate_blob | num blobs: 3 | ValidateBlob

crates/primitives/benches/validate_blob_tx.rs::validate_blob::blob_validation::Blob Transaction KZG validation

151.3 µs151.2 µs

sparse trie[init size 1000 | update size 100 | num updates 10]

crates/trie/sparse/benches/root.rs::root::calculate_root_from_leaves_repeated::calculate root from leaves repeated

10.8 ms10.8 ms

sparse trie[init size 10000 | update size 100 | num updates 3]

crates/trie/sparse/benches/root.rs::root::calculate_root_from_leaves_repeated::calculate root from leaves repeated

6.7 ms6.7 ms

prefix set | size: 100 | `BTreeSet` with `BTreeSet:range` lookup

crates/trie/common/benches/prefix_set.rs::prefix_set::prefix_set_lookups::Prefix Set Lookups

40.1 µs40.1 µs

Legacy[dataset_10240/targets_2048]

crates/trie/trie/benches/proof_v2.rs::proof_comparison::bench_proof_algos::Proof

870.4 ms869.6 ms

sparse trie[init size 1000 | update size 100 | num updates 1]

crates/trie/sparse/benches/root.rs::root::calculate_root_from_leaves_repeated::calculate root from leaves repeated

1.1 ms1.1 ms

V2[dataset_10240/targets_128]

crates/trie/trie/benches/proof_v2.rs::proof_comparison::bench_proof_algos::Proof

638.3 ms637.7 ms

Legacy[dataset_10240/targets_128]

crates/trie/trie/benches/proof_v2.rs::proof_comparison::bench_proof_algos::Proof

654.3 ms653.8 ms

prefix set | size: 1000 | `Vec` with custom cursor lookup

crates/trie/common/benches/prefix_set.rs::prefix_set::prefix_set_lookups::Prefix Set Lookups

146.3 µs146.2 µs

hash builder[init size 1000 | update size 100 | num updates 10]

crates/trie/sparse/benches/root.rs::root::calculate_root_from_leaves_repeated::calculate root from leaves repeated

24.7 ms24.7 ms

sparse trie[init size 10000 | update size 100 | num updates 1]

crates/trie/sparse/benches/root.rs::root::calculate_root_from_leaves_repeated::calculate root from leaves repeated

2.3 ms2.3 ms

sparse trie[init size 1000 | update size 100 | num updates 5]

crates/trie/sparse/benches/root.rs::root::calculate_root_from_leaves_repeated::calculate root from leaves repeated

5.4 ms5.4 ms

hash builder[init size 1000 | update size 1000 | num updates 5]

crates/trie/sparse/benches/root.rs::root::calculate_root_from_leaves_repeated::calculate root from leaves repeated

28.8 ms28.8 ms

V2[dataset_10240/targets_2048]

crates/trie/trie/benches/proof_v2.rs::proof_comparison::bench_proof_algos::Proof

640.4 ms639.9 ms

V2[dataset_10240/targets_64]

crates/trie/trie/benches/proof_v2.rs::proof_comparison::bench_proof_algos::Proof

637.6 ms637.2 ms

V2[dataset_10240/targets_1]

crates/trie/trie/benches/proof_v2.rs::proof_comparison::bench_proof_algos::Proof

637.2 ms636.8 ms

validate_blob | num blobs: 4 | ValidateBlob

crates/primitives/benches/validate_blob_tx.rs::validate_blob::blob_validation::Blob Transaction KZG validation

151.8 µs151.8 µs

Legacy[dataset_10240/targets_64]

crates/trie/trie/benches/proof_v2.rs::proof_comparison::bench_proof_algos::Proof

645.5 ms645.2 ms

Legacy[dataset_10240/targets_1]

crates/trie/trie/benches/proof_v2.rs::proof_comparison::bench_proof_algos::Proof

637.1 ms636.7 ms

Legacy[dataset_10240/targets_16]

crates/trie/trie/benches/proof_v2.rs::proof_comparison::bench_proof_algos::Proof

639.2 ms638.9 ms

ordered_trie_root

crates/trie/trie/benches/trie_root.rs::benches::trie_root_benchmark::Receipts root calculation::receipts root | size: 100 | triehash

1.2 ms1.2 ms

V2[dataset_10240/targets_16]

crates/trie/trie/benches/proof_v2.rs::proof_comparison::bench_proof_algos::Proof

637.7 ms637.4 ms

V2[dataset_128/targets_16]

crates/trie/trie/benches/proof_v2.rs::proof_comparison::bench_proof_algos::Proof

699.3 µs699.1 µs

sparse trie[init size 10000 | update size 100 | num updates 5]

crates/trie/sparse/benches/root.rs::root::calculate_root_from_leaves_repeated::calculate root from leaves repeated

11.1 ms11.1 ms

validate_blob | num blobs: 1 | ValidateBlob

crates/primitives/benches/validate_blob_tx.rs::validate_blob::blob_validation::Blob Transaction KZG validation

146.8 µs146.7 µs

receipts root | size: 1000 | HashBuilder

crates/trie/trie/benches/trie_root.rs::benches::trie_root_benchmark::Receipts root calculation

9.1 ms9.1 ms

V2[dataset_10240/targets_512]

crates/trie/trie/benches/proof_v2.rs::proof_comparison::bench_proof_algos::Proof

638.7 ms638.5 ms

sparse trie[init size 10000 | update size 1000 | num updates 1]

crates/trie/sparse/benches/root.rs::root::calculate_root_from_leaves_repeated::calculate root from leaves repeated

11.7 ms11.6 ms

Legacy[dataset_10240/targets_512]

crates/trie/trie/benches/proof_v2.rs::proof_comparison::bench_proof_algos::Proof

703.3 ms703.1 ms

sparse trie[init size 1000 | update size 1000 | num updates 5]

crates/trie/sparse/benches/root.rs::root::calculate_root_from_leaves_repeated::calculate root from leaves repeated

24.9 ms24.9 ms

prefix set | size: 100 | `BTreeSet` with `Iterator:any` lookup

crates/trie/common/benches/prefix_set.rs::prefix_set::prefix_set_lookups::Prefix Set Lookups

149.3 µs149.3 µs

sparse trie[init size 1000 | update size 1000 | num updates 10]

crates/trie/sparse/benches/root.rs::root::calculate_root_from_leaves_repeated::calculate root from leaves repeated

49.7 ms49.7 ms

recover ECDSA

crates/primitives/benches/recover_ecdsa_crit.rs::benches::criterion_benchmark

206.7 µs206.6 µs

receipts root | size: 100 | HashBuilder

crates/trie/trie/benches/trie_root.rs::benches::trie_root_benchmark::Receipts root calculation

936.9 µs936.8 µs

sequence hashing[100]

crates/trie/trie/benches/hash_post_state.rs::post_state::hash_post_state::Hash Post State

258.9 ms258.9 ms

parallel hashing[100]

crates/trie/trie/benches/hash_post_state.rs::post_state::hash_post_state::Hash Post State

258.9 ms258.9 ms

parallel hashing[1000]

crates/trie/trie/benches/hash_post_state.rs::post_state::hash_post_state::Hash Post State

2.6 s2.6 s

sparse trie[init size 10000 | update size 1000 | num updates 5]

crates/trie/sparse/benches/root.rs::root::calculate_root_from_leaves_repeated::calculate root from leaves repeated

56 ms56 ms

V2[dataset_128/targets_1]

crates/trie/trie/benches/proof_v2.rs::proof_comparison::bench_proof_algos::Proof

677.8 µs677.8 µs

ordered_trie_root

crates/trie/trie/benches/trie_root.rs::benches::trie_root_benchmark::Receipts root calculation::receipts root | size: 10 | triehash

131.9 µs131.9 µs

Legacy[dataset_1024/targets_64]

crates/trie/trie/benches/proof_v2.rs::proof_comparison::bench_proof_algos::Proof

11.4 ms11.4 ms

Legacy[dataset_128/targets_1]

crates/trie/trie/benches/proof_v2.rs::proof_comparison::bench_proof_algos::Proof

707.8 µs707.8 µs

prefix set | size: 10 | `BTreeSet` with `BTreeSet:range` lookup

crates/trie/common/benches/prefix_set.rs::prefix_set::prefix_set_lookups::Prefix Set Lookups

5.1 µs5.1 µs

prefix set | size: 100 | `Vec` with custom cursor lookup

crates/trie/common/benches/prefix_set.rs::prefix_set::prefix_set_lookups::Prefix Set Lookups

16.7 µs16.7 µs

receipts root | size: 10 | HashBuilder

crates/trie/trie/benches/trie_root.rs::benches::trie_root_benchmark::Receipts root calculation

112.1 µs112.1 µs

prefix set | size: 1000 | `BTreeSet` with `Iterator:any` lookup

crates/trie/common/benches/prefix_set.rs::prefix_set::prefix_set_lookups::Prefix Set Lookups

14.9 ms14.9 ms

sparse trie[init size 10000 | update size 1000 | num updates 10]

crates/trie/sparse/benches/root.rs::root::calculate_root_from_leaves_repeated::calculate root from leaves repeated

111.5 ms111.5 ms

sequence hashing[1000]

crates/trie/trie/benches/hash_post_state.rs::post_state::hash_post_state::Hash Post State

2.6 s2.6 s

sparse trie[init size 10000 | update size 100 | num updates 10]

crates/trie/sparse/benches/root.rs::root::calculate_root_from_leaves_repeated::calculate root from leaves repeated

22.1 ms22.1 ms

ordered_trie_root

crates/trie/trie/benches/trie_root.rs::benches::trie_root_benchmark::Receipts root calculation::receipts root | size: 1000 | triehash

11.8 ms11.8 ms

sparse trie[init size 1000 | update size 100 | num updates 3]

crates/trie/sparse/benches/root.rs::root::calculate_root_from_leaves_repeated::calculate root from leaves repeated

3.3 ms3.3 ms

hash builder[init size 1000 | update size 1000 | num updates 10]

crates/trie/sparse/benches/root.rs::root::calculate_root_from_leaves_repeated::calculate root from leaves repeated

57.4 ms57.4 ms

prefix set | size: 1000 | `BTreeSet` with `BTreeSet:range` lookup

crates/trie/common/benches/prefix_set.rs::prefix_set::prefix_set_lookups::Prefix Set Lookups

469.6 µs469.7 µs

V2[dataset_1024/targets_2048]

crates/trie/trie/benches/proof_v2.rs::proof_comparison::bench_proof_algos::Proof

11.6 ms11.6 ms

V2[dataset_128/targets_128]

crates/trie/trie/benches/proof_v2.rs::proof_comparison::bench_proof_algos::Proof

754.9 µs755.3 µs

V2[dataset_1024/targets_64]

crates/trie/trie/benches/proof_v2.rs::proof_comparison::bench_proof_algos::Proof

10.6 ms10.6 ms

Legacy[dataset_128/targets_512]

crates/trie/trie/benches/proof_v2.rs::proof_comparison::bench_proof_algos::Proof

991.6 µs992.2 µs

Legacy[dataset_1024/targets_128]

crates/trie/trie/benches/proof_v2.rs::proof_comparison::bench_proof_algos::Proof

12.2 ms12.2 ms

hash builder[init size 10000 | update size 1000 | num updates 5]

crates/trie/sparse/benches/root.rs::root::calculate_root_from_leaves_repeated::calculate root from leaves repeated

127.7 ms127.8 ms

V2[dataset_128/targets_64]

crates/trie/trie/benches/proof_v2.rs::proof_comparison::bench_proof_algos::Proof

734.9 µs735.5 µs

V2[dataset_1024/targets_128]

crates/trie/trie/benches/proof_v2.rs::proof_comparison::bench_proof_algos::Proof

10.7 ms10.7 ms

hash builder[init size 10000 | update size 1000 | num updates 3]

crates/trie/sparse/benches/root.rs::root::calculate_root_from_leaves_repeated::calculate root from leaves repeated

77.3 ms77.4 ms

V2[dataset_1024/targets_16]

crates/trie/trie/benches/proof_v2.rs::proof_comparison::bench_proof_algos::Proof

10.5 ms10.6 ms

hash builder[init size 1000 | update size 100 | num updates 5]

crates/trie/sparse/benches/root.rs::root::calculate_root_from_leaves_repeated::calculate root from leaves repeated

12.4 ms12.5 ms

validate_blob | num blobs: 2 | ValidateBlob

crates/primitives/benches/validate_blob_tx.rs::validate_blob::blob_validation::Blob Transaction KZG validation

149.6 µs149.8 µs

Legacy[dataset_128/targets_16]

crates/trie/trie/benches/proof_v2.rs::proof_comparison::bench_proof_algos::Proof

739.9 µs740.8 µs

hash builder[init size 10000 | update size 1000 | num updates 10]

crates/trie/sparse/benches/root.rs::root::calculate_root_from_leaves_repeated::calculate root from leaves repeated

254.2 ms254.5 ms

hash builder[init size 10000 | update size 100 | num updates 3]

crates/trie/sparse/benches/root.rs::root::calculate_root_from_leaves_repeated::calculate root from leaves repeated

26.8 ms26.8 ms

V2[dataset_1024/targets_1]

crates/trie/trie/benches/proof_v2.rs::proof_comparison::bench_proof_algos::Proof

10.5 ms10.5 ms

Legacy[dataset_1024/targets_16]

crates/trie/trie/benches/proof_v2.rs::proof_comparison::bench_proof_algos::Proof

10.7 ms10.7 ms

sparse trie[init size 10000 | update size 1000 | num updates 3]

crates/trie/sparse/benches/root.rs::root::calculate_root_from_leaves_repeated::calculate root from leaves repeated

33.8 ms33.9 ms

Legacy[dataset_1024/targets_1]

crates/trie/trie/benches/proof_v2.rs::proof_comparison::bench_proof_algos::Proof

10.5 ms10.5 ms

sparse trie[init size 1000 | update size 1000 | num updates 3]

crates/trie/sparse/benches/root.rs::root::calculate_root_from_leaves_repeated::calculate root from leaves repeated

15 ms15 ms

validate_blob | num blobs: 6 | ValidateBlob

crates/primitives/benches/validate_blob_tx.rs::validate_blob::blob_validation::Blob Transaction KZG validation

154.7 µs154.9 µs

hash builder[init size 10000 | update size 100 | num updates 5]

crates/trie/sparse/benches/root.rs::root::calculate_root_from_leaves_repeated::calculate root from leaves repeated

43.9 ms43.9 ms

size 100000 | updated 1% | depth 4

crates/trie/sparse/benches/rlp_node.rs::rlp_node::update_rlp_node_level::update rlp node level

11.3 ms11.3 ms

sparse trie[5000]

crates/trie/sparse/benches/root.rs::root::calculate_root_from_leaves::calculate root from leaves

28.2 ms28.2 ms

V2[dataset_128/targets_2048]

crates/trie/trie/benches/proof_v2.rs::proof_comparison::bench_proof_algos::Proof

1.1 ms1.1 ms

sparse trie[1000]

crates/trie/sparse/benches/root.rs::root::calculate_root_from_leaves::calculate root from leaves

5.7 ms5.7 ms

Legacy[dataset_1024/targets_2048]

crates/trie/trie/benches/proof_v2.rs::proof_comparison::bench_proof_algos::Proof

19.5 ms19.6 ms

size 100000 | updated 0.1% | depth 4

crates/trie/sparse/benches/rlp_node.rs::rlp_node::update_rlp_node_level::update rlp node level

-1%

1.4 ms1.4 ms

size 100000 | updated 0.1% | depth 5

crates/trie/sparse/benches/rlp_node.rs::rlp_node::update_rlp_node_level::update rlp node level

-1%

1.1 ms1.1 ms

size 100000 | updated 1% | depth 3

crates/trie/sparse/benches/rlp_node.rs::rlp_node::update_rlp_node_level::update rlp node level

-1%

21.5 ms21.7 ms

size 100000 | updated 1% | depth 2

crates/trie/sparse/benches/rlp_node.rs::rlp_node::update_rlp_node_level::update rlp node level

-1%

24.4 ms24.5 ms

size 100000 | updated 1% | depth 1

crates/trie/sparse/benches/rlp_node.rs::rlp_node::update_rlp_node_level::update rlp node level

-1%

24.5 ms24.7 ms

size 100000 | updated 1% | depth 0

crates/trie/sparse/benches/rlp_node.rs::rlp_node::update_rlp_node_level::update rlp node level

-1%

24.5 ms24.7 ms

size 100000 | updated 1% | depth 5

crates/trie/sparse/benches/rlp_node.rs::rlp_node::update_rlp_node_level::update rlp node level

-1%

8.2 ms8.3 ms

Commits

Click on a commit to change the comparison range

Base

main

98a7095

-0.09%

fix(multiproof): batch at HashedPostState level instead of EvmState

3c60275

14 hours ago

by yongkangc

+0.2%

chore: remove outdated comment

e2864b3

12 hours ago

by yongkangc

+0.05%

perf(multiproof): optimize state update batching - Remove state.clone() by accepting &EvmState in evm_state_to_hashed_post_state - Call update_with_state once on merged state instead of per sub-update (MultiAddedRemovedKeys only cares about final values, not intermediates)

e8fadf3

11 hours ago

by yongkangc

-0.08%

perf(multiproof): defer hashing with SealedStateUpdate Introduce SealedStateUpdate to capture is_changed semantics at seal time while deferring expensive keccak256 hashing until after batching. Key changes: - SealedStateUpdate stores unhashed addresses/slots (20-byte keys) - seal() captures is_changed filter per-TX (cheap, no hashing) - extend() merges sealed updates safely (no flags to corrupt) - into_hashed_post_state() hashes once after batch merge Performance: For 10 TXs touching same address with 50 slots: - Before: 510 hashes on EVM thread (per-TX hashing) - After: 51 hashes on multiproof thread (once per batch)

3dacccf

10 hours ago

by yongkangc

+0.13%

chore(multiproof): remove local benchmark test Remove bench_clone_vs_hash_conversion_small_updates test that was used for local performance sanity checks during development.

115be9c

10 hours ago

by yongkangc

-0.24%

test(multiproof): add unit tests for SealedStateUpdate Add comprehensive unit tests covering: - extend() with selfdestruct scenarios - extend() with selfdestruct-then-recreate - extend() storage last-writer-wins semantics - into_hashed_post_state() key hashing - into_hashed_post_state() with wiped accounts - into_hashed_post_state() wiped accounts with new storage - estimate_targets() calculation - seal() filtering of touched accounts and changed storage - seal() handling of selfdestructed accounts Also marks evm_state_to_hashed_post_state as #[cfg(test)] since it's only used in tests, and fixes doc comment formatting.

0a92dc3

10 hours ago

by yongkangc

+0.03%

chore: clarify state sealing comment

3a12525

7 hours ago

by yongkangc

+0.13%

refactor(multiproof): replace SealedStateUpdate with merge_evm_state This simplifies the batching fix by using a custom merge function instead of a separate sealed type. The core issue: EvmState::extend overwrites storage slots including their original_value, breaking is_changed() semantics. The previous fix (SealedStateUpdate) captured is_changed at seal time and deferred hashing. The new approach is simpler: merge_evm_state() merges EvmState updates while preserving original_value from the base state. This ensures is_changed() returns correct results after batching, without needing a separate type. Changes: - Remove SealedStateUpdate struct and its seal/extend/into_hashed_post_state methods - Add merge_evm_state() that preserves base.original_value when merging slots - Add estimate_evm_state_targets() for batching decisions - Update MultiProofMessage::StateUpdate to use EvmState directly - Update state_hook to clone EvmState instead of sealing - Update tests to use EvmState and merge_evm_state

21829c2

7 hours ago

by yongkangc

Home Terms Privacy Docs