On Dec 16, 2014, at 2:59 AM, Jan Stolarek wrote:

What does your algorithm look like when you write it directly? Something like this:

flatten_many fmode roles tys = unzip `liftM` mapM go (zip roles tys) where go (Nominal,ty) = flatten_one (fmode { fe_eq_rel = NomEq }) ty go (Representational,ty) = flatten_one (fmode { fe_eq_rel = ReprEq }) ty go (Phantom, ty) = -- See Note [Phantoms in the flattener] return (ty, mkTcPhantomCo ty ty)

?

Maybe this has something to do with `zipWithAndUnzipM` not being tail-recursive vs. direct version being able to fuse intermediate lists?

My direct version is even uglier:

flatten_many fmode roles tys = go roles tys where go (Nominal:rs) (ty:tys) = do { (xi, co) <- flatten_one (setFEEqRel fmode NomEq) ty ; (xis, cos) <- go rs tys ; return (xi:xis, co:cos) } go (Representational:rs) (ty:tys) = do { (xi, co) <- flatten_one (setFEEqRel fmode ReprEq) ty ; (xis, cos) <- go rs tys ; return (xi:xis, co:cos) } go (Phantom:rs) (ty:tys) = do { (xis, cos) <- go rs tys ; -- See Note [Phantoms in the flattener] return (ty:xis, mkTcPhantomCo ty ty:cos) } go _ _ = return ([], [])

I could refactor to make it better, but I would be worried that the version you wrote would suffer from the same problems as zipWithAndUnzipM. Will check to see, though. On Dec 16, 2014, at 4:01 AM, Joachim Breitner wrote:

another guess (without looking at the code, sorry): Are they in the same module? I.e., can GHC specialize the code to your particular Monad?

No, they're not in the same module. I could also try moving the zipWithAndUnzipM function to the same module, and even specializing it by hand to the right monad. Could that be preventing the fusing? On Dec 16, 2014, at 8:49 AM, Simon Peyton Jones wrote:

That seems surprising. I'd build a profiled compiler (GhcProfiled=YES) and see what it says.

If it increases allocation by 30% overall, there must be a LOT of calls to this function. Should there be so many?

I've been working from a profiled compiler. That's how I found that this function was the culprit -- it certainly wasn't my first guess! Yes, there are A LOT of calls: 7,106,808 to be exact. (The test case is perf/compiler/T9872a; the function is flatten_many). The number of calls doesn't vary from before my commit, though, so the raw number isn't the problem -- it's the allocation. I'll try turning some of these knobs to see where the difference is. Thanks, Richard

I've learned several very interesting things in this analysis. - Inlining polymorphic methods is very important. Here are some data points to back up that claim: * Original implementation using zipWithAndUnzipM: 8,472,613,440 bytes allocated in the heap * Adding {-# INLINE #-} to the definition thereof: 6,639,253,488 bytes allocated in the heap * Using `inline` at call site to force inlining: 6,281,539,792 bytes allocated in the heap The middle step above allowed GHC to specialize zipWithAndUnzipM to my particular monad, but GHC didn't see fit to actually inline the function. Using `inline` forced it, to good effect. (I did not collect data on code sizes, but it wouldn't be hard to.) By comparison: * Hand-written recursion: 6,587,809,112 bytes allocated in the heap Interestingly, this is *not* the best result! Conclusion: We should probably add INLINE pragmas to Util and MonadUtils. - I then looked at rejiggering the algorithm to keep the common case fast. This had a side effect of changing the zipWithAndUnzipM to mapAndUnzipM, from Control.Monad. To my surprise, this brought disaster! * Using `inline` and mapAndUnzipM: 7,463,047,432 bytes allocated in the heap * Hand-written recursion: 5,848,602,848 bytes allocated in the heap That last number is better than the numbers above because of the algorithm streamlining. But, the inadequacy of mapAndUnzipM surprised me -- it already has an INLINE pragma in Control.Monad of course. Looking at -ddump-simpl, it seems that mapAndUnzipM was indeed getting inlined, but a call to `map` remained, perhaps causing extra allocation. Conclusion: We should examine the implementation of mapAndUnzipM (and similar functions) in Control.Monad. Is it as fast as possible? In the end, I was unable to bring the allocation numbers down to where they were before my work. This is because the flattener now deals in roles. Most of its behavior is the same between nominal and representational roles, so it seems silly (though very possible) to specialize the code to nominal to keep that path fast. Instead, I identified one key spot and made that go fast. Thus, there is a 7% bump to memory usage on very-type-family-heavy code, compared to before my commit on Friday. (On more ordinary code, there is no noticeable change.) Validating my patch locally now; will push when that's done. Thanks, Richard On Dec 16, 2014, at 10:41 AM, Joachim Breitner wrote:

Hi,

Am Dienstag, den 16.12.2014, 09:59 -0500 schrieb Richard Eisenberg:

...

On Dec 16, 2014, at 4:01 AM, Joachim Breitner wrote:

...

another guess (without looking at the code, sorry): Are they in the same module? I.e., can GHC specialize the code to your particular Monad?

...

No, they're not in the same module. I could also try moving the zipWithAndUnzipM function to the same module, and even specializing it by hand to the right monad.

I did mean zipWithAndUnzipM, so maybe yes: Try that.

(I find it hard to believe that any polymorphic monadic code should perform well, with those many calls to an unknown (>>=) with a function parameter, but maybe I’m too pessimistic here.)

...

Could that be preventing the fusing?

There is not going to be any fusing here, at least not list fusion; that would require your code to be written in terms of functions with fusion rules.

Greetings, Joachim

-- Joachim “nomeata” Breitner mail@joachim-breitner.de • http://www.joachim-breitner.de/ Jabber: nomeata@joachim-breitner.de • GPG-Key: 0xF0FBF51F Debian Developer: nomeata@debian.org

_______________________________________________ ghc-devs mailing list ghc-devs@haskell.org http://www.haskell.org/mailman/listinfo/ghc-devs

If you use INLINEABLE, that should make the function specialisable to a particular monad, even if it's in a different module. You shouldn't need INLINE for that. I don't understand the difference between cases (2) and (3). I am still suspicious of why there are so many calls to this one function that it, alone, is allocating a significant proportion of compilation of the entire run of GHC. Are you sure there isn't an algorithmic improvement to be had, to simply reduce the number of calls? Simon | -----Original Message----- | From: ghc-devs [mailto:ghc-devs-bounces@haskell.org] On Behalf Of | Richard Eisenberg | Sent: 16 December 2014 21:46 | To: Joachim Breitner | Cc: ghc-devs@haskell.org | Subject: Re: performance regressions | | I've learned several very interesting things in this analysis. | | - Inlining polymorphic methods is very important. Here are some data | points to back up that claim: | * Original implementation using zipWithAndUnzipM: 8,472,613,440 | bytes allocated in the heap | * Adding {-# INLINE #-} to the definition thereof: 6,639,253,488 | bytes allocated in the heap | * Using `inline` at call site to force inlining: 6,281,539,792 | bytes allocated in the heap | | The middle step above allowed GHC to specialize zipWithAndUnzipM to my | particular monad, but GHC didn't see fit to actually inline the | function. Using `inline` forced it, to good effect. (I did not collect | data on code sizes, but it wouldn't be hard to.) | | By comparison: | * Hand-written recursion: 6,587,809,112 bytes allocated in the | heap | Interestingly, this is *not* the best result! | | Conclusion: We should probably add INLINE pragmas to Util and | MonadUtils. | | | - I then looked at rejiggering the algorithm to keep the common case | fast. This had a side effect of changing the zipWithAndUnzipM to | mapAndUnzipM, from Control.Monad. To my surprise, this brought | disaster! | * Using `inline` and mapAndUnzipM: 7,463,047,432 bytes | allocated in the heap | * Hand-written recursion: 5,848,602,848 bytes | allocated in the heap | | That last number is better than the numbers above because of the | algorithm streamlining. But, the inadequacy of mapAndUnzipM surprised | me -- it already has an INLINE pragma in Control.Monad of course. | Looking at -ddump-simpl, it seems that mapAndUnzipM was indeed getting | inlined, but a call to `map` remained, perhaps causing extra | allocation. | | Conclusion: We should examine the implementation of mapAndUnzipM (and | similar functions) in Control.Monad. Is it as fast as possible? | | | | In the end, I was unable to bring the allocation numbers down to where | they were before my work. This is because the flattener now deals in | roles. Most of its behavior is the same between nominal and | representational roles, so it seems silly (though very possible) to | specialize the code to nominal to keep that path fast. Instead, I | identified one key spot and made that go fast. | | Thus, there is a 7% bump to memory usage on very-type-family-heavy | code, compared to before my commit on Friday. (On more ordinary code, | there is no noticeable change.) | | Validating my patch locally now; will push when that's done. | | Thanks, | Richard | | On Dec 16, 2014, at 10:41 AM, Joachim Breitner wrote: | | > Hi, | > | > | > Am Dienstag, den 16.12.2014, 09:59 -0500 schrieb Richard Eisenberg: | >> On Dec 16, 2014, at 4:01 AM, Joachim Breitner wrote: | >> | >>> another guess (without looking at the code, sorry): Are they in | the | >>> same module? I.e., can GHC specialize the code to your particular | Monad? | > | >> No, they're not in the same module. I could also try moving the | >> zipWithAndUnzipM function to the same module, and even specializing | >> it by hand to the right monad. | > | > I did mean zipWithAndUnzipM, so maybe yes: Try that. | > | > (I find it hard to believe that any polymorphic monadic code should | > perform well, with those many calls to an unknown (>>=) with a | > function parameter, but maybe I'm too pessimistic here.) | > | > | >> Could that be preventing the fusing? | > | > There is not going to be any fusing here, at least not list fusion; | > that would require your code to be written in terms of functions | with | > fusion rules. | > | > Greetings, | > Joachim | > | > -- | > Joachim "nomeata" Breitner | > mail@joachim-breitner.de * http://www.joachim-breitner.de/ | > Jabber: nomeata@joachim-breitner.de * GPG-Key: 0xF0FBF51F Debian | > Developer: nomeata@debian.org | > | > _______________________________________________ | > ghc-devs mailing list | > ghc-devs@haskell.org | > http://www.haskell.org/mailman/listinfo/ghc-devs | | _______________________________________________ | ghc-devs mailing list | ghc-devs@haskell.org | http://www.haskell.org/mailman/listinfo/ghc-devs

I still would like to understand why INLINE does not make it inline. That's weird. Eg way to reproduce. Simion | -----Original Message----- | From: Richard Eisenberg [mailto:eir@cis.upenn.edu] | Sent: 17 December 2014 15:56 | To: Simon Peyton Jones | Cc: Joachim Breitner; ghc-devs@haskell.org | Subject: Re: performance regressions | | By unsubstantiated guess is that INLINEABLE would have the same effect | as INLINE here, as GHC doesn't see fit to actually inline the | function, even with INLINE -- the big improvement seen between (1) and | (2) is actually specialization, not inlining. The jump from (2) to (3) | is actual inlining. Thus, it seems that GHC's heuristics for inlining | aren't working out for the best here. | | I've pushed my changes, though I agree with Simon that more research | may uncover even more improvements here. I didn't focus on the number | of calls because that number didn't regress. Will look into this soon. | | Richard | | On Dec 17, 2014, at 4:15 AM, Simon Peyton Jones | wrote: | | > If you use INLINEABLE, that should make the function specialisable | to a particular monad, even if it's in a different module. You | shouldn't need INLINE for that. | > | > I don't understand the difference between cases (2) and (3). | > | > I am still suspicious of why there are so many calls to this one | function that it, alone, is allocating a significant proportion of | compilation of the entire run of GHC. Are you sure there isn't an | algorithmic improvement to be had, to simply reduce the number of | calls? | > | > Simon | > | > | -----Original Message----- | > | From: ghc-devs [mailto:ghc-devs-bounces@haskell.org] On Behalf Of | > | Richard Eisenberg | > | Sent: 16 December 2014 21:46 | > | To: Joachim Breitner | > | Cc: ghc-devs@haskell.org | > | Subject: Re: performance regressions | > | | > | I've learned several very interesting things in this analysis. | > | | > | - Inlining polymorphic methods is very important. Here are some | > | data points to back up that claim: | > | * Original implementation using zipWithAndUnzipM: | 8,472,613,440 | > | bytes allocated in the heap | > | * Adding {-# INLINE #-} to the definition thereof: | 6,639,253,488 | > | bytes allocated in the heap | > | * Using `inline` at call site to force inlining: | 6,281,539,792 | > | bytes allocated in the heap | > | | > | The middle step above allowed GHC to specialize zipWithAndUnzipM | to | > | my particular monad, but GHC didn't see fit to actually inline | the | > | function. Using `inline` forced it, to good effect. (I did not | > | collect data on code sizes, but it wouldn't be hard to.) | > | | > | By comparison: | > | * Hand-written recursion: 6,587,809,112 bytes allocated in | the | > | heap | > | Interestingly, this is *not* the best result! | > | | > | Conclusion: We should probably add INLINE pragmas to Util and | > | MonadUtils. | > | | > | | > | - I then looked at rejiggering the algorithm to keep the common | > | case fast. This had a side effect of changing the | zipWithAndUnzipM | > | to mapAndUnzipM, from Control.Monad. To my surprise, this brought | > | disaster! | > | * Using `inline` and mapAndUnzipM: 7,463,047,432 bytes | > | allocated in the heap | > | * Hand-written recursion: 5,848,602,848 bytes | > | allocated in the heap | > | | > | That last number is better than the numbers above because of the | > | algorithm streamlining. But, the inadequacy of mapAndUnzipM | > | surprised me -- it already has an INLINE pragma in Control.Monad | of course. | > | Looking at -ddump-simpl, it seems that mapAndUnzipM was indeed | > | getting inlined, but a call to `map` remained, perhaps causing | > | extra allocation. | > | | > | Conclusion: We should examine the implementation of mapAndUnzipM | > | (and similar functions) in Control.Monad. Is it as fast as | possible? | > | | > | | > | | > | In the end, I was unable to bring the allocation numbers down to | > | where they were before my work. This is because the flattener now | > | deals in roles. Most of its behavior is the same between nominal | > | and representational roles, so it seems silly (though very | > | possible) to specialize the code to nominal to keep that path | fast. | > | Instead, I identified one key spot and made that go fast. | > | | > | Thus, there is a 7% bump to memory usage on very-type-family- | heavy | > | code, compared to before my commit on Friday. (On more ordinary | > | code, there is no noticeable change.) | > | | > | Validating my patch locally now; will push when that's done. | > | | > | Thanks, | > | Richard | > | | > | On Dec 16, 2014, at 10:41 AM, Joachim Breitner | breitner.de> wrote: | > | | > | > Hi, | > | > | > | > | > | > Am Dienstag, den 16.12.2014, 09:59 -0500 schrieb Richard | Eisenberg: | > | >> On Dec 16, 2014, at 4:01 AM, Joachim Breitner | breitner.de> wrote: | > | >> | > | >>> another guess (without looking at the code, sorry): Are they | in | > | the >>> same module? I.e., can GHC specialize the code to your | > | particular Monad? | > | > | > | >> No, they're not in the same module. I could also try moving | the | > | >> zipWithAndUnzipM function to the same module, and even | > | specializing >> it by hand to the right monad. | > | > | > | > I did mean zipWithAndUnzipM, so maybe yes: Try that. | > | > | > | > (I find it hard to believe that any polymorphic monadic code | > | should > perform well, with those many calls to an unknown (>>=) | > | with a > function parameter, but maybe I'm too pessimistic here.) | > | > > >> Could that be preventing the fusing? | > | > | > | > There is not going to be any fusing here, at least not list | > | fusion; > that would require your code to be written in terms of | > | functions with > fusion rules. | > | > | > | > Greetings, | > | > Joachim | > | > | > | > -- | > | > Joachim "nomeata" Breitner | > | > mail@joachim-breitner.de * http://www.joachim-breitner.de/ > | > | Jabber: nomeata@joachim-breitner.de * GPG-Key: 0xF0FBF51F Debian | > | > Developer: nomeata@debian.org > > | > | _______________________________________________ | > | > ghc-devs mailing list | > | > ghc-devs@haskell.org | > | > http://www.haskell.org/mailman/listinfo/ghc-devs | > | | > | _______________________________________________ | > | ghc-devs mailing list | > | ghc-devs@haskell.org | > | http://www.haskell.org/mailman/listinfo/ghc-devs | >

I've gained a little more insight here, but only a little. INLINE doesn't work because zipWithAndUnzipM is recursive. Oddly, using worker/wrapper made allocations go *up*, so that's somehow not the answer. When I use `inline`, GHC will inline the function once; recursive calls remain. This seems to the local minimum in allocations. Using `inline` gives roughly a 7% allocation level change on this pathological case. To reproduce, just compile HEAD's TcFlatten with and without the call to `inline`. You can see, using -ddump-simpl, what GHC is doing. Then, you can check the allocation numbers by compiling perf/compiler/T9872a.hs. My tests were all using the default build settings, with an unmodified build.mk, as that seemed to be the most performant setting. In other news, a slight change to the algorithm (see #9872, comment 23) makes a 50% improvement. Will hopefully commit tonight, after a full local validation run. Richard On Dec 17, 2014, at 10:59 AM, Simon Peyton Jones wrote:

I still would like to understand why INLINE does not make it inline. That's weird.

Eg way to reproduce.

Simion

| -----Original Message----- | From: Richard Eisenberg [mailto:eir@cis.upenn.edu] | Sent: 17 December 2014 15:56 | To: Simon Peyton Jones | Cc: Joachim Breitner; ghc-devs@haskell.org | Subject: Re: performance regressions | | By unsubstantiated guess is that INLINEABLE would have the same effect | as INLINE here, as GHC doesn't see fit to actually inline the | function, even with INLINE -- the big improvement seen between (1) and | (2) is actually specialization, not inlining. The jump from (2) to (3) | is actual inlining. Thus, it seems that GHC's heuristics for inlining | aren't working out for the best here. | | I've pushed my changes, though I agree with Simon that more research | may uncover even more improvements here. I didn't focus on the number | of calls because that number didn't regress. Will look into this soon. | | Richard | | On Dec 17, 2014, at 4:15 AM, Simon Peyton Jones | wrote: | | > If you use INLINEABLE, that should make the function specialisable | to a particular monad, even if it's in a different module. You | shouldn't need INLINE for that. | > | > I don't understand the difference between cases (2) and (3). | > | > I am still suspicious of why there are so many calls to this one | function that it, alone, is allocating a significant proportion of | compilation of the entire run of GHC. Are you sure there isn't an | algorithmic improvement to be had, to simply reduce the number of | calls? | > | > Simon | > | > | -----Original Message----- | > | From: ghc-devs [mailto:ghc-devs-bounces@haskell.org] On Behalf Of | > | Richard Eisenberg | > | Sent: 16 December 2014 21:46 | > | To: Joachim Breitner | > | Cc: ghc-devs@haskell.org | > | Subject: Re: performance regressions | > | | > | I've learned several very interesting things in this analysis. | > | | > | - Inlining polymorphic methods is very important. Here are some | > | data points to back up that claim: | > | * Original implementation using zipWithAndUnzipM: | 8,472,613,440 | > | bytes allocated in the heap | > | * Adding {-# INLINE #-} to the definition thereof: | 6,639,253,488 | > | bytes allocated in the heap | > | * Using `inline` at call site to force inlining: | 6,281,539,792 | > | bytes allocated in the heap | > | | > | The middle step above allowed GHC to specialize zipWithAndUnzipM | to | > | my particular monad, but GHC didn't see fit to actually inline | the | > | function. Using `inline` forced it, to good effect. (I did not | > | collect data on code sizes, but it wouldn't be hard to.) | > | | > | By comparison: | > | * Hand-written recursion: 6,587,809,112 bytes allocated in | the | > | heap | > | Interestingly, this is *not* the best result! | > | | > | Conclusion: We should probably add INLINE pragmas to Util and | > | MonadUtils. | > | | > | | > | - I then looked at rejiggering the algorithm to keep the common | > | case fast. This had a side effect of changing the | zipWithAndUnzipM | > | to mapAndUnzipM, from Control.Monad. To my surprise, this brought | > | disaster! | > | * Using `inline` and mapAndUnzipM: 7,463,047,432 bytes | > | allocated in the heap | > | * Hand-written recursion: 5,848,602,848 bytes | > | allocated in the heap | > | | > | That last number is better than the numbers above because of the | > | algorithm streamlining. But, the inadequacy of mapAndUnzipM | > | surprised me -- it already has an INLINE pragma in Control.Monad | of course. | > | Looking at -ddump-simpl, it seems that mapAndUnzipM was indeed | > | getting inlined, but a call to `map` remained, perhaps causing | > | extra allocation. | > | | > | Conclusion: We should examine the implementation of mapAndUnzipM | > | (and similar functions) in Control.Monad. Is it as fast as | possible? | > | | > | | > | | > | In the end, I was unable to bring the allocation numbers down to | > | where they were before my work. This is because the flattener now | > | deals in roles. Most of its behavior is the same between nominal | > | and representational roles, so it seems silly (though very | > | possible) to specialize the code to nominal to keep that path | fast. | > | Instead, I identified one key spot and made that go fast. | > | | > | Thus, there is a 7% bump to memory usage on very-type-family- | heavy | > | code, compared to before my commit on Friday. (On more ordinary | > | code, there is no noticeable change.) | > | | > | Validating my patch locally now; will push when that's done. | > | | > | Thanks, | > | Richard | > | | > | On Dec 16, 2014, at 10:41 AM, Joachim Breitner | breitner.de> wrote: | > | | > | > Hi, | > | > | > | > | > | > Am Dienstag, den 16.12.2014, 09:59 -0500 schrieb Richard | Eisenberg: | > | >> On Dec 16, 2014, at 4:01 AM, Joachim Breitner | breitner.de> wrote: | > | >> | > | >>> another guess (without looking at the code, sorry): Are they | in | > | the >>> same module? I.e., can GHC specialize the code to your | > | particular Monad? | > | > | > | >> No, they're not in the same module. I could also try moving | the | > | >> zipWithAndUnzipM function to the same module, and even | > | specializing >> it by hand to the right monad. | > | > | > | > I did mean zipWithAndUnzipM, so maybe yes: Try that. | > | > | > | > (I find it hard to believe that any polymorphic monadic code | > | should > perform well, with those many calls to an unknown (>>=) | > | with a > function parameter, but maybe I'm too pessimistic here.) | > | > > >> Could that be preventing the fusing? | > | > | > | > There is not going to be any fusing here, at least not list | > | fusion; > that would require your code to be written in terms of | > | functions with > fusion rules. | > | > | > | > Greetings, | > | > Joachim | > | > | > | > -- | > | > Joachim "nomeata" Breitner | > | > mail@joachim-breitner.de * http://www.joachim-breitner.de/ > | > | Jabber: nomeata@joachim-breitner.de * GPG-Key: 0xF0FBF51F Debian | > | > Developer: nomeata@debian.org > > | > | _______________________________________________ | > | > ghc-devs mailing list | > | > ghc-devs@haskell.org | > | > http://www.haskell.org/mailman/listinfo/ghc-devs | > | | > | _______________________________________________ | > | ghc-devs mailing list | > | ghc-devs@haskell.org | > | http://www.haskell.org/mailman/listinfo/ghc-devs | >

Hi, Am Montag, den 15.12.2014, 23:48 -0500 schrieb Richard Eisenberg:

Can anyone tell me: why? Have I made some horrible mistake in the implementation? And, relatedly: how can I fix this? I want to learn from this experience how to avoid this problem next time...

another guess (without looking at the code, sorry): Are they in the same module? I.e., can GHC specialize the code to your particular Monad? Greetings, Joachim -- Joachim Breitner e-Mail: mail@joachim-breitner.de Homepage: http://www.joachim-breitner.de Jabber-ID: nomeata@joachim-breitner.de