Lean Kernel Arena / perf/loop-unfolded-once

Test "perf/loop-unfolded-once"

Expected: 👍 accept · Size: 4.1 MB · Lines: 84.7 k · lean4export: 3.1.0 · Lean: 4.36.0 · Timeout: 40.0 s · 📄 Declaration · 🔗 Source

The declaration to check compares

allInK 0 N (fun i => g w i)
decide (Nat.allTR (N - 0) (fun k _ => (fun i => g w i) (0 + k)) = true)

with N = 1000000 and g, w variables, where allInK lo hi p := Nat.allTR (hi - lo) fun k _ => p (lo + k).

Unfolding allInK once gives the Nat.allTR term on the right, and decide (b = true) reduces to b through instDecidableEqBool, for Θ(1). A checker that unfolds Nat.allTR and its tail-recursive loop instead lays out the && of N tests stuck on g, for Θ(N) time and nesting depth.

Official (v4.36.0) needs 0.3 s here. Distilled from AxiomMath/CFSG's CFSG.Sporadic.HNSchreier.Native.Kernel.orbitTreeCheck_certificate, where a change leaves the same comparison over 1140000 points.

Checker Result ⏱️ 🧠
nano-lean 👍 37.8 ms (÷14) 182.5 MB (+79%)
gruszka 👍 44.2 ms (÷12) 86.6 MB (-15%)
sokonanoda 👍 45.3 ms (÷12) 145.8 MB (+43%)
rpylean 👍 59.6 ms (÷8.8) 62.4 MB (-39%)
pestka 👍 99.9 ms (÷5.2) 74.0 MB (-27%)
kefir 👍 140 ms (÷3.7) 20.9 MB (÷4.9)
palladium 👍 95.1 ms (÷5.5) 63.0 MB (-38%)
con-ron 👍 348 ms (-34%) 93.4 MB (-8%)
kefir-wasm 👍 758 ms (+45%) 125.3 MB (+23%)
con-agua 👍 424 ms (-19%) 51.2 MB (-50%)
nanobruijn 👍 270 ms (-49%) 33.5 MB (÷3.0)
nanoda 👍 218 ms (÷2.4) 11.6 MB (÷8.8)
con-leche 👍 360 ms (-31%) 40.0 MB (÷2.5)
pestka-wasm 👍 635 ms (+21%) 567.2 MB (×5.6)
tenet-jvm 👍 1.92 s (×3.7) 198.0 MB (+94%)
official-nightly 👍 464 ms (-12%) 109.3 MB (+7%)
eink0rn ⌛ — —
official 👍 524 ms 101.9 MB
ind-models 👍 868 ms (+65%) 135.5 MB (+33%)
tenet 👍 851 ms (+62%) 181.7 MB (+78%)
tenet-hs 👍 406 ms (-22%) 83.1 MB (-18%)
kiota 👍 293 ms (-44%) 61.2 MB (-40%)
ocaml4lean 👍 380 ms (-28%) 47.0 MB (÷2.2)
logos-kernel ⌛ — —
evmlean 🚫 307 ms 104.9 MB
mini 🚫 250 ms 71.8 MB
overfull ⌛ — —
lean4cobol ✋ 1.78 s 21.6 MB
lean4lean ✋ 279 ms 93.5 MB
canonical-min ✋ 640 ms 1.0 GB
nanoclo 👍 138 ms (÷3.8) 111.5 MB (+9%)
vow-lean-kernel 🚫 65.8 s 54.4 MB
lazylean 👍 187 ms (÷2.8) 30.0 MB (÷3.4)
metalean-slow 🚫 228 ms 68.1 MB
metalean-fast 👍 1.00 s (+91%) 108.8 MB (+7%)
nanoclo-fortran 👍 329 ms (-37%) 28.7 MB (÷3.5)
mathgraph 👍 56.5 ms (÷9.3) 133.2 MB (+31%)