Lean Kernel Arena / perf/gf3-matrix-product

Test "perf/gf3-matrix-product"

Expected: 👍 accept · Size: 781.8 KB · Lines: 15.0 k · lean4export: 3.1.0 · Lean: 4.36.0 · Timeout: 70.0 s · 📄 Declaration · 🔗 Source

The declaration to check is

Nat.beq (fp 4) 361572011084151223 = true

proved by decide +kernel, where fp m multiplies 781×781 matrices over GF(3) along a fixed word of length m and reduces the product modulo 2^61 - 1. A matrix is a pair of bit-sliced Nat literals of 609 961 bits (the entries equal to 1 and those equal to 2), and one product runs 781 steps of shifting, masking, multiplying and xoring numbers of that size. The 14 input matrices are generated from Nat.pow b 32000 inside the file, so the test has no data.

This is a scaled-down copy of a real proof: the theorem ck97 of AxiomMath/CFSG's Certificates.Kernel.Sporadic.Fi24Seven.C06, which checks one chunk of a straight-line program over such matrices with CFSG's own mul3s and prodV (copied unchanged). ck97 has 86 products; this test has 3.

It measures big-Nat arithmetic and what the reduction caches keep. Every product's intermediates are big literals that a checker's whnf caches hold until the declaration ends, so memory grows by about 1 GiB per product: the official kernel (v4.35.0) needs about 17 G instructions and 3.5 GiB here, and ck97 itself about 87 GiB. A checker that hashes big literals by their low 64 bits only (lean4#15686) or keeps more intermediates than needed shows it here.

Checker Result ⏱️ 🧠
nano-lean 👍 835 ms (÷2.2) 3.6 GB (+2%)
gruszka 👍 2.44 s (+34%) 230.3 MB (÷16)
sokonanoda 👍 3.22 s (+77%) 3.7 GB (+4%)
rpylean 👍 3.49 s (+92%) 786.7 MB (÷4.6)
pestka 👍 1.39 s (-23%) 712.2 MB (÷5.1)
kefir 👍 3.58 s (+97%) 58.7 MB (÷62)
palladium 👍 1.53 s (-16%) 6.2 GB (+75%)
con-ron 👍 8.33 s (×4.6) 3.6 GB (+2%)
kefir-wasm 👍 9.21 s (×5.1) 173.1 MB (÷21)
con-agua 👍 3.99 s (×2.2) 3.5 GB (-1%)
nanobruijn 👍 2.92 s (+60%) 3.2 GB (-11%)
nanoda 👍 2.89 s (+59%) 3.2 GB (-11%)
con-leche 👍 2.12 s (+16%) 3.5 GB (-2%)
pestka-wasm ⌛ — —
tenet-jvm 👍 9.94 s (×5.5) 5.0 GB (+40%)
official-nightly 👍 2.35 s (+29%) 3.6 GB (0%)
eink0rn 🚫 15.8 s 8.1 GB
official 👍 1.82 s 3.5 GB
ind-models 👍 1.94 s (+7%) 3.6 GB (0%)
tenet 👍 13.6 s (×7.5) 3.6 GB (0%)
tenet-hs 👍 1.38 s (-24%) 3.0 GB (-16%)
kiota 👍 2.89 s (+59%) 4.0 GB (+13%)
ocaml4lean 👍 28.5 s (×16) 9.4 GB (×2.6)
logos-kernel 💥 12.3 s 13.9 GB
evmlean 🚫 305 ms 105.2 MB
mini 🚫 79.9 ms 68.0 MB
overfull ⌛ — —
lean4cobol ✋ 448 ms 15.1 MB
lean4lean ✋ 90.5 ms 87.7 MB
canonical-min ✋ 435 ms 1.0 GB
nanoclo 👍 3.13 s (+72%) 3.7 GB (+5%)
vow-lean-kernel ⌛ — —
lazylean 👍 4.08 s (×2.2) 3.1 GB (-12%)
metalean-slow 🚫 105 ms 66.4 MB
metalean-fast 👍 3.42 s (+88%) 3.5 GB (0%)
nanoclo-fortran 👍 1.78 min (×59) 7.0 GB (+98%)
mathgraph 👍 2.61 s (+44%) 3.8 GB (+6%)