Skip to content

Return sorted data from compute_trie_input #19249

New issue
New issue
Open
#19340
Open
Return sorted data from compute_trie_input#19249
#19340
Assignees
yongkangc
Labels
A-engineRelated to the engine implementationC-perfA change motivated by improving speed, memory usage or disk footprint
@mediocregopher

Description

@mediocregopher
mediocregopher
opened on Oct 23, 2025

Describe the feature

compute_trie_input is used to compute the in-memory overlay which will be passed to the MultiProofTask so that proof computation can take into account in-memory blocks which haven't been persisted to the database yet.

reth/crates/engine/tree/src/tree/payload_validator.rs

Lines 999 to 1006 in 4548209

fn compute_trie_input<TP: DBProvider + BlockNumReader + TrieReader>(
&self,
persisting_kind: PersistingKind,
provider: TP,
parent_hash: B256,
state: &EngineApiTreeState<N>,
allocated_trie_input: Option<TrieInput>,
) -> ProviderResult<TrieInput> {

compute_trie_input returns a TrieInput which contains HashedPostState and TrieUpdates, both unsorted data structures.

reth/crates/trie/common/src/input.rs

Lines 5 to 15 in 4548209

pub struct TrieInput {
/// The collection of cached in-memory intermediate trie nodes that
/// can be reused for computation.
pub nodes: TrieUpdates,
/// The in-memory overlay hashed state.
pub state: HashedPostState,
/// The collection of prefix sets for the computation. Since the prefix sets _always_
/// invalidate the in-memory nodes, not all keys from `self.state` might be present here,
/// if we have cached nodes for them.
pub prefix_sets: TriePrefixSetsMut,
}

The TrieInput then gets converted into a MultiProofConfig, which is almost exactly the same but uses HashedPostStateSorted and TrieUpdatesSorted.

reth/crates/engine/tree/src/tree/payload_processor/multiproof.rs

Lines 66 to 78 in 4548209

/// Common configuration for multi proof tasks
#[derive(Debug, Clone)]
pub(super) struct MultiProofConfig {
/// The sorted collection of cached in-memory intermediate trie nodes that
/// can be reused for computation.
pub nodes_sorted: Arc<TrieUpdatesSorted>,
/// The sorted in-memory overlay hashed state.
pub state_sorted: Arc<HashedPostStateSorted>,
/// The collection of prefix sets for the computation. Since the prefix sets _always_
/// invalidate the in-memory nodes, not all keys from `state_sorted` might be present here,
/// if we have cached nodes for them.
pub prefix_sets: Arc<TriePrefixSetsMut>,
}

This conversion uses a few milliseconds per block:

Image

We should introduce a TrieInputSorted which contains the sorted forms of the fields, and which can therefore be converted into a MultiProofConfig for free. This type should be returned from compute_trie_input.

Ideally we would want to eliminate all places in the hot path where we are converting to/from the sorted trie input data. This will mean modifying ExecutedBlock to hold HashedPostStateSorted and TrieUpdatesSorted as well, and possibly other unforeseen changes.

Additional context

No response

Metadata

Metadata

Assignees

Labels

A-engineRelated to the engine implementationC-perfA change motivated by improving speed, memory usage or disk footprint

Type

No type

Projects

Reth Tracker

Status

Backlog

Milestone

No milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions