feat(optimizer): bound call-site inlining growth per expression - #286
Merged
Conversation
A call-site paste pays off when it meets a known-constructor fold and collapses; a product-type monad (State over Tuple) has no tag to test, so its pasted bind/pure bodies survive whole and a long chain grows linearly with no payoff. Whether a paste collapses is unknowable at the paste site — the fold may need other pastes and reductions that happen later in the same sweep — so the sweep itself becomes the speculation: * optimizeExp measures each call-site-inlining sweep against inlineGrowthBudget (a quarter of the input size, floored at smallInlineBudget). A sweep that grew past the allowance — growth without collapse — is discarded, result and change flag both, and redone with the heuristic paste tiers disarmed (DirectedPastesOnly). Explicit @inline directives and the env-reading constructor folds keep firing in the fallback sweep. * The discarded sweep never reports Rewritten, so a converged module still reports Unmodified and the specialize fixpoint terminates; the veto is re-attempted each round against the then-current environment, so a collapse unlocked by a neighbour's settled form still lands. * The dial is calibrated from both sides of the golden corpus: it must reject the transformer stack of LongStackBind (grows past a third of its host when nothing folds) and stay above the transient growth of a multi-round collapse (the Either chain grows just under a fifth before folding a round later; a lower dial freezes it unfolded). See Note [Bounded call-site inlining growth]. The plain State chain of LongStateBind (~10% node growth diluted in a huge host expression) sits below any dial that keeps the Either chain collapsing; catching it needs the measurement at fixpoint convergence rather than per sweep — a follow-up.
Twenty-one goldens move, .ir and .lua only; every eval/golden.txt oracle is untouched and green. LongStackBind sheds the unrolled ExceptT-over-State machinery (1187 → 888 lines, back at its pre-inliner size); TailRecM2Shadow, StringCodePoints, NumberIsNaN, UncurryCtor, the GenericEq pair and six more lose paste residue. Four goldens grow by a few lines where a vetoed expression now keeps its workers shared instead of pasted (CprResult +9, LongApplyChain +11, CSE and DerivedFunctor +3). Zero-line movers carry only the binder renumbering that the discarded speculative sweeps shift.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Closes #221.
Problem
Every call-site paste is a bet. It pays off when the pasted method body meets a known-constructor fold and collapses; it loses when nothing folds. A product-type monad is the losing case by construction:
Statethreads a single-constructorTuple, no tag test exists, and the pastedbind/purebodies survive whole at every step of the chain. The residual growth measured on the corpus wasLongStateBind+275 andLongStackBind+285 lines against their pre-#180 baselines. A check at the paste site cannot decide the bet, as the issue lays out: the fold that would collapse a paste often needs several other pastes and reductions first, so the outcome only exists after the sweep has run.Approach
The sweep itself becomes the speculation.
optimizeExpruns the rewrite with all paste tiers armed, then comparesexpSizebefore and after againstinlineGrowthBudget: a quarter of the input size, floored atsmallInlineBudget. A sweep that stayed within the allowance is kept, since either the collapse happened or the growth is bounded. A sweep that grew past it is growth without collapse: its result and its change flag are both discarded, and the sweep is redone with the heuristic paste tiers disarmed (DirectedPastesOnly, threaded toinlineSaturatedCallandresolveDictionaryProp). Explicit@inlinedirectives keep firing in the fallback sweep (a directive is the user overriding the heuristics), and so do the env-reading constructor folds, which only shrink.The veto lives inside
optimizeExp, so it covers every path that pastes: the per-binding sweeps, recursive-group members, exports (where the whole program concentrates in application mode), and the final re-sweep. The discarded sweep never reportsRewritten, so a converged module still reportsUnmodified, the specialize fixpoint terminates, and the checked runner's contract holds. The baseline resets each round, which keeps the veto non-sticky: an expression vetoed in round N is re-attempted in round N+1 against the then-current environment.Calibration
The dial is pinned from both sides of the golden corpus. It must reject the chains where every paste survives: the
ExceptT-over-Statestack ofLongStackBindgrows past a third of its host. And it must stay above the transient growth of a collapse that spans fixpoint rounds: theEitherchain ofLongEitherBindfirst grows when its binds paste and only folds a round later, once the environment carries its settled neighbours. Probing the dial showed that chain freezing at its unfolded worst (59 → 698 lines) anywhere at or below 16.7%, with its measured transient growth sitting between 16.7% and 20%: a quarter clears it with margin and still catches the transformer stack. Note [Bounded call-site inlining growth] records the mechanism, the dial rationale, and the contracts.Results
Twenty-one goldens move,
.irand.luaonly; everyeval/golden.txtoracle is untouched and green.LongStackBindsheds the unrolled transformer machinery: 1187 → 888 lines, back at its pre-inliner 902-line baseline.TailRecM2Shadowdrops 162 → 139, andStringCodePoints,NumberIsNaN,UncurryCtor, the two GenericEq goldens and six more lose paste residue. Four goldens grow by a few lines where a vetoed expression now keeps its workers shared instead of pasted (CprResult+9,LongApplyChain+11,CSEandDerivedFunctor+3 each). The zero-line movers carry only binder renumbering: a discarded speculative sweep still consumes name-supply freshness, which shifts the numbering downstream.The plain
Statechain ofLongStateBindstays as it is. Its growth is ~10% in IR nodes (many tiny pastes diluted in one huge host expression), which sits below any dial that keeps theEitherchain collapsing: a 6.25% dial does shrink it to 747 lines, below the pre-inliner baseline, but freezesLongEitherBind. Catching it needs the measurement at fixpoint convergence, where transient growth is invisible; that is filed as #287.Verification
Three unit specs written red-first pin the behavior: a 16-site product-monad dictionary chain keeps its dictionary shared (red before the change: the dictionary was pasted away and collected), a collapsing Maybe chain still dissolves end to end (green throughout), and an
@inline alwaysfield still pastes inside a growth-vetoed expression (red before: no fallback sweep existed). The full suite is green (990 examples, 0 failures), including luacheck and the Lua differential; goldens were accepted withPSLUA_GOLDEN_ACCEPT=1and re-verified with a clean run.