Skip to content

Choose case columns by Maranget's pbaN composite - #311

Merged
Unisay merged 1 commit into
mainfrom
issue-237/pban-column-heuristic
Jul 27, 2026
Merged

Choose case columns by Maranget's pbaN composite#311
Unisay merged 1 commit into
mainfrom
issue-237/pban-column-heuristic

Conversation

@Unisay

@Unisay Unisay commented Jul 27, 2026

Copy link
Copy Markdown
Collaborator

Closes #237.

mkCase compiles a PureScript case to 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 the pbaN composite 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 the MatchHistory pruning 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:

case 'x', 'y' of
  'a', 'p' -> 1
  'b', 'p' -> 2
  'c', 'p' -> 3
  'd', 'p' -> 4
  'a', 'q' -> 5

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:

if 'a'=='x' then (if 'p'=='y' then 1 else if 'q'=='y' then 5 else fail)
else if 'b'=='x' then (if 'p'=='y' then 2 else fail)
else if 'c'=='x' then (if 'p'=='y' then 3 else fail)
else if 'd'=='x' then (if 'p'=='y' then 4 else fail)
else fail

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):

if 'p'=='y' then
  (if 'a'=='x' then 1 else if 'b'=='x' then 2
   else if 'c'=='x' then 3 else if 'd'=='x' then 4 else fail)
else
  (if 'd'=='x' then fail
   else if 'a'=='x' then (if 'q'=='y' then 5 else fail) else fail)

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's literalNegatives (1 1 -> 1; 2 2 -> 2; 1 2 -> 3; _ _ -> 4), once 1 == v has failed the remaining clauses only ever test the second scrutinee v1 against 2 (one distinct pattern) while the first scrutinee v still carries two, so pbaN retires v1 first — verbatim from the golden diff:

-    elseif 2 == v then
-      if 2 == v1 then return 2 else return 4 end
+    elseif 2 == v1 then
+      if 2 == v then return 2 else return 4 end

Verification: the corpus eval goldens (hand-verified runtime-output oracles, never auto-accepted) pass unchanged, so only tree shape moved, not semantics; ./bench/ci reports bench 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.

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
@Unisay Unisay self-assigned this Jul 27, 2026
@Unisay
Unisay marked this pull request as ready for review July 27, 2026 07:56
@Unisay
Unisay merged commit c908d28 into main Jul 27, 2026
2 checks passed
@Unisay
Unisay deleted the issue-237/pban-column-heuristic branch July 27, 2026 08:01
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

Replace the single-metric case column heuristic with Maranget's composite pbaN

1 participant