0xMiden / 0xMiden/miden-vm

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

オープン
#2,319 コメント 0 件 リアクション 1 件 担当者 0 名 GitHub で見る
corelib
主要言語
Rust
スター
772
フォーク
352
平均マージ
1日 12時間
マージ済み PR(30日)
93

説明

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.

コントリビューションガイド

コントリビューションガイドを開く

評価

この issue はまだ評価されていません。

新しい issue をメールで受け取る

初心者向けの GitHub issue を短くまとめたダイジェスト。