[GHC] #9291: Don't reconstruct sum types if the type subtly changes
#9291: Don't reconstruct sum types if the type subtly changes
----------------------------------------------+----------------------------
Reporter: schyler | Owner:
Type: feature request | Status: new
Priority: normal | Milestone:
Component: Compiler | Version: 7.8.2
Keywords: | Operating System:
Architecture: Unknown/Multiple | Unknown/Multiple
Difficulty: Moderate (less than a day) | Type of failure:
Blocked By: | None/Unknown
Related Tickets: | Test Case:
| Blocking:
----------------------------------------------+----------------------------
Consider this test case:
{{{
module Main (main) where
fun :: Either Int String -> Either String String
fun x = case x of
Left int -> Left (show int)
Right str -> Right str
{-# NOINLINE fun #-}
main :: IO ()
main = do
l <- getLine
print $ fun (Right l)
}}}
The core we get for fun looks like:
{{{
Main.fun [InlPrag=NOINLINE]
:: Data.Either.Either GHC.Types.Int GHC.Base.String
-> Data.Either.Either GHC.Base.String GHC.Base.String
[GblId, Arity=1, Caf=NoCafRefs, Str=DmdType
#9291: Don't reconstruct sum types if the type subtly changes ----------------------------+---------------------------------------------- Reporter: schyler | Owner: Type: feature | Status: new request | Milestone: Priority: normal | Version: 7.8.2 Component: | Keywords: Compiler | Architecture: Unknown/Multiple Resolution: | Difficulty: Moderate (less than a day) Operating System: | Blocked By: Unknown/Multiple | Related Tickets: Type of failure: | None/Unknown | Test Case: | Blocking: | ----------------------------+---------------------------------------------- Comment (by schyler): Clarification, the ticket is talking about performing the coercion in the `Right ->` branch, where the reconstruction *seems* pointless. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9291#comment:1 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9291: Don't reconstruct sum types if the type subtly changes ----------------------------+---------------------------------------------- Reporter: schyler | Owner: Type: feature | Status: new request | Milestone: Priority: normal | Version: 7.8.2 Component: | Keywords: Compiler | Architecture: Unknown/Multiple Resolution: | Difficulty: Moderate (less than a day) Operating System: | Blocked By: Unknown/Multiple | Related Tickets: Type of failure: | None/Unknown | Test Case: | Blocking: | ----------------------------+---------------------------------------------- Comment (by nomeata): Are Core’s coercions expressible enough for this? I don’t think so. So one would have to resort to `unsafeCoerce` here, which wouldn’t be nice. Or this can be done at the STG stage, but then we might miss further optimizations. Tricky. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9291#comment:2 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9291: Don't reconstruct sum types if the type subtly changes ----------------------------+---------------------------------------------- Reporter: schyler | Owner: Type: feature | Status: new request | Milestone: Priority: normal | Version: 7.8.2 Component: | Keywords: Compiler | Architecture: Unknown/Multiple Resolution: | Difficulty: Moderate (less than a day) Operating System: | Blocked By: Unknown/Multiple | Related Tickets: Type of failure: | None/Unknown | Test Case: | Blocking: | ----------------------------+---------------------------------------------- Comment (by schyler): Why would the compiler inserting unsafeCoerce be bad? I would have thought that's something the compiler should be able to do a lot of, given we have such a better type system than other languages which can't prove it's safe. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9291#comment:3 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9291: Don't reconstruct sum types if the type subtly changes ----------------------------+---------------------------------------------- Reporter: schyler | Owner: Type: feature | Status: new request | Milestone: Priority: normal | Version: 7.8.2 Component: | Keywords: Compiler | Architecture: Unknown/Multiple Resolution: | Difficulty: Moderate (less than a day) Operating System: | Blocked By: Unknown/Multiple | Related Tickets: Type of failure: | None/Unknown | Test Case: | Blocking: | ----------------------------+---------------------------------------------- Comment (by nomeata): The type system of Core is actually _better_ than that of Haskell (for some value of better). And having a typed intermediate language has many benefits, e.g. it is easier to spot bugs in the core-to-core transformations. An example for what happens when you use unsafeCoerce, even internally: GeneralizedNewtypeDeriving used to be implemented this way, and together with Type Families or GADTS it was suddenly possible to crash a Haskell program. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9291#comment:4 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9291: Don't reconstruct sum types if the type subtly changes ----------------------------+---------------------------------------------- Reporter: schyler | Owner: Type: feature | Status: new request | Milestone: Priority: normal | Version: 7.8.2 Component: | Keywords: Compiler | Architecture: Unknown/Multiple Resolution: | Difficulty: Moderate (less than a day) Operating System: | Blocked By: Unknown/Multiple | Related Tickets: Type of failure: | None/Unknown | Test Case: | Blocking: | ----------------------------+---------------------------------------------- Comment (by goldfire): The way that we have proved Haskell's type system safe is precisely because Core is proved safe. Haskell itself, from a formal standpoint, is defined solely by its transformation into Core. If the compiler used `unsafeCoerce` internally, then any claims of safety would be bogus. What is seems you're asking for is a strange new beast in Core... something of a dependently-typed coercion, that requires a proof that the term it is coercing is built with the constructors whose type is not changing. I don't think this is impossible, but I don't envy the person that does the proof! This is somewhat disappointing, because I agree that it would be great to have this optimization! Perhaps others see the theory differently... -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9291#comment:5 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9291: Don't reconstruct sum types if the type subtly changes ----------------------------+---------------------------------------------- Reporter: schyler | Owner: Type: feature | Status: new request | Milestone: Priority: normal | Version: 7.8.2 Component: | Keywords: Compiler | Architecture: Unknown/Multiple Resolution: | Difficulty: Moderate (less than a day) Operating System: | Blocked By: Unknown/Multiple | Related Tickets: Type of failure: | None/Unknown | Test Case: | Blocking: | ----------------------------+---------------------------------------------- Comment (by rwbarton): I think the lens package uses this pattern extensively, or at least something closely related. In discussion with "napping" on IRC the idea arose to extend Core-level `case` with the power to generalize the type of its scrutinee. For example, if `x :: Either Int String`, then (using a syntax inspired by as- patterns, and omitting some noisy details) {{{ case x of _ { xLeft@(Left int) -> {- here xLeft :: Either Int b (we don't use it) -} Left @ String @ String (show @ Int int) xRight@(Right str) -> {- here xRight :: Either a String -} xRight @ String } }}} The appropriate amount of type generalization would depend on the type variables that appear in the fields of the constructor that was matched, after translating GADT constructors into type equality constraints. For example given the type `data X a b where MkX :: b -> X Int b`, if we match `x :: X Int Char` with `MkX Char`, we cannot generalize the type of `x` to `X a Char`, since the translated type of `MkX` is `MkX :: (a ~ Int) => b -> X a b` which does mention `a` on the left-hand side (in a constraint). This is all rather similar to role inference for data types, I imagine, except done on a per-constructor basis. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9291#comment:6 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9291: Don't reconstruct sum types if the type subtly changes ----------------------------+---------------------------------------------- Reporter: schyler | Owner: Type: feature | Status: new request | Milestone: Priority: normal | Version: 7.8.2 Component: | Keywords: Compiler | Architecture: Unknown/Multiple Resolution: | Difficulty: Moderate (less than a day) Operating System: | Blocked By: Unknown/Multiple | Related Tickets: Type of failure: | None/Unknown | Test Case: | Blocking: | ----------------------------+---------------------------------------------- Comment (by goldfire): That's an interesting idea, perhaps somewhat saner than dependently-typed coercions. But, proving such a thing type-safe would be quite a bear, I think. It seems to hinge on parametricity, which is not yet proven for Haskell or Core. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9291#comment:7 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9291: Don't reconstruct sum types if the type subtly changes ----------------------------+---------------------------------------------- Reporter: schyler | Owner: Type: feature | Status: new request | Milestone: Priority: normal | Version: 7.8.2 Component: | Keywords: Compiler | Architecture: Unknown/Multiple Resolution: | Difficulty: Moderate (less than a day) Operating System: | Blocked By: Unknown/Multiple | Related Tickets: Type of failure: | None/Unknown | Test Case: | Blocking: | ----------------------------+---------------------------------------------- Comment (by schyler): @rwbarton, does that still make it simple for the CSE to eliminate extra branches? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9291#comment:8 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9291: Don't reconstruct sum types if the type subtly changes ----------------------------+---------------------------------------------- Reporter: schyler | Owner: Type: feature | Status: new request | Milestone: Priority: normal | Version: 7.8.2 Component: | Keywords: Compiler | Architecture: Unknown/Multiple Resolution: | Difficulty: Moderate (less than a day) Operating System: | Blocked By: Unknown/Multiple | Related Tickets: Type of failure: | None/Unknown | Test Case: | Blocking: | ----------------------------+---------------------------------------------- Comment (by nomeata): (Even more crazy idea: One can even take this further. What about `case x of Right str -> Just str`. `Right` and `Just` can be used interchangeable at runtime (same constructor number, same number of arguments of the same shape). The compiler could create only one constructor for each such shape, and optimize the code above to `case x of Right _ -> x`. Furthermore we could have representational coercions between datatypes that are α-equal... Although I doubt that the run-time benefit of that will be high, and we’d lose all hopes to implement something like `vacuum` or `ghc-vis`.) -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9291#comment:9 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9291: Don't reconstruct sum types if the type subtly changes ----------------------------+---------------------------------------------- Reporter: schyler | Owner: Type: feature | Status: new request | Milestone: Priority: normal | Version: 7.8.2 Component: | Keywords: Compiler | Architecture: Unknown/Multiple Resolution: | Difficulty: Moderate (less than a day) Operating System: | Blocked By: Unknown/Multiple | Related Tickets: Type of failure: | None/Unknown | Test Case: | Blocking: | ----------------------------+---------------------------------------------- Comment (by schyler): I would be less interested in the cost of the operation as much as I would be interested in the possibility that the CSE could merge multiple branches, which means loops can be tighter. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9291#comment:10 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9291: Don't reconstruct sum types if the type subtly changes ----------------------------+---------------------------------------------- Reporter: schyler | Owner: Type: feature | Status: new request | Milestone: Priority: normal | Version: 7.8.2 Component: | Keywords: Compiler | Architecture: Unknown/Multiple Resolution: | Difficulty: Moderate (less than a day) Operating System: | Blocked By: Unknown/Multiple | Related Tickets: Type of failure: | None/Unknown | Test Case: | Blocking: | ----------------------------+---------------------------------------------- Comment (by nomeata):
I would be less interested in the cost of the operation as much as I would be interested in the possibility that the CSE could merge multiple branches, which means loops can be tighter. Your idea is absolutely glorious.
If you worry about small resulting code, then doing the transformation in STG (which is untyped) might be feasible. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9291#comment:11 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9291: Don't reconstruct sum types if the type subtly changes ----------------------------+---------------------------------------------- Reporter: schyler | Owner: Type: feature | Status: new request | Milestone: Priority: normal | Version: 7.8.2 Component: | Keywords: Compiler | Architecture: Unknown/Multiple Resolution: | Difficulty: Moderate (less than a day) Operating System: | Blocked By: Unknown/Multiple | Related Tickets: Type of failure: | None/Unknown | Test Case: | Blocking: | ----------------------------+---------------------------------------------- Comment (by rwbarton): Replying to [comment:8 schyler]:
@rwbarton, does that still make it simple for the CSE to eliminate extra branches?
Good question. I don't think it would get CSEd at the Core level, but hopefully it would in a later pass (STG or Cmm). -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9291#comment:12 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9291: Don't reconstruct sum types if the type subtly changes ----------------------------+---------------------------------------------- Reporter: schyler | Owner: Type: feature | Status: new request | Milestone: Priority: normal | Version: 7.8.2 Component: | Keywords: Compiler | Architecture: Unknown/Multiple Resolution: | Difficulty: Moderate (less than a day) Operating System: | Blocked By: Unknown/Multiple | Related Tickets: Type of failure: | None/Unknown | Test Case: | Blocking: | ----------------------------+---------------------------------------------- Comment (by simonpj): I hate the fact that a type-system question forces us to lose a potential optimisation. But I do not know any well-typed way around this particular one. I'm absolutely not willing for the compiler to add `unsafeCoerce`s to the code! One of GHC's most unique and distinctive features is its commitment to a solidly-typed intermediate language, and I'm not willing to compromise that property. There is a long tradition in Haskell of doing things the Right Way and using the pain to drive innovation. (Monads, System FC, kind polymorphism, etc etc.) All that said, STG code is un-typed and I would be quite happy with STG- level optimisations that transformed {{{ case e of y { ... C a b -> C a b ... } =====> case e of y { ... C a b -> y ... } }}} and then commoned identical branches. (The above transformation is done in Core too, but not when the types don't match. In STG that doesn't matter.) Simon -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9291#comment:13 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9291: Don't reconstruct sum types if the type subtly changes ----------------------------+---------------------------------------------- Reporter: schyler | Owner: Type: feature | Status: new request | Milestone: Priority: normal | Version: 7.8.2 Component: | Keywords: Compiler | Architecture: Unknown/Multiple Resolution: | Difficulty: Moderate (less than a day) Operating System: | Blocked By: Unknown/Multiple | Related Tickets: Type of failure: | None/Unknown | Test Case: | Blocking: | ----------------------------+---------------------------------------------- Comment (by nomeata): Isn’t the first part of that transformation just a case of CSE, just as done on Core? If we do this, we’d probably also want {{{ case e of y { ... C a b -> f (C a b) ... } =====> case e of y { ... C a b -> f y ... } }}} -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9291#comment:14 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9291: Don't reconstruct sum types if the type subtly changes ----------------------------+---------------------------------------------- Reporter: schyler | Owner: Type: feature | Status: new request | Milestone: Priority: normal | Version: 7.8.2 Component: | Keywords: Compiler | Architecture: Unknown/Multiple Resolution: | Difficulty: Moderate (less than a day) Operating System: | Blocked By: Unknown/Multiple | Related Tickets: Type of failure: | None/Unknown | Test Case: | Blocking: | ----------------------------+---------------------------------------------- Comment (by simonpj): Indeed. Simon -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9291#comment:15 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9291: Don't reconstruct sum types if the type subtly changes -------------------------------------+------------------------------------- Reporter: schyler | Owner: Type: feature | Status: new request | Milestone: Priority: normal | Version: 7.8.2 Component: Compiler | Keywords: Resolution: | Architecture: Unknown/Multiple Operating System: | Difficulty: Moderate (less Unknown/Multiple | than a day) Type of failure: | Blocked By: None/Unknown | Related Tickets: Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Comment (by rwbarton): Replying to [comment:9 nomeata]:
(Even more crazy idea: One can even take this further. What about `case x of Right str -> Just str`. `Right` and `Just` can be used interchangeable at runtime (same constructor number, same number of arguments of the same shape). The compiler could create only one constructor for each such shape, and optimize the code above to `case x of Right _ -> x`. Furthermore we could have representational coercions between datatypes that are α-equal... Although I doubt that the run-time benefit of that will be high, and we’d lose all hopes to implement something like `vacuum` or `ghc-vis`.)
This could make `toInteger :: Int -> Integer` a no-op, for example. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9291#comment:16 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9291: Don't reconstruct sum types if the type subtly changes -------------------------------------+------------------------------------- Reporter: schyler | Owner: Type: feature | Status: new request | Milestone: Priority: normal | Version: 7.8.2 Component: Compiler | Keywords: Resolution: | Architecture: Unknown/Multiple Operating System: | Difficulty: Moderate (less Unknown/Multiple | than a day) Type of failure: | Blocked By: None/Unknown | Related Tickets: Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Comment (by carter): could this be done ethically at the STG or CMM layer if we were able to keep enough information lying around at those layers? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9291#comment:17 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9291: Don't reconstruct sum types if the type subtly changes -------------------------------------+------------------------------------- Reporter: schyler | Owner: Type: feature | Status: new request | Milestone: Priority: normal | Version: 7.8.2 Component: Compiler | Keywords: Resolution: | Architecture: Unknown/Multiple Operating System: | Difficulty: Moderate (less Unknown/Multiple | than a day) Type of failure: | Blocked By: None/Unknown | Related Tickets: Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Comment (by simonpj): Replying to [comment:17 carter]:
could this be done ethically at the STG or CMM layer if we were able to keep enough information lying around at those layers?
Yes, I think it could; both are much less strongly typed than Core. STG would be much better than CMM. There isn't currently an STG optimisation pass, but you could add one. Simon -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9291#comment:18 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9291: Don't reconstruct sum types if the type subtly changes -------------------------------------+------------------------------------- Reporter: schyler | Owner: Type: feature | Status: new request | Milestone: Priority: normal | Version: 7.8.2 Component: Compiler | Keywords: Resolution: | Architecture: Unknown/Multiple Operating System: | Difficulty: Moderate (less Unknown/Multiple | than a day) Type of failure: | Blocked By: None/Unknown | Related Tickets: Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Changes (by heisenbug): * cc: heisenbug (added) -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9291#comment:19 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9291: Don't reconstruct sum types if the type subtly changes -------------------------------------+------------------------------------- Reporter: schyler | Owner: Type: feature request | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.8.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Revisions: -------------------------------------+------------------------------------- Changes (by rwbarton): * cc: rwbarton (added) -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9291#comment:20 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9291: Don't reconstruct sum types if the type subtly changes -------------------------------------+------------------------------------- Reporter: schyler | Owner: Type: feature request | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.8.2 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: | -------------------------------------+------------------------------------- Changes (by osa1): * cc: osa1 (added) -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9291#comment:21 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9291: Don't reconstruct sum types if the type subtly changes -------------------------------------+------------------------------------- Reporter: schyler | Owner: Type: feature request | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.8.2 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: | -------------------------------------+------------------------------------- Changes (by slyfox): * cc: slyfox (added) -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9291#comment:22 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9291: Don't reconstruct sum types if the type subtly changes -------------------------------------+------------------------------------- Reporter: schyler | Owner: Type: feature request | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.8.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by RyanGlScott): * cc: RyanGlScott (added) -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9291#comment:24 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9291: Don't reconstruct sum types if the type subtly changes -------------------------------------+------------------------------------- Reporter: schyler | Owner: Type: feature request | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.8.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by ekmett): * cc: ekmett (added) -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9291#comment:25 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9291: Don't reconstruct sum types if the type subtly changes -------------------------------------+------------------------------------- Reporter: schyler | Owner: Type: feature request | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.8.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by maoe): * cc: maoe (added) -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9291#comment:26 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
I hate the fact that a type-system question forces us to lose a
#9291: Don't reconstruct sum types if the type subtly changes -------------------------------------+------------------------------------- Reporter: schyler | Owner: Type: feature request | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.8.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by nomeata): I was considering this problem a bit more today, and my best shot at this so far turned out to be quite similar to what [comment:6 rwbarton] already suggested above. Richard thinks this might be interesting to get right (with type safety proofs and all that). Replying to [comment:13 simonpj]: potential optimisation. Me too! Although any solution will likely incur some changes to Core, and that probably needs to be justified by more than the unhappy feeling I have about Core’s type system getting in the way of producing the obviously right code. Does anyone have a practical example where this bug bytes a lot? Maybe something with lenses, or with generic programs? It seems to affect, for example, every `Functor` instance for a sum type where the type parameter is not used in at least one of the branches. Anyways, I started writing down a possible approach with more detail at CaseBinderGeneralisation. Comments welcome. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9291#comment:27 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9291: Don't reconstruct sum types if the type subtly changes -------------------------------------+------------------------------------- Reporter: schyler | Owner: Type: feature request | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.8.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by simonpj): The wiki page looks plausible... but rather a lot of work for a modest gain. I wonder if a better approach would be a STG-level CSE pass? (No types there!) -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9291#comment:28 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9291: Don't reconstruct sum types if the type subtly changes -------------------------------------+------------------------------------- Reporter: schyler | Owner: Type: feature request | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.8.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by goldfire): Replying to [comment:28 simonpj]:
The wiki page looks plausible... but rather a lot of work for a modest gain.
As Joachim hinted at above, this is also my stance. There might be some interesting theory here and some fun proofs, but I'm unconvinced that all the heavy lifting will be worth it. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9291#comment:29 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9291: Don't reconstruct sum types if the type subtly changes -------------------------------------+------------------------------------- Reporter: schyler | Owner: Type: feature request | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.8.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by Iceland_jack): * cc: Iceland_jack (added) -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9291#comment:30 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9291: Don't reconstruct sum types if the type subtly changes -------------------------------------+------------------------------------- Reporter: schyler | Owner: Type: feature request | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.8.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by osa1): CSE implementation in STG is one of the things I'm hoping to try when I have some time. I have a branch here that allows STG-to-STG plugins: https://github.com/osa1/ghc/tree/stg_plugins, this may help. We just need a version of `TrieMap` for STG expressions and then the pass should be trivial. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9291#comment:31 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
I wonder if a better approach would be a STG-level CSE pass? (No types
#9291: Don't reconstruct sum types if the type subtly changes
-------------------------------------+-------------------------------------
Reporter: schyler | Owner:
Type: feature request | Status: new
Priority: normal | Milestone:
Component: Compiler | Version: 7.8.2
Resolution: | Keywords:
Operating System: Unknown/Multiple | Architecture:
Type of failure: Runtime | Unknown/Multiple
performance bug | Test Case:
Blocked By: | Blocking:
Related Tickets: | Differential Rev(s):
Wiki Page: |
-------------------------------------+-------------------------------------
Comment (by nomeata):
there!)
Is general CSE on the STG level safe? We would have to pay attention not
to CSE two invocations of `newSTRef`, for example! Consider
{{{#!hs
foo :: Integer -> Integer
foo n = runST (newSTRef 1 >>= \r -> modifySTRef r (+n) >> readSTRef r)
+ runST (newSTRef 1 >>= \r -> modifySTRef r (+2*n) >> readSTRef r)
}}}
which generated this STG
{{{
STGCSE.foo :: GHC.Integer.Type.Integer -> GHC.Integer.Type.Integer
[GblId, Arity=1, Str=
#9291: Don't reconstruct sum types if the type subtly changes -------------------------------------+------------------------------------- Reporter: schyler | Owner: Type: feature request | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.8.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by simonpj): Ha ha. Excellent point! -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9291#comment:33 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9291: Don't reconstruct sum types if the type subtly changes -------------------------------------+------------------------------------- Reporter: schyler | Owner: Type: feature request | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.8.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by nomeata): There is value in working with a typed intermediate language, isn’t it ;-) -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9291#comment:34 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9291: Don't reconstruct sum types if the type subtly changes -------------------------------------+------------------------------------- Reporter: schyler | Owner: Type: feature request | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.8.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by osa1): Is this related with typed-ness of the IR? I think if we do some of the transformations we do during `coreToStg` we would have the same problem in Core too. I'm wondering if a solution could be as simple as treating state tokens as different from each other when comparing expressions... -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9291#comment:35 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9291: Don't reconstruct sum types if the type subtly changes -------------------------------------+------------------------------------- Reporter: schyler | Owner: Type: feature request | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.8.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by nomeata):
Is this related with typed-ness of the IR?
Yes! The type system of Core ensures that we cannot get the ST stuff wrong (to some extent. It still requires us to also not inline `runRW#`, for example).
I think if we do some of the transformations we do during `coreToStg` we would have the same problem in Core too.
You mean inlining `runRW#`? Right, we should not do that. I tried that once, and it broke :-)
I'm wondering if a solution could be as simple as treating state tokens as different from each other when comparing expressions...
Sure, such reasoning will be required. Is the only such case? Also, in this case, CSE’ing the state token isn’t the problem per se (the state token is a zero-width value, so operationally, they are all equal). The real problem is CSE’ing `newMutRef#` which has a side-effect. So maybe only CSE’ing constructor applications is a safer start. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9291#comment:36 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9291: Don't reconstruct sum types if the type subtly changes -------------------------------------+------------------------------------- Reporter: schyler | Owner: Type: feature request | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.8.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by rwbarton): Replying to [comment:36 nomeata]:
Is this related with typed-ness of the IR?
Yes! The type system of Core ensures that we cannot get the ST stuff wrong (to some extent. It still requires us to also not inline `runRW#`, for example).
Is this really true? Say I write {{{#!hs f :: Bool -> IORef Int -> IO () f b v = v `seq` when b (writeIORef v 3) }}} GHC produces {{{ f1 = \ b_auQ v_auR eta_B1 -> case v_auR `cast` ... of _ { STRef ipv_sPi -> case b_auQ of _ { False -> (# eta_B1, () #); True -> case writeMutVar# ipv_sPi f2 eta_B1 of s2#_aQd { __DEFAULT -> (# s2#_aQd, () #) } } } }}} What stops me from rewriting this via case-of-case to the inequivalent {{{ f1 = \ b_auQ v_auR eta_B1 -> case v_auR `cast` ... of _ { STRef ipv_sPi -> case writeMutVar# ipv_sPi f2 eta_B1 of s2#_aQd { __DEFAULT -> case b_auQ of _ { False -> (# eta_B1, () #); -- Haha, don't actually use s2#_aQd here. True -> (# s2#_aQd, () #) } } } }}} I think it is just the flag `has_side_effects = True` on `writeMutVar#`, and doesn't have to do with types. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9291#comment:37 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9291: Don't reconstruct sum types if the type subtly changes -------------------------------------+------------------------------------- Reporter: schyler | Owner: Type: feature request | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.8.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by nomeata): Uh. Good point. I guess we’d need a linear type system to prevent your illegal double-use of `eta_B1` here :-) (It is not really “case-of-case” that you are doing there, but your point still holds.) Note that this would be an illegal transformation not only for `writeMutVar#` but for anything that is not provabley total, even a pure but non-terminating function. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9291#comment:38 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9291: Don't reconstruct sum types if the type subtly changes -------------------------------------+------------------------------------- Reporter: schyler | Owner: Type: feature request | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.8.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by rwbarton): Right, so it's not a very good example. But I think correctness of IO mostly relies on the state threading discipline (which doesn't need types), combined I guess with the need to preserve the semantics of possibly-diverging-but-otherwise-pure programs. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9291#comment:39 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9291: Don't reconstruct sum types if the type subtly changes -------------------------------------+------------------------------------- Reporter: schyler | Owner: nomeata Type: feature request | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.8.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D2871 Wiki Page: | -------------------------------------+------------------------------------- Changes (by nomeata): * owner: => nomeata * differential: => Phab:D2871 Comment: I started working on this (at the STG stage, CSE’ing only constructors, and not across lambdas) at Phab:D2871. Not merge-worthy yet, but preliminary review is welcome. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9291#comment:40 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9291: Don't reconstruct sum types if the type subtly changes -------------------------------------+------------------------------------- Reporter: schyler | Owner: nomeata Type: feature request | Status: patch Priority: normal | Milestone: Component: Compiler | Version: 7.8.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D2871 Wiki Page: | -------------------------------------+------------------------------------- Changes (by nomeata): * status: new => patch Comment: Ok, should be ready for review. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9291#comment:41 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9291: Don't reconstruct sum types if the type subtly changes
-------------------------------------+-------------------------------------
Reporter: schyler | Owner: nomeata
Type: feature request | Status: patch
Priority: normal | Milestone:
Component: Compiler | Version: 7.8.2
Resolution: | Keywords:
Operating System: Unknown/Multiple | Architecture:
Type of failure: Runtime | Unknown/Multiple
performance bug | Test Case:
Blocked By: | Blocking:
Related Tickets: | Differential Rev(s): Phab:D2871
Wiki Page: |
-------------------------------------+-------------------------------------
Comment (by Joachim Breitner
#9291: Don't reconstruct sum types if the type subtly changes -------------------------------------+------------------------------------- Reporter: schyler | Owner: nomeata Type: feature request | Status: closed Priority: normal | Milestone: Component: Compiler | Version: 7.8.2 Resolution: fixed | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D2871 Wiki Page: | -------------------------------------+------------------------------------- Changes (by nomeata): * status: patch => closed * resolution: => fixed Comment: Done. Would still be fun to be able to do this (and stuff like #5344) in Core, but that would require serious work on the type level. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9291#comment:43 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9291: Don't reconstruct sum types if the type subtly changes
-------------------------------------+-------------------------------------
Reporter: schyler | Owner: nomeata
Type: feature request | Status: closed
Priority: normal | Milestone:
Component: Compiler | Version: 7.8.2
Resolution: fixed | Keywords:
Operating System: Unknown/Multiple | Architecture:
Type of failure: Runtime | Unknown/Multiple
performance bug | Test Case:
Blocked By: | Blocking:
Related Tickets: | Differential Rev(s): Phab:D2871
Wiki Page: |
-------------------------------------+-------------------------------------
Comment (by heisenbug):
Replying to [comment:42 Joachim Breitner
In [changeset:"19d5c7312bf0ad9ae764168132aecf3696d5410b/ghc" 19d5c73/ghc]: {{{ #!CommitTicketReference repository="ghc" revision="19d5c7312bf0ad9ae764168132aecf3696d5410b" Add a CSE pass to Stg (#9291)
...
Introduces the flag -fstg-cse, enabled by default with -O for now. It might also be a good candidate for -O2.
Will you revisit the `-O2` inclusion sometime later? /me was always under the impression that all performance-increasing optimisations from `-O` would be included in `-O2`.
Differential Revision: https://phabricator.haskell.org/D2871 }}}
-- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9291#comment:44 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
Will you revisit the -O2 inclusion sometime later? /me was always under
#9291: Don't reconstruct sum types if the type subtly changes -------------------------------------+------------------------------------- Reporter: schyler | Owner: nomeata Type: feature request | Status: closed Priority: normal | Milestone: Component: Compiler | Version: 7.8.2 Resolution: fixed | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D2871 Wiki Page: | -------------------------------------+------------------------------------- Comment (by nomeata): the impression that all performance-increasing optimisations from -O would be included in -O2. Oh, of course it is in `-O2`! The question is whether it should only be in `-O`. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9291#comment:45 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9291: Don't reconstruct sum types if the type subtly changes -------------------------------------+------------------------------------- Reporter: schyler | Owner: nomeata Type: feature request | Status: closed Priority: normal | Milestone: Component: Compiler | Version: 7.8.2 Resolution: fixed | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D2871 Wiki Page: | -------------------------------------+------------------------------------- Comment (by heisenbug): Looking at the tests, I do not see `Either x y <-> Maybe y` coercions. Are these supposed to be done? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9291#comment:46 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
Looking at the tests, I do not see Either x y <-> Maybe y coercions. Are
#9291: Don't reconstruct sum types if the type subtly changes -------------------------------------+------------------------------------- Reporter: schyler | Owner: nomeata Type: feature request | Status: closed Priority: normal | Milestone: Component: Compiler | Version: 7.8.2 Resolution: fixed | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D2871 Wiki Page: | -------------------------------------+------------------------------------- Comment (by nomeata): these supposed to be done? Are you referring to treating a `Just x` directly `Right x`, i.e. using similarly looking constructors at a different type? That is not included here, and it is not clear whether we actually want it done. If you think we do, please open a new ticket for it. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9291#comment:47 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9291: Don't reconstruct sum types if the type subtly changes -------------------------------------+------------------------------------- Reporter: schyler | Owner: nomeata Type: feature request | Status: closed Priority: normal | Milestone: Component: Compiler | Version: 7.8.2 Resolution: fixed | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D2871 Wiki Page: | -------------------------------------+------------------------------------- Comment (by heisenbug): Replying to [comment:47 nomeata]:
Looking at the tests, I do not see Either x y <-> Maybe y coercions. Are these supposed to be done?
Are you referring to treating a `Just x` directly `Right x`, i.e. using similarly looking constructors at a different type? That is not included here, and it is not clear whether we actually want it done. If you think we do, please open a new ticket for it.
Yes, that is what I mean. They would be memory-layout compatible. I'll ponder a bit more, and if I still think it's a good idea, I'll follow up with a ticket. Thanks for doing this! -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9291#comment:48 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9291: Don't reconstruct sum types if the type subtly changes -------------------------------------+------------------------------------- Reporter: schyler | Owner: nomeata Type: feature request | Status: closed Priority: normal | Milestone: Component: Compiler | Version: 7.8.2 Resolution: fixed | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D2871 Wiki Page: | -------------------------------------+------------------------------------- Comment (by heisenbug): Replying to [comment:48 heisenbug]: I followed up with #13861 on this. Let's see what people think :-) -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9291#comment:49 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9291: Don't reconstruct sum types if the type subtly changes
-------------------------------------+-------------------------------------
Reporter: schyler | Owner: nomeata
Type: feature request | Status: closed
Priority: normal | Milestone:
Component: Compiler | Version: 7.8.2
Resolution: fixed | Keywords:
Operating System: Unknown/Multiple | Architecture:
Type of failure: Runtime | Unknown/Multiple
performance bug | Test Case:
Blocked By: | Blocking:
Related Tickets: | Differential Rev(s): Phab:D2871
Wiki Page: |
-------------------------------------+-------------------------------------
Comment (by heisenbug):
@nomeata, I have
{{{#!hs
data Boo = Tru | Fal
quux True = Fal
quux False = Tru
{-# NOINLINE quux #-}
}}}
which compiles to STG
{{{
quux_rCA :: GHC.Types.Bool -> Main.Boo
[GblId, Arity=1, Caf=NoCafRefs, Str=
#9291: Don't reconstruct sum types if the type subtly changes -------------------------------------+------------------------------------- Reporter: schyler | Owner: nomeata Type: feature request | Status: closed Priority: normal | Milestone: Component: Compiler | Version: 7.8.2 Resolution: fixed | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D2871 Wiki Page: | -------------------------------------+------------------------------------- Comment (by nomeata): Yes, it preserves the strictness: `id = \x. x` is strict in `x` , since `id ⊥ = ⊥`. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9291#comment:51 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
participants (1)
-
GHC