Choose case columns by Maranget's pbaN composite - #311
Merged
Conversation
Replace the single-metric column selection in matchChosenByHeuristic (pick the match tested by the most other clauses) with the pbaN composite from Maranget's "Compiling Pattern Matching to Good Decision Trees", adapted to the clause-per-row representation: maximise the needed prefix (p), then minimise distinct patterns on the column (b), then minimise the sub-tests those patterns expose (a), tie-breaking leftmost (N). Surrounding decision-tree construction and MatchHistory pruning are unchanged. On matrices where the metrics disagree the composite emits a smaller tree: the new unit test's five-clause matrix compiles to 8 tests instead of 9. Corpus impact is a neutral test-order swap in Golden.CasePruning.Test only; eval goldens and bench counters are unchanged. Closes #237
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 #237.
mkCasecompiles a PureScriptcaseto a decision tree of nested if/else tests, choosing at every step which outstanding pattern test to emit next — a "column" here is a focused sub-value of a scrutinee (the scrutinee expression plus the projection steps into it). The chooser,matchChosenByHeuristic, used a single metric: pick the column tested by the most other clauses. This PR replaces that metric with thepbaNcomposite from Maranget's "Compiling Pattern Matching to Good Decision Trees" (ML 2008), adapted to the clause-per-row representation. Candidates are scored lexicographically: p — the number of consecutive clauses, starting from the current one, that test the column (a test every following clause needs cannot be wasted); b — fewest distinct patterns tested on the column across the remaining clauses (a column with fewer distinct tests is retired sooner); a — fewest sub-tests those patterns expose once passed; N — leftmost on full ties. Everything around the choice is untouched, including theMatchHistorypruning that skips tests whose outcome is already decided on a path.Where the metrics disagree, the composite emits a smaller tree. The new unit test (
test/Language/PureScript/Backend/IR/Spec.hs, "tests the column with fewer distinct patterns first") compiles this five-clause matrix, where every clause tests both columns — so the old total-count metric ties (4 vs 4) and falls back to the left column — while pbaN sees four distinct patterns on column 1 against two on column 2 and tests column 2 first:The pre-change compiler (captured by the test's red run before the fix) produces 9 tests — the column-2 test
'p' == 'y'is re-emitted inside every branch of the four-way column-1 chain:With pbaN the column-2 test runs once and the column-1 chain follows once per outcome — 8 tests (this is the tree the unit test asserts):
Across the golden corpus the change is a wash, which is the intended safety property: exactly one module moves, and only by an order swap with an identical test count. In
Golden.CasePruning.Test'sliteralNegatives(1 1 -> 1; 2 2 -> 2; 1 2 -> 3; _ _ -> 4), once1 == vhas failed the remaining clauses only ever test the second scrutineev1against2(one distinct pattern) while the first scrutineevstill carries two, so pbaN retiresv1first — verbatim from the golden diff:Verification: the corpus eval goldens (hand-verified runtime-output oracles, never auto-accepted) pass unchanged, so only tree shape moved, not semantics;
./bench/cireportsbench counters match goldens, so the LuaJIT FNEW/TNEW censuses and trace reports over the linked bench artifacts are byte-identical; the full suite is green and the IR spec group was re-run 10 times with fresh seeds. Code-size delta across the corpus is zero lines.