U256 Acceleration Benchmarking

Measures the performance gain of ZisK hardware-accelerated U256 arithmetic over the pure-Rust ruint implementation, across a stratified grid of input sizes.

---

What is measured

Operations

Twelve U256 binary operations are benchmarked, covering addition, subtraction, and multiplication variants as well as division and remainder:

Group	Operations
Overflowing	overflowing_add, overflowing_sub, overflowing_mul
Checked	checked_add, checked_sub, checked_mul, checked_div
Saturating	saturating_add, saturating_sub, saturating_mul
Wrapping	wrapping_div, wrapping_rem

Each operation is compiled into two ELF binaries targeting the ZisK zkVM (riscv64ima-zisk-zkvm-elf):

• ruint variant — uses ruint::Uint<256, 4> from the Rust standard library crate.
• accel variant — calls the corresponding extern "C" hardware-accelerated function (overflowing_add256_c, checked_sub256_c, etc.) provided by the ZisK runtime.

Metrics

The ZisK emulator (ziskemu) reports two cost metrics per execution:

• steps — total RISC-V instruction count. A pure count of work; not sensitive to the specific cost model assigned to each instruction.
• total — weighted cost sum. Reflects the prover's actual workload: different instruction types carry different weights according to the ZisK cost model.

Both are captured for every benchmark run.

Acceleration ratio

The ratio reported for each (operation, input) pair is:

acceleration = marginal_ruint / marginal_accel

where the marginal cost isolates the per-iteration contribution by subtracting the fixed startup overhead:

marginal = metric(N iterations) − metric(1 iteration)

Running at N = 100 000 iterations makes the per-operation signal large relative to the startup noise (~295 M total / ~21 k steps), so even cheap operations like addition can be measured accurately. A ratio of 1.0 means no acceleration; higher is better.

---

Measurement methodology

Loop structure and black_box

Each benchmark binary runs the target operation in a loop:

for _ in 0..ITERATIONS {
    let a_bb = core::hint::black_box(a);
    let b_bb = core::hint::black_box(b);
    let res  = core::hint::black_box(op(a_bb, b_bb));
}

core::hint::black_box is an optimization barrier that survives LTO. It forces the compiler to rematerialize the inputs on every iteration, preventing the loop from being collapsed into a single call or eliminated as dead code. See ITERATION_STRATEGY.md for a detailed rationale and the problems with alternative approaches.

Measurement bias for cheap operations. Each black_box call costs ~8 instructions (stack store + load for a [u64; 4]); the two calls per iteration add ~16 instructions of fixed overhead. Because this overhead is additive, it does not cancel in the ratio:

ratio_measured = (ruint_op + overhead) / (accel_op + overhead)  ≠  ruint_op / accel_op

The overhead pulls the ratio toward 1. For mul/div/rem — where both variants cost hundreds of instructions — 16 instructions is negligible. For add/sub — where the ruint path may cost only 10–20 instructions — the bias can halve the apparent ratio. The reported acceleration ratios for add/sub operations should be interpreted as lower bounds on the true hardware gain.

Input distribution

U256 spans roughly 78 decimal orders of magnitude. With a uniform draw from [0, 2^256), the probability of a value having bit-length exactly k is 2^(k−1) / 2^256, so ~50% of draws have 256 bits, ~75% have at least 255, and a 32-bit value appears roughly once per 2^224 draws. Uniform sampling would overwhelmingly produce full 256-bit values (all four 64-bit limbs populated), giving essentially no coverage of small operands. Instead the generator samples bit-lengths uniformly (log-uniform / bit-length-uniform distribution): a k-bit value is drawn from [2^(k−1), 2^k − 1] with k chosen uniformly from {1, 32, 64, 96, 128, 160, 192, 224, 256}.

Rather than pure random draws, a stratified grid is used: every (a_bits, b_bits) cell in the 9×9 Cartesian product gets one or more independent samples. This guarantees coverage of the full 2-D input space and makes it possible to plot acceleration as a heatmap indexed by operand size. See gen-inputs/src/main.rs for the full rationale.

---

Repository layout

gen-inputs/             Rust binary — generates the stratified grid of .bin input files
bench-common/           Shared library — reads inputs, exposes ITERATIONS constant
bench-<op>/             One Rust binary per operation (12 total)
collect-data.py         Runs ziskemu for all ops × inputs, writes acceleration.csv
visualize.py            Reads acceleration.csv, writes boxplot + per-op heatmaps
run-stats.sh            Thin wrapper around ziskemu -X that outputs JSON {steps, total}
linearity-check/        Sanity check — verifies cost grows linearly with iteration count
data/                   Output directory for acceleration.csv
inputs/grid/            Output directory for generated .bin input files
output/                 Staging directory for compiled ELF binaries
images/                 Output directory for generated plots

---

Setup

Python environment

./setup.sh

This creates .venv/ and installs the required packages (numpy, matplotlib). On Debian/Ubuntu, if python3-venv is missing the script will print the exact apt install command needed.

Activate the environment before running Python scripts:

source .venv/bin/activate

Or call the venv interpreter directly without activating:

.venv/bin/python3 collect-data.py
.venv/bin/python3 visualize.py

ZisK toolchain

Building benchmark ELFs requires cargo-zisk and the riscv64ima-zisk-zkvm-elf Rust target. Running them requires ziskemu. Add the ZisK release binaries to PATH:

export PATH="/path/to/zisk/target/release:$PATH"

The path stored in run-stats.sh (ZISK_BIN) points to a local build of the zisk repository; update it if your build lives elsewhere.

---

Workflow

1. Generate input files

cargo run --release -p gen-inputs

Writes inputs/grid/ — one .bin file per (a_bits, b_bits, sample) cell (81 files with the default 9×9 grid and 1 sample per cell). Files are named {a_bits:03}_{b_bits:03}_{sample:02}.bin so their coordinates are encoded in the filename.

To regenerate with a different random seed:

cargo run --release -p gen-inputs -- inputs/grid 1234

2. Collect acceleration data

python3 collect-data.py

For each (operation, input_file) pair this builds four ELF variants (ruint/accel × 1/100 000 iterations), runs them under ziskemu, computes the two-point marginal costs, and appends a row to data/acceleration.csv. Built ELFs are cached in output/; delete a cached ELF to force a rebuild.

The run is resumable: rows already present in the CSV are skipped on restart. Progress and an ETA are printed to stdout.

Options:

-o / --output PATH        Output CSV (default: data/acceleration.csv)
--input-dir PATH          Grid input directory (default: inputs/grid)
--staging-dir PATH        Cached ELF directory (default: output)
--operations A,B,...      Run only a subset of operations
--skip-build              Skip build phase (assume ELFs already staged)

Example — collect data for addition operations only:

python3 collect-data.py --operations bench-overflowing-add,bench-checked-add,bench-saturating-add

3. Visualize results

python3 visualize.py

Reads data/acceleration.csv and writes to images/:

• boxplot.png — two vertically stacked box-plot panels (steps metric / total metric), one box per operation, with median annotated. A dashed red line marks ratio = 1 (no acceleration).
• {op}.png (one per operation) — two side-by-side heatmaps (steps / total), axes are a_bits × b_bits. Each cell is annotated with the mean acceleration ratio for that operand-size combination.

Options:

csv                       Input CSV (default: data/acceleration.csv)
-d / --output-dir DIR     Output directory (default: images)

Example — write plots to a custom directory:

python3 visualize.py data/acceleration.csv -d results/plots

---

Linearity check

Before trusting acceleration ratios, verify that cost actually grows linearly with iteration count (i.e., the two-point method is valid):

./linearity-check/check-linearity.sh

This builds bench-overflowing-mul at five iteration counts (1, 10, 100, 1 000, 10 000) for both variants and fits a line through (iterations, metric). It prints a table of cost/iter values and R² for each variant × metric combination, and exits non-zero if R² < 0.9999 for any series.