Hunting down a compilation performance regression involving type families

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Hunting down a compilation performance regression involving type families

Ryan Scott
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
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Hunting down a compilation performance regression involving type families

Richard Eisenberg-4

> 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
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Hunting down a compilation performance regression involving type families

Ryan Scott
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:

> 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
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Hunting down a compilation performance regression involving type families

David Feuer-2
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

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.
-----
[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
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Hunting down a compilation performance regression involving type families

Baldur Blöndal
This a use case for ImplicationConstraints, or what

On Jun 6, 2017 19:02, "David Feuer" <[hidden email]> wrote:
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

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.
-----
[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


_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Hunting down a compilation performance regression involving type families

Ryan Scott
In reply to this post by Ryan Scott
Ah yes, I believe you're referring to https://ghc.haskell.org/trac/ghc/ticket/8767 (which I wasn't aware of). And yes, I do believe we'd need some combination of QuantifiedContexts/ImplicationConstraints to fully support everything.

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:
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

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.
-----
[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
Loading...