perf: bound expression comparisons in the type inference cache (#16046) This PR fixes quadratic elaboration behavior for large string-literal equalities such as `theorem t : s = String.ofList l := rfl`. The type inference cache uses structural expression equality. When a lookup encounters a separately allocated copy of a cached expression, matching hashes are followed by a traversal to establish equality. For large expressions, this traversal can cost substantially more than computing the type. Repeated comparisons of growing intermediate expressions accumulate quadratic work. Matchers and string-literal conversion expose the problem, but the underlying issue is structural equality during cache lookup. Introduce budgeted expression comparisons returning equal, unequal, or exhausted, and a persistent cache storing one candidate per full hash. Locate candidates without structural expression comparison, then validate them using budgeted equality. On exhaustion, evict the candidate and return a cache miss, allowing type inference to compute and cache the result. This preserves inexpensive structural cache hits while avoiding repeated large traversals. Use budget 64 for the `MetaM` type inference cache. Retain the existing WHNF, definitional-equality, unit-like, and kernel caches. The comparison follows the existing recursive equality implementation and accounts for string and metadata payloads; names, universe levels, and natural-number literals retain ordinary equality. Pointer sharing can affect whether a comparison exhausts its budget, so the operation breaks referential transparency and is exposed through `BaseIO`. The following measurements count user-mode instructions for the complete Lean invocation, including declaration generation, elaboration, attribute validation, and kernel checking. Before and after use identical inputs and matching recursion limits, with one Lean worker pinned to the same CPU. The recursion limit is 100,000 at the two smaller sizes and 1,000,000 at the two larger sizes. For `:= rfl`: | String length | Before | After | |---:|---:|---:| | 8,192 | 60,047,586,140 | 45,086,604,920 | | 16,384 | 149,553,658,274 | 88,574,754,680 | | 32,768 | 422,108,821,130 | 176,832,509,126 | | 65,536 | 1,341,360,340,506 | 355,894,892,690 | For `:= (rfl)`: | String length | Before | After | |---:|---:|---:| | 8,192 | 35,435,242,280 | 20,452,849,927 | | 16,384 | 99,980,150,815 | 38,982,426,197 | | 32,768 | 321,950,232,826 | 76,311,678,593 | | 65,536 | 1,138,411,788,117 | 152,127,218,091 | At 65,536 characters, the change reduces instructions for bare `rfl` by 73.5%. Doubling from 32,768 increases instructions 3.18× before and 2.01× after. The removed work grows 4.02× on that doubling, consistent with eliminating the quadratic component over the measured range. Bare `:= rfl` and parenthesized `:= (rfl)` share the same ordinary term-elaboration path: infer `rfl`'s implicit arguments using the expected type, then check the resulting proof's type against that expected type again. Bare `:= rfl` additionally triggers automatic `@[defeq]` inference. Its validator performs another equality check with fresh caches and smart unfolding disabled. Parentheses suppress this automatic attribute. The tactic form `:= by rfl` performs one substantive equality check and constructs an `Eq.refl` proof; it also avoids the automatic attribute. Parentheses alone leave the original cache problem largely intact. The additional attribute-validation cost remains approximately unchanged: 202.9 billion instructions before and 203.8 billion after at 65,536 characters. This PR preserves the existing elaboration and attribute-validation behavior while removing the observed quadratic cache overhead. A complete Mathlib build passes all 8,662 modules, using 96,577,405,692,077 instructions, compared with 96,446,853,181,169 before: +0.135% in one run per configuration. All reported instruction counters have 100% coverage. Regression tests cover budget exhaustion, pointer sharing, binder-sensitive and binder-insensitive equality, metadata payloads, hash collisions, persistent cache snapshots, and scaling with and without matchers. AI assistance: Codex. Closes #15985
This is the repository for Lean 4.
See Install Lean.
Please read our Contribution Guidelines first.
See Building Lean.