Re: Sigh. Inlining heuristics.

[Daniel Berlin <dan at cgsoftware dot com>]

Daniel Berlin <dan@cgsoftware.com> writes:

Also note that we don't have the architecture to be super aggressive
at inlining and good at it.
We've pretty much proven that we suck at it right now.  We increase
compile times dramatically with little to show for it on the C++ side.  If anybody
vehemently disagrees with this, then we're going to have to agree to
disagree, and i'll just withdraw the patch and put it in my local
tree.
I feel since there is an "inline" keyword to force inlining, and no
"noinline" keyword, and we always inline "inline" stuff, it's easy
enough to tell a moderately smart but sometimes stupid inliner to
inline something.  However, we can't tell the super aggressive inliner to stop
right now, we only have a max insn per root of inline tree cutoff.
I'm trying to do both. Give a way to say "don't bloat my code and
compile times by inlining till you've made one huge function out of my
entire module that is 2% faster but took 45x longer to compile", while
trying to teach it to not do overly stupid things that decrease
performance and increase compile time, even if it means missing 10 or
20% of smart things, but decreasing compile time by a factor of 4
(which is what it does on even simple cases. 31 seconds to 7).
Basically, i think the performance degradation from inlining
absolutely everything costs more than the performance increase we
might miss with the new heuristic.  If i'm wrong, put inline next to
your function. :)  We can't be perfect with any heuristic (otherwise
it would be a total solution, not a heuristic), and if someone thinks
they can do better, feel free. Let me know if i can help.
But if we had the profiling info to prove this, we'd just inline based
on that anyway. And as I said to Carlo, i'm happy to improve the heuristic to take
certain things into account that we can currently do. I can try
inlining if the argument is constant.   Hopefully, we
won't need this heruistic for 3.1, we'll have enough architecture to
do something much smarter.
I read a lot of papers on inlining techniques before coming up with
this heuristic. It's not something I pulled out of thin air. :)
Most assume enough of an architecture to really bound
excessive code growth/keep the inliner from spending tons of time
inlining procedures statistically not going to give us a lot of gain.
We don't have this. It's being worked on by multiple people.
 Maybe we will for 3.1, maybe we won't
But we need something as a fallback, and what we have clearly has problems.
Ideally, we'd probably want to end up, with something like the hp writeup,
where we have a time budget, and go for the highest priority sites first. 
--Dan

> One thing people seem to be missing is that we recursively inline, and
> the heuristics are relative to the base of the inlining tree.
> So if you have
> 
>a->b->c->d->e
> 
> and a was large, we'd still inline all of them.
> 
> However, then we compile b (which itself was small), we currently
> *also* 
> inline b->c->d->e when we compile b, 
> which makes no sense, since the consumers of b inside the translation
> unit already inlined it if it made sense (IE they were larger).
> 
> If c is a very large function, you'll end up increasing the code size,
> and compile time, but generally not performance.
> 
> Simple example.
> 
> right now, given these functions and sizes
> 
> a
> 100 stmts
> b
> 2 stmts
> c
> 50 stmts
> d
> 1000 stmts
> e 
> 100 stmts
> 
> and the following call trees:
> 
>a->b->c->d->[a sometimes, e sometimes]
> (it's not an infinite loop)
> Right now, with the current heuristics
> We go to process a
> a will become 100+2+50+1000+100+2+50+1000+100.....  statements long
> (it's actually going to become MAX_INLINE_INSNS)
> We output code for a.
> completely done with a, but saved the tree for inlining into other
> functions.
> Now we go to process b
> b will become 2+50+1000+100+....MAX_INLINE_INSNS statements long
> finish processing of b
> process c
> c will become 50+1000+100...MAX_INLINE_INSNS statements long
> finish processing c
> process d
> d will become 1000+100...MAX_INLINE_INSNS statements long
> finish processing d
> 
> MAX_INLINE_INSNS is 10k.
> So we now have a 2 statement function that got inlined until it was
> 10k.
> And it made no sense. It increased code size, but didn't improve
> performance (probably made it much worse). And we spent a long time
> compiling it, too. 
> 
> Why?
> inlining b into a makes sense (arguably, c into b into a makes sense,
> but d into c into b into a doesn't. This is the fudge factor i added)
> 
> inlining b into a into d  makes sense.
> 
> Once you'd done these two, however,
> things like
> inlining e into d into c into b makes no sense. b is a small function,
> it's callers already inlined it (and what it calls). We're just
> wasting time here, and increasing the code size.
> 
> My heuristic says d into c into b is not smart.
> 
> Realize that the argument that something else might call b too doesn't
> change anything. If it's inside the translation unit, we'll consider
> inlining it when we compile something that calls whatever else calls
> b.
> 
> We don't have interprocedural analysis, so i haven't pessimized long
> call chains anymore that we did before.   I've just stopped inlining
> along paths that we can't see making sense.  
> 
> The patholigical case for this heuristic is having a call tree where
> each function down the call tree is exactly fudge factor * original
> root tree size - 1.
> We'll do what we do now in this case, for that inlining call tree.
> 
> I haven't even actually pessimized any code (our performance on things
> like stepanov stayed the same or got better, while compilation time
> went down)
> 
> 
> Some things to think about if you think i'm wrong. Say you had.
> 
> test2.c
> int a()
> {
>         int i;
>         for (i = 0; i <50000; i++)
>                 b(i)
>}
> 
> test.c
> int b(int a)
> {
>         c(a);
>}
> int c(int)
> {
>         10k lines.
>}
> 
> we would inline c into b right now.
> 
> But since a is outside the translation unit, we wouldn't see it
> anyway to inline b into. So we've only saved call overhead of b
> calling c, at a cost of increase of 10000x in b's
> code. Since 10000x code growth is usually more than the number
> of instructions involved in making the call, and is more likely to
> push other stuff out of the instruction cache, it wasn't a good idea.
> My heuristic would say this. 
> 
> Now, say you move a into test.c.
> 
> Currently, we'll
> 
> inline c into b into a for a.
> 
> c into b for b.
> 
> 
> Since the main caller of b is a, and we already inlined b *and* c into
> a, it doesn't make sense to do it again just for b. 10000x code
> growth, large compile time increase, no performance increase.
> 
> My heuristic will still do
> inline c into b into a for a.
> 
> which was the important one.
> 
> It won't do c into b for b.
> 
> 
> Not that i think it's perfect. I know it's not.  but people seem to be trying to raise
> an issue that is already pretty much accounted for.
> 
> It's pretty hard to come up with cases where we won't do inlining we
> should with the heuristic, and equally hard to come with cases where
> we should do inlining we don't.
> 
> You'd have to deliberately architect your code in such a way that
> knows this.  But even if you did that, you'd do worse with what we
> currently do anyway.
> 
> 
> In addition, we inline anything marked inline (we do now, too), so
> that's always a fall back.
> 
> --Dan
> 
> -- 
> "I used to own an ant farm but had to give it up.  I couldn't
> find tractors small enough to fit it.
> "-Steven Wright

-- 
"I stayed up all night playing poker with Tarot cards.  I got a
full house and four people died.
"-Steven Wright