Re: Inlining heuristics for C++

[Carlo Wood <carlo at alinoe dot com>]

On Mon, Jul 09, 2001 at 09:46:59PM -0400, Daniel Berlin wrote:
> This is effectively expressing the rule: "Small functions should be
> inlined into larger ones.  Larger functions should not be inlined into
> small ones".

This doesn't seem logical.  I think I can follow the reasoning behing it
though:

- The overhead of a function call can be neglected for large functions,
  therefore it only makes sense to worry about inlining and small functions.
  As a result, only small functions are normally intented to be inlined
  by the programmer.

This works perfectly in C, but for some reason C++ is different: there is
being done a LOT more inlining.  Especially, many functions are inlined
that are not even visible to the programmer.

Therefore I propose to let go the 'human' factor - and look at inlining
from a mathematical point of view.  Suppose we have:

int f1(int i)
{
  // something
  return result;
}

int f2(int i)
{
  // uses f1() once
  return result;
}

And suppose that f1() is *only* called from within f2().
Then does the size of f1 matter?

The ONLY trade off that can be made concerning inlining is
that of call-overhead against program size *growth*.

The variables that are involved are:
1) size of the function
2) whether or not the function needs external linkage
   (size factor).
3) for each inlining decision seperately: how often
   a specific source line will be hit (call-overhead
   factor).

Obviously, the latter is unknown at the time the compiler
needs to make the decision whether to inline or not.
But I think we'll all agree that calling a function 10
times isn't worth an inline... Actually, I am pretty sure
that there is only ONE reason why inlining makes sense:
when it is within a loop somehow (a BIG loop).
When a function is called 100,000 times I start to get
interested in inlining ;).

So, back to the example:

int f1(int i)
{
  // 100 lines of code
  return result;
}

int f2(int i)
{
  // uses f1() once, 1000 lines of code
  return result;
}

int f3(int i)
{
  // uses f2 once, 10 lines of code
  return result;
}

int main(void)
{
  int s = 0;
  for (int i = 0; i < 1000000; ++i)
    s += f3(i); 
  cout << s << '\n';
  return 0;
}

and,

by inlining f3 in main() we lose one million times a call overhead;
by inlining recursively f2, we lose again one million times a call overhead;
and by inlining recursively f1, we lose again one million times a call overhead.

Despite the fact that we have to compare "one million times a call overhead"
with the different object code growths, the sizes of f1, f2 and f3 relative
to eachother are totally irrelevant.

> Where what is considered "larger" is fudged by a factor.
> 
> If you have a one line member, that calls a huge function, whatever
> *calls* that member will inline the member, and then whatever that member calls
> will probably beinlined, but the the externally visible member call itself (ie the non-inlined one) will not
> inline the huge function into itself.
> 
> Which seems to make sense to me.

I have Real Life examples of the opposite, where I needed the large function
to be inlined in the smaller one.  The reason being that I had many small
functions with a little difference, and a bulk functionality that had no
difference and for which I didn't want to add duplicated code but also
didn't want to add call over-head.

> However, this doesn't control code growth, it could inline a lot of
> small functions until it hits the limit.
> 
> So the other heuristic i've added controls code growth by saying we don't
> want to increase the number of statements in the function by more than
> a factor of x over what we started with (when we started inlining).
> 
> An expression of the rule: "Don't make the function more than x times bigger than
> it originally was".

I think is only marginal important - perhaps even neglectible.  If, say, there are
5 (small) functions that inline eachother, then that adds a factor of 5 to
whatever we gave as weight to a call-overhead - which is essentially not much
(a loop of 1000000 or 200000, in *practise* being an unknown loop size:
 unknown == 5 * unknown, for me).

PS I am not against your patch, because I think that in reality programmers
   always will mark functions 'inline' or put them in the class declaration
   when it really matters.  Hopefully you *ALWAYS* inline functions that
   are marked 'inline' and/or defined in the class declaration - then it is
   fine with me whatever g++ does to reduce code size and compile time ;).

-- 
Carlo Wood <carlo@alinoe.com>