Drawing the line on inline

[Posted January 3, 2006 by corbet]

Kernel programmers tend to like inline functions. They resemble C macros, in that they result in code inserted directly into the calling function, with no added function call overhead. But, unlike macros, they offer type checking and the ability to include multiple lines of code without adding a pile of backslashes. In cases where a function is optimized out entirely, an inline function turns into no code at all - a level of efficiency which is hard to beat. And, in some cases, inlining is required; consider, for example, functions which embody special assembly instructions needed by the kernel.

Inline functions also have their costs, however. Their code is duplicated for every call, so inline functions which are called from more than one place make the kernel larger. Increasingly, developers are becoming aware that this size increase carries a performance penalty. As the gap between CPU and memory speeds grows, cache behavior increasingly determines how fast a program runs. So the performance benefits of inline functions are often, at best, illusory, and sometimes negative; a larger kernel will be a slower kernel.

Ingo Molnar recently raised this issue with a set of patches changing how the kernel is built. By turning on unit-at-a-time compilation (which causes gcc to consider an entire file in its optimization decisions) and by turning off forced inlining, he was able to achieve a 5.3% size reduction. Taking things to an extreme, and applying these patches to an "allyesconfig" kernel (one with all configuration options turned on) results in a nearly 25% smaller kernel. That is, to say the least, a significant size reduction to be achieved by such a small patch. Anybody interested in de-bloating the kernel should be paying attention.

These patches have not been accepted by everybody, however. In particular, the turning off of forced inlining is controversial. When gcc is not forced to honor the inline keyword, it makes its own decisions, based on the size of the function and how many times it is called. When told to optimize for size, in particular, gcc will have a strong bias against inline functions. This approach yields a significant size reduction, but there is a problem: Linus doesn't trust the gcc maintainers to code consistent and correct inline heuristics, and Andrew Morton doesn't either. Rather than turning off forced inlining and letting gcc figure things out, they would rather go through the code and remove unnecessary inline declarations one by one.

It is true that the kernel has been burned by changes to how gcc handles inline in the past. Since then, gcc seems to have gotten smarter, and one can argue that its maintainers have become more aware of the issues. There is also the little fact that cleaning up the existing inline declarations is not a small job; Ingo says:

There are 22,000+ inline functions in the kernel right now (inlined about a 100,000 times), and we'd have to change _thousands_ of them. They are causing an unjustified code bloat of somewhere around 20-30%.

Arjan van de Ven adds:

The reality is, most driver writers (in fact kernel code writers) tend to overestimate the gain of inline in THEIR code, and to underestimate the cumulative cost of it. Despite what akpm says, I think gcc can make a better judgement than most of these authors (probably including me :). We can remove 6400 now, but a year from now, another 1000 have been added back again I bet.

How all of this will turn out is unclear. Certainly one can expect a higher level of resistance to patches adding inline functions in the future. There is likely to be a long flurry of de-inlining patches as well. The ability to turn off forced inlining might be added to the build system as an experimental option; some distributors may even decide to use this option for the kernels they ship. But enough developers seem uncomfortable with the idea of turning off forced inlining wholesale that this option may not get beyond the "experimental" stage for some time.

Index entries for this article
Kernel	Coding style
Kernel	Inline functions

to post comments

Drawing the line on inline

Posted Jan 6, 2006 16:42 UTC (Fri) by giraffedata (guest, #1954) [Link] (1 responses)

Not mentioned in the article is one important and often overlooked fact about inlining: Inlining happens automatically. This is just about forced inlining. Even without the "inline" keyword, Gcc will inline a function if it looks beneficial. I think current versions have a way to explicitly exclude a function from inlining.

So one really should use "inline" only where one has reason to believe he's smarter than Gcc, and forced inlining should always be respected.

One other reason to use "inline" is where you use that warning option that warns you about unused functions. If you put a function in a header file, since not every file that includes the header file will use that function, you get that warning if you don't declare "inline".

Drawing the line on inline

Posted Jan 13, 2006 8:13 UTC (Fri) by xoddam (subscriber, #2322) [Link]

It used to be that no-one trusted compilers to do register allocation
optimally either, but now they do (admittedly there is a canonical
algorithm for it, which AFAIK isn't the case for inlining) so the
register keyword is vestigial.

> Gcc will inline [any] function if it looks beneficial.

Only if it's in the same compilation unit -- if there's only a prototype
available, the compiler can see no code to inline.

As things stand at the moment, only functions which developers think
should be inlined are available in the API headers, and those are *all*
marked with the inline keyword -- there'd be no point putting a function
in a header if you didn't want it inlined.

unit-at-a-time optimisation is an improvement, but it falls waaay short
of whole-program optimisation. When that's available I'm sure no one
will trust the compiler -- initially.

Any performance data?

Posted Jan 6, 2006 17:54 UTC (Fri) by sepreece (guest, #19270) [Link] (3 responses)

I read through the discussion thread and didn't find any information about the performance impact of removing the inlining. While it's not unreasonable to think that cache hit rates would improve, it would be nice to see some data indicating what the bottom line performance change is.

Any performance data?

Posted Jan 7, 2006 14:40 UTC (Sat) by jospoortvliet (guest, #33164) [Link] (1 responses)

point is, it is very hard to measure. it can make a difference, but no
reliable real-world benchmarks exist, afaik. its very much a matter of
opinion, after all...

Any performance data?

Posted Jan 10, 2006 17:23 UTC (Tue) by sepreece (guest, #19270) [Link]

Benchmarking is hard and people use it to lie a lot. On the other hand, though, the reason people do inlining, usually, is to improve performance, so you'd think that somebody pushing reduced inlining would have done some kind of performance study to see if the changes hurt performance unacceptably.

In other words, I'm not concerned about whether the experiments are scalable or universally applicable, but it would be interesting to know whether it had had any observable effect on whatever ingo chose to observe.

I'd be especially interested in things like interrupt latency, which I would expect Ingo to be well-prepared to measure.

Any performance data?

Posted Jan 12, 2006 22:25 UTC (Thu) by anton (subscriber, #25547) [Link]

The effect of code duplicating optimizations (like inlining) on cache
miss rates can be counterintuitive. E.g., Mueller and Whaley [1]
tried an optimizationm that increased code size by 50%, and found that
it reduced the number of cache misses.

In the context of our work on replication in interpreters we have
tried to use partial replication to reduce the code size by a factor
of two or more (compared to full replication), but found that this
increased the cache misses significantly; partial inlining resulted in
worse spatial locality, and apparently this had more influence than
the code size. This research is not yet published.

Here is a scenario where de-inlining can increase cache misses:
Consider that a function is inlined in several places in the kernel,
but these different places are called so far apart that the function
is expelled from the cache between these executions. Then de-inlining
has no benefit for the cache hit rate; but it can have a cost:

- the direct cost is that the function probably does not utilize all
of the cache line where it starts and where it ends (whereas the
inlined version would share these lines with the caller which is also
executed). I.e., de-inlining reduces spatial locality.

- the indirect cost is that optimizations enabled by inlining are
suppressed, and these optimizations may reduce the code size and thus
the cache footprint.

[1] Frank Mueller and David B. Whalley. Avoiding Unconditional Jumps by
Code Replication. SIGPLAN '92 Conference on Programming Language
Design and Implementation, pp. 322-330, 1992.

what is missing

Posted Jan 9, 2006 7:50 UTC (Mon) by guybar (guest, #798) [Link] (1 responses)

IMHO, is the distribution of function calls per "average" kernel.
And even better, per specific kernel.

Why not run the kernel with no inlineing and oprofile, determine which are , say, the 10% of the inlined functions called 90% of the time, and run an automated "deinlining" script ?

what is missing

Posted Jan 28, 2006 21:39 UTC (Sat) by ringerc (subscriber, #3071) [Link]

It's not that simple unfortunately. If one was to try to give each function a "score" for inlining, where larger numbers mean better to inline, one might use at least the following rules:

Function is called very frequently (+, large potential benefit)
Function is is very small and simple (+, low code bloat)
Function is called from many different locations (-, high code bloat)

... and I don't doubt there are more factors I've missed, especially when considering cache and register use issues. I'm about as far from an expert as you might find - "not totally clueless" perhaps.

As far as I know the ideal inline function is something like:

int one() { return 1; }

int addone(int in) { return in+1; }

or perhaps something slightly more complex that's called from relatively few places. Forcing the inlining of:

void runEventLoop()
{
   // 100 lines of branch-heavy event dispatch code including
   // infrequently used cases, error handling, etc
}

... could to very nasty things to your program's binary size and performance if it's called from many places at all.

Whether to inline a function is not simple to evaluate from static analysis of source code. The compiler does a somewhat better job, and can be given directives to control its inlining behaviour. Given this, it seems sensible to only force inlining where you know the compiler gets it wrong, or where you know it's absolutely critical to inline a function.

Drawing the line on inline

Posted Jan 16, 2006 21:34 UTC (Mon) by roc (subscriber, #30627) [Link] (1 responses)

One thing that's missing from this discussion is that in many cases you want some invocations of function F to be inlined and other invocations of the same function to NOT be inlined. In particular invocations of F in hot paths should be inlined and invocations in cold, infrequently executed code should not (unless inlining F is actually smaller than a regular function call to F). You can't get this effect just by twiddling 'inline' declarations in the source, so the compiler (perhaps assisted with profile information) can actually do a better job then you can at the source level (unless you go around inline the code by hand in the source code, which is madness).

moving inline keyword from callee to caller

Posted Feb 23, 2007 14:03 UTC (Fri) by samtherecordman (guest, #43207) [Link]

In the case where you want to a function to be inline in some cases and not others what about:

int small_function(int val)
{
return val+1;
}

void main()
{
int i = 0;

for(i = 0; i < 10000; i++)
{
small_function() __inline__
}
}

This would support selective inlining, and also helps the programmer who is new to the code visualize what is going on - you don't need to see the definiton of small_function() to see that the function will be inlined.