sparse-trie-as-cache - Branch - paradigmxyz/reth

refactor(engine): sparse trie as cache - move sequencer and add proof target generation

#21102

Comparing

sparse-trie-as-cache

(

b861b13

) with

main

(

a74cb9c

)

Untouched: 118

Skipped: 7

Benchmarks

Skipped (7)

Passed

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

+3%

9.7 ms9.4 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

+1%

27.4 ms27.1 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%

3.9 µs3.9 µ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

+1%

27.2 ms27.1 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

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.9 ms5.9 ms

Legacy[dataset_1024/targets_2048]

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

+1%

19.6 ms19.5 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

132.4 ms131.8 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

87.3 ms86.9 ms

collect_twice[1000]

crates/trie/common/benches/hashed_state.rs::benches::bench_from_parallel_iterator::HashedPostState::from_par_iter

725.7 µs723.4 µs

fold_reduce[100]

crates/trie/common/benches/hashed_state.rs::benches::bench_from_parallel_iterator::HashedPostState::from_par_iter

156.6 µs156.1 µs

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

80.2 ms80 ms

V2[dataset_1024/targets_512]

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

11 ms11 ms

V2[dataset_128/targets_512]

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

837.5 µs835.8 µs

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.7 ms12.7 ms

V2[dataset_128/targets_64]

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

731.2 µs729.7 µs

Legacy[dataset_128/targets_512]

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

1,001.7 µs999.8 µs

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.7 ms

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

25.2 ms25.2 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 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

hash builder[1000]

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

4.5 ms4.5 ms

sequence hashing[100]

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

256.8 ms256.6 ms

parallel hashing[100]

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

256.9 ms256.7 ms

V2[dataset_1024/targets_16]

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

10.6 ms10.6 ms

validate_blob | num blobs: 4 | ValidateBlob

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

151.9 µs151.8 µs

validate_blob | num blobs: 3 | ValidateBlob

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

150.8 µs150.7 µs

Legacy[dataset_128/targets_1]

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

704.6 µs704.3 µ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

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.6 ms2.6 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.4 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.8 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

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 10000 | update size 100 | num updates 5]

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

44.5 ms44.5 ms

V2[dataset_1024/targets_64]

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

10.6 ms10.6 ms

collect_twice[50000]

crates/trie/common/benches/hashed_state.rs::benches::bench_from_parallel_iterator::HashedPostState::from_par_iter

42.6 ms42.6 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

recover ECDSA

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

206.6 µs206.6 µ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

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

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.6 ms17.6 ms

collect_twice[100]

crates/trie/common/benches/hashed_state.rs::benches::bench_from_parallel_iterator::HashedPostState::from_par_iter

87.9 µs87.9 µ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

validate_blob | num blobs: 2 | ValidateBlob

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

149.7 µs149.7 µs

validate_blob | num blobs: 6 | ValidateBlob

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

154.7 µs154.7 µ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

3.3 µs3.3 µ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

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

V2[dataset_1024/targets_128]

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 5]

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

56 ms56 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

hash builder[5000]

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

22.3 ms22.3 ms

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 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

V2[dataset_128/targets_1]

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

677.3 µs677.4 µ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

262.4 ms262.4 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

fold_reduce[1000]

crates/trie/common/benches/hashed_state.rs::benches::bench_from_parallel_iterator::HashedPostState::from_par_iter

1.4 ms1.4 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

fold_reduce[50000]

crates/trie/common/benches/hashed_state.rs::benches::bench_from_parallel_iterator::HashedPostState::from_par_iter

71.3 ms71.4 ms

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 1000 | update size 1000 | num updates 10]

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

58.5 ms58.5 ms

receipts root | size: 1000 | HashBuilder

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

9.1 ms9.1 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.1 µs146.2 µs

Legacy[dataset_1024/targets_64]

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

11.4 ms11.4 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

V2[dataset_1024/targets_2048]

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

11.5 ms11.5 ms

V2[dataset_10240/targets_512]

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

637.4 ms637.7 ms

Legacy[dataset_10240/targets_512]

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

701.8 ms702.2 ms

collect_twice[10000]

crates/trie/common/benches/hashed_state.rs::benches::bench_from_parallel_iterator::HashedPostState::from_par_iter

6.8 ms6.8 ms

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

fold_reduce[10000]

crates/trie/common/benches/hashed_state.rs::benches::bench_from_parallel_iterator::HashedPostState::from_par_iter

12.1 ms12.1 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

7.6 ms7.6 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.3 µs469.7 µs

Legacy[dataset_10240/targets_2048]

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

868.9 ms869.7 ms

receipts root | size: 100 | HashBuilder

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

936.7 µs937.6 µ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.6 ms49.7 ms

ordered_trie_root

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

131.8 µs132 µs

Legacy[dataset_1024/targets_1]

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

10.5 ms10.5 ms

V2[dataset_10240/targets_128]

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

636.4 ms637.1 ms

size 100000 | updated 1% | depth 5

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

8.4 ms8.4 ms

Legacy[dataset_10240/targets_128]

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

652.4 ms653.2 ms

V2[dataset_1024/targets_1]

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

10.5 ms10.5 ms

V2[dataset_10240/targets_2048]

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

639 ms639.9 ms

sparse trie[1000]

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

5.7 ms5.7 ms

V2[dataset_10240/targets_64]

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

636.2 ms637.1 ms

validate_blob | num blobs: 5 | ValidateBlob

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

153.3 µs153.5 µs

Legacy[dataset_10240/targets_64]

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

644 ms644.9 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 µs40.1 µs

V2[dataset_10240/targets_1]

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

635.7 ms636.7 ms

V2[dataset_10240/targets_16]

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

636.1 ms637 ms

Legacy[dataset_10240/targets_1]

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

635.5 ms636.4 ms

Legacy[dataset_10240/targets_16]

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

637.4 ms638.4 ms

Legacy[dataset_128/targets_16]

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

733.1 µs734.4 µs

Legacy[dataset_128/targets_64]

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

806.7 µs808.1 µs

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

29.3 ms29.3 ms

receipts root | size: 10 | HashBuilder

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

111.7 µs111.9 µs

Legacy[dataset_1024/targets_512]

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

15.4 ms15.4 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

V2[dataset_128/targets_16]

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

695.8 µs697.7 µs

size 100000 | updated 0.1% | depth 0

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

3.7 ms3.7 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

3.7 ms3.7 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

size 100000 | updated 0.1% | depth 2

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

3.5 ms3.5 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.4 ms11.5 ms

sparse trie[5000]

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

28.3 ms28.4 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.6 ms24.8 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.7 ms24.9 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.7 ms24.9 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.7 ms21.9 ms

V2[dataset_128/targets_2048]

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

-1%

1.1 ms1.2 ms

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

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

-1%

5.1 µs5.1 µs

V2[dataset_128/targets_128]

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

-1%

738.5 µs749.7 µs

Legacy[dataset_128/targets_128]

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

-2%

855 µs870.5 µs

Legacy[dataset_128/targets_2048]

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

-2%

1.2 ms1.2 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

-2%

1.4 ms1.4 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

-3%

2.5 ms2.5 ms

Commits

Click on a commit to change the comparison range

Base

main

a74cb9c

-0.15%

feat(trie): add generic proof target generation methods to SparseStateTrie Add generate_account_proof_targets and generate_storage_proof_targets methods to the generic SparseStateTrie<A, S> impl block. These methods: - Return full proofs (min_len=0) for all keys as a safe fallback - Exclude keys that are already fully revealed as leaves - Work with any SparseTrieInterface implementation The existing optimized methods that calculate actual min_len depths based on revealed nodes are renamed to *_optimized and remain on the SerialSparseTrie specialization for use when maximum efficiency is needed. This allows the engine tree's sparse trie task to generate proof targets regardless of whether it's using SerialSparseTrie or ParallelSparseTrie.

2c1d387

15 hours ago

by gakonst

+0.35%

fix(engine): add const to set_next_sequence for clippy

536859e

14 hours ago

by gakonst

-0.31%

feat(trie): implement generate_proof_targets on ParallelSparseTrie

156421e

14 hours ago

by gakonst

+0.01%

feat(engine): add proof worker handle infrastructure to SparseTrieTask Add infrastructure for SparseTrieTask to dispatch proof requests directly to proof workers: - Add proof_worker_handle field for dispatching proof requests - Add proof_result_rx for receiving proof results - Add with_proof_worker_handle() builder method This prepares for the sparse-trie-as-cache optimization where the sparse trie generates proof targets based on revealed nodes.

b861b13

4 hours ago

by gakonst

Home Terms Privacy Docs