0xMiden / 0xMiden/protocol

AggLayer: further optimize frontier loading

Abierto
#2,857 0 comentarios 0 reacciones 0 asignados Ver en GitHub
agglayer
Lenguaje dominante
Rust
Estrellas
132
Forks
167
Merge medio
1 d 23 h
PR fusionados (30 d)
110

Descripción

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.

Guía de contribución

Abrir la guía de contribución

Evaluación

Este issue todavía no se ha evaluado.

Recibe los nuevos issues en tu correo

Un resumen breve de issues de GitHub para principiantes.