[GHC] #14201: Implement ideas from "Compiling Pattern Matching to Good Decision Trees"

[GHC]

#14201: Implement ideas from "Compiling Pattern Matching to Good Decision Trees"
-------------------------------------+-------------------------------------
        Reporter:  AndreasK          |                Owner:  AndreasK
            Type:  feature request   |               Status:  new
        Priority:  normal            |            Milestone:
       Component:  Compiler          |              Version:  8.2.1
      Resolution:                    |             Keywords:
Operating System:  Unknown/Multiple  |         Architecture:
                                     |  Unknown/Multiple
 Type of failure:  None/Unknown      |            Test Case:
      Blocked By:                    |             Blocking:
 Related Tickets:                    |  Differential Rev(s):
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by AndreasK):

 The Algorithm informally explained:

 Use a recursive match function very similar to the current approach.

 match :: PatternMatrix -> DecompositionKnowledge -> FailExpr -> DsM(Expr)

 FailExpr: Same as now.

 DecompositionKnowledge: Represents the knowledge about each occurrence.
 Each entry is one of
 * Evaluated (`Case x of _ -> expr`)
 * The Value/Tag (`Case x of A -> expr`)
 * Constructors we can rule out. (`Case x of { _ -> expr; A -> notTaken }`
 )


 PatternMatrix:
 Similar to the current EquationInfo. However each RHS is extended with a
 list of constraints which must be satisfied before we can sucessfully
 match on that RHS.
 The constraints codify the strictness semantices based on the actual
 values of the arguments.

 Each RHS has the constraint of it's own row and the ones of all rows
 above.

 So a equation `A !_ B = 1` has the following constraint in pseudo syntax:
 {{{
 Eval (1) &&
 if (Val(1) == A)
     then Eval (2) && Eval (3)
     else True
 }}}

 In match:
 * Check which occurrences are strict in ALL Rows.
 * Select one of these based on some heuristic
 * Generate alternatives for each constructor in that row (and possibly a
 default).
 * Generate the code for the alternatives by:
   * Removing the evaluated column and unreachable rows from the matrix
   * Add knowledge gained by taking this alternative.
   * Calling match again with the updated Matrix/Knowledge to generate the
 code.


 Only chosing from the strict set of occurrences is already **enough to
 guarantee we don't increase strictness**.
 BUT it can lead to a function being less strict though. See SPJ's example
 above.

 Ideally we chose the next occurrence from the strict set such that few
 comparisons are made to pick a RHS using little code.
 However so far it seems the heuristic chosen hardly matters.

 But I have only tried quiet simple ones namely:
 * Left to Right
 * Constructor Count in the Row
 * Constructor Count till the first irrefutable pattern.
 * Number of different Tags
 * Right to Left. (The only one which is clearly inferior)


 **To preserve strictness:**

 Once a RHS was selected all constraints must be satisfied before we can
 jump into the actual RHS code.
 We satisfy `Eval (x)` by evaluating the Occurrence x.
 When solving `Eval (x)` we generate alternatives for all Constructors
 mentioned in the constraints.

 If we resolve the constraints left to right until all are satisfied we can
 guarantee that we
 don't skip evaluation of any arguments that should have been evaluated.

 Going back to SPJ's example to see how this works. Once we evaluted the
 second argument to `C`:
 We can immediatly select the third RHS.
 However we still have the unsolved constraint `Eval(0) && if 0 == A then
 Eval(1) else True`.

 To satisfy it we simply create another case expression to evaluate
 the first argument with a single branch for A. After that all constraints
 are solved so we put the RHS as the expression of that branch.

 On top of the above it also require some special casing for View Patterns
 and Synonyms before it can implemented into GHC.
 However both can be dealt with by using a mixture rule similar to the
 current approach.

 ----

 Results so far on ~190k unique simple patterns pulled from hackage
 packages.
 (No View/Synonym or N+K Patterns)

 Most patterns are boring and the result does not or barely change:

 * For ~150k patterns the resulting code is the some for the original
 algorithm and decision trees. ~120k of these have only a single equation
 and hence don't allow for any optimization either way.

 I used the simplest heuristic (choose the left most strict occurrence) to
 build a core like AST **so without applying GHC's simplifier** I got these
 results:

 * (+0.84%) more Terms are generated by decision trees.
 * Comparisons (sum over all patterns):
   * (-1.93%) fewer comparisons to select the worst case.
   * (-1.14%) fewer comparisons required to select a RHS on average.


 I tried a few other heuristics as well but there is not enough difference
 between these to look into it without also comparing in detail how running
 it through the simplifier changes things.

 Transpiling the AST used to GHC Source code and looking at the Core there
 are some small changes but I expect that above numbers to change very
 little based on these.

 Looking only at patterns where the algorithm makes a difference for the
 number of comparisons required the tree based approach makes about 30%
 fewer comparisons for both worst and average case.

 While this is a lot it comes with a larger code size (and more join
 points) so it's hard to tell how much of a difference it makes when it
 comes to generated machine code.

 Some of it might be because I didn't push it through the simplifier but
 that seems to hit the tree based code harder then the current approach for
 the examples I looked at I'm somewhat optimistic that it is a genuine
 reduction of case expressions evaluated.

-- 
Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/14201#comment:11>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler