0xMiden / 0xMiden/miden-vm

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

未關閉
#2,319 0 則留言 1 個 reaction 已指派 0 人 在 GitHub 檢視
corelib
主要語言
Rust
星號
772
分支
352
平均合併
1 天 12 小時
30 天內合併 PR
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 摘要。