Test "perf/identical-nesting"
Expected: 馃憤 accept 路 Size: 8.7鈥疜B 路 Lines: 172 路 lean4export: 3.1.0 路 Lean: 4.29.1 路 Timeout: 50.0鈥痵 路 馃搫 Declaration 路 馃敆 Source
The declaration to check compares
f4 (f4 (... (f4 N.O) ...)) and f4 (f4 (... (f4 N.O) ...))
n applications of f4 on each side, the same term twice, where f0 is the
identity on N and each of f1, f2, f3, f4 applies its predecessor
twice, so the nesting expands into 16n applications of f0.
The test asks whether a checker compares the two sides before it starts unfolding, which answers in 螛(n). Unfolding one side at a time offers 16n applications to choose from per side, and the reachable pairs of partially unfolded sides grow exponentially in n.
N=30 in the Lean source. From Courant and Leroy, POPL 2026, 搂10.
| Checker | Result | 鈴憋笍 | 馃 | |||
|---|---|---|---|---|---|---|
| mathgraph | 馃憤 | 1鈥痬s | (梅40) | 33.6鈥疢B | (-49%) | |
| sokonanoda | 馃憤 | 1鈥痬s | (梅40) | 33.6鈥疢B | (-49%) | |
| nanoclo | 馃憤 | 1鈥痬s | (梅31) | 49.3鈥疢B | (-25%) | |
| con-ron | 馃憤 | 23鈥痬s | (-17%) | 58.7鈥疢B | (-11%) | |
| lazylean | 馃憤 | 1鈥痬s | (梅20) | 21.4鈥疢B | (梅3.1) | |
| nanoda | 馃憤 | 1鈥痬s | (梅43) | 3.0鈥疢B | (梅22) | |
| nanobruijn | 馃憤 | 1鈥痬s | (梅28) | 10.0鈥疢B | (梅6.6) | |
| con-leche | 馃憤 | 4鈥痬s | (梅7.4) | 26.0鈥疢B | (梅2.5) | |
| eink0rn | 馃憤 | 2鈥痬s | (梅16) | 12.0鈥疢B | (梅5.5) | |
| ind-models | 馃憤 | 62鈥痬s | (脳2.2) | 105.9鈥疢B | (+61%) | |
| official | 馃憤 | 28鈥痬s | (0%) | 65.8鈥疢B | (0%) | |
| lean4lean | 馃憤 | 28鈥痬s | (0%) | 96.4鈥疢B | (+46%) | |
| tenet | 馃憤 | 130鈥痬s | (脳4.6) | 44.0鈥疢B | (-33%) | |
| nanoclo-fortran | 馃憤 | 1鈥痬s | (梅23) | 4.6鈥疢B | (梅14) | |
| lean4cobol | 馃憤 | 5鈥痬s | (梅5.2) | 13.7鈥疢B | (梅4.8) | |
| evmlean | 馃憤 | 1.1鈥痵 | (脳41) | 130.8鈥疢B | (+99%) | |
| mini | 馃憤 | 38鈥痬s | (+37%) | 73.9鈥疢B | (+12%) | |
| overfull | 馃憤 | 21.0鈥痵 | (脳749) | 46.4鈥疢B | (-30%) | |
| kiota | 馃憤 | 1鈥痬s | (梅31) | 7.0鈥疢B | (梅9.5) | |
| canonical-min | 馃毇 | 387鈥痬s | 1.1鈥疓B | |||
| rpylean | 馃憤 | 1鈥痬s | (梅49) | 4.5鈥疢B | (梅15) | |
| vow-lean-kernel | 馃憤 | 97鈥痬s | (脳3.5) | 8.2鈥疢B | (梅8.1) | |
| official-v4.28.0 | 馃憤 | 35鈥痬s | (+24%) | 72.8鈥疢B | (+11%) | |
| still-nanoda | 馃憤 | 1鈥痬s | (梅44) | 3.1鈥疢B | (梅21) | |
| nyaya | 馃憤 | 3鈥痬s | (梅11) | 9.5鈥疢B | (梅6.9) | |
| parse-only | 馃憤 | 28鈥痬s | (-1%) | 66.1鈥疢B | (0%) |