On inlining in C++

On inlining in C++

[Gabriel Dos Reis]

This text I should have sent a while ago.  


	  Give C++ "inline" its original and obvious meaning

	     Gabriel Dos Reis <gdr@integrable-solutions>
				=====

          "Inlining was considered important for the utility of classes"
                    -- B. Stroustrup in "The Design an Evolution of C++"


  This note is about handling of "inline" by C++ implementations.
It has grown up after various misfortunate experience with
different C++ implementations, reading reports and complaints from C++
users; it is also a reaction to the more or less recent semantics
shift implementors are trying to put in the "inline" keyword.  While
this paper uses examples based on GCC/g++ behaviour to illustrate some
points, I believe that most of the issues are not unique to GCC. 

A cost-free functional abstraction
----------------------------------

One of the principal uses of inline functions is to offer safe,
cost-free functional access to small, simple expressions.  Consider:

   inline int min(int a, int b)
   { 
      return a > b ? b : a; 
   }

Call to abstractions like min() should not incur function call overhead.
A function like min() is just a convenient notation for the simple
expression it contains.  

Is there an alternative way to express that notation?   Often, people
in fear, doubt and uncertainty of their compilers not substituting an
inline function body at call sites resort to macros:

   #define MIN(A, B)   ((A) > (B) ? (B) : (A))

However, that is only a very rough approximation: The macro MIN does
suffer from several serious problems:
  * It does break scope rules and it cannot be passed around. 
  * It does break function call semantics - it evaluates its arguments
    more than once.  
In other words, that macro looses both semantics and syntax of a function.
That loss is a show-stopper as far as programming in C++ goes.  

A compiler targetting a given language should implement the semantics
and support usage patterns of that language.   For example, a C++
compiler should inline a call like min(2003-20, 49 * 36) yielding something
like 
   
       (2003-20) > (49 * 36)? (49 * 36) : (2003-20)

which a front-end or back-end optimization should reduce to plain
1764. Even the first C++ compiler, Cfront, could do that in 1985.
Interestingly, the GCC manual[1] (as of this writing) describes inline
functions as follows: 

	       An Inline Function is As Fast as a Macro

    By declaring a function inline, you can direct GCC to integrate
    that function's code into the code for its callers. This makes
    execution faster by eliminating the function-call overhead; in
    addition, if any of the actual argument values are constant, their
    known values may permit simplifications at compile time so that not
    all of the inline function's code needs to be included. 

The interesting point about that documentation is that it is close to
the documented meaning of "inline" found in any official C++ manual
since 1981[2]. 

Crossing protection barrier ought to be free
--------------------------------------------

Another important use of inline function is for providing controled
access to protected data. In fact, such uses were the decisive factors
for introducing inline function in C++:

   In particular, [Stroustrup, 1982b] observes that people had made
   data members public to avoid the function call overhead incurred by
   a constructor for simple classes where only one or two assignments
   are needed for initialization.  The immediate cause for the
   inclusion of inline functions into C with Classes was a project
   that couldn't afford function call overhead for some classes
   involved in real-time processing.  For classes to be useful in that
   applications, crossing the protection barrier had to be free.
                 -- B. Stroustrup in "The Design and Evolution of C++" 

Those words were written more than 20 years ago, but they do sound so
familiar, so contemporary.  Access control is a compile-time notion.
A controled access to protected data ought to be free.  

It is crucial to realize that "inline" in C++ does not mean "leave
this to the back-end".  It has a language specific meaning. Inline is
in C++ exactly because the programmer cannot rely on a compiler
reliably inline predictably and reasonably according to the
programmer's needs for a particular program. Even if one compiler does
it right, reliance on a compiler's inlining heuristics 	will not lead
to portable  behavior vis a vis the performance.  Inlining was
introduced as a language feature into C++ exactly to give the
programmer control, a lever to state his preference for an alternate
function call mechanism, namely <it>substitution</it>. An advantage of
substitution is that once inlined, the function body can expose many
optimization opportunities that otherwise would necessitate more
advanced infrastructures. 

More than twenty years after its introduction in C++, do major and
common C++ compilers get "inline" right?  I fear the answer is
<strong>no</strong> for many of them.  Failures to implement the
meaning of "inline" and to support usage patterns has been incitative
for otherwise talented  programmers to deploy all sorts of
workarounds, going against good software practice, defeating the 
intended semantics of common abstractions[3].  Simple abstractions like

  template<class T>
    inline const T& min(const T& a, const T& b)
    {
       return a > b ? b : a;
    }

or std::string::end() should be efficiently handled by C++ compilers.
Simple inline functions should be cost-free.  Functions that provide
controled access to data should be as efficient as accessing the data
directly.  Whatever strategy C++ implementors use to implement "inline",
the delivered behaviour should meet the documented obvious and
original meaning of "inline". 


Is "inline" just like "register"?
---------------------------------

It is not uncommon to see the argument that "inline" is just a
<em>hint</em>, like "register", and as such the compiler should treat
them equally, i.e. ignore the C++ programmer preference because the
compiler knows best.  

Such an argument is confusing.  There is no dispute that "inline" is a
hint.  But it is a hint only because, quoting again [4], p. 34:

   This is a logical necessity because one can write inline functions
   that cannot at compile time be proven not to cause infinite
   recursions;  trying to inline one of those would lead to infinite
   compilations.  Leaving "inline" a hint is also a practical
   advantage because it allows the compiler writer to handle
   "pathological" by simply not inlining. 

Another way Stroustrup used to put the logical necessity is: "we don't
want to require the compiler to solve the halting problem".  Of course,
"pathological" is not clearly defined, but it is matter of fact that no
simple, short expression is pathogolical.  In the very early days,
a loop in a function called in a way that required use of its return
value to be used was considered pathological, but most compilers can
do better today and this case can be very important because inlining
in this case opens possibilities for optimization. 

Furthermore, it is not true that in real code the compiler often knows
better than the programmer what to inline.  Compiler heuristics don't
serve all people well[5] and "inline" was introduced into C++ exactly to
give the programmer control.  The current state of compiler technology
and development is not at the same level of sophistication as that of
automatic register allocation.  Given the control offered by a simple
and straightforward implementation of "inline", good programmers
consistently produce well performing code.  Furthermore, compiler
technology is still far from the maturity level where a language
independent meaning of "inline" could be productively substituted for
the language specific meaning it has in C++.  When compilers are as
good at inlining as they are at register allocation, "inline" can go
the way of "register".  However, we are nowhere near that level of
sophistication yet, so we should - in the best C and C++ tradition -
trust the programmer. 

Failure to meet behaviour that have been documented for more than two
decades will only increase dialect proliferations, because the
fundamental need will still be there, and people will continue to
reinvent "inline" with vendor lock-in syntaxes.  Compiler middle ends
and back ends are not the right places to change an ISO standardized
language. 


Should an Inline Function returning a structure make a difference?
------------------------------------------------------------------

No, an inline function returning a structure or class should not make
any difference.  For that, it is crucial to understand the language
specific meaning of inlining in C++: It is substitution of the
function body for the usual call.  In other words, it is an alternate
implementation of function call mechanism.  Compiler back-ends that
insist on  using a language-neutral meaning for C++ inline fail to
understand that feature.  Dare I say, they fail to support C++.

Even more so, it is essential that an inline function returning a
structure that contains a scalar be as efficiently supported as an
inline function returning just that scalar.  The reason is that
liberal use of types is central for programming in C++, and most of
the types involved in most C++ programs are user-defined types,
i.e. structures or classes.  


Acknowledgments
---------------

The writing of this paper benefited from support, inputs and
improvements from friends I would like to thank.  Bjarne Stroustrup
patiently corrected errors and confusing formulations contained
in the drafts of this note.  He also provided assistance for history.
Paolo Carlini made careful reading, asking for better clarifications
and explanations.  Benjamin Kosnik provided data through his continual
exercising, improvement and testing for a "-Winline"-clean GNU
implementation of the C++ standard library.  Any remaining error, 
inaccuracy are my responsability.  


[Stroustrup, 1982b] Bjarne Stroustrup: "Adding Classes to C: An
Exercise in Language Evolution".  Bell Laboratories Computer Science
internal document.  April 1982.  Software: Practice & Experience,
Vol 13, 1983.

Footnotes: 
[1] GCC 3.3 Manual 
    http://gcc.gnu.org/onlinedocs/gcc-3.3/gcc/Inline.html#Inline

[2] Bjarne Stroustrup, private communication.

[3] See patches included in the message
    http://gcc.gnu.org/ml/libstdc++/2003-02/msg00102.html 

[4] Bjarne Stroustrup: "The Design and Evolution of C++", 1994 Addison-Wesly.
 
[5] http://gcc.gnu.org/ml/gcc/2001-08/msg01206.html

Re: On inlining in C++

[Joe Buck]

On Mon, Aug 04, 2003 at 03:06:43PM +0200, Gabriel Dos Reis wrote:
> 	  Give C++ "inline" its original and obvious meaning
> 
> 	     Gabriel Dos Reis <gdr@integrable-solutions>

Excellent article.  I think that anyone who wishes to oppose the argument
should be asked to demonstrate that we can get better quality of results
by deviating from the simple approach Gaby describes; philosophical
arguments should not suffice.

Re: On inlining in C++

[Mike Stump]

On Monday, August 4, 2003, at 09:31 AM, Joe Buck wrote:
> On Mon, Aug 04, 2003 at 03:06:43PM +0200, Gabriel Dos Reis wrote:
>> 	  Give C++ "inline" its original and obvious meaning
>>
>> 	     Gabriel Dos Reis <gdr@integrable-solutions>
>
> Excellent article.

This is a complete waste of time.  inlining is an optimization.  
Optimizations are always subject to improvement.  Therefore, inlining 
is subject to improvement.

Removing the optimizer from inlining isn't where we are going, it just 
isn't going to happen, ever, get over it.

What isn't a waste of time, would be to point out a case where the 
optimizer gets it wrong, and explain what would be better, and then we 
can retune the optimizer to be _better_ without that being at the 
expense of other code.  We already knew that some of the heuristics are 
probably wrong for C.  If people want, we can bump up the numbers a ton 
for the heuristic for things marked with inline (or whatever else 
anyone would like) and then wait for the bug reports that said we went 
too far, and then bump them back down some...

It would be good if we could sign up lots of people to benchmark their 
favorite programs as we tune it around, and give timely feedback on 
them so that we know how things are being impacted.

Re: On inlining in C++

[Thomas Kunert]

Mike Stump wrote:
> On Monday, August 4, 2003, at 09:31 AM, Joe Buck wrote:
> 
>> On Mon, Aug 04, 2003 at 03:06:43PM +0200, Gabriel Dos Reis wrote:
>>
>>>       Give C++ "inline" its original and obvious meaning
>>>
>>>          Gabriel Dos Reis <gdr@integrable-solutions>
>>
>>
>> Excellent article.
> 
> 
> This is a complete waste of time.  inlining is an optimization.  
> Optimizations are always subject to improvement.  Therefore, inlining is 
> subject to improvement.
> 
> Removing the optimizer from inlining isn't where we are going, it just 
> isn't going to happen, ever, get over it.
> 
> What isn't a waste of time, would be to point out a case where the 
> optimizer gets it wrong, and explain what would be better, and then we 
> can retune the optimizer to be _better_ without that being at the 
> expense of other code.  We already knew that some of the heuristics are 
> probably wrong for C.  If people want, we can bump up the numbers a ton 
> for the heuristic for things marked with inline (or whatever else anyone 
> would like) and then wait for the bug reports that said we went too far, 
> and then bump them back down some...
> 
> It would be good if we could sign up lots of people to benchmark their 
> favorite programs as we tune it around, and give timely feedback on them 
> so that we know how things are being impacted.
> 
> 

As a C++ programmer I would like to ask you to retain a mechanism to tell
the compiler "Inline at least everything I marked as inline." Currently,
this mechanism is -finline-limit=1000000.

Correct decisions about efficient inlining depend on many parameters the
compiler does not know, e.g.

- How much time takes one call of the function. This time in general depends
 on the actual parameters and cannot be guessed by the compiler.

- How much total time does the code spent in the function. If this time is
 only a few micro seconds, there is absolutely no point in inlining.

- From how many places the function is being called throughout the program.

- How often the function is called from a certain position.

The programmer has the complete picture. He has an idea about the actual
parameters passed to the function. He can actually measure the time.
He knows if some function is critical or not.

Maybe someday in the distant future compilers are smart enough to find out
these things. But currently I strongly prefer to control inlining myself,
because in most cases I know better. The compiler should be allowed to
overrule my decision only if it can prove me wrong.

Thanks,
Thomas Kunert 

Re: On inlining in C++

[Gabriel Dos Reis]

Mike Stump <mrs@apple.com> writes:

| On Monday, August 4, 2003, at 09:31 AM, Joe Buck wrote:
| > On Mon, Aug 04, 2003 at 03:06:43PM +0200, Gabriel Dos Reis wrote:
| >> 	  Give C++ "inline" its original and obvious meaning
| >>
| >> 	     Gabriel Dos Reis <gdr@integrable-solutions>
| >
| > Excellent article.
| 
| This is a complete waste of time.  inlining is an optimization.

This way lies confusion.

[...]

| are probably wrong for C.  If people want, we can bump up the numbers

It it a matter of bumping numbers.

-- Gaby

Re: On inlining in C++

[Matthias Benkmann]

Maybe I've missed it but I don't think I've seen an argument against the
suggestion of a switch to turn off the heuristics for inline-declared
functions. Just put it in and let the users decide. Case closed.
Everyone's happy. Where is the problem?

MSB

-- 
I've had fun before. This isn't it.

Re: On inlining in C++

[Mike Stump]

On Tuesday, August 5, 2003, at 01:25 AM, Gabriel Dos Reis wrote:
> If people want, we can bump up the numbers
>
> It it a matter of bumping numbers.

Ok, submit numbers for a testcase, before the change, a suggested 
change, and numbers after...  I think it is productive if we bump up 
the number, not to 4233153983 from a previous of 300, but rather to 
another number such that your testcase gets 95% of the benefit you see 
to switching to a number like 4233153983 and for all lower numbers, the 
you get <95% of the improvement.


For example:

n	time
300	500.0
310	492.0
320	492.0
350	491.0
380	490.0
392	489.0
393	460.0
400	460.0
410	461.0
500	459.0
1000	459.2
3000	458.0
...

So, instead of picking 3000, as the best, we pick 393, as then we get 
most of the benefit, maybe not all, but most.  I'd ask that the 
testcase be real code, or abstracted from real code, not purely 
invented to move the numbers.

Also, any such change should be weighed against real code, SPEC, a 
boost or something like it benchmark and so on...  plus anything else 
people would like to run against.

For example, some numbers were put in for C++ because of odd template 
code, where everything is marked inline but, we don't want to explode 
things, but these same number probably hurt C inlining performance.  
I've not seen too many people complaining that C inlines too much (well 
other than indirectly about -O3, which we can discount as a factor for 
some types of changes), and have seen lots of people complaining that C 
inlines too little, so, bumping up some of the numbers for C, easily 
makes sense.

Likewise, even for C++, we should be happy to experiment some with the 
numbers and collect feedback on those experiments and _then_ make an 
informed choice on what the numbers are.

My hope is that we can globally improve the choices the compiler makes 
by default, not just for any one testcase.

I'd rather have a debate that tuning the defaults for KDE speed is 
slightly more important than tuning for raw SPEC speed, as SPEC people 
have ways to get the right numbers into the compiler.  Or that tuning 
for boost is more important than tuning for <name of some other random 
C++ project>...

Also, we could discuss, should this tuning parameter be used in this 
case or should this other parameter be used (or invented), for example, 
for methods contained textually inside a class, should we use the same 
parameter as functions marked inline in C or...  Here is where I'd love 
your feedback.

If you are the only one to submit numbers, then you might be able to 
move any of the numbers anyway you want.  If others don't like such a 
movement, sooner or later someone is going to have to submit numbers, 
and then we might have to revisit the issue.

I don't want you to feel like you are loosing, or that the compiler 
isn't doing the best that it can.  I'd rather empower you to tell us 
the performance you see, and ask for a change of default, or ask for 
improvements in the underlying algorithms; then based upon all that we 
hear from everyone, the maintainers are going to have to just make the 
best choices they can.  The process should be open, honest and 
reflective of the needs of users.

If that sounds reasonable, let's do it, if it doesn't, ignore me...  :-)

Re: On inlining in C++

[Gabriel Dos Reis]

Mike Stump <mrs@apple.com> writes:

| On Tuesday, August 5, 2003, at 01:25 AM, Gabriel Dos Reis wrote:
| > If people want, we can bump up the numbers
| >
| > It it a matter of bumping numbers.
| 
| Ok, submit numbers for a testcase, before the change, a suggested

sorry, I see I incorrect typed the message:  I meant

  It is not a matter of bumping numbers.
        ^^^
 
| change, and numbers after...  I think it is productive if we bump up

I'm working on putting a utility in place that get help have a picture
on what is going on, instead of just throwing out numbers.

[...]

| If you are the only one to submit numbers, then you might be able to
| move any of the numbers anyway you want.  If others don't like such a
| movement, sooner or later someone is going to have to submit numbers,
| and then we might have to revisit the issue.

That is why I'm working on settting up utilities so that people can
judge by themselves what is going on.  As someone put it some day,
there are lies, dead lies and benchmarks :-)

[...]

| If that sounds reasonable, let's do it, if it doesn't, ignore me...  :-)

You don't expect me to ignore you just because I don't fully agree
with you :-)

-- Gaby

Re: On inlining in C++

[Gabriel Dos Reis]

Mike Stump <mrs@apple.com> writes:

[...]

| For example, some numbers were put in for C++ because of odd template
| code, where everything is marked inline but, we don't want to explode
| things, but these same number probably hurt C inlining performance.
| I've not seen too many people complaining that C inlines too much
| (well other than indirectly about -O3, which we can discount as a
| factor for some types of changes), and have seen lots of people
| complaining that C inlines too little, so, bumping up some of the
| numbers for C, easily makes sense.

I guess so, but I would like to avoid the mistake that inlining is
language-neutral.

-- Gaby

Re: On inlining in C++

[Scott Robert Ladd]

Mike Stump wrote:
> If that sounds reasonable, let's do it, if it doesn't, ignore me...  :-)

Your proposal sounds quite reasonable to me.

I've actually been working on something a bit more extensive, with an 
eye toward identifying the best g++ and gcc options for compiling 
certain types of numerical code. I'll see if I can adapt my in-house 
tests to focus more on inlining.

Note that my tests are only in-house because I'm still developing my 
testing theories. I suspectm, though, that some of the numbers could be 
useful in the current debate.

-- 
Scott Robert Ladd
Coyote Gulch Productions (http://www.coyotegulch.com)
Software Invention for High-Performance Computing

Re: On inlining in C++

[Mike Stump]

On Tuesday, August 5, 2003, at 12:29 PM, Gabriel Dos Reis wrote:
> | > It it a matter of bumping numbers.
> |
> | Ok, submit numbers for a testcase, before the change, a suggested
>
> sorry, I see I incorrect typed the message:  I meant
>
>   It is not a matter of bumping numbers.

Ah, but I include algorithmic changes in the set of allowable changes 
as well, surely, that is sufficient.  If not, please provide a testcase 
that cannot be solved this way, and the proof that it cannot be solved. 
  :-)

> I'm working on putting a utility in place that get help have a picture
> on what is going on, instead of just throwing out numbers.

Hum...  Sounds interesting, the trick will be to make it reflective of 
what users will experience with the compiler, as in the end, that is 
about what we have to optimize for.

Re: On inlining in C++

[Joe Buck]

On Mon, Aug 04, 2003 at 10:49:01PM -0700, Mike Stump wrote:
> On Monday, August 4, 2003, at 09:31 AM, Joe Buck wrote:
> > On Mon, Aug 04, 2003 at 03:06:43PM +0200, Gabriel Dos Reis wrote:
> >> 	  Give C++ "inline" its original and obvious meaning
> >>
> >> 	     Gabriel Dos Reis <gdr@integrable-solutions>
> >
> > Excellent article.
> 
> This is a complete waste of time.  inlining is an optimization.  
> Optimizations are always subject to improvement.  Therefore, inlining 
> is subject to improvement.

Fine.  Then accept Gaby's proposal as a stopgap solution until we can
produce an automatic inliner that is any good.

Re: On inlining in C++

[Joe Buck]

On Tue, Aug 05, 2003 at 02:41:26PM -0700, Mike Stump wrote:
> On Tuesday, August 5, 2003, at 12:29 PM, Gabriel Dos Reis wrote:
> > | > It it a matter of bumping numbers.
> > |
> > | Ok, submit numbers for a testcase, before the change, a suggested
> >
> > sorry, I see I incorrect typed the message:  I meant
> >
> >   It is not a matter of bumping numbers.
> 
> Ah, but I include algorithmic changes in the set of allowable changes 
> as well, surely, that is sufficient.  If not, please provide a testcase 
> that cannot be solved this way, and the proof that it cannot be solved. 
>   :-)

OK, here's the algorithm: for -O2 and below, attempt to inline a C++
function if and only if it is either declared inline, or is defined in
a class body.  I say "attempt" to excuse the places where we can't inline
because of recursion, excessive lookahead (call comes before the
definition), or some other reason that prevents inlining.  Issue a
-Winline warning when inlining fails.

This might harm some users who don't use a coherent process to decide
what gets inlined.  Fine.  They will learn.

For -O3, try what you want, and maybe I could recommend its use someday,
but not for 3.2 or 3.3 and C++.  For evidence why, I suggest looking at a
recent speed comparison between Gentoo and Debian versions of a number of
apps: why did Gentoo come out slower despite its custom optimizations?  My
theory: -O3.

See
 
http://articles.linmagau.org/modules.php?op=modload&name=Sections&file=index&req=viewarticle&artid=227

Re: On inlining in C++

[Scott Robert Ladd]

Joe Buck wrote:
> For -O3, try what you want, and maybe I could recommend its use someday,
> but not for 3.2 or 3.3 and C++.  For evidence why, I suggest looking at a
> recent speed comparison between Gentoo and Debian versions of a number of
> apps: why did Gentoo come out slower despite its custom optimizations?  My
> theory: -O3.

I ran into precisely the behavior you describe above: -O3 produces 
slower code than -O2 in several cases.

For example, on my C benchmark of Huffman compression (lots of bit 
manipulations and small loops), run on a 2.8GHz Pentium 4 hardware with 
gcc 3.2.2:

options  time (secs)
-------  -----------
n/a      44.4
-Os      28.4
-O1      26.3
-O2      30.2
-O3      30.7

Using -funroll-all-loops and other options can bring the run-time down 
to under 24 seconds. I'm still investigating how various "inline" 
settings affect the outcome; on preliminary tests, -finline-functions is 
definitely a loser.

I've been distracted by paying work (silly me!), but I'll try to get my 
results into coherent form in the coming days. I probably need to run 
tests for GCC 3.4, too...

-- 
Scott Robert Ladd
Coyote Gulch Productions (http://www.coyotegulch.com)
Software Invention for High-Performance Computing

Re: On inlining in C++

[Gerald Pfeifer]

On Tue, 5 Aug 2003, Joe Buck wrote:
> Fine.  Then accept Gaby's proposal as a stopgap solution until we can
> produce an automatic inliner that is any good.

I tried to keep out of this, but -- let's see numbers, please.

Jan and me have performed relatively extensive tests in June when Jan
was working on the improved inliner, and also Richard Guenther has been
running extensive tests with his applications.

Arguing about the skills of C++ programmers, their possible intentions,
etc. really does not seem very productive (and several of the claims made
definitely do not match my experience).  In general, in GCC-land, if one
wants to change current behavior, the burden is on him to show that the
change is benefical.

Gerald

Re: On inlining in C++

[Gabriel Dos Reis]

Gerald Pfeifer <gerald@pfeifer.com> writes:

| On Tue, 5 Aug 2003, Joe Buck wrote:
| > Fine.  Then accept Gaby's proposal as a stopgap solution until we can
| > produce an automatic inliner that is any good.
| 
| I tried to keep out of this, but -- let's see numbers, please.

I would like people realize that "C++ inline" is not just about
numbers.  "C++ inline" is not an alias to "optimize".  Among other
things, it is statement of programmer's preference for an alternate
function call mechanism.  

7.1.2/3

  [...] The inline specifier indicates to the implementation that
  inline substitution of the function body at the point of call is to
  be preferred to the usual function call mechanism. [...]

The intent is clear.


Moreover -- something I'm not proposing for g++ --, "C++ inline" is an
actual request for ABI change in the sense that if in a translation
unit -- therefore in all translation units -- the copy constructor is
inline and the class is simple enough, the compiler can pass the data
in register, not in stack.  That function call mechanism provides
optimal efficiency for class types abondantly used in programming in
C++, starting with the standard library itself. 

In other words, "C++ inline" goes beyond random numbers. 

But as I said, I'm not proposing an ABI breakage.

-- Gaby

On inlining in C++ with unit-at-a-time code

[Jan Hubicka]

> On Tue, 5 Aug 2003, Joe Buck wrote:
> > Fine.  Then accept Gaby's proposal as a stopgap solution until we can
> > produce an automatic inliner that is any good.
> 
> I tried to keep out of this, but -- let's see numbers, please.
> 
> Jan and me have performed relatively extensive tests in June when Jan
> was working on the improved inliner, and also Richard Guenther has been
> running extensive tests with his applications.
Hi,
Concerning the inlining limits, I believe we should increase them.  We
did some testing with Andreas and the SPEC scores gradualy improve with
inline limit increasing (that wasn't the case of old inlining size
estimates).  The sizes around 150 seems to give best performance/code
size ratio.  For x86-64 the peak is slightly earlier, for i386 slightly
later reflecting large function call costs of i386.

Situation seems to be the same for C++ programs I tested too (your
benchmark suite and similar).  For functions marked explicitely as
inline I would like the limit to see even higher limit if C++
programming style allows us to do, this needs more testing, but I think
the values around 500 would be OK.

Unforutnately we can't do the change on mainline yet as old inlining
heuristics is still active for -O2 and will result in memory bombs then.
I hope we can enable unit-at-a-time at -O2 by default and solve the
problem in easy way.  In SuSE we are experimentally building the
distribution with it and now all problems directly attributable to
unit-at-a-time seems to be gone.  I will send more detailed summary
sometime next week as this week I am on the trip.  Of course few
remaining patches I sent needs to get in first but Mark seems to be
doing great job on reviewing them.

So please if you complain about the inlining decisions, can you, please
try -O2 -funit-at-a-time --param max-insns-inline-single=500 --param
max-insns-inline-auto=150 and send me a testcases in case it won't do
what do you want? (if it inlines way too much, please try to lower the
inline-single limit to 150 again, I didn't do much testing with
inline-single limit set so high)

With this settings I believe we should be able to quite consistently
outperform the old inlining heuiristics of 2.95 both compile time-memory
wise and code quality wise.

Honza

Re: On inlining in C++ with unit-at-a-time code

[Scott Robert Ladd]

Jan Hubicka wrote:
> So please if you complain about the inlining decisions, can you, please
> try -O2 -funit-at-a-time --param max-insns-inline-single=500 --param
> max-insns-inline-auto=150 and send me a testcases in case it won't do
> what do you want? (if it inlines way too much, please try to lower the
> inline-single limit to 150 again, I didn't do much testing with
> inline-single limit set so high)

Am I correct that -funit-at-a-time and --param max-insns-inline-* came 
came into existence with the advent of 3.4?

While I follow this list closely, are there any other "new" optimization 
options I should be considering when testing 3.4?


-- 
Scott Robert Ladd
Coyote Gulch Productions (http://www.coyotegulch.com)
Software Invention for High-Performance Computing

Re: On inlining in C++ with unit-at-a-time code

[Gerald Pfeifer]

On Thu, 7 Aug 2003, Jan Hubicka wrote:
> Concerning the inlining limits, I believe we should increase them.

Sure, your analysis seems convincing...

> Situation seems to be the same for C++ programs I tested too (your
> benchmark suite and similar).

...and if someone else has conflicting test results, we can always
consider these later.

> For functions marked explicitely as inline I would like the limit to
> see even higher limit if C++ programming style allows us to do, this
> needs more testing, but I think the values around 500 would be OK.

In the light of recent discussion on this list, this seems like a
good idea.

> I hope we can enable unit-at-a-time at -O2 by default and solve the
> problem in easy way.  In SuSE we are experimentally building the
> distribution with it and now all problems directly attributable to
> unit-at-a-time seems to be gone.

Well, if you can build an entire distribution without problems, that
certainly looks good enough.

> With this settings I believe we should be able to quite consistently
> outperform the old inlining heuiristics of 2.95 both compile time-memory
> wise and code quality wise.

Cool. Really.

Gerald

Re: On inlining in C++ with unit-at-a-time code

[Mike Stump]

On Wednesday, August 13, 2003, at 03:45 PM, Gerald Pfeifer wrote:
> On Thu, 7 Aug 2003, Jan Hubicka wrote:
>> Concerning the inlining limits, I believe we should increase them.
>
> Sure, your analysis seems convincing...

I wasn't going to chime in, but...

I'm happy with the above sort of testing/experiments and am happy to 
have them increased.  When we have a balance of complaints for and 
against a change, then we know it is time to fundamentally improve the 
algorithms involved.  It feels to me that we've erred on the too small 
side for a while.

Thanks for doing this work, and thanks to anyone that offers feedback 
on the `right' values to use, and how bad things are, if the defaults 
are right.

Re: On inlining in C++ with unit-at-a-time code

[Andreas Jaeger]

[-- Attachment #1: Type: text/plain, Size: 1015 bytes --]

Gerald Pfeifer <gerald@pfeifer.com> writes:

> On Thu, 7 Aug 2003, Jan Hubicka wrote:
>> I hope we can enable unit-at-a-time at -O2 by default and solve the
>> problem in easy way.  In SuSE we are experimentally building the
>> distribution with it and now all problems directly attributable to
>> unit-at-a-time seems to be gone.
>
> Well, if you can build an entire distribution without problems, that
> certainly looks good enough.

We still have one failure in C++ that Honza will look at before we can
declare "it builds an entire distribution".

But other than that, it looks really good.  We just had to change half
a dozen packages were we had to add an attribute ((used)) since
functions/variables where used only via inline assembly.  And we
tested on x86, x86-64, ia64 and ppc.

Andreas
-- 
 Andreas Jaeger, aj@suse.de, http://www.suse.de/~aj
  SuSE Linux AG, Deutschherrnstr. 15-19, 90429 Nürnberg, Germany
   GPG fingerprint = 93A3 365E CE47 B889 DF7F  FED1 389A 563C C272 A126

[-- Attachment #2: Type: application/pgp-signature, Size: 197 bytes --]

Re: On inlining in C++ with unit-at-a-time code

[Gerald Pfeifer]

On Thu, 14 Aug 2003, Andreas Jaeger wrote:
> But other than that, it looks really good.  We just had to change half
> a dozen packages were we had to add an attribute ((used)) since
> functions/variables where used only via inline assembly.

Couldn't/shouldn't the compiler detect this kind of use as well, or
are these cases where the name of the function/variable actually never
was used?

Gerald

Re: On inlining in C++ with unit-at-a-time code

[Jan Hubicka]

> On Thu, 14 Aug 2003, Andreas Jaeger wrote:
> > But other than that, it looks really good.  We just had to change half
> > a dozen packages were we had to add an attribute ((used)) since
> > functions/variables where used only via inline assembly.
> 
> Couldn't/shouldn't the compiler detect this kind of use as well, or
> are these cases where the name of the function/variable actually never
> was used?

It is the case where the variable is unused in the source just
referenced by hand from the inline assembly.  Since we don´t parse it,
we can´t notice the reference.

Honza
> 
> Gerald

Re: On inlining in C++ with unit-at-a-time code

[Jan Hubicka]

> Jan Hubicka wrote:
> >So please if you complain about the inlining decisions, can you, please
> >try -O2 -funit-at-a-time --param max-insns-inline-single=500 --param
> >max-insns-inline-auto=150 and send me a testcases in case it won't do
> >what do you want? (if it inlines way too much, please try to lower the
> >inline-single limit to 150 again, I didn't do much testing with
> >inline-single limit set so high)
> 
> Am I correct that -funit-at-a-time and --param max-insns-inline-* came 
> came into existence with the advent of 3.4?
> 
> While I follow this list closely, are there any other "new" optimization 
> options I should be considering when testing 3.4?

-funit-at-a-time is new optimization and it is on by default at -O3 now.
max-inline-insns came in earlier but have somewhat different meaning as
the idea of instruction used to be number of statements * 10 and now it
is size of the syntactic tree with noop nodes ignored and some expensive
nodes thread specially.
I think I've misspelled the option in orignal email tought.

Honza
> 
> 
> -- 
> Scott Robert Ladd
> Coyote Gulch Productions (http://www.coyotegulch.com)
> Software Invention for High-Performance Computing

Re: On inlining in C++ with unit-at-a-time code

[Falk Hueffner]

Jan Hubicka writes:

> > On Thu, 14 Aug 2003, Andreas Jaeger wrote:
> > > But other than that, it looks really good.  We just had to change half
> > > a dozen packages were we had to add an attribute ((used)) since
> > > functions/variables where used only via inline assembly.
> > 
> > Couldn't/shouldn't the compiler detect this kind of use as well, or
> > are these cases where the name of the function/variable actually never
> > was used?
> 
> It is the case where the variable is unused in the source just
> referenced by hand from the inline assembly.  Since we don?t parse it,
> we can?t notice the reference.

Maybe we could create a pseudo constraint which would emit the name of
a symbol, and mark it as used?

-- 
	Falk

Re: On inlining in C++ with unit-at-a-time code

[Geoff Keating]

neroden@twcny.rr.com (Nathanael Nerode) writes:

> Jan said:
> >Unforutnately we can't do the change on mainline yet as old inlining
> >heuristics is still active for -O2 and will result in memory bombs 
> >then.
> >I hope we can enable unit-at-a-time at -O2 by default and solve the
> >problem in easy way.  In SuSE we are experimentally building the
> >distribution with it and now all problems directly attributable to
> >unit-at-a-time seems to be gone.  I will send more detailed summary
> >sometime next week as this week I am on the trip.  Of course few
> >remaining patches I sent needs to get in first but Mark seems to be
> >doing great job on reviewing them.
> 
> I would also like to see unit-at-a-time enabled by default for GCC 3.4.
> Given that it's always a valid way to compile C/C++, I'd like to see
> it enabled at *all* optimization levels (although it makes little 
> pratical difference at -O0).
> 
> Think this will be possible?  :-)

I don't think it would be a good idea at -O0 because of the extra
memory consumption.  I'm not sure whether it'd be appropriate at -O1,
I suspect probably not, it's pretty expensive.  I'd like to see it on
at -O2 for sure, and maybe -Os.

-- 
- Geoffrey Keating <geoffk@geoffk.org>

Re: On inlining in C++ with unit-at-a-time code

[Joe Buck]

On Thu, Aug 07, 2003 at 03:23:44PM -0400, Nathanael Nerode wrote:
> I would also like to see unit-at-a-time enabled by default for GCC 3.4.
> Given that it's always a valid way to compile C/C++, I'd like to see
> it enabled at *all* optimization levels (although it makes little 
> pratical difference at -O0).
> 
> Think this will be possible?  :-)

What's the cost for doing unit-at-a-time in terms of compile time and
virtual memory consumption?

Re: On inlining in C++ with unit-at-a-time code

[Nathanael Nerode]

Jan said:
>Unforutnately we can't do the change on mainline yet as old inlining
>heuristics is still active for -O2 and will result in memory bombs 
>then.
>I hope we can enable unit-at-a-time at -O2 by default and solve the
>problem in easy way.  In SuSE we are experimentally building the
>distribution with it and now all problems directly attributable to
>unit-at-a-time seems to be gone.  I will send more detailed summary
>sometime next week as this week I am on the trip.  Of course few
>remaining patches I sent needs to get in first but Mark seems to be
>doing great job on reviewing them.

I would also like to see unit-at-a-time enabled by default for GCC 3.4.
Given that it's always a valid way to compile C/C++, I'd like to see
it enabled at *all* optimization levels (although it makes little 
pratical difference at -O0).

Think this will be possible?  :-)

-- 
Nathanael Nerode  <neroden at gcc.gnu.org>
http://home.twcny.rr.com/nerode/neroden/fdl.html