0xMiden / 0xMiden/miden-vm

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

Open
#2,319 0 comments 1 reaction 0 assignees View on GitHub
corelib
Dominant language
Rust
Stars
772
Forks
352
Avg merge
1d 12h
Merged PRs (30d)
93

Description

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.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.