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

 I added rudimentary support for Records and made it work nicely with
 -XStrict.

 After playing around with nofib a lot I have essentially given up using it
 as a primary benchmarking tool

 I tried using nofib to benchmark (compile times) for #14524 which was
 inconclusive even when the performance difference for the function in
 question was ~10%.

 Running nofib with my changes didn't really produce results for the same
 issue of variance drowning out any difference the results would have made.

 == So my plan for now is:

 * Ditch nofib for the time being.
 * Create micro benchmarks and use criterion to check the difference.
 * Once I feel i have a reasonably sized set of benchmarks:
   * Look for pattern matching heavy real world examples and benchmark
 these.
     Based on the results of the OCaml implementation I don't expect
 measurable results unless there are not trivial patterns in a inner loop.
   * Gather feedback if gain/complexity trade off warrants inclusion in
 GHC.
   * Depending on the outcome of the above stop working on this or tidy up
 my code and get it into HEAD.

 == Micro Benchmarks:

 I mirror them on [https://github.com/AndreasPK/pattern_benchmarks Github].

 Here is a
 [https://cdn.rawgit.com/AndreasPK/pattern_benchmarks/31dd3321/results/res_noinline.html
 result] for two simple patterns.

 I've uploaded the results also as attachment if GH becomes unavailable.
 (criterion_log)

 The two patterns I started with (each once used with enums once with Int)
 are at worst as fast and at best ~15% faster. (But then 15% of little is
 still not much).

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