Issues resulting from inlining build
I think I finally figured out the deeper problem behind an issue I was having getting some things to fuse fully. I'm hoping someone has a brilliant idea for getting around it. Of course, it may be that someone else has thoroughly studied the matter and determined that there's no good solution. Suppose we write crazy :: T -> [U] crazy x = some $ long $ fusion $ pipeline oops f = map f $ crazy x uhOh c n = foldr c n $ crazy Pig ohMy = take bignum $ crazy amigo When GHC compiles crazy, it rewrites the pieces of the pipeline to build/foldr forms, fuses them, and produces crazy x = build someBigFunction In then inlines build, producing crazy x = anotherBiggy So far, this looks reasonably sensible, but it's likely bad. The problem is that GHC will (rightly) conclude that `build someBigFunction` is too big to inline, and therefore the fusion will break at that boundary and we'll produce intermediate lists in the functions that use crazy. Now if we were playing the part of the compiler by hand, we would likely factor out someBigFunction and then *refrain from inlining build*. That is, we would get {-# NOINLINE crazyB #-} crazyB x = someBigFunction crazy = nonInliningBuild crazyB Since we've factored out someBigFunction into crazyB, we can now safely inline crazy itself, allowing the pipeline to continue beyond it. The problem, of course, is that when we *don't* fuse beyond, there is some performance penalty (I have not tried to measure it yet) to passing in (:) and [] at runtime instead of fixing them at compile time.
Hi, Am Sonntag, den 27.07.2014, 15:29 -0400 schrieb David Feuer:
I think I finally figured out the deeper problem behind an issue I was having getting some things to fuse fully. I'm hoping someone has a brilliant idea for getting around it. Of course, it may be that someone else has thoroughly studied the matter and determined that there's no good solution. Suppose we write
crazy :: T -> [U] crazy x = some $ long $ fusion $ pipeline
oops f = map f $ crazy x uhOh c n = foldr c n $ crazy Pig ohMy = take bignum $ crazy amigo
When GHC compiles crazy, it rewrites the pieces of the pipeline to build/foldr forms, fuses them, and produces
crazy x = build someBigFunction
In then inlines build, producing
crazy x = anotherBiggy
So far, this looks reasonably sensible, but it's likely bad.
It is good for the uses of crazy where no further fusion happens. For the other cases, I believe GHC will rather try to get the original definition inlined. Maybe alredy "some $ long $ fusion $ pipeline" was deemed to big to be inlined – in that case an {-# INLINEABLE crazy #-} could help.
The problem is that GHC will (rightly) conclude that `build someBigFunction` is too big to inline, and therefore the fusion will break at that boundary and we'll produce intermediate lists in the functions that use crazy. Now if we were playing the part of the compiler by hand, we would likely factor out someBigFunction and then *refrain from inlining build*. That is, we would get
{-# NOINLINE crazyB #-} crazyB x = someBigFunction
crazy = nonInliningBuild crazyB
Since we've factored out someBigFunction into crazyB, we can now safely inline crazy itself, allowing the pipeline to continue beyond it. The problem, of course, is that when we *don't* fuse beyond, there is some performance penalty (I have not tried to measure it yet) to passing in (:) and [] at runtime instead of fixing them at compile time.
There is another downside to this: This way, with fusion, you will get rid of the intermediate list, but you will have calls from someBigFunction to unknown functions, which is slow. The nice thing about fusion is not just getting rid of the list, but also the local optimizations that happen when the new “cons” and “nil” get in touch with the code in someBigFunction. So the approach taken seems to be: Either inline "some $ long $ fusion $ pipeline" and do all the transformation at the use site, or call "anotherBiggy", but nothing in between. 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
On Jul 27, 2014 3:48 PM, "Joachim Breitner"
Am Sonntag, den 27.07.2014, 15:29 -0400 schrieb David Feuer: It is good for the uses of crazy where no further fusion happens.
Yes, I know that.
For the other cases, I believe GHC will rather try to get the original definition inlined. Maybe alredy "some $ long $ fusion $ pipeline" was deemed to big to be inlined – in that case an {-# INLINEABLE crazy #-} could help.
Right, I *could* do that, but then there's a potential for "code explosion" from inlining something too big at a lot of call sites.
it. The problem, of course, is that when we *don't* fuse beyond, there is some performance penalty (I have not tried to measure it yet) to passing in (:) and [] at runtime instead of fixing them at compile time.
There is another downside to this: This way, with fusion, you will get rid of the intermediate list, but you will have calls from someBigFunction to unknown functions, which is slow.
Yes, that was included by reference.
The nice thing about fusion is not just getting rid of the list, but also the local optimizations that happen when the new “cons” and “nil” get in touch with the code in someBigFunction.
Yes, that's definitely a benefit. My point is that when you *have* to break things up (necessarily sacrificing opportunities for further analysis), it's often better to break between the build and its argument than before the build. Either way, you're giving up the opportunities you describe, but breaking before the build you also get the allocation. Context: I was doing some simple testing of my proposed replacement of unfoldr with an inlinable, fusable version. I managed to hit one of those wonky little cutoffs. When I wrote something in the general nature of f :: Int -> [Int] f n = map (+1) $ unfoldr go 0 where go k | k <= n = Just (k, k+1) | otherwise = Nothing g :: Int -> Int g n = foldr (*) 1 $ f n Then when f was exported, it was not inlined, and didn't fuse with the foldr in g, so there was a ton of allocation running g, whereas when f was not exported, it fused completely.
Think of this like worker/wrapper. Given ‘crazy’, with some large body, you want to turn it into crazy x = build (\cn. craxy’ c n x) {-# INLINE crazy #-} Now you can inline crazy everywhere, which will allow a consuming foldr to cancel with the build. And without duplicating all the code. But if there *is* no foldr, you’ll end up with calls like (crazy’ (:) []) , which will be considerably less efficient than the original function. So you really want *both* crazy’ and crazy’ specialised to (:) and []. GHC doesn’t do this automatically, because it really works well if the body of crazy is a good producer. But you could imagine automating it. Simon From: Libraries [mailto:libraries-bounces@haskell.org] On Behalf Of David Feuer Sent: 27 July 2014 20:29 To: Haskell Libraries Subject: Issues resulting from inlining build I think I finally figured out the deeper problem behind an issue I was having getting some things to fuse fully. I'm hoping someone has a brilliant idea for getting around it. Of course, it may be that someone else has thoroughly studied the matter and determined that there's no good solution. Suppose we write crazy :: T -> [U] crazy x = some $ long $ fusion $ pipeline oops f = map f $ crazy x uhOh c n = foldr c n $ crazy Pig ohMy = take bignum $ crazy amigo When GHC compiles crazy, it rewrites the pieces of the pipeline to build/foldr forms, fuses them, and produces crazy x = build someBigFunction In then inlines build, producing crazy x = anotherBiggy So far, this looks reasonably sensible, but it's likely bad. The problem is that GHC will (rightly) conclude that `build someBigFunction` is too big to inline, and therefore the fusion will break at that boundary and we'll produce intermediate lists in the functions that use crazy. Now if we were playing the part of the compiler by hand, we would likely factor out someBigFunction and then *refrain from inlining build*. That is, we would get {-# NOINLINE crazyB #-} crazyB x = someBigFunction crazy = nonInliningBuild crazyB Since we've factored out someBigFunction into crazyB, we can now safely inline crazy itself, allowing the pipeline to continue beyond it. The problem, of course, is that when we *don't* fuse beyond, there is some performance penalty (I have not tried to measure it yet) to passing in (:) and [] at runtime instead of fixing them at compile time.
participants (3)
-
David Feuer -
Joachim Breitner -
Simon Peyton Jones