0xMiden / 0xMiden/miden-vm

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

Đang mở
#2,319 0 bình luận 1 reaction 0 người được giao Xem trên GitHub
corelib
Ngôn ngữ chính
Rust
Star
772
Fork
352
Merge trung bình
1 ngày 12 giờ
Pull request đã merge (30 ngày)
93

Mô tả

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.

Hướng dẫn đóng góp

Mở hướng dẫn đóng góp

Đánh giá

Issue này chưa được đánh giá.

Nhận issue mới trong hộp thư của bạn

Bản tóm tắt ngắn những issue GitHub phù hợp với người mới.