BTreeMap feature flag for zk-EVMs

[eyusufatik]

From RiscZero's docs.

In ZkVm's BTreeMap's are preferred over HashMap's due to their better performance in guest codes.

A lot of projects that need ZK-proving EVM or even Ethereum blocks choose rust-based ZkEVM's for their developer friendly and efficient workflows. And most of these projects end up leveraging this repository.

On our tests for Citrea, we've found out a cycle count (less cycle counts -> cheaper, faster proofs) improvement of 3% can be achieved if the state related structs are modified to use BTreeMap instead of HashMap. The patch we used for this benchmark for revm be found here. The changes are based on v45 as Citrea currently depends on v45.

The proposed change is to create a feature flag that swaps out HashMaps for BTreeMap wherever it is applicable, so that zk-EVM projects gets above mentioned benefits.

If accepted, I would like to start working on this right away.

Also, just to mention I've ran the benches on v45, and BTreeMap patch beats the original HashMap version:

HashMap
Running benches/bench.rs (target/release/deps/bench-c6929c4e35c9133e)
Gnuplot not found, using plotters backend
snailtracer/transact/analysed
                        time:   [29.467 ms 29.599 ms 29.746 ms]
                        change: [+3.9863% +4.3265% +4.6922%] (p = 0.00 < 0.05)
                        Performance has regressed.
Found 1 outliers among 10 measurements (10.00%)
  1 (10.00%) high mild
snailtracer/eval        time:   [23.807 ms 23.904 ms 23.960 ms]
                        change: [-0.4023% +0.0638% +0.4897%] (p = 0.79 > 0.05)
                        No change in performance detected.

BTreeMap
 Running benches/bench.rs (target/release/deps/bench-c6929c4e35c9133e)
Gnuplot not found, using plotters backend
snailtracer/transact/analysed
                        time:   [28.172 ms 28.346 ms 28.475 ms]
                        change: [-4.8741% -4.3060% -3.7821%] (p = 0.00 < 0.05)
                        Performance has improved.
snailtracer/eval        time:   [23.548 ms 23.566 ms 23.608 ms]
                        change: [-1.3233% -0.8740% -0.3800%] (p = 0.00 < 0.05)
                        Change within noise threshold.
Found 2 outliers among 10 measurements (20.00%)
  2 (20.00%) high mild


HashMap
  Running benches/bench.rs (target/release/deps/bench-c6929c4e35c9133e)
Gnuplot not found, using plotters backend
analysis/transact/raw   time:   [8.0241 µs 8.0373 µs 8.0569 µs]
analysis/transact/analysed
                        time:   [3.8433 µs 3.8549 µs 3.8726 µs]

BTreeMap
Running benches/bench.rs (target/release/deps/bench-c6929c4e35c9133e)
Gnuplot not found, using plotters backend
analysis/transact/raw   time:   [7.2875 µs 7.2984 µs 7.3130 µs]
                        change: [-9.3535% -9.0410% -8.7581%] (p = 0.00 < 0.05)
                        Performance has improved.
Found 1 outliers among 10 measurements (10.00%)
  1 (10.00%) low mild
analysis/transact/analysed
                        time:   [3.1368 µs 3.1489 µs 3.1631 µs]
                        change: [-18.702% -18.271% -17.832%] (p = 0.00 < 0.05)
                        Performance has improved.


HashMap
Running benches/bench.rs (target/release/deps/bench-c6929c4e35c9133e)
Gnuplot not found, using plotters backend
transfer/transact/analysed
                        time:   [1.2679 µs 1.2708 µs 1.2741 µs]
Found 12 outliers among 100 measurements (12.00%)
  1 (1.00%) low mild
  6 (6.00%) high mild
  5 (5.00%) high severe

BTreeMap
 Running benches/bench.rs (target/release/deps/bench-c6929c4e35c9133e)
Gnuplot not found, using plotters backend
transfer/transact/analysed
                        time:   [1.1541 µs 1.1576 µs 1.1608 µs]
                        change: [-9.2685% -8.9859% -8.6621%] (p = 0.00 < 0.05)
                        Performance has improved.
Found 3 outliers among 100 measurements (3.00%)
  1 (1.00%) high mild
  2 (2.00%) high seve

Again, if not opposed I can run benches on the latest code to see if BTreeMap's still performing better, if so, we can forget about feature-gating and just use BTreeMaps.

[rakita]

Interesting, did you try different Hashers for HashMap? This can be enabled with alloy features (not sure when it is added, maybe it is not inside v45).

I woundn't mind adding feature flag for btreemap switch it is small diff but it is a small change

[eyusufatik]

Just realized there is more HashMap's to replace with BTreeMap's. Going to compare cycle counts again.

Looks like a seperate zkvm feature is the way to go.

Also the feature can go directly to alloy-primitives where HashMap is pulled from in this repo. But I fear that might break a lot of things all of a sudden given alloy's usage in many different repositories 🤔

[eyusufatik]

Just realized there is more HashMap's to replace with BTreeMap's. Going to compare cycle counts again.

Looks like a seperate zkvm feature is the way to go.

Also the feature can go directly to alloy-primitives where HashMap is pulled from in this repo. But I fear that might break a lot of things all of a sudden given alloy's usage in many different repositories 🤔

This brings the total reduction to %3.4.

I still want to benchmark map-hashbrown feature of alloy, however, there is rust version issues with alloy and reth so can't benchmark that yet. will also benchmark that once risc0 rust 1.83 support is out, if the btreemap flag is still feasible I'll open a PR.

[rakita]

if the btreemap flag is still feasible I'll open a PR.

Gotcha, woudn't mind if you made a pr.

But be aware if reth crates are used, they probably use alloy hashmap not one from revm.

[eyusufatik]

if the btreemap flag is still feasible I'll open a PR.

Gotcha, woudn't mind if you made a pr.

But be aware if reth crates are used, they probably use alloy hashmap not one from revm.

Yeah that might be problematic. We'll see 👍