AggLayer: further optimize frontier loading
- 主要语言
- Rust
- 星标
- 132
- 派生
- 167
- 平均合并
- 1 天 23 小时
- 30 天内合并 PR
- 110
描述
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.
贡献指南
评估
这个 Issue 还没有评估数据。