#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