0xMiden / 0xMiden/protocol

AggLayer: further optimize frontier loading

Đang mở
#2,857 0 bình luận 0 reaction 0 người được giao Xem trên GitHub
agglayer
Ngôn ngữ chính
Rust
Star
132
Fork
167
Merge trung bình
1 ngày 23 giờ
Pull request đã merge (30 ngày)
110

Mô tả

As described in [this commit](https://github.com/0xMiden/protocol/pull/2752/changes/13f0d9068458616c730c5f2f484794a445b53b00#diff-3181b2b0e91167fbd1aafc4c9c2f97deac70118c873e35feac4a849ed27003e4R442-R455), 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.

Hướng dẫn đóng góp

Mở hướng dẫn đóng góp

Đánh giá

Issue này chưa được đánh giá.

Nhận issue mới trong hộp thư của bạn

Bản tóm tắt ngắn những issue GitHub phù hợp với người mới.