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

 How much of a goal is performance at -O1?

 I have quite a few examples where we gain performance at -O1 but most of
 these disappear at -O2.

 Similarly tree matching improves Strict code much more than regular lazy
 code.
 However Strict code is reasonably rare so here also not sure how to rate
 the tradeoff.

 Code of the sort `nf (sum . map (\(a,b,c) -> (Aug.gen_func_1 a b c)))`
 where f is a random pattern mapping Enums to Ints is 2%-3% faster (average
 and median) when applying it to all possible enum combinations. (At -O2)
 with a bigger difference at -O1 or if I make the code strict.

 Benchmarking/Finding "normal" code where it makes a difference turned out
 quite hard though.
 * It requires a minimum complexity of the pattern to make a difference.
 (At least two strict arguments, and it has to be advantageous to swap the
 evaluation order).
 * Pattern matching often contributes just a fraction of the total time
 making it more difficult to benchmark the difference.
 * (Speculation): Code where patterns are performance sensitive already
 accounts for the current algorithm.
 * Most of hackage doesn't build without modification on HEAD making it
 very time consuming to get benchmarks building at all.

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