input-output-hk / input-output-hk/Lean-blaster
[performance] SMT emission expands shared expression DAGs exponentially
- Dominant language
- Lean
- Stars
- 57
- Forks
- 11
- Avg merge
- 1d 5h
- Merged PRs (30d)
- 10
Description
SMT terms are shared in memory, but both printing and solver submission traverse them as trees. A chain with one shared node per level therefore emits exponentially more text.
Minimal reproducer on beta `bafdd4f7`:
```lean
import Blaster
open Blaster.Smt
private def chain : Nat → SmtTerm
| 0 => .SmtIdent (.SimpleIdent (.NormalSymbol "x"))
| n + 1 =>
let t := chain n
.AppTerm (.SimpleIdent (.ReservedSymbol "+")) #[t, t]
#eval (toString (chain 16)).utf8ByteSize
#eval (toString (chain 17)).utf8ByteSize
```
The AST has only 17/18 distinct nodes, but query text approximately doubles at each level. This affects large symbolic residuals even when optimizer and translator caches preserve sharing. Existing #138/#160 investigate optimizer retention and context reuse; this issue isolates the later serialization stage.
A local `perf/sharing-blowup` branch already contains an SMT `let`-sharing implementation. Reuse and audit that work for the latest beta, rather than writing another implementation. Scope and symbol collisions, parallel SMT let bindings, annotations/triggers, and recursive function bodies need regression coverage. Validate solver outcomes with sharing enabled and disabled, and measure bytes, submission time and total time on a generated large Blaster example.
Contributor guide
No contributing guide indexed for this repository
Research direction
Reproduce the chain example on beta bafdd4f7, then inspect the SMT printing and solver-submission paths. Start from the local perf/sharing-blowup branch and audit it against the latest beta, including scope collisions, parallel bindings, annotations or triggers, and recursive function bodies. Done means regression coverage, matching solver outcomes with sharing enabled and disabled, and measurements of bytes, submission time, and total time on a large generated Blaster example.
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
- Active
- Clarity
- Mostly clear
- Newbie friendliness
- 50/100