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

 I agree that if the only difference is which exception is raised, then
 it's like `exn1 + exn2` and we can be imprecise about which one we get.

 But since you don't give an algorithm, it's hard to tell whether that's
 all that can happen.  For example
 {{{
 f :: T -> T -> Int
 f A A = 1
 f B A = 2
 f C _ = 3

 f2 :: T -> T -> Int
 f2 A A = 1
 f2 A B = 2
 f2 _ C = 3
 }}}
 Here `f1 C exn` will return 3, but `f2 exn C` will throw `exn`.  So order
 matters here.

 I guess you need to prove that the algorithm you use doesn't change
 semantics.

 The other question is this: what performance is on the table?  It'd be
 more convincing if you had some examples where better pattern-match
 compilation causes significantly less code, or better performance.  I'm
 sure the pattern-match compiler will be more complicated, and we want to
 trade that complexity for some tangible benefit.

 You can probably start to answer this question with some hand-written A/B
 examples: "if we had a better compiler we'd get this much better code".

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