Re: Sigh. Inlining heuristics.

[Carlo Wood <carlo at alinoe dot com>]

I wrote:
> I'll try to explain point 1) tomorrow without wanting to make a big point out of it

On Mon, Jul 09, 2001 at 10:19:24PM -0700, Linus Torvalds wrote:
> Why do you care about the relative size of the inliner vs the inlinee AT
> ALL?
> 
> If you have function (a) that calls function (b), it doesn't really
> _matter_ whether (a) is smaller than (b) or not.
...

Well, with Linus on my side there isn't much extra weight I can add ;).
But I'll try anyway... as promised.

The "disagreement" seems to be about the following.

Given: function (a) calls function (b).
Your heuristics compares the size of a  (Sa) with the size of b  (Sb), and uses that
in the decision whether or not to inline (b) into (a).
I think that only the absolute size of (b) matters.

My claim should be clear from a simple example where we calculate the
resulting code size.  Here I consider the WHOLE program, not just one
tiny ARBITRARY function - the keyword being "arbitrary", because that
is what (a) is in this case.

Without inlining we have:

int f(b)
{
  // Size of (b)
}

int f(a)
{
  // Size of (a)
  f(b)
}

Total size	: Sa + Sb.
Speed		: execution time (a) + 1 function call + execution time of (b).

With inlining we have:

int f(b)
{
  // Size of (b)
}

int f(a)
{
  // Size of (a)
  // Size of (b)
}

Total size	: Sa + 2 * Sb.
Speed		: execution time (a) + execution time of (b).

Trade off: Sb <--> 1 function call.

The fact that the actual size of function (a) did grow 100 times, or 10,000 times
is irrelevant.  If you want RELATIVE numbers then AT MOST you can claim a growth
of a factor of 2 (in this case): (Sa + 2 * Sb) / (Sa + Sb) == 2  if Sb >> Sa.
But, because the size of the total application is unknown and PER inlining case
is significant larger anyway*), I think that it makes a lot more sense to look at
the absolute values (just Sb), although it always stays rather 'fuzzy' I suppose.

[ *) See below, Sb <= 200 instructions.  Total size of application is say 100,000
  instructions, thus the relative growth-per-inline-decision is:
  (100,000 + 200) / 100,000 == 1 ]

Now lets look closer at the 'Trade off': a single function call is not interesting
to inline (it will make a difference of microseconds on the *total* execution
time of an application).  Even when a function is called from many places in the
source code: the number of calls is insignificant [ Moreover, if a functions is
called at N different places (outside any loop thus) then the trade off becomes
N * Size <--> N function calls; which has no influence on the decision ].

Therefore the only case in which we can be interested in inlining is when
1) it might result in large optimization (for instance when the function parameters
   are constant).
2) the function is called from within a loop.

Now I am inclined to think that when a function (a) is called from within a loop,
but (a) was not inlined, then there is no reason to inline (b) into (a): apparently
'one call-overhead times loop-size' is not important (otherwise (a) was inlined to
begin with).  So, I'd say that if (b) is called inside (a) and it is not inside a
loop in (a) itself, there is no Real Important reason to inline it (we know we have
already at least one call overhead anyway).

I propose the following simple (per function) heuristics:

If we are not inside a loop, then only inline a function when:
1) it is marked 'inline', or
2) the size of the inlined function is less than 20 instructions.
3) the function is called with a constant as parameter (not string literal?).

If we ARE in a loop (possibly after recursively inlining multiple functions)
we inline the function when:
1) it is marked 'inline', or
2) the size of the inlined function is less then 200 instructions.
3) the function is called with a constant as parameter (not string literal?).

---

Since loops are so important here, the heuristic should indeed (as you showed)
break 'infinite' loops of functions that call themselfs recursively.
[ Lets say: --> is an inlined 'call', while ==> is a real call ].

For example,

  a --> b --> c --> d --> a

I have the feeling that this is the reason why you introduced relative sizes:
to stop the growth a at a reasonable point.

Using my heuristics proposal above, this loop would either be broken immedeately
or not at all.  Since the infinite loop is the interesting case here, lets assume
all functions have a size of less than 20 instructions.

Then it is trivial to see that there is no logical place to break this loop:
all functions are equivalent, each can be the entry point of the loop.

What should be done imho is to switch from recursive to iterative:

a becomes: a --> b --> c --> d and then a 'goto' to the top of the function.

likewise, b would become: b --> c --> d -> a  and then a 'goto' to the start of 'b'.

But this 'goto' is not what we're optimizing at this point, so just let cut the loop
at the first recursive call (no goto but a call).

At that moment the following becomes interesting: what if function 'd' contains
a loop that calls 'a'?  In that case, I think, we SHOULD inline 'a' in 'd' and
could do:
  a --> b --> c --> d -loop-> a ==> b
or even:
  a --> b --> c --> d -loop-> a --> b --> c ==> d
because 'd' contains the loop, if later optimization doesn't introduce the
previously mentioned 'goto'.

-- 
Carlo Wood <carlo@alinoe.com>