input-output-hk / input-output-hk/Lean-blaster

[performance] Constructor choice hoisting creates exponential contexts for independent fields

Open
#238 0 comments 0 reactions 0 assignees View on GitHub
Dominant language
Lean
Stars
57
Forks
11
Avg merge
1d 5h
Merged PRs (30d)
10

Description

## Problem

On the reviewed beta stack at `36c3a15a9fdc9f3237ad376f8d67665e3742d3f8`, independently conditional fields of a constructor are lifted into an outer decision tree. A list of twelve independently chosen bits creates 16,379 optimization contexts and 117,084 hash-cons entries. The input has twelve independent choices and a compact representation with one choice per element.

This is a preparation/normalization growth issue, separate from SMT text expansion in #231. It is a small reproducer relevant to the larger `#prep_uplc` investigation in #138. I checked the open PRs: #160 addresses ancestor cache reuse and retention, not this constructor-distribution policy. #77 contains tests for the propagation rule itself; the concern here is its cost when applied indiscriminately.

## Minimal reproducer

Run this as a native Lake test module importing `Tests.Utils`:

```lean
import Tests.Utils
open Lean Meta Elab Command

run_cmd liftTermElabM do
let e ← Tests.parseTerm (← `(
fun (a b c d e f g h i j k l : Bool) =>
[if a then (1 : Nat) else 0, if b then 1 else 0,
if c then 1 else 0, if d then 1 else 0,
if e then 1 else 0, if f then 1 else 0,
if g then 1 else 0, if h then 1 else 0,
if i then 1 else 0, if j then 1 else 0,
if k then 1 else 0, if l then 1 else 0]))
let (_, env) ← Blaster.Optimize.command default e
IO.println s!"hashcons={env.optEnv.hashConsCache.size} contexts={env.optEnv.options.nextCtxId}"
```

Reducing the example to 4 and 8 binders/elements gives:

| Independent choices | Hash-cons entries | Allocated context counter |
|---:|---:|---:|
| 4 | 2,517 | 75 |
| 8 | 9,375 | 1,027 |
| 12 | 117,084 | 16,379 |

These are deterministic structural counts from Lean 4.24.0 on Apple M2 Max; no solver is invoked. Timing is deliberately omitted from this reproducer.

## Candidate direction and validation requirement

Allow choices to remain inside constructor fields, with reduction driven by the consuming function, or use a cost-aware distribution policy. Simply disabling all constructor hoisting is not a safe default performance recommendation: an isolated prototype makes SellNFT/Governance preparation much cheaper but increases subsequent proof work and slows the CIP-153 global preparation. A fix must check the residual's usability, positive properties, and expected counterexamples in addition to preparation time.

The fixing PR should include `Issue.lean` with `#testOptimize` checks for compact constructor choices and their consumers, plus a bounded structural-growth regression.

Contributor guide

No contributing guide indexed for this repository

Research direction

Start by running the native Lake reproducer importing Tests.Utils and inspect the propagation tests in #77 and the broader #prep_uplc investigation in #138. Add Issue.lean with #testOptimize checks for compact constructor choices and their consumers, plus a bounded structural-growth regression; done also requires checking residual usability, positive properties, and expected counterexamples.

Written by the indexing model from the issue text.

Assessment

Domain
compilers, performance
Issue type
Bug
Difficulty
5/5
Estimated time
Over a week
Activity status
Active
Clarity
Mostly clear
Newbie friendliness
45/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.