Skip to content

AggLayer: further optimize frontier loading #2857

@mmagician

Description

@mmagician

As described in this commit, there is potentially further room to improve the B2AGG note cycle counts:

#! Note, that not all entries that are written to storage will be meaningfully read again.
#! Some frontier heights may be written multiple times before they are read again. For example:
#! for a tree of depth=4, the frontier entry at height=2 will be written with the pattern 0b_X0XX:
#! - num_leaves = 0b_0000 (0),
#! - num_leaves = 0b_0001 (1),
#! - num_leaves = 0b_0010 (2),
#! - num_leaves = 0b_0011 (3),
#! before it's ever read when inserting the 5th leaf (when pre-insert num_leaves = 0b_0100 (4)).
#! Notice that only the last write here is meaningful.
#!
#! This pattern is later repeated for height=2 but when the upper bit is 1:
#! - num_leaves = 0b_1000 (8),
#! - num_leaves = 0b_1001 (9),
#! - num_leaves = 0b_1010 (10),
#! - num_leaves = 0b_1011 (11),
#! before it's read again when inserting the 13th leaf (when pre-insert num_leaves = 0b_1100 (12)).
#!
#! This is a little wasteful, but already better than the previous implementation, which
#! unconditionally saved all frontier entries to storage.
#! TODO: potential room for optimization here? Need to see if this affects root computation

If I'm not mistaken, for a tree depth=32, we only have 1/32 meaningful writes.

One thing to note is that they might not be evenly distributed (TODO confirm this?), which might lead to more variance / unpredictability in cycle counts across different B2AGG notes, although we already have a small degree of variance to due how many reads vs. writes are performed.

Metadata

Metadata

Assignees

No one assigned

    Labels

    agglayerPRs or issues related to AggLayer bridging integration

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions