0xMiden / 0xMiden/protocol

AggLayer: further optimize frontier loading

未关闭
#2,857 0 条评论 0 个 reaction 已指派 0 人 在 GitHub 查看
agglayer
主要语言
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 还没有评估数据。

把新 issue 发到你的邮箱

精选适合新手参与的 GitHub issue 摘要。