Test "perf/identical-nesting"
Expected: 馃憤 accept 路 Size: 8.7鈥疜B 路 Lines: 172 路 lean4export: 3.1.0 路 Lean: 4.34.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 | 鈴憋笍 | 馃 | |||
|---|---|---|---|---|---|---|
| sokonanoda | 馃憤 | 1鈥痬s | (梅40) | 40.0鈥疢B | (-39%) | |
| mathgraph | 馃憤 | 1鈥痬s | (梅40) | 33.7鈥疢B | (-49%) | |
| nanoclo | 馃憤 | 1鈥痬s | (梅38) | 49.7鈥疢B | (-24%) | |
| con-ron | 馃憤 | 23鈥痬s | (-18%) | 58.9鈥疢B | (-10%) | |
| nanobruijn | 馃憤 | 1鈥痬s | (梅34) | 9.0鈥疢B | (梅7.3) | |
| nanoda | 馃憤 | 1鈥痬s | (梅44) | 3.2鈥疢B | (梅21) | |
| lazylean | 馃憤 | 1鈥痬s | (梅24) | 21.5鈥疢B | (梅3.1) | |
| con-leche | 馃憤 | 4鈥痬s | (梅7.2) | 22.0鈥疢B | (梅3.0) | |
| eink0rn | 馃憤 | 2鈥痬s | (梅18) | 12.8鈥疢B | (梅5.1) | |
| official | 馃憤 | 28鈥痬s | (0%) | 65.7鈥疢B | (0%) | |
| ind-models | 馃憤 | 104鈥痬s | (脳3.7) | 105.1鈥疢B | (+60%) | |
| lean4lean | 馃憤 | 28鈥痬s | (0%) | 97.7鈥疢B | (+49%) | |
| tenet | 馃憤 | 130鈥痬s | (脳4.6) | 44.4鈥疢B | (-32%) | |
| tenet-hs | 馃憤 | 1鈥痬s | (梅20) | 9.5鈥疢B | (梅6.9) | |
| lean4cobol | 馃憤 | 5鈥痬s | (梅5.2) | 13.5鈥疢B | (梅4.9) | |
| evmlean | 馃憤 | 1.7鈥痵 | (脳59) | 254.6鈥疢B | (脳3.9) | |
| mini | 馃憤 | 38鈥痬s | (+36%) | 74.1鈥疢B | (+13%) | |
| overfull | 馃憤 | 21.0鈥痵 | (脳744) | 46.9鈥疢B | (-29%) | |
| metalean-slow | 馃憤 | 32鈥痬s | (+12%) | 71.6鈥疢B | (+9%) | |
| tenet-jvm | 馃憤 | 106鈥痬s | (脳3.7) | 64.9鈥疢B | (-1%) | |
| nanoclo-fortran | 馃憤 | 1鈥痬s | (梅24) | 4.5鈥疢B | (梅15) | |
| kiota | 馃憤 | 1鈥痬s | (梅38) | 7.1鈥疢B | (梅9.3) | |
| metalean-fast | 馃憤 | 31鈥痬s | (+8%) | 73.6鈥疢B | (+12%) | |
| canonical-min | 馃毇 | 387鈥痬s | 1.1鈥疓B | |||
| rpylean | 馃憤 | 1鈥痬s | (梅49) | 4.4鈥疢B | (梅15) | |
| vow-lean-kernel | 馃憤 | 96鈥痬s | (脳3.4) | 8.6鈥疢B | (梅7.7) | |
| parse-only | 馃憤 | 28鈥痬s | (-1%) | 66.1鈥疢B | (+1%) |