0xMiden / 0xMiden/miden-vm

Improve performance of stdlib's `smt::set` with multiple pairs

Abierto
#2,319 0 comentarios 1 reacción 0 asignados Ver en GitHub
corelib
Lenguaje dominante
Rust
Estrellas
772
Forks
352
Merge medio
1 d 12 h
PR fusionados (30 d)
93

Descripción

https://github.com/0xMiden/miden-vm/pull/2248 landed initial support for updating multi-leaves in Smt trees but performance can be improved.

Right now, when a key-pair is inserted or removed from a list of key-pairs in a leaf, a new buffer is created by copying the existing key-pairs (with an element added or removed). This allows us to compute a hash of the leaf, but also update the `advice_map` (which is required for smt::get to work).

This solution might be acceptable because it's easy to understand what's going on (auditability), and in majority of the cases leaves will be small. However, a few potential improvements have been identified:
* Small optimizations in the existing procedure. We can likely remove one or two local variables that maybe are not strictly necessary.
* Improve average-case scenario and splice arrays in place. Rather than copying the entire leaf buffer, shift the suffix left or right by one element. This introduces a bit of code duplication: if we insert and need to shift elements right, we need to memcpy from the end. Code for this already exists: https://github.com/reilabs/miden-vm/commits/gs/multileaf-set-splice/
* Further improve speed by not doing any memory copying at all. This would require a new instruction to update advice_map (something like adv.append_mem: advice_map[K] <- advice_map[K] . mem[a..b]). This would also drastically simplify the code: https://github.com/reilabs/miden-vm/commit/1005446828032e5c6cbda61e4e5a9d406ebb8b01

Let's discuss which solution makes sense before creating a PR to address this.

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.