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

 It took some time but I have a proof of concept in GHC.

 This means it falls back to the default algorithm if it encounters:
 * Non vanilla constructors (So only Haskell98 Constructors)
 * Records
 * Any of the pattern extensions.
 * I've only implemented the trivial left-to-right Heuristic so far.

 So keep this in mind for the rest of this comment:

 ----

 == Examples

 Pretty much all of the trivial examples I had collected come out the same
 either way with -O
 But then it's not too surprising when using the left-to-right Heuristic.

 A gain at -O2:
 {{{
 badMix :: Int# -> Int# -> Int#
 badMix 1# 1# = 1#
 badMix _  2# = 1#
 badMix 1# 3# = 1#

 -------------------------------------------

   = \ ds_dY4 ds1_dY5 ->
       case ds_dY4 of {
         __DEFAULT ->
           case ds1_dY5 of {
             __DEFAULT -> case badMix1 of wild2_00 { };
             2# -> 1#
           };
         1# ->
           case ds1_dY5 of {
             __DEFAULT -> case badMix1 of wild2_00 { };
             1# -> 1#;
             -- 2# -> 1#; This alternative is removed in the tree approach
             3# -> 1#
           }
       }
 }}}
 However this doesn't apply when types are changed to Int -> Int -> a. Not
 yet sure why.

 I will first finish dealing with Records properly and then see if I can
 find more examples.
 At that point it should be somewhat clear if further work makes sense.


 ----

 == Nofib

 Nofib give a mean of 0% for runtime but -0.1% for time lapsed. Min/Max
 where -1.9%/+1.8% for runtime.
 So there seems to be at least some potential there.

 I plan to see how it turns out when I finish work on Records and add a few
 Heuristics.
 If that gives the same result it's probably not worth it but we will see.


 ----

 == Implementation

 === Size

 The size of that implementation is about 1100 additional Lines in it's
 current State.

 It's however pretty verbose for Haskell and some of it could be combined
 with existing functionality. Mostly because functions in DsUtil generally
 make some
 assumptions that won't hold for my algorithm so require slight
 adjustments.

 === Complexity

 I would say implementing the scheme itself so far was straight forward.

 What complicated/delayed matters most was figuring out the current
 codebase in general.

 In particular some comments in the desugarer were outdated to the point
 where they
 confused me more than they helped.
 There were invariants which contradicted the implementation, references to
 non-existant functions, the works.
 I've got a patch committed that fixed some of that but there is much room
 for improvement still.

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