Dependent integer division rounds, 2026-09-10

This is an arithmetic microbenchmark, not a proposed secure delay function. It compares exact division algorithms for identical dependent state updates on M4, Graviton5 and the Hetzner EPYC Genoa guest. Every round mixes the quotient into the next round's numerators and divisors. There is one worker. Parallel divisions within one round do not constitute independent chains.

Results

Median nanoseconds per dependent round, three repetitions; lower is better. Each cell uses the fastest implementation measured on that machine for the specified identical round.

SVE32 improves Graviton's own native scalar implementation by 1.34×, but after optimizing x86 unsigned vector conversions, Graviton and Hetzner differ by only 1.2% in this test. M4 remains roughly 2× faster at the identical four-division round. SVE64 is slower than Graviton's own scalar implementation here; the corrected floating estimate is its fastest measured 64-bit variant. For bit permutations, Graviton beats this M4 software implementation by 4.7–5.5×, while Hetzner's scalar BMI2 implementation beats Graviton by 1.8–2.5×. None of these experiments establishes a unique Graviton latency advantage.

Full medians/ranges and rates are in summary.json. Most final Graviton timings varied less than 0.1%; Hetzner scalar64 ranged from 8.45 to 9.97 ns and M4 scalar64 from 4.32 to 4.52 ns. Do not overinterpret small platform differences. All implementations and all machines produced identical final states for their corresponding 30-million-round division and five-million-round bit permutation cases, and every source/binary hash in the run metadata matches the retained artifact.

Assembly confirms udiv z*.d / udiv z*.s, bext, bdep, and bgrp on Graviton, and DIVQ/DIVL, vector floating division, PEXT/PDEP/POPCNT on Hetzner. Optimizing the x86 four-lane unsigned integer↔double conversions improved that exploratory path from about 14.95 to 9.90 ns, and final median was 9.84 ns. The original compiler expansion therefore would have exaggerated the Graviton advantage.

Work per round

• *64: two unsigned 64-bit divisions, two 64-bit state lanes. Each divisor is 65536 plus the low 16 bits of the other lane. The two quotient values are added, rotated 17 bits, XORed into each original lane, multiplied by an odd constant, and incremented by the other divisor.
• *32: four unsigned 32-bit divisions, four state lanes. Each divisor is 256 plus the next lane's low eight bits. Each quotient is added to the next lane's quotient, rotated 11 bits, XORed into the original lane, multiplied by an odd constant and incremented by the next divisor.

All arithmetic state updates wrap at their stated width. Divisors change every round and are always nonzero. Numerators span their full width; quotients are not engineered to be almost always zero or one. The divisor ranges are intentionally specified: performance and competing algorithms can change with other operand distributions. The two widths are different algorithms and their round rates should not be directly compared as equal work.

Implementations and optimization

• scalar: native integer division in scalar registers, allowing the CPU to overlap divisions within a round.
• fp: scalar-source conversion to double and division; the compiler may vectorize it. For 64-bit inputs, an estimated quotient is corrected using the signed residual of wrapping integer multiply/subtract. The divisor restriction bounds the floating error well below one quotient unit, so one correction suffices. For 32-bit inputs, double precision already returns an exact truncated quotient over this range.
• vector: explicitly grouped double precision division. Hetzner uses AVX-512 unsigned conversion intrinsics to avoid the inefficient expansion of GCC's portable vector conversion. Other platforms use portable compiler vector types. The actual generated instructions are preserved in assembly files; in particular GCC on Arm scalarizes some nominal vector operations.
• float32: four single precision quotients, followed by an integer residual correction per lane. The chosen input/divisor ranges bound the combined conversion and division rounding error to at most one quotient unit. This tests a faster exact alternative to missing vector integer division on x86.
• sve: actual SVE unsigned integer vector division on Graviton. Uses exactly two 64-bit or four 32-bit active lanes, so work matches the other implementations independently of architectural vector length.

No fast-math options are used. The residual method assumes ordinary IEEE binary floating point and the tested compilers' two's-complement conversion of wrapping unsigned differences to signed integers. These benchmark-specific arguments are not a proof for unrestricted integer division algorithms or an adversarial delay construction.

Reproduction and validation

bench.c is standalone C. run.py contains an independent Python integer reference; every implementation's 10,000-round state must match it before timing. Final runs use three repetitions of 30 million dependent rounds per implementation. Equal-width, equal-count outputs are compared across all implementations and all machines. Timing includes loop overhead, lane mixing and arithmetic, with two clock reads per complete run. It excludes compilation and process launch.

Local: cc -O3 -mcpu=apple-m4 -std=c11 bench.c -o bench-local, then python3 run.py m4 bench-local none neon check and python3 run.py m4 bench-local none neon final.

Hetzner: GCC 13.3, cc -O3 -march=native -std=c11 bench.c -o bench; use python3 run.py hetzner bench 3 native check and final. The single benchmark worker is pinned to guest CPU 3. The host's physical SMT placement and other tenants are not visible.

Graviton: existing Debian toolchain container, GCC 12.2, cc -O3 -march=armv9-a+sve2 -mtune=neoverse-n2 -std=c11 bench.c -o bench. GCC 12 does not recognize Neoverse V3, so the nearest available N2 scheduling model is used while SVE operations are explicit. Binary runs natively on the parent instance, pinned to CPU 15. This is not an enclave measurement.

Production services and enclave are left running. Final timing is coordinated with the other benchmark agents to stop their builds and measurements. M4 has no hard core pinning; macOS and unrelated system activity remain uncontrolled. Results are observations on these machines, not a guarantee of the fastest possible implementation, frequency-normalized microarchitecture comparison, or a security bound.

Source, raw timing output, assembly, compiler logs, binary hashes and an artifact manifest are retained here. Named Graviton build containers are preserved stopped, without changing production configuration.

Optional bit permutation diagnostic

bitperm.c and run-bitperm.py test two 64-bit lanes with changing masks, one dependent round at a time. One variant extracts selected bits and deposits them at a rotated mask (two extracts and two deposits per round). The other groups selected bits below unselected bits (two groups per round). Masks always contain at least one set and one clear bit. Both variants then add the other state lane, rotate, XOR and multiply before the next round.

Graviton uses SVE2 BEXT/BDEP/BGRP, Hetzner uses scalar BMI2 PEXT/PDEP (two PEXT plus POPCNT per group), and all machines also run a portable six-stage broadword bit compression/expansion implementation. The M4 comparison is this software implementation, not proof that no better M4 implementation exists. Python bit-by-bit reference checks validate 1,000 rounds before measurement. Final runs use three repetitions of five million rounds; matching final states are checked across machines and implementations. The division and bit permutation rates describe different work and must not be combined as interchangeable hashes.

Independent review of floating-quotient correctness: another review agent checked bench.c without running competing workloads and found no correctness issue under the stated domains. For 64-bit division, input-conversion error is at most 1024, giving at most 1/64 quotient error at divisor 65536; binary64 division contributes a similarly small rounding term. For float32 and divisor at least 257, the bound is 128/257 + 0.5 < 1; divisor 256 is exact binary scaling and separately safe. Consequently one residual correction is sufficient. Python reference checks and long-run final-state agreement supply empirical cross-checks, rather than replacing this domain argument.

Bit permutation reproduction: use the same native M4/Hetzner compiler commands with bitperm.c; Graviton requires -march=armv9-a+sve2-bitperm -mtune=neoverse-n2. Run python3 run-bitperm.py HOST BINARY CPU KIND check then final, where KIND is software, bmi2, or sve. The original reference used Python 3.10 int.bit_count; after discovering the Graviton host uses an older Python, the retained harness uses the equivalent portable bin(x).count('1'). The failed compatibility attempt is preserved in the logs; successful checks and finals are in graviton-final2.log.