Lean Kernel Arena / perf/short-circuit-and

Test "perf/short-circuit-and"

Expected: 👍 accept · Size: 3.8 MB · Lines: 77.5 k · lean4export: 3.1.0 · Lean: 4.36.0 · Timeout: 3.67 min · 📄 Declaration · 🔗 Source

The declarations to check compare

false && eqA 600 (unpack 600 11 p) (unpack 600 11 q)      and      false && Nat.beq p q

(and two variants: the sides swapped, and the conjunction nested in a second one as in the CFSG goal), where p and q are variables, unpack n w p reads n points of w bits out of p, and eqA compares two arrays point by point.

&& is a match on its first argument, so unfolding it reduces both sides to false, for Θ(1). A checker that compares the arguments of the shared head first compares the open second arguments instead, which are not definitionally equal: it reduces points Nat.land (Nat.shiftRight p (w * i)) m by peeling the shift bit by bit down to the free p, for Θ((n·w)²), and only then unfolds &&. Unlike in discarded-argument, the head discards its second argument only because the first is false, and the arguments are open terms that can neither be evaluated nor quickly told apart.

Official (v4.36.0) needs about 14 s and 1.6 GB here. Distilled from AxiomMath/CFSG's CertificateChecks.Batch27581.p2, where the same shape over 1755 points of 11 bits takes it 441 s, and sokonanoda and Gruszka past 8 GB.

Checker Result ⏱️ 🧠
nano-lean 👍 40.1 ms (÷436) 185.3 MB (÷8.4)
gruszka 👍 44.5 ms (÷394) 93.0 MB (÷17)
sokonanoda 👍 2.63 s (÷6.7) 1.4 GB (-7%)
rpylean 👍 54.7 ms (÷320) 59.4 MB (÷26)
pestka 👍 3.06 s (÷5.7) 277.8 MB (÷5.6)
kefir 👍 132 ms (÷132) 22.4 MB (÷69)
palladium 👍 5.84 s (÷3.0) 2.4 GB (+56%)
con-ron 👍 9.90 s (-43%) 1.6 GB (+8%)
kefir-wasm 👍 746 ms (÷23) 125.4 MB (÷12)
con-agua 👍 13.1 s (-25%) 2.0 GB (+31%)
nanobruijn 👍 11.5 s (-34%) 1.7 GB (+11%)
nanoda 👍 10.8 s (-38%) 1.8 GB (+16%)
con-leche 👍 12.4 s (-29%) 2.7 GB (+75%)
pestka-wasm 👍 10.5 s (-40%) 1.3 GB (-17%)
tenet-jvm 👍 16.7 s (-4%) 3.8 GB (×2.5)
official-nightly 👍 14.3 s (-18%) 1.6 GB (+7%)
eink0rn 👍 456 ms (÷38) 312.4 MB (÷5.0)
official 👍 17.5 s 1.5 GB
ind-models 👍 17.9 s (+2%) 1.5 GB (+1%)
tenet 👍 36.1 s (×2.1) 6.2 GB (×4.1)
tenet-hs 👍 31.1 s (+78%) 808.6 MB (-48%)
kiota 👍 28.4 s (+62%) 2.5 GB (+67%)
ocaml4lean 👍 32.3 s (+84%) 4.5 GB (×3.0)
logos-kernel 👍 2.95 s (÷5.9) 3.3 GB (×2.2)
evmlean 🚫 306 ms 105.9 MB
mini 🚫 243 ms 71.5 MB
overfull ⌛ — —
lean4cobol ✋ 1.53 s 21.6 MB
lean4lean ✋ 262 ms 94.3 MB
canonical-min ✋ 621 ms 1.0 GB
nanoclo 👍 2.62 s (÷6.7) 1.3 GB (-17%)
vow-lean-kernel 👍 13.0 s (-26%) 39.6 MB (÷39)
lazylean 👍 2.66 s (÷6.6) 275.4 MB (÷5.6)
metalean-slow 🚫 216 ms 65.7 MB
metalean-fast 👍 24.7 s (+41%) 4.0 GB (×2.6)
nanoclo-fortran 👍 6.10 s (÷2.9) 3.6 GB (×2.4)
mathgraph 👍 3.67 s (÷4.8) 2.9 GB (+91%)