Comparing heap allocators for zkEVM
ZisK exposes four allocators as Cargo features in the ziskos entrypoint. Other allocators exist in the codebase but they are disabled.
For evaluating the options I used the ZisK emulator ziskemu, which runs guest execution (without generating a proof) and accumulates AIR-cost. The cost derived from the execution trace translates to the proving complexity. While we ultimately care about proving time, using the emulator to measure AIR-costs is more practical.
Allocator options
All allocators can be selected via Cargo feature:
bump (default): The simplest possible allocator. Keeps a pointer to the next free byte and advances it on each allocation. Memory is never reclaimed.
dlmalloc (explainer): Each allocated block carries a small header with its size and a flag. When a block is freed, dlmalloc adds it to the free list and checks neighbors. If adjacent blocks are also free, it merges them into a larger block so future allocations can reuse the space.
talc: Similar mechanism to dlmalloc with merging of adjacent free blocks, but organizes free blocks into buckets.
tlsf (explainer): Instead of searching a list, it uses a two-level bitmap to jump directly to a free block of the right size. Amortized O(1) alloc/free.
How are the costs calculated
ZisK is a collection of specialised modules much like a modern CPU. Each module (state machine) has its own execution trace. Every instruction the guest executes fills rows in one or more traces. The emulator sequentially executes each instruction, looks up per-op cost constants, and accumulates into buckets:
MAIN: Cost of processing, proportional to the number of instructions executed. Every instruction contributes one row here regardless of what it does. This is the baseline before any operation-specific overhead.OPCODES: Additional rows for the operation itself, on top of MAIN. These cover simple operations (add, sub, mul, shifts, bitwise). For example, a multiplication fills MAIN with one row and OPCODES with the multiplication cost.PRECOMPILES: Specialised circuits for operations too expensive to express as RISC-V sequences. An example for precompiles is a hash function call.MEMORY: Additional rows for memory reads and writes, including extra overhead for non-aligned accesses.BASE: Fixed overhead independent of the guest program. For example the overhead needed for lookup tables.
Total cost = MAIN + OPCODES + PRECOMPILES + MEMORY + BASE. Per-op costs are defined in zisk_ops_costs.rs. The current memory limit is set to 512MB in mem.rs.
50 Mainnet blocks
The first setting where I evaluated the allocator is on the mainnet blocks 24949787 - 24949836, by using zkevm-benchmark-workload to run the ZisK v0.16.1. I used the locally compiled ethrex stateless client from commit b112f94.
| Mainnet cost: ethrex b112f94 ZisK v0.16.1 | bump | dlmalloc | talc | tlsf |
|---|---|---|---|---|
Min gas block 14M: block 24949797 |
24.71B | 26.27B | 26.52B | 27.53B |
Max gas block 56M: block 24949791 |
77.71B | 83.18B | 83.86B | 87.24B |
| Average over all blocks | 45.44B | 48.61B | 49.02B | 51.06B |
In all cases it holds: bump < dlmalloc < talc < tlsf. I wanted to check min and max gas block to see if there is noticeable difference in the costs, but it does not seem to be the case. The delta for bump and dlmalloc is consistent across the three rows (6%, 6.5%, 6.5%). We can also take a look at the distribution of the costs across the state machines.
As expected BASE and PRECOMPILES are identical across all allocators. The largest difference is in the MAIN costs (+9% to 16%). No matter if the allocator performs comparison or traversal to evaluate the free space, each of these steps adds complexity to the MAIN state machine. The difference on MEMORY is less significant (+5% to 8%). The allocators store some additional data in form of a header or metadata but this overhead is relatively small. The measurements in a table format can be viewed in the last section of the blog.
EEST Fixtures
The current mainnet (Fusaka) block gas limit is 60M. The next Glamsterdam fork raises it to 200M. How does this affect zkEVMs? Keep in mind that, average case performance matters less than worst-case. A single “prover killer” block that crashes on memory or exceeds the 12s block time is enough to halt proof generation.
I used fixtures generated using the EEST benchmark suite for 100M gas limit. To parse the generated tests for the zkevm-benchmark-workload I used witness-generator-cli. The exact commands are listed in the last section.
100M fixtures
In these EEST tests the bump allocator still performs the best however, we see the first OOM, which is a problem. The tests like ADD and MULMOD, which do not make many allocations, unsurprisingly, do not show much difference in the total cost. But other tests like SSTORE or SLOAD show more variety.
Aside from that, we can also measure the memory usage. Or more precisely the highest address touched from the PR1141 on ZisK. In this measurement keccak_max_permutation OOMs, and there are other tests like modexp and sha256 that also allocate a lot. This suggests that for higher gas limits they might also fail.
The memory usage across dlmalloc, talc, and tlsf is similar. Since memory is cleared between blocks, the choice between these three should come down to AIR-cost performance rather than memory footprint.
Allocator comparison
Across almost all of the tests we are seeing bump < dlmalloc < talc < tlsf in terms of the AIR-costs. The profiling data also show the costs of the function calls. The average for the above 100M EEST tests is the following:
| Compare allocator function calls | bump | dlmalloc | talc | tlsf |
|---|---|---|---|---|
| alloc | too small, not recorded | 1.32% | 1.89% | 2.37% |
| free | 0% | 0.85% | 1.13% | 1.83% |
Bump does the least work resulting in lowest costs. After that dlmalloc is the second candidate. On native hardware, talc and tlsf can win through cache locality or fast bit operations. These advantages do not translate from standard computation to zkVM.
Without getting into too many allocator details, let’s look into tests with higher gas where the memory limits are a bigger problem. The following tests take long to compute, so I will compare just dlmalloc and bump.
200M fixtures
As expected the tests mentioned above (modexp, sha256) fail for the 200M gas limit. It is possible to avoid the OOM by increasing the memory limit for the bump allocator on a fork of ZisK. This prevents the crashes and is even more efficient on the modexp test.
However, these results cover only a small subset of 200M tests. Running all of the 200M tests is just too heavy to do locally. It is very possible that there exist some tests which fail even for the 1.5GB memory limit with bump allocator.
Below we compare the memory usage, where dlmalloc is consistently lower, making it safer for potential future L1 inclusion.
Conclusion
The trivial bump allocator performs better on AIR cost in almost all cases, however from just the few tests tried there are OOMs and more can be seen at zkevm-benchmark-runs. From the measured cases the most viable option seems to use dlmalloc.
Notes
Useful commands
Building ELF file
docker run --rm \
-v "$PWD":/ere-guests \
-v "$PWD/output":/output \
-v "<path to ethrex>":/ethrex \
-v "<path to zisk>":/zisk \
"ghcr.io/eth-act/ere/ere-compiler-zisk:0.12.1" \
--compiler-kind rust-customized \
--guest-dir /ere-guests/bin/stateless-validator-ethrex/zisk \
--output-dir /output \
--elf-name stateless-validator-ethrex-zisk.elf
Generating EEST fixtures
uv run fill \
--gas-benchmark-values <gas limit> --fork Prague \
--output <output name> --clean -n auto \
-k "<test name>" \
tests/benchmark/compute
Converting EEST fixtures to inputs:
EF_TEST_TRIE=default cargo run --release -p witness-generator-cli -- \
-o <output file> \
tests --eest-fixtures-path <input files>
Running ziskemu
RUST_LOG=info RAYON_NUM_THREADS=2 cargo run --release -p ere-hosts \
-- --zisk-profile --zkvms zisk --bin-path <path to ere-guests>/output \
stateless-validator --execution-client ethrex \
--input-folder <path to generated inputs>
Data tables
| Cost distribution mainnet: ethrex b112f94 ZisK v0.16.1 | bump | dlmalloc | talc | tlsf |
|---|---|---|---|---|
MAIN |
27.0B | 29.5B | 29.7B | 31.3B |
PRECOMPILES |
7.8B | 7.8B | 7.8B | 7.8B |
OPCODES |
6.8B | 7.2B | 7.5B | 8.0B |
MEMORY |
3.5B | 3.8B | 3.7B | 3.7B |
BASE |
293.6M | 293.6M | 293.6M | 293.6M |
| Cost by allocator (100M): ethrex 81484be ZisK v0.16.1 | bump | dlmalloc | talc | tlsf |
|---|---|---|---|---|
| arithmetic[opcode_ADD-benchmark] | 157.82B | 157.83B | 157.83B | 157.84B |
| arithmetic[opcode_MULMOD-benchmark] | 116.54B | 116.55B | 116.55B | 116.56B |
| ecrecover[ecrecover-benchmark] | 78.36B | 80.22B | 80.74B | 82.55B |
| keccak_max_permutations[benchmark] | OOM | 470.79B | 470.88B | 470.90B |
| modexp[mod_1024_exp_2-benchmark] | 577.20B | 588.51B | 592.20B | 594.76B |
| sha256[benchmark] | 41.44B | 41.45B | 41.50B | 41.55B |
| storage_access_cold_benchmark[SLOAD-benchmark] | 34.12B | 37.81B | 39.20B | 43.656 |
| storage_access_cold_benchmark[SSTORE_new-benchmark] | 420.88B | 430.70B | 435.47B | 443.26B |
| storage_access_warm_benchmark[SLOAD-benchmark] | 90.140B | 90.12B | 90.13B | 90.19B |
| MEM usage by allocator (100M): ethrex 81484be ZisK v0.16.1 | bump | dlmalloc | talc | tlsf |
|---|---|---|---|---|
| arithmetic[opcode_ADD-benchmark] | 0.48% | 0.46% | 0.45% | 0.45% |
| arithmetic[opcode_MULMOD-benchmark] | 0.48% | 0.46% | 0.45% | 0.45% |
| ecrecover[ecrecover-benchmark] | 1.73% | 0.46% | 0.45% | 0.45% |
| keccak_max_permutations[benchmark] | 100% | 0.49% | 0.45% | 0.50% |
| modexp[mod_1024_exp_2-benchmark] | 91.09% | 0.46% | 0.45% | 0.45% |
| sha256[benchmark] | 50.49% | 0.55% | 0.53% | 0.53% |
| storage_access_cold_benchmark[SLOAD-benchmark] | 7.83% | 3.51% | 3.19% | 3.65% |
| storage_access_cold_benchmark[SSTORE_new-benchmark] | 0.49% | 0.47% | 0.46% | 0.46% |
| storage_access_warm_benchmark[SLOAD-benchmark] | 0.56% | 0.46% | 0.45% | 0.45% |
| Cost by allocator (200M): ethrex 81484be ZisK v0.16.1 | bump 512MB Mem | bump 1536MB Mem | dlmalloc |
|---|---|---|---|
| mod_arithmetic[opcode_MULMOD-mod_bits_191-benchmark] | 2.375T | 2.375T | 2.375T |
| ecrecover[ecrecover-benchmark] | 156.34B | 156.36B | 160.06B |
| keccak_max_permutations[benchmark] | OOM | 945.27B | 941.48B |
| mcopy[fixed_src_dst_True-copy_size_0-mem_size_1048576-benchmark] | 335.36B | 335.36B | 335.37B |
| test_modexp[mod_1024_exp_2-benchmark] | OOM | 1.15T | 1.17T |
| sha256[benchmark] | OOM | 82.37B | 82.40B |
| Absolute MEM usage by allocator (200M): ethrex 81484be ZisK v0.16.1 | bump MEM 1536MB (B) | dlmalloc (B) |
|---|---|---|
| mod_arithmetic[opcode_MULMOD-mod_bits_191-benchmark] | 2,547,923 | 2,424,832 |
| ecrecover[ecrecover-benchmark] | 15,836,691 | 2,424,832 |
| keccak_max_permutations[benchmark] | 1,067,406,171 | 2,818,048 |
| mcopy[fixed_src_dst_True-copy_size_0-mem_size_1048576-benchmark] | 4,123,571 | 4,128,768 |
| test_modexp[mod_1024_exp_2-benchmark] | 967,632,603 | 2,424,832 |
| sha256[benchmark] | 535,117,379 | 3,080,192 |