#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):
But since you don't give an algorithm, it's hard to tell whether that's all that can happen.\\
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.
Indeed. I aim to maintain strictness properties of the current algorithm and if I manage that this can't happen. Intuitively this follows from the fact that if we maintain strictness properties and one of the arguments contains a exception we are guaranteed to trigger or avoid it if the old algorithm would have done so. Actually matching the strictness is the hard part especially avoiding potential loss of strictness. So far I worked out a way to apply good decision trees when I ignore the loss of strictness and a way to prevent loss of strictness on paper. I haven't yet worked out completely how I will combine them and how this will impact the complexity of the algorithm.
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".
It's easy to come up with examples where the current approach generates unnecessary large code sizes on paper. What I'm not sure about is how often these actually occur in regular code. So my next steps are: 1. Combine maintaining strictness with the approach in good trees. * Implement it for a subset of ghc's patterns outside of ghc. (Constructor/Variable/Wildcard) * Re implement the current approach in the same framework. 2. Put some instrumentation into the pattern matching code and sample patterns from as much code as I can. 3. Hopefully get results indicating that it's worth implementing in GHC. 4. Implement it as part of GHC. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14201#comment:7 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler