mediocregopher/extension-hashes - Branch - paradigmxyz/reth

perf(trie): store extension node hashes

#21104

Comparing

mediocregopher/extension-hashes

(

412ab7e

) with

main

(

a74cb9c

)

Untouched: 118

Skipped: 7

Benchmarks

Skipped (7)

Passed

collect_twice[100]

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

+6%

87.9 µs83.3 µs

size 100000 | updated 0.1% | depth 2

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

+4%

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

+4%

3.7 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

+4%

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

+3%

1.1 ms1.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

+1%

8.4 ms8.3 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

+1%

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

+1%

2.5 ms2.4 ms

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

Legacy[dataset_128/targets_512]

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

+1%

1,001.7 µs993.8 µs

V2[dataset_1024/targets_2048]

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

+1%

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

V2[dataset_1024/targets_512]

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

+1%

11 ms10.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

collect_twice[1000]

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

+1%

725.7 µs722.1 µ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.6 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 ms132 ms

Legacy[dataset_1024/targets_16]

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

10.7 ms10.7 ms

V2[dataset_1024/targets_16]

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

10.6 ms10.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

validate_blob | num blobs: 2 | ValidateBlob

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

149.7 µs149.4 µ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

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_128/targets_512]

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

837.5 µs836.3 µs

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

V2[dataset_1024/targets_1]

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

10.5 ms10.5 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

Legacy[dataset_1024/targets_64]

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

11.4 ms11.4 ms

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

80.2 ms80.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

V2[dataset_128/targets_128]

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

738.5 µs738.1 µs

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

receipts root | size: 10 | HashBuilder

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

111.7 µs111.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.2 µ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.8 µs

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

collect_twice[50000]

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

42.6 ms42.6 ms

Legacy[dataset_128/targets_1]

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

704.6 µs704.4 µs

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

validate_blob | num blobs: 6 | ValidateBlob

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

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

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

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

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

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

3.9 µs3.9 µs

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

sequence hashing[100]

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

256.8 ms256.9 ms

parallel hashing[100]

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

256.9 ms256.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

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

recover ECDSA

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

206.6 µs206.7 µs

validate_blob | num blobs: 1 | ValidateBlob

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

146.8 µs146.8 µs

sparse trie[1000]

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

5.7 ms5.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

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

fold_reduce[10000]

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

12.1 ms12.1 ms

receipts root | size: 100 | HashBuilder

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

936.7 µs937.1 µs

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

Legacy[dataset_1024/targets_128]

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

12.2 ms12.2 ms

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

Legacy[dataset_10240/targets_2048]

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

868.9 ms869.3 ms

V2[dataset_10240/targets_2048]

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

639 ms639.3 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 10]

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

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

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

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

5.9 ms5.9 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.7 ms12.7 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

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

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

V2[dataset_10240/targets_128]

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

636.4 ms637.2 ms

Legacy[dataset_10240/targets_128]

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

652.4 ms653.2 ms

hash builder[1000]

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

4.5 ms4.5 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

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

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

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

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

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

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

sparse trie[5000]

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

28.3 ms28.3 ms

V2[dataset_10240/targets_1]

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

635.7 ms636.9 ms

Legacy[dataset_10240/targets_1]

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

635.5 ms636.7 ms

Legacy[dataset_10240/targets_512]

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

701.8 ms703.2 ms

V2[dataset_10240/targets_512]

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

637.4 ms638.7 ms

Legacy[dataset_128/targets_64]

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

806.7 µs808.4 µs

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.8 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_16]

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

636.1 ms637.8 ms

Legacy[dataset_10240/targets_16]

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

637.4 ms639.2 ms

Legacy[dataset_1024/targets_512]

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

15.4 ms15.4 ms

V2[dataset_128/targets_64]

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

731.2 µs733.5 µ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.4 ms

Legacy[dataset_10240/targets_64]

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

644 ms646.1 ms

V2[dataset_10240/targets_64]

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

636.2 ms638.3 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

Legacy[dataset_128/targets_128]

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

855 µs858.2 µs

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

27.4 ms27.5 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

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.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.6 ms24.7 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.8 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.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.8 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_16]

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

-1%

695.8 µs699.9 µs

size 100000 | updated 1% | depth 4

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

-1%

11.4 ms11.5 ms

Legacy[dataset_128/targets_16]

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

-1%

733.1 µs738.9 µs

V2[dataset_128/targets_2048]

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

-1%

1.1 ms1.2 ms

Legacy[dataset_128/targets_2048]

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

-2%

1.2 ms1.2 ms

fold_reduce[100]

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

-3%

156.6 µs161 µs

fold_reduce[50000]

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

-3%

71.3 ms73.5 ms

Commits

Click on a commit to change the comparison range

Base

main

a74cb9c

-0.05%

perf(trie): store extension node hashes Add opt-in support for storing extension node hashes in parent branch nodes' hash_mask. This reduces database lookups during proof generation by avoiding the need to traverse through extension nodes to find the underlying branch hash. The feature is controlled via the `with_store_extension_node_hashes` builder method on `SerialSparseTrie`. Changes: - Add `store_extension_node_hashes` field to `SerialSparseTrie` - Add `with_store_extension_node_hashes` builder method - Add `is_extension` method to `SparseNodeType` - Update hash mask computation in `rlp_node` to include extension node hashes when the feature is enabled - Add test for the new functionality Closes #17922

8faf9f9

15 hours ago

by gakonst

+0.11%

perf(trie): always store extension node hashes Remove configurable flag - extension node hashes are now always stored in parent branch nodes' hash_mask. This reduces database lookups during proof generation. Updated test to allow sparse trie to have more hash_mask bits than HashBuilder (since HB doesn't store extension hashes yet).

64e2647

14 hours ago

by gakonst

+0.02%

perf(trie): implement extension hash storage on ParallelSparseTrie Address review comment: extension node hashes are now stored in parent branch nodes' hash_mask for both SerialSparseTrie and ParallelSparseTrie. Changes: - Update rlp_node hash_mask logic to include extension nodes that should be stored in db - Update assert_with_hash_builder to allow sparse trie to have MORE hash_mask bits than HashBuilder (for extension node hashes) - Update test_mainnet_block_24185431 to expect extension hash at child 1 Note: The alloy-trie branch (alexey/always-store-branch-nodes) is stale and uses old nybbles. This functionality was implemented directly in reth's sparse tries without depending on alloy-trie changes.

0b59681

5 hours ago

by gakonst

fix: add backticks to doc comment for clippy

412ab7e

5 hours ago

by gakonst

Home Terms Privacy Docs