Derived `DecidableEq` instance is not inlined
Nobody has claimed this yet.
- Dominant language
- Lean
- Stars
- 9.2k
- Forks
- 990
- Avg merge
- 1d 17h
- Merged PRs (30d)
- 175
Description
Prerequisites
Please put an X between the brackets as you perform the following steps:
- Check that your issue is not already filed:
https://github.com/leanprover/lean4/issues - Reduce the issue to a minimal, self-contained, reproducible test case.
Avoid dependencies to Mathlib or Batteries. - Test your test case against the latest nightly release, for example on
https://live.lean-lang.org/#project=lean-nightly
(You can also use the settings there to switch to “Lean nightly”)
Description
In the following example, the function f is measurably slower than f':
inductive Node where
| done
| epsilon (next : Nat)
| split (next₁ : Nat) (next₂ : Nat)
deriving DecidableEq
@[inline, always_inline]
def Node.isDone (n : Node) : Bool :=
match n with
| .done => true
| _ => false
set_option trace.Compiler.result true
def f (n : Node) : Nat :=
-- This comparison was not inlined
if n = .done then
42
else
1
def f' (n : Node) : Nat :=
-- This version seems faster in my actual example
if n.isDone then
42
else
1
Context
As reported on Zulip: #lean4 > Suboptimal codegen when comparing against a constant
Steps to Reproduce
Here is the above turned into a benchmark (adapted from the first comment below to prevent Lean from reusing the Node storage for the IO result):
import Lean.Meta.Basic
inductive Node where
| done
| char (c : Char) (next : Nat)
deriving DecidableEq
@[inline, always_inline]
def Node.isDone (n : Node) : Bool :=
match n with
| .done => true
| _ => false
@[noinline]
def f (n : Node) : Nat :=
-- This comparison was not inlined
if n = .done then
42
else
1
def fIO (n : Node) : IO Nat :=
return f n
def n := 100000000
def loopF : IO Unit := do
for _ in [0:n] do
discard <| fIO <| .char 'a' 0
@[noinline]
def f' (n : Node) : Nat :=
-- This version seems faster in my actual example
if n.isDone then
42
else
1
def f'IO (n : Node) : IO Nat :=
return f' n
def loopF' : IO Unit := do
for _ in [0:n] do
discard <| f'IO <| .char 'a' 0
def main : IO Unit := do
for _ in [0:5] do
timeit "f" loopF
timeit "f'" loopF'
Expected behavior: f and f' are both equally fast in all situations.
Actual behavior: On my machine, I get timing like this for compiled code:
f 1.36s
f' 1.21s
f 1.36s
f' 1.17s
f 1.34s
f' 1.2s
f 1.37s
f' 1.21s
f 1.38s
f' 1.22s
Versions
nightly-2025-08-07 on Linux
Impact
Add 👍 to issues you consider important. If others are impacted by this issue, please ask them to add 👍 to it.
Contributor guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Start with the minimal Node benchmark in the issue and enable trace.Compiler.result to compare generated code for f and f'. Investigate why the derived DecidableEq comparison is not inlined; done means compiled f and f' have equivalent performance in the reported cases.
Written by the indexing model from the issue text.
Assessment
- Domain
- compilers, performance
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 35/100