#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): It took some time but I have a proof of concept in GHC. This means it falls back to the default algorithm if it encounters: * Non vanilla constructors (So only Haskell98 Constructors) * Records * Any of the pattern extensions. * I've only implemented the trivial left-to-right Heuristic so far. So keep this in mind for the rest of this comment: ---- == Examples Pretty much all of the trivial examples I had collected come out the same either way with -O But then it's not too surprising when using the left-to-right Heuristic. A gain at -O2: {{{ badMix :: Int# -> Int# -> Int# badMix 1# 1# = 1# badMix _ 2# = 1# badMix 1# 3# = 1# ------------------------------------------- = \ ds_dY4 ds1_dY5 -> case ds_dY4 of { __DEFAULT -> case ds1_dY5 of { __DEFAULT -> case badMix1 of wild2_00 { }; 2# -> 1# }; 1# -> case ds1_dY5 of { __DEFAULT -> case badMix1 of wild2_00 { }; 1# -> 1#; -- 2# -> 1#; This alternative is removed in the tree approach 3# -> 1# } } }}} However this doesn't apply when types are changed to Int -> Int -> a. Not yet sure why. I will first finish dealing with Records properly and then see if I can find more examples. At that point it should be somewhat clear if further work makes sense. ---- == Nofib Nofib give a mean of 0% for runtime but -0.1% for time lapsed. Min/Max where -1.9%/+1.8% for runtime. So there seems to be at least some potential there. I plan to see how it turns out when I finish work on Records and add a few Heuristics. If that gives the same result it's probably not worth it but we will see. ---- == Implementation === Size The size of that implementation is about 1100 additional Lines in it's current State. It's however pretty verbose for Haskell and some of it could be combined with existing functionality. Mostly because functions in DsUtil generally make some assumptions that won't hold for my algorithm so require slight adjustments. === Complexity I would say implementing the scheme itself so far was straight forward. What complicated/delayed matters most was figuring out the current codebase in general. In particular some comments in the desugarer were outdated to the point where they confused me more than they helped. There were invariants which contradicted the implementation, references to non-existant functions, the works. I've got a patch committed that fixed some of that but there is much room for improvement still. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14201#comment:13 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler