GHC: Ticket #6048: Exponential inlining code blowup
http://ghc.haskell.org/trac/ghc/ticket/6048
<p>
(Transferring a new thread from <a class="new ticket" href="http://ghc.haskell.org/trac/ghc/ticket/5539" title="bug: GHC panic - Simplifier ticks exhausted (new)">#5539</a> to a new ticket, since it's really a separate problem.) kosmikus helpfully provided this program
</p>
<pre class="wiki">module TestCase where
import Control.Applicative
data X = X
(Maybe String)
(Maybe String)
(Maybe String)
(Maybe String)
(Maybe String)
(Maybe String)
(Maybe String)
(Maybe String)
(Maybe String)
mb :: (String -> Maybe a) -> String -> Maybe (Maybe a)
mb _ "" = Just Nothing
mb _ "-" = Just Nothing
mb p xs = Just <$> p xs
run :: [String] -> Maybe X
run
[ x1
, x2
, x3
, x4
, x5
, x6
, x7
, x8
, x9
] = X
<$> mb pure x1
<*> mb pure x2
<*> mb pure x3
<*> mb pure x4
<*> mb pure x5
<*> mb pure x6
<*> mb pure x7
<*> mb pure x8
<*> mb pure x9
</pre><p>
Unless <tt>mb</tt> is marked as <tt>NOINLINE</tt>, it gets expanded in the body of run a number of times that seems to grow exponentially with the size of the list (9 in the example).
</p>
en-usGHChttp://ghc.haskell.org/trac/ghc/chrome/site/ghc_logo.png
http://ghc.haskell.org/trac/ghc/ticket/6048
Trac 1.0.9simonpjThu, 26 Apr 2012 15:13:29 GMT
http://ghc.haskell.org/trac/ghc/ticket/6048#comment:1
http://ghc.haskell.org/trac/ghc/ticket/6048#comment:1
<p>
I know what is going on. It's a consequence of Max's patch
</p>
<pre class="wiki">commit dfe536be7d5d662ae75671797750b487c1ef59b7
Author: Max Bolingbroke <batterseapower@hotmail.com>
Date: Wed Mar 7 19:44:31 2012 +0000
Give a unfolding argument discount proportional to the number of available arguments
Ensures that h1 gets inlined into its use sites in cases like:
"""
h1 k = k undefined undefined undefined
undefined undefined undefined
undefined undefined undefined
undefined undefined undefined
undefined undefined undefined
undefined undefined undefined
a = h1 (\x _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ -> x)
b = h1 (\_ x _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ -> x)
"""
I've benchmarked this on nofib (albeit recompiling only the
benchmarks, not the library) and it hardly shifts the numbers - binary
size is up by 0.1% at most (average 0.0%) and the worst-case
allocation increase is 0.2% (best case -0.1%, 0.0% average).
If you also rebuild the libraries with this change, the only further
change is a +0.2% allocation increase in cacheprof. So this looks like
a pretty low-risk change that will considerably benefit certain
programs.
</pre><p>
In kosmikus's program we have lots of join points looking like
</p>
<pre class="wiki"> $j x = case .. of
p1 -> Just (x 3)
p2 -> Just (x 4)
</pre><p>
and stuff like that. Because of Max's patch, some very big join functions (size 350 or so) get very big discounts. The bigger the function, the more calls to 'x' there are, so the bigger the discount! So no matter how big the join point gets, it is still inlined. Hence the exponential behaviour, which starts with a case-of-case nest. No, this is not good.
</p>
<p>
Max's reasoning is describe in <tt>Note [Function application discount]</tt> in <tt>CoreUnfold</tt>, which I reproduce below for convenience. But the reasoning is flawed. Suppose we have
</p>
<pre class="wiki">let $j x = ....(x 3)...(x 4)....
h y = <BIG EXPR>
in
...($j h)...
</pre><p>
Then <tt>$j</tt> gets the massive discount for the applications of <tt>x</tt>. But when we inline <tt>$j</tt> we just get
</p>
<pre class="wiki"> ....(....(h 3)...(h 4)....).....
</pre><p>
and since <tt>h</tt> is big, there we stop. So the anticipated cancellation has not materialised. It really only materialises when
</p>
<ul><li>The parameter to <tt>$j</tt> is used once in <tt>$j</tt>'s body.
</li><li>The argument to the call of <tt>$j</tt> is a literal lambda.
</li></ul><p>
Unless Max has a better idea I'm going to revert his change. BTW kudos to Max for a detailed comment so we can actually see the reasoning.
</p>
<p>
Simon
</p>
<p>
Max's comment:
</p>
<pre class="wiki">Note [Function application discount]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
I noticed that the output of the supercompiler generates a lot of code
with this form:
"""
module Inlining where
h1 k = k undefined undefined undefined
undefined undefined undefined
undefined undefined undefined
undefined undefined undefined
undefined undefined undefined
undefined undefined undefined
a = h1 (\x _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ -> x)
b = h1 (\_ x _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ -> x)
c = h1 (\_ _ x _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ -> x)
d = h1 (\_ _ _ x _ _ _ _ _ _ _ _ _ _ _ _ _ _ -> x)
e = h1 (\_ _ _ _ x _ _ _ _ _ _ _ _ _ _ _ _ _ -> x)
f = h1 (\_ _ _ _ _ x _ _ _ _ _ _ _ _ _ _ _ _ -> x)
g = h1 (\_ _ _ _ _ _ x _ _ _ _ _ _ _ _ _ _ _ -> x)
h = h1 (\_ _ _ _ _ _ _ x _ _ _ _ _ _ _ _ _ _ -> x)
i = h1 (\_ _ _ _ _ _ _ _ x _ _ _ _ _ _ _ _ _ -> x)
j = h1 (\_ _ _ _ _ _ _ _ _ x _ _ _ _ _ _ _ _ -> x)
k = h1 (\_ _ _ _ _ _ _ _ _ _ x _ _ _ _ _ _ _ -> x)
l = h1 (\_ _ _ _ _ _ _ _ _ _ _ x _ _ _ _ _ _ -> x)
m = h1 (\_ _ _ _ _ _ _ _ _ _ _ _ x _ _ _ _ _ -> x)
n = h1 (\_ _ _ _ _ _ _ _ _ _ _ _ _ x _ _ _ _ -> x)
o = h1 (\_ _ _ _ _ _ _ _ _ _ _ _ _ _ x _ _ _ -> x)
p = h1 (\_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ x _ _ -> x)
q = h1 (\_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ x _ -> x)
r = h1 (\_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ x -> x)
"""
With GHC head the applications of h1 are not inlined, which hurts the
quality of the generated code a bit. I was wondering why h1 wasn't
getting inlined into each of "a" to "i" - after all, it has a manifest
lambda argument.
It turns out that the code in CoreUnfold gives a fixed discount of
opt_UF_FunAppDiscount to a function argument such as "k" if it applied
to any arguments. This is enough to ensure that h1 is inlined if the number
of arguments applied to k is below a certain limit, but if many arguments are
applied to k then the fixed discount can't overcome the size of the
chain of apps, and h1 is never inlined.
My proposed solution is to change CoreUnfold.funSize so that longer
chains of arguments being applied to a lambda-bound function give a
bigger discount. The motivation for this is that we would *generally*
expect that the lambda at the callsite has enough lambdas such that
all of the applications within the body can be beta-reduced away. This
change might lead to over eager inlining in cases like this, though:
{{{
h1 k = k x y z
{-# NOINLINE g #-}
g = ...
main = ... h1 (\x -> g x) ...
}}}
In this case we aren't able to beta-reduce away all of the
applications in the body of h1 because the lambda at the call site
only binds 1 argument, not the 3 allowed by the type. I don't expect
this case to be particularly common, however.
I chose the bonus to be (size - 20) so that application to 1 arg got
same bonus as the old fixed bonus (i.e. opt_UF_FunAppDiscount, which is 60).
If you have the bonus being (size - 40) then $fMonad[]_$c>>= with interesting
2nd arg doesn't inline in cryptarithm2 so we lose some deforestation, and
overall binary size hardly falls.
</pre>
Ticketsimonpj@…Wed, 09 May 2012 16:56:32 GMT
http://ghc.haskell.org/trac/ghc/ticket/6048#comment:2
http://ghc.haskell.org/trac/ghc/ticket/6048#comment:2
<p>
commit <a class="changeset" href="http://ghc.haskell.org/trac/ghc/changeset/980372f357667c1ba63b28acbf5798826890b7a5/ghc" title="Re-do the "function application discount" (fixes Trac #6048)
* Undoes ...">980372f357667c1ba63b28acbf5798826890b7a5</a>
</p>
<pre class="wiki">Author: Simon Peyton Jones <simonpj@microsoft.com>
Date: Wed May 9 16:22:49 2012 +0100
Re-do the "function application discount" (fixes Trac #6048)
* Undoes Max's very aggressive function-inlining change
(see comments with Trac #6048)
* Resticts function application discount to functions
that occur just once in the body. It was the multiple
occurrences that led to the exponential behavour in
Trac #6048.
See Note [Function application discount] in CoreUnfold.
Module binary sizes are down 2% on average, which is good.
Allocations wobble about a bit, but only on a few benchmarks
and not by much, so it seems a price worth paying to avoid
exponential behaviour!
Allocs
Min -1.2%
Max +2.8%
Geometric Mean +0.0%
compiler/coreSyn/CoreUnfold.lhs | 122 +++++++++++----------------------------
1 files changed, 35 insertions(+), 87 deletions(-)
</pre>
TicketsimonpjWed, 09 May 2012 17:02:35 GMTstatus changed; testcase, resolution set
http://ghc.haskell.org/trac/ghc/ticket/6048#comment:3
http://ghc.haskell.org/trac/ghc/ticket/6048#comment:3
<ul>
<li><strong>testcase</strong>
set to <em>perf/compiler/T6048</em>
</li>
<li><strong>status</strong>
changed from <em>new</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
</ul>
<p>
Really nice example. Thank you for making it so compelling. Fixed!
</p>
Ticket