Bypass long division for reduced small-modulus additions

perfloop/uint256 · INEFFICIENT ALGORITHM

https://perfloop.ai/t/oss/case_bt6k1ex9sr

Verdict

VERIFIED · settled 2026-08-24

Hypothesis

The source shows that AddMod's inline conditional-subtraction route is gated by m[3] != 0, while smaller moduli go through AddOverflow and then Mod. For a nonzero reduced sum that is at least m and wider than uint64, Mod reaches udivrem/udivremKnuth; the division's word-length work is avoidable when both inputs are already strictly below m. The relevant size dimension is modulus limb width: the missed route covers 1-, 2-, and 3-word moduli below 2^192, whereas the existing inline route only covers a nonzero fourth word.

I ran the checked-in BenchmarkAddMod sweep: reduced-or-equal operand samples took 11.09 ns/op for mod64, 23.04 for mod128, 25.90 for mod192, and 8.277 for mod256 on this runner. I then ran a deleted scratch guard prototype, not a source patch: 30,000 randomized comparisons against the current AddMod, including z aliasing x, y, and m, passed. On the same benchmark shape its guarded route measured 11.51->7.208 ns/op (mod64), 23.15->6.726 (mod128), and 26.62->6.646 (mod192). This measures the candidate's reduced-operand path rather than production frequency or an integrated implementation. The established cadence is one AddMod call per inner benchmark iteration, with x carried from the previous modular result and y selected from the <=m sample set; no production cadence is traced and the supplied hotness prior is low.

The removed delta on the trigger is the AddOverflow-to-Mod fallback chain and, when the reduced sum crosses m, its quotient/remainder division; the replacement is fixed four-limb add/subtract work. A case session should integrate the guard and run an independent big.Int differential/fuzz test across m=0, m=1, limb boundaries around 2^64/2^128/2^192, carry-producing high moduli, and every result alias. It should rerun a reduced-versus-unreduced operand and modulus-width sweep, checking for lower ns/op and reduced CPU attribution to Mod/udivrem for the reduced m<2^192 cells, while showing no regression for fallback cells.

Change to test: Before the existing m>=2^192 route, add a m!=0 && x<m && y<m route that computes the four-limb sum and one carry-aware conditional subtraction. Keep the current near-reduced large-modulus route and division-backed fallback for operands that fail the reduced guard, including all existing alias semantics.

Where it lives

perfloop/uint256 · uint256.go

Evidence

AddMod exact reduced sum / 128-bit modulus · 10 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 10.73 6.276 −42.1% (−4.511) −5.662 to −3.832 < −0.5363 PASSED
B/op 0 0 0 0 to 0 ≤ 0 PASSED
allocs/op 0 0 0 0 to 0 ≤ 0 PASSED

AddMod exact reduced sum / 192-bit modulus · 10 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 9.811 6.069 −38.9% (−3.812) −4.163 to −3.631 < −0.4905 PASSED
B/op 0 0 0 0 to 0 ≤ 0 PASSED
allocs/op 0 0 0 0 to 0 ≤ 0 PASSED

AddMod operands at the modulus / 128-bit modulus · 10 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 9.045 8.282 −9.1% (−0.823) −0.896 to −0.487 ≤ 0.4522 PASSED
B/op 0 0 0 0 to 0 ≤ 0 PASSED
allocs/op 0 0 0 0 to 0 ≤ 0 PASSED

AddMod operands at the modulus / 192-bit modulus · 10 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 8.85 8.058 −8.5% (−0.7515) −2.144 to −0.56 ≤ 0.4425 PASSED
B/op 0 0 0 0 to 0 ≤ 0 PASSED
allocs/op 0 0 0 0 to 0 ≤ 0 PASSED

Checks: 5 of 5 passed. Verification: no defect found.

Timeline