#14201: Implement ideas from "Compiling Pattern Matching to Good Decision Trees" -------------------------------------+------------------------------------- Reporter: AndreasK | Owner: (none) Type: feature | Status: new request | Priority: normal | Milestone: Component: Compiler | Version: 8.2.1 Keywords: | Operating System: Unknown/Multiple Architecture: | Type of failure: None/Unknown Unknown/Multiple | Test Case: | Blocked By: Blocking: | Related Tickets: Differential Rev(s): | Wiki Page: -------------------------------------+------------------------------------- = The basic Ideas Currently GHC uses Augustssons algorithm for pattern matching which was published in 85 which works fine for many cases. However there has been research on how to do better than that for a while now. Most notably by Maranget in "Compiling Pattern Matching to Good Decision Trees". I plan to look into applying his ideas to GHC for my undergraduate thesis. Thanks to imprecise exceptions we should be able to reorder argument evaluation as long as this doesn't make our programs more strict. Proofing that is high on my bucket list but hasn't been done yet. = Pros and Cons **Advantages** would be: * It should lead to equal or better code for the vast majority of patterns. * It might reduce compile times for cases were we can desugar directly to good code. **Disadvantages**: * Desugaring gets more complex. It' obvious that since the underlying algorithm is more complex the desugarer would also grow in complexity in accordance. It is hard to say in advance how much of a difference it will make but I hope it won't be too bad. Depending on the runtime of the new algorithm compared to the old one this might also speed up compilation for cases where the old algorithm generated code that had to be heavily optimized by the simplifier. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14201 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler