Test "perf/identical-nesting"
Expected: 馃憤 accept 路 Size: 8.7鈥疜B 路 Lines: 172 路 lean4export: 3.1.0 路 Lean: 4.29.1 路 馃搫 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 | (梅42) | 33.7鈥疢B | (-47%) | |
| ind-models | 馃憤 | 62鈥痬s | (脳2.2) | 103.5鈥疢B | (+64%) | |
| official-nightly | 馃憤 | 28鈥痬s | (+1%) | 65.3鈥疢B | (+3%) | |
| evmlean | 馃憤 | 1.1鈥痵 | (脳41) | 131.2鈥疢B | (脳2.1) | |
| nanoda | 馃憤 | 1鈥痬s | (梅44) | 3.0鈥疢B | (梅21) | |
| mini | 馃憤 | 38鈥痬s | (+37%) | 74.5鈥疢B | (+18%) | |
| lean4lean | 馃憤 | 28鈥痬s | (0%) | 93.3鈥疢B | (+48%) | |
| sokonanoda | 馃憤 | 1鈥痬s | (梅42) | 33.6鈥疢B | (-47%) | |
| zignodamus | 馃憤 | 1鈥痬s | (梅52) | 4.6鈥疢B | (梅14) | |
| nanoclo | 馃憤 | 1鈥痬s | (梅31) | 43.5鈥疢B | (-31%) | |
| nanobruijn | 馃憤 | 1鈥痬s | (梅29) | 9.9鈥疢B | (梅6.4) | |
| kiota | 馃憤 | 1鈥痬s | (梅32) | 6.7鈥疢B | (梅9.4) | |
| official | 馃憤 | 28鈥痬s | (0%) | 63.1鈥疢B | (0%) | |
| vow-lean-kernel | 馃憤 | 97鈥痬s | (脳3.4) | 8.0鈥疢B | (梅7.9) | |
| rpylean | 馃憤 | 1鈥痬s | (梅40) | 8.1鈥疢B | (梅7.8) | |
| official-v4.28.0 | 馃憤 | 35鈥痬s | (+24%) | 72.9鈥疢B | (+16%) | |
| still-nanoda | 馃憤 | 1鈥痬s | (梅45) | 3.1鈥疢B | (梅21) | |
| nyaya | 馃憤 | 3鈥痬s | (梅11) | 9.9鈥疢B | (梅6.4) | |
| parse-only | 馃憤 | 27鈥痬s | (-2%) | 60.5鈥疢B | (-4%) |