Lean Kernel Arena / perf/ite-taken-branch

Test "perf/ite-taken-branch"

Expected: 👍 accept · Size: 4.3 MB · Lines: 88.9 k · lean4export: 3.1.0 · Lean: 4.36.0 · Timeout: 3.83 min · 📄 Declaration · 🔗 Source

The declarations to check compare

(if true = true then piA else tA)      and      piA

(and two variants: the sides swapped, and a case split on a variable o as in the CFSG proof), where piA := invCand 300 tA is the inverse of a permutation table, computed by a for loop of Array.set!.

Unfolding ite and deciding true = true takes the then branch, and the sides are identical, for Θ(1). But piA is higher than ite, and a checker that unfolds the higher side first evaluates piA, for Θ(n²) list steps, before ite gets its turn. Unlike in unroll-versus-evaluate, the cheap step is on the lower side, it is a Decidable instance rather than a recursion, and the other side is a constant without arguments.

Official (v4.36.0) needs about 14 s and 1.7 GB here, nearly all of it evaluating piA, piB and piC. Distilled from AxiomMath/CFSG's CertificateChecks.Batch27011.optI_eq, where the same shape over 1755 points takes it, sokonanoda, con-ron and con-leche past 8 GB.

Checker Result ⏱️ 🧠
nano-lean 👍 41.1 ms (÷472) 178.9 MB (÷9.5)
gruszka 👍 49.0 ms (÷396) 88.1 MB (÷19)
sokonanoda 👍 2.93 s (÷6.6) 1.5 GB (-9%)
rpylean 👍 64.3 ms (÷302) 62.5 MB (÷27)
pestka 👍 134 ms (÷145) 80.1 MB (÷21)
kefir 👍 4.12 s (÷4.7) 384.2 MB (÷4.4)
palladium 👍 6.35 s (÷3.1) 2.6 GB (+58%)
con-ron 👍 11.6 s (-40%) 1.6 GB (-5%)
kefir-wasm 👍 5.96 s (÷3.3) 627.6 MB (÷2.7)
con-agua 👍 15.7 s (-19%) 2.0 GB (+21%)
nanobruijn 👍 13.6 s (-30%) 1.9 GB (+13%)
nanoda 👍 14.1 s (-27%) 2.0 GB (+18%)
con-leche 👍 14.8 s (-24%) 3.4 GB (×2.0)
pestka-wasm 👍 805 ms (÷24) 623.7 MB (÷2.7)
tenet-jvm 👍 17.9 s (-8%) 4.1 GB (×2.5)
official-nightly 👍 13.6 s (-30%) 1.7 GB (+1%)
eink0rn 👍 20.4 s (+5%) 4.3 GB (×2.6)
official 👍 19.4 s 1.7 GB
ind-models 👍 19.8 s (+2%) 1.7 GB (0%)
tenet 👍 39.1 s (×2.0) 7.4 GB (×4.4)
tenet-hs 👍 52.0 s (×2.7) 1.1 GB (-36%)
kiota 👍 11.9 s (-39%) 1.9 GB (+14%)
ocaml4lean 👍 37.7 s (+94%) 4.7 GB (×2.8)
logos-kernel 👍 2.54 s (÷7.6) 2.7 GB (+64%)
evmlean 🚫 305 ms 106.6 MB
mini 🚫 59.4 ms 66.1 MB
overfull ⌛ — —
lean4cobol ✋ 1.70 s 21.6 MB
lean4lean ✋ 293 ms 92.4 MB
canonical-min ✋ 653 ms 1.0 GB
nanoclo 👍 1.48 s (÷13) 896.2 MB (-47%)
vow-lean-kernel 👍 26.4 s (+36%) 111.3 MB (÷15)
lazylean 👍 7.16 s (÷2.7) 285.5 MB (÷6.0)
metalean-slow 🚫 296 ms 65.7 MB
metalean-fast 👍 33.1 s (+71%) 4.7 GB (×2.8)
nanoclo-fortran 👍 5.74 s (÷3.4) 2.9 GB (+74%)
mathgraph 👍 3.51 s (÷5.5) 2.5 GB (+47%)