[GHC] #11527: Pattern match translation suboptimal
#11527: Pattern match translation suboptimal -------------------------------------+------------------------------------- Reporter: augustss | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.8.3 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: -------------------------------------+------------------------------------- Compile the following code and look at the (sad) intermediate code: {{{ baz :: Integer -> Int -> Int baz 10 1 = 1 baz 20 1 = 2 baz 10 2 = 2 baz 20 2 = 3 baz 10 3 = 1 baz 20 3 = 2 baz 10 4 = 2 baz 20 4 = 3 baz _ _ = 0 }}} The pattern match compiler has not rearranged the clauses, and so it produces an 8 level deep nested test. Now change the type signature to {{{ baz :: Int -> Int -> Int }}} Now the pattern match compiler does its job and rearranges the clauses to make the tests 2 levels deep. The same phenomenon happens when matching string literals. For the predefined String type the right thing happens, but for some other string type (using OverloadedStrings) it doesn't. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11527 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#11527: Pattern match translation suboptimal -------------------------------------+------------------------------------- Reporter: augustss | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.8.3 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): For `Integer` I agree we could and should do better. But what about {{{ baz :: (Num a) => a -> Int -> Int }}} which is what you'll get if you don't have a type signature. The report specifies something like this: {{{ baz n x | n == fromInteger 10, x == 1 = 1 | n == fromInteger 20, x == 1 = 2 | n == fromInteger 10, x == 2 = 2 ...etc... }}} Now you might think that we can common up all those tests for `n == fromInteger 10` to get {{{ baz n x | n == fromInteger 10 = case x of 1 -> 1 2 -> 2 ... etc ... | n == fromInteger 20 = ...etc.. }}} But what if both `n == fromInteger 10` and `n == fromInteger 20` are ''both true''? Now it's not OK to group together all the matches against 10. How annoying! The best we can do is to do CSE on those `fromInteger` calls. It's all very irritating but I don't see how to do better. Except for `Integer` when we know that the `Num` instance has good properties. Is that particular case worth improving? Perhaps, and it would not be hard -- I can offer guidance. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11527#comment:1 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#11527: Pattern match translation suboptimal -------------------------------------+------------------------------------- Reporter: augustss | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.8.3 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 augustss): I agree that in general we can't rearrange the tests. Unfortunately, this means that using your own string type instead of String can be quite costly if you do pattern matching (that's actually my use case). Since we can't assume that the compiler can deduce the necessary property, I suggest we add some way to convey the information. Some different ways: * Annotation on the Eq instance to say that it is sane. * Annotation on the case expression to say that we want more aggressive reordering. * A compiler flag that says we want more aggressive reordering. An annotation on the Eq instance seems like the nicest option. I'm quite keen to minimize the performance penalty for using a different string type. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11527#comment:2 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#11527: Pattern match translation suboptimal -------------------------------------+------------------------------------- Reporter: augustss | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.8.3 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 augustss): Or maybe the annotation should be on the type. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11527#comment:3 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#11527: Pattern match translation suboptimal -------------------------------------+------------------------------------- Reporter: augustss | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.8.3 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): Sounds great to me. Yes, injectivity of `fromString` and `fromInteger` seem like the key points. Would you like to propose a design, describe it on a wiki page, agree it, and maybe implement it? Simon -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11527#comment:4 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#11527: Pattern match translation suboptimal -------------------------------------+------------------------------------- Reporter: augustss | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.8.3 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 augustss): OK, I'll start by making a wiki page. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11527#comment:5 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
participants (1)
-
GHC