Richard,
In an effort to figure out why programs with lots of type families have become so much slower over the last few GHC releases, I've been looking at GHC Trac #12545 [1], which provides a very self-contained test case that became considerably slower to compile from GHC 7.10 to 8.0. Thanks to this test case, I found one of the sources of the slowdown: a single, very small commit of yours [2]. What's baffling, though, is that I can't figure out why that commit makes compilation so much slower. I tried making profiled builds of GHC before and after that commit and attaching SCCs to the new code, but to my surprise, their contribution to the overall compilation time was negligible. So I'm out of ideas on what might be causing this. The only hint I have is the output of -ddump-simpl-stats/-dshow-passes. Before that commit, there's a point where the terms, types, and coercions go up: *** Float out(FOS {Lam = Just 0, Consts = True, OverSatApps = False}): Result size of Float out(FOS {Lam = Just 0, Consts = True, OverSatApps = False}) = {terms: 20,769, types: 1,157,897, coercions: 3,635,961} *** Simplifier: Result size of Simplifier iteration=1 = {terms: 44,081, types: 2,451,155, coercions: 9,802,016} But after that commit, the terms and types jump up considerably higher! *** Simplifier: Result size of Simplifier = {terms: 16,429, types: 864,761, coercions: 2,184,448} *** Simplifier: Result size of Simplifier iteration=1 = {terms: 87,357, types: 4,366,893, coercions: 10,008,352} Here are the relevant bits from -ddump-simpl-stats. Before that commit: 150 PreInlineUnconditionally 40 PostInlineUnconditionally 220 UnfoldingDone 110 RuleFired 380 BetaReduction After that commit: 306 PreInlineUnconditionally 160 PostInlineUnconditionally 360 UnfoldingDone 308 RuleFired 1238 BetaReduction Does you know what might be going on here? Ryan S. ----- _______________________________________________ ghc-devs mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs |
> On May 31, 2017, at 5:21 PM, Ryan Scott <[hidden email]> wrote: > Does you know what might be going on here? I think so, but I don't know how to fix it. The commit you found (thank you!) makes simple_opt_expr (the "simple optimizer", run directly after desugaring, even with -O0) a little more selective in what `case` expressions it throws away. Previous to that commit, the optimizer would throw away a `case error "deferred type error" of _ -> ...` which is terrible. It seems that you have discovered that we are now too timid in throwing away unhelpful cases. It would be interesting to know what the newly-retained cases look like, so that we might throw them away. But there remains a mystery: Why do we need this code at all? Reading Note [Getting the map/coerce RULE to work] closely, it seems we need to simplify forall a b (co :: a ~R# b). let dict = MkCoercible @* @a @b co in case Coercible_SCSel @* @a @b dict of _ [Dead] -> map @a @b (\(x :: a) -> case dict of MkCoercible (co :: a ~R# b) -> x |> co) = let dict = ... in ... to forall a b (co :: a ~R# b). map @a @b (\(x :: a) -> x |> co) = \(x :: [a]) -> x |> [co] Part of doing so is to drop the `case Coercible_SCSel ...`, which gets in the way. The mystery is why this needs special code -- shouldn't the eliminate-case-of-known-constructor do the trick? This would require unfolding Coercible_SCSel. Does that happen? It would seem not... but maybe it should, which would remove the special-case code that I changed in that commit, and quite likely would simplify much more code besides. So: Is Coercible_SCSel unfolded during simple_opt? If not, what wonderful or terrible things happen if we do? If so, why does case-of-known-constructor not work here? My guess is that answering these questions may solve the original problem, but this guess could be wrong. Richard _______________________________________________ ghc-devs mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs |
Hrm. It's a shame that supporting this map/coerce RULE causes such pain. This makes me wonder: can we get rid of this RULE? Eric Mertens pointed out a trick [1] that's used in the profunctors library to make mapping coerce over certain Profunctors more efficient. To adapt this trick for Functor, we'd need to add another class method: class Functor f where fmap :: (a -> b) -> f a -> f b (<#>) :: Coercible a b => (a -> b) -> f a -> f b (<#>) = \f -> \p -> p `seq` fmap f p Now, when implementing Functor instances, if we are working with a datatype whose role is representational or phantom, we can make (<#>) really fast: data List a = Nil | Cons a (List a) instance Functor List where fmap = ... (<#>) = coerce Now, instead of relying on (map MkNewtype Nil) to rewrite to Nil, we can just use (MkNewtype <#> Nil)! No map/coerce RULE necessary :) OK, I realize that suggesting that we remove the RULE is perhaps a touch too far. But it does sting that we have to pay hefty compilation penalties because of its existence... Ryan S. ----- On Wed, May 31, 2017 at 7:25 PM, Richard Eisenberg <[hidden email]> wrote:
_______________________________________________ ghc-devs mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs |
In reply to this post by Ryan Scott
Edward Kmett has explained that this isn't sufficient when things go higher order. His suggested improvement is liftCoercion :: Maybe (Coercion a b -> Coercion (f a) (f b)) David Feuer Well-Typed, LLP -------- Original message -------- From: Ryan Scott <[hidden email]> Date: 6/6/17 1:41 PM (GMT-05:00) To: Richard Eisenberg <[hidden email]> Cc: GHC developers <[hidden email]>, Eric Mertens <[hidden email]> Subject: Re: Hunting down a compilation performance regression involving type families This makes me wonder: can we get rid of this RULE? Eric Mertens pointed out a trick [1] that's used in the profunctors library to make mapping coerce over certain Profunctors more efficient. To adapt this trick for Functor, we'd need to add another class method: class Functor f where fmap :: (a -> b) -> f a -> f b (<#>) :: Coercible a b => (a -> b) -> f a -> f b (<#>) = \f -> \p -> p `seq` fmap f p Now, when implementing Functor instances, if we are working with a datatype whose role is representational or phantom, we can make (<#>) really fast: data List a = Nil | Cons a (List a) instance Functor List where fmap = ... (<#>) = coerce Now, instead of relying on (map MkNewtype Nil) to rewrite to Nil, we can just use (MkNewtype <#> Nil)! No map/coerce RULE necessary :) OK, I realize that suggesting that we remove the RULE is perhaps a touch too far. But it does sting that we have to pay hefty compilation penalties because of its existence... Ryan S. ----- [1] http://hackage.haskell.org/package/profunctors-5.2/docs/Data-Profunctor-Unsafe.html#v:-35- . On Wed, May 31, 2017 at 7:25 PM, Richard Eisenberg <[hidden email]> wrote: > > > On May 31, 2017, at 5:21 PM, Ryan Scott <[hidden email]> wrote: > > Does you know what might be going on here? > > I think so, but I don't know how to fix it. > > The commit you found (thank you!) makes simple_opt_expr (the "simple > optimizer", run directly after desugaring, even with -O0) a little more > selective in what `case` expressions it throws away. Previous to that > commit, the optimizer would throw away a `case error "deferred type error" > of _ -> ...` which is terrible. It seems that you have discovered that we > are now too timid in throwing away unhelpful cases. It would be interesting > to know what the newly-retained cases look like, so that we might throw > them away. > > But there remains a mystery: Why do we need this code at all? Reading Note > [Getting the map/coerce RULE to work] closely, it seems we need to simplify > > forall a b (co :: a ~R# b). > let dict = MkCoercible @* @a @b co in > case Coercible_SCSel @* @a @b dict of > _ [Dead] -> map @a @b (\(x :: a) -> case dict of > MkCoercible (co :: a ~R# b) -> x |> co) = let dict = ... in ... > > to > > forall a b (co :: a ~R# b). > map @a @b (\(x :: a) -> x |> co) = \(x :: [a]) -> x |> [co] > > Part of doing so is to drop the `case Coercible_SCSel ...`, which gets in > the way. The mystery is why this needs special code -- shouldn't the > eliminate-case-of-known-constructor do the trick? This would require > unfolding Coercible_SCSel. Does that happen? It would seem not... but maybe > it should, which would remove the special-case code that I changed in that > commit, and quite likely would simplify much more code besides. > > So: Is Coercible_SCSel unfolded during simple_opt? If not, what wonderful > or terrible things happen if we do? If so, why does > case-of-known-constructor not work here? My guess is that answering these > questions may solve the original problem, but this guess could be wrong. > > Richard > > _______________________________________________ ghc-devs mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs |
This a use case for ImplicationConstraints, or what On Jun 6, 2017 19:02, "David Feuer" <[hidden email]> wrote:
_______________________________________________ ghc-devs mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs |
In reply to this post by Ryan Scott
Ah yes, I believe you're referring to https://ghc.haskell.org/ But in any case, don't let this discussion side-track too much from the matter at hand (the type family compilation slowdown). My suggestion _was_ somewhat tongue-in-cheek, after all ;) Ryan S. On Tue, Jun 6, 2017 at 11:01 AM, David Feuer <[hidden email]> wrote:
_______________________________________________ ghc-devs mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs |
Free forum by Nabble | Edit this page |