0xPolygonZero / zk_evm

Apache License 2.0
77 stars 32 forks source link

perf(continuations): Do not propagate touched addresses set to 0 #441

Closed hratoanina closed 3 weeks ago

hratoanina commented 1 month ago

Right now, we propagate to MemAfter all touched memory adresses (except pruned contexts). However, since uninitialized addresses are set to 0 by default (except for preinitialized segments), we can omit 0-value addresses from MemAfter. This would probably require one or two Memory columns, but would remove many rows from MemAfter and MemBefore.

Nashtare commented 1 month ago

We're actually at 28 columns already for Memory (I had forgotten the several ones added from context pruning), so we can afford to add 2. Given that we can actually allow up to 4 new columns before the next permutation, we may as well consider pre-initializing additional segments (if need be).

hratoanina commented 1 month ago

It's actually trickier than expected. On the branch https://github.com/0xPolygonZero/zk_evm/commits/no_zero_value_propagation/ there's a partial version which uses 32 columns total, and removes zero values only if context and segment are non-zero, which means that it's missing non-preinitialized segments in context 0. Including them would either require to go over 32 columns or come up with some clever constraints I haven't found yet. If the gains are enough as is I don't think we should bother.

Nashtare commented 1 month ago

As discussed on slack, it seems an approach on a segment basis may be more beneficial, according to initial benchmarks, as most of the overhead (outside of the Code and TrieData segments which can't be ignored) is coming from 3 segments including RlpRaw, whose filtering even in context 0 would bring benefits.