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++

[Diego Novillo]

On Tue, 2003-08-05 at 22:00, Joe Buck wrote:

> Compile the following code with "gcc -O2 -S il.C" using the trunk on x86,
> and take a look.  The problem is that we prematurely commit the tmp object
> to the stack, even though after inlining its address is not taken.
> 
> --------------------------------------
> struct bar { int i; int j;};
> 
> #define MACRO(foo) (foo).i + (foo).j
> 
> inline int func(const bar& foo) {
>     return foo.i + foo.j;
> }
> 
> int call_macro()
> {
>     bar tmp;
>     tmp.i = 1;
>     tmp.j = 2;
>     return MACRO(tmp);
> }
> 
> int call_func()
> {
>     bar tmp;
>     tmp.i = 1;
>     tmp.j = 2;
>     return func(tmp);
> }
> --------------------------------------
>
Much later than I would've wanted, but this is fixed now on tree-ssa. 
Both functions are optimized into 'return 3;'.


Diego.

Re: On inlining in C++

[Nick Ing-Simmons]

Robert Dewar <dewar@gnat.com> writes:
>> Perhaps there is, but the Principle of Least Surprise favours a
>> fairly literal interpretation of "inline".
>
>I don't agree, a huge blow up in size, resulting in slower execution because
>of icache overload, can also qualify as a surprise.
>
>Indeed we find that customers are quite often surprised to find that -O3
>is slower than -O2 (as well as generating lots of code).

And of course cache size depends on which hardware is in use,
so what is right for a consumer-oid Celeron is not right for a 
server-oid Pentium-IV.

Re: On inlining in C++

[Kevin Atkinson]

On Fri, 8 Aug 2003, Marc Espie wrote:

> I thought the days where g++ was implementing a gnu mutant of C++ were
> gone. Maybe I'm wrong ?

So you are trying to say that compiler specific extensions are a bad thing
or compiler specific extensions that conflict with the standard are a
thing?

Re: On inlining in C++

[Marc Espie]

In article <20030804173619.F0FD7F2D7C@nile.gnat.com> you write:
>> Inline as I have described is close to what has been documented for
>> two decades in official C++ manuals.
>
>Well if you really believe that C++ programmers read "official C++
>manuals" then you are talking about a different population of programmers
>entirely.
>

Blink, blink.

So what ?

Is g++ trying to implement ISO C++, or a language that more or less
corresponds to the most widely deployed dialect of C++ out there
(probably Visual C++) and drop any attempt at conformance ?

Gaby quotes from the standard, and from the creator of the language.
It seems that other proficient C++ programmers in that thread agree
with him (err, I do).

I thought the days where g++ was implementing a gnu mutant of C++ were
gone. Maybe I'm wrong ?

Re: On inlining in C++

[Joe Buck]

On Wed, Aug 06, 2003 at 02:56:20PM -0400, Robert Dewar wrote:
> > Given that we can't inline mutually recursive functions, it is always
> > possible to fix the order so that things work, though it can be a pain
> > in the ass.
> 
> and that can be a bad distortion of the source code for bad reasons!

I've got to produce code that gets by at least four distinct C++
compilers, and pretty much all of them have this issue.  It goes away
with the new unit-at-a-time approach, but for portability programmers
will still need to consider order.

In practice, this problem is not that bad.  Declarations and
definitions are separate.  The declarations, with their documentation,
can appear in their most natural order; definitions might need to be
rearranged.  With a documentation-generating tool such as doxygen, or
a smart source code browser, the position of a given definition in the
source code becomes less of an issue.

Re: On inlining in C++

[Robert Dewar]

> Given that we can't inline mutually recursive functions, it is always
> possible to fix the order so that things work, though it can be a pain
> in the ass.

and that can be a bad distortion of the source code for bad reasons!

Re: On inlining in C++

[Alexandre Oliva]

Can we all agree with these statements, inferred from my reading of
the C++ Standard?

- inline functions are functions that are defined inside a class body,
  or explicitly marked with the inline keyword.

- for inline functions, inline substitution is to be preferred over
  the standard call sequences.

- a function may be defined in multiple translation units without
  violating the ODR only if the function is inline and the definitions
  are equivalent, as defined in the ODR.

- inline substitution doesn't modify the behavior of the program as
  far as the abstract machine of the standard is concerned, so it
  might be applied to non-inline functions as well, per the as-if
  rule.  Conversely, not performing inline substitution of an inline
  function is legal, even if not to be preferred.

-- 
Alexandre Oliva   Enjoy Guarana', see http://www.ic.unicamp.br/~oliva/
Red Hat GCC Developer                 aoliva@{redhat.com, gcc.gnu.org}
CS PhD student at IC-Unicamp        oliva@{lsd.ic.unicamp.br, gnu.org}
Free Software Evangelist                Professional serial bug killer

Re: On inlining in C++

[Joe Buck]

On Wed, Aug 06, 2003 at 10:30:09AM +0100, Richard Earnshaw wrote:
> > Richard Earnshaw <rearnsha@arm.com> writes:
> > 
> > | > I would point out that the documentation says "as fast as a macro",
> > | > but it should really say "as fast or faster than a macro".
> > | 
> > | Or "better than a macro".
> > 
> > "As fast as a macro" is just fine :-)
> 
> Ah! but it's not, as can be seen from this discussion... :-)

If tree-ssa ever manages to fix the problem I first pointed out on the
gcc2 list in 1994, then we'll actually achieve this goal (of inline
functions being as fast as macros) in almost all cases.

Actually, we have made progress since then: we handle the case of
structs/classes with one element (which occurs for many STL iterators)
well, and we don't get quite as many dead stores in other cases, though
the code still shows artifacts of premature stack slot assignment not
being completely undone, which can kill performance when it happens in an
inner loop.

Re: On inlining in C++

[Joe Buck]

On Tue, Aug 05, 2003 at 11:01:12PM -0400, Robert Dewar wrote:
> > excessive lookahead (call comes before the
> > definition)
> 
> This actually seems like a pretty serious limitation to me ...

Given that we can't inline mutually recursive functions, it is always
possible to fix the order so that things work, though it can be a pain
in the ass.

Re: On inlining in C++

[Gabriel Dos Reis]

Richard Earnshaw <rearnsha@arm.com> writes:

| > I would point out that the documentation says "as fast as a macro",
| > but it should really say "as fast or faster than a macro".
| 
| Or "better than a macro".

"As fast as a macro" is just fine :-)

-- Gaby

Re: On inlining in C++

[Richard Earnshaw]

> Richard Earnshaw <rearnsha@arm.com> writes:
> 
> | > I would point out that the documentation says "as fast as a macro",
> | > but it should really say "as fast or faster than a macro".
> | 
> | Or "better than a macro".
> 
> "As fast as a macro" is just fine :-)

Ah! but it's not, as can be seen from this discussion... :-)

R.

Re: On inlining in C++

[Richard Earnshaw]

> I would point out that the documentation says "as fast as a macro",
> but it should really say "as fast or faster than a macro".

Or "better than a macro".

R.

Re: On inlining in C++

[Steven Bosscher]

Op wo 06-08-2003, om 05:01 schreef Robert Dewar:
> > excessive lookahead (call comes before the
> > definition)
> 
> This actually seems like a pretty serious limitation to me ...

Hail to unit-at-a-time.

Re: On inlining in C++

[Andreas Jaeger]

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

dewar@gnat.com (Robert Dewar) writes:

>> excessive lookahead (call comes before the
>> definition)
>
> This actually seems like a pretty serious limitation to me ...

Fixed already with -funit-at-a-time,

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++

[Robert Dewar]

> excessive lookahead (call comes before the
> definition)

This actually seems like a pretty serious limitation to me ...

Re: On inlining in C++

[Joe Buck]

> > Ah, but even if we fix the inlining issues, we still aren't keeping the
> > promise: inline functions are still slower in many cases if 
> > struct/class
> > objects with more than one member are passed by reference.

On Tue, Aug 05, 2003 at 10:15:05PM -0400, Andrew Pinski wrote:
>   (but that macro is not equivalent to that function).

Yes, you can nitpick it, but the effect is real.

Re: On inlining in C++

[Andrew Pinski]

On Tuesday, Aug 5, 2003, at 22:00 US/Eastern, Joe Buck wrote:

>
>>> There are tons of messages in this (or related thread) so it might be
>>> possible that I missed a message that disagreed with the
>>> interpretation of the documentation I quoted.  Can you give reference
>>> to such a message?
>
> On Tue, Aug 05, 2003 at 11:16:56AM -0700, Geoff Keating wrote:
>> I would point out that the documentation says "as fast as a macro",
>> but it should really say "as fast or faster than a macro".
>
> Ah, but even if we fix the inlining issues, we still aren't keeping the
> promise: inline functions are still slower in many cases if 
> struct/class
> objects with more than one member are passed by reference.
  (but that macro is not equivalent to that function).
>
> Compile the following code with "gcc -O2 -S il.C" using the trunk on 
> x86,
> and take a look.  The problem is that we prematurely commit the tmp 
> object
> to the stack, even though after inlining its address is not taken.

Yes this is a know defect in gcc which should be fixed soon on the 
tree-ssa branch,
it is not yet but it should be soon.

Thanks,
Andrew Pinski

Re: On inlining in C++

[Joe Buck]

On Tue, Aug 05, 2003 at 08:03:33PM +0200, Matthias Benkmann wrote:
> On Tue, 5 Aug 2003 15:00:49 +0200 (CEST) Richard Guenther
> <rguenth@tat.physik.uni-tuebingen.de> wrote:
> 
> > The point is, all these "people will optimize" suggestions go against
> > portability to different compilers.  
> 
> How many developers using GCC care about other compilers?

I do.

> And how is portability harmed anyway? If GCC starts honouring inline
> declarations and people use this feature for GCC-specific optimization,
> then the worst that will happen is that a different compiler that does not
> honour inline uses its built-in heuristics when compiling the program.

Other compilers, for the most part, either honor the "inline" keyword or
can be made to issue an explanatory warning as to why the programmer's
request was not honored.  cfront's inlining capability was extremely
limited, and required that it be straightforward to rewrite the function
call as an expression involving the arguments.  But even so, it was
predictable.

Re: On inlining in C++

[Joe Buck]

> > There are tons of messages in this (or related thread) so it might be
> > possible that I missed a message that disagreed with the
> > interpretation of the documentation I quoted.  Can you give reference 
> > to such a message?

On Tue, Aug 05, 2003 at 11:16:56AM -0700, Geoff Keating wrote:
> I would point out that the documentation says "as fast as a macro",
> but it should really say "as fast or faster than a macro".

Ah, but even if we fix the inlining issues, we still aren't keeping the
promise: inline functions are still slower in many cases if struct/class
objects with more than one member are passed by reference.

Compile the following code with "gcc -O2 -S il.C" using the trunk on x86,
and take a look.  The problem is that we prematurely commit the tmp object
to the stack, even though after inlining its address is not taken.

--------------------------------------
struct bar { int i; int j;};

#define MACRO(foo) (foo).i + (foo).j

inline int func(const bar& foo) {
    return foo.i + foo.j;
}

int call_macro()
{
    bar tmp;
    tmp.i = 1;
    tmp.j = 2;
    return MACRO(tmp);
}

int call_func()
{
    bar tmp;
    tmp.i = 1;
    tmp.j = 2;
    return func(tmp);
}
--------------------------------------

Re: On inlining in C++

[Gabriel Dos Reis]

Steven Bosscher <s.bosscher@student.tudelft.nl> writes:

| Op di 05-08-2003, om 20:03 schreef Matthias Benkmann:
| > On Tue, 5 Aug 2003 15:00:49 +0200 (CEST) Richard Guenther
| > <rguenth@tat.physik.uni-tuebingen.de> wrote:
| > 
| > > The point is, all these "people will optimize" suggestions go against
| > > portability to different compilers.  
| > 
| > How many developers using GCC care about other compilers?
| 
| In the scientific community, most do.

Yes.  I myself got high interests in GCC when working on a European
scientific project, using C++.  
And I'm still working on scientific computing projects.  
I just don't mention it in my signature :-) 

-- Gaby

Re: On inlining in C++

[Steven Bosscher]

Op di 05-08-2003, om 20:03 schreef Matthias Benkmann:
> On Tue, 5 Aug 2003 15:00:49 +0200 (CEST) Richard Guenther
> <rguenth@tat.physik.uni-tuebingen.de> wrote:
> 
> > The point is, all these "people will optimize" suggestions go against
> > portability to different compilers.  
> 
> How many developers using GCC care about other compilers?

In the scientific community, most do.

I know I do.

Gr.
Steven

Re: On inlining in C++

[Geoff Keating]

Gabriel Dos Reis <gdr@integrable-solutions.net> writes:

> dewar@gnat.com (Robert Dewar) writes:
> 
> | > The behaviour I'm arguing for is that one documented for over two
> | > decades.  That is not passion.
> | 
> | No, but it is goal-directed interpretation.
> 
> Not really.  I see people disagreeing with the notion of trusting the
> programmer.  
> 
> There are tons of messages in this (or related thread) so it might be
> possible that I missed a message that disagreed with the
> interpretation of the documentation I quoted.  Can you give reference 
> to such a message?

I would point out that the documentation says "as fast as a macro",
but it should really say "as fast or faster than a macro".

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

Re: On inlining in C++

[Matthias Benkmann]

On Tue, 5 Aug 2003 15:00:49 +0200 (CEST) Richard Guenther
<rguenth@tat.physik.uni-tuebingen.de> wrote:

> The point is, all these "people will optimize" suggestions go against
> portability to different compilers.  

How many developers using GCC care about other compilers?
And how is portability harmed anyway? If GCC starts honouring inline
declarations and people use this feature for GCC-specific optimization,
then the worst that will happen is that a different compiler that does not
honour inline uses its built-in heuristics when compiling the program.
The thing that DOES go against portability to other compilers is stuff
like "always_inline". THAT is unportable. You're saying that offering this
as the only option of optimizing for GCC is better?????

> Optimizing inlining in a portable
> way ist just not possible

Only if you want to have portability to very exotic platforms that few
people care about and for which GCC is certainly not a very relevant
compiler in the 1st place.

MSB

p.s.: Please do not CC me. Thank you.

Re: On inlining in C++

[Gabriel Dos Reis]

dewar@gnat.com (Robert Dewar) writes:

| > The behaviour I'm arguing for is that one documented for over two
| > decades.  That is not passion.
| 
| No, but it is goal-directed interpretation.

Not really.  I see people disagreeing with the notion of trusting the
programmer.  

There are tons of messages in this (or related thread) so it might be
possible that I missed a message that disagreed with the
interpretation of the documentation I quoted.  Can you give reference 
to such a message?

-- Gaby

Re: On inlining in C++

[Robert Dewar]

> The behaviour I'm arguing for is that one documented for over two
> decades.  That is not passion.

No, but it is goal-directed interpretation. Not everyone agrees with
your interpretation of the documentation! (I hope that you can see
that this statement at least is correct :-)

Re: On inlining in C++

[Scott Robert Ladd]

Robert Dewar wrote:
> Even the mechanism of dispatchinhg calls is completely undefined (and there
> are indeed two radically different mechanisms, one of which has no overhead
> from multiple inheritance, but costs quite a bit if you use MI). There are
> many things in C++ where the programmer has very little control (elaboration
> is another example).

Apples and oranges.

Standard C++ includes an "inline" keyword so I can specify that a 
function should be treated a an expected fashion (if possible). The 
language also includes the ability to inline functions by declaring them 
inside the class definition. It seems to me that the existence of those 
mechanisms implies that a compiler should respect them.

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

Re: On inlining in C++

[Gabriel Dos Reis]

dewar@gnat.com (Robert Dewar) writes:

| > So?
| > 
| > -- Gaby
| 
| So, the notion of trusting the programmer is not an absolute one. 

That might not be an absolute one accoding to your definition of
aboslute.  But it is a practical notion that has served to design,
evolve and standardize the language.  That might be another difference
between C++ and Ada.

[...]

| (without much data, but with much passion) 

The behaviour I'm arguing for is that one documented for over two
decades.  That is not passion.

-- Gaby

Re: On inlining in C++

[Robert Dewar]

> So?
> 
> -- Gaby

So, the notion of trusting the programmer is not an absolute one. C++ is
fairly far from what Tuck would call a WYSIWYG language, where you have a
reasonable knowledge of the code being generated at all times. Dispatching,
elaboration, destructor handling, exceptions, are among many cases where
the implementation model is entirely undefined by the language, and varies
between implementations, so if you expect your trusted programmer to know
what is going on, that's not always achievable.

To some extent, the current discussion is on whether inlining should or 
should not be WYSIWYG in Tuck's sense (I find this quite a useful
notion in language design and implemenation). Gaby and others argue (without
much data, but with much passion) that inlining should never be up to the
compiler. Others argue (without much data, but with much passion) that of
course the implementation model for inlining should be something the
compiler controls.

Re: On inlining in C++

[Gabriel Dos Reis]

dewar@gnat.com (Robert Dewar) writes:

| > I use C++ because it implicitly trusts the programmer; that is part of 
| > the core C++ philosophy.
| 
| Even the mechanism of dispatchinhg calls is completely undefined (and there
| are indeed two radically different mechanisms, one of which has no overhead
| from multiple inheritance, but costs quite a bit if you use MI). There are
| many things in C++ where the programmer has very little control (elaboration
| is another example).

So?

-- Gaby

Re: On inlining in C++

[Robert Dewar]

> 
> I use C++ because it implicitly trusts the programmer; that is part of 
> the core C++ philosophy.

Even the mechanism of dispatchinhg calls is completely undefined (and there
are indeed two radically different mechanisms, one of which has no overhead
from multiple inheritance, but costs quite a bit if you use MI). There are
many things in C++ where the programmer has very little control (elaboration
is another example).

Re: On inlining in C++

[Scott Robert Ladd]

Robert Dewar wrote:
> You are assuming a model of someone who understands the possible effects
> of inlining and knows what an instruction cache is and how it works. The
> readership and writership of this list is hardly a representative cross-
> section of "in the trenches" C++ programmers, who in my experience have
> very little awarness of what is going on at the machine level.

I've spent more than a decade managing and working with C++ programmers. 
In my experience, a programmer with "very little awareness" is likely to 
make many significant mistakes; any ill-uses of "inline" will be masked 
by other programming ignorances.

I use C++ because it implicitly trusts the programmer; that is part of 
the core C++ philosophy.

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

Re: On inlining in C++

[Robert Dewar]

Steven said

> So far, no-one has actually tried it and produced numbers.

Sounds like a relatively easy way to get some numbers, and definitely
data would help clear the air of guesses on all sides. These guesses
may be better or worse informed, but they are still guesses :-)

Re: On inlining in C++

[Robert Dewar]

> Even if we change gcc in the way that Gaby suggests, we could still
> provide the existing behaviour as a flag.  A sort of restricted
> -finline-functions.  It's not like we have to lose the existing
> behaviour entirely.

But the flag already exists, ultimately this is a discussion about where
to set the thresshold by default.

Re: On inlining in C++

[Robert Dewar]

> - 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.

This is not nearly so simple as you think. Because of the phenomenon of
cache thrashing, you can get a procedure which looks very tiny, and the
timings of your chip may imply that the call is almost free (e.g. on the
power architecture), but because of cache thrashing you get horrible
behavior in a loop.

> 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.

Well for sure that's not true, to have the complete picture requires an
exact simulation of cache behavior and in any case with hundreds of
instructions in flight, analyzing what is going on can be very very hard.

> 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.

Possibly, but it is likely to be a case of the blind leading the blind, since
often neither the programmer nor the compiler really know enough.

Fortunately, as someone pointed out, in exewcution time, it is fairly unusual
that inlining can make a difference (we certainly have some customers with
very large critical applications, e.g. in air traffic control,, where it
does make a difference, but this is not the norm). One effect you do want
to avoid is some huge blowup in code size, which in the worst case blows
up the compiler as well.

Re: On inlining in C++

[Gabriel Dos Reis]

Richard Guenther <rguenth@tat.physik.uni-tuebingen.de> writes:

| On 5 Aug 2003, Gabriel Dos Reis wrote:
| 
| > Richard Guenther <rguenth@tat.physik.uni-tuebingen.de> writes:
| >
| > | On 5 Aug 2003, Gabriel Dos Reis wrote:
| > |
| > | > Richard Guenther <rguenth@tat.physik.uni-tuebingen.de> writes:
| > | >
| > | > | The point is, all these "people will optimize" suggestions go against
| > | > | portability to different compilers.
| > | >
| > | > It is going to be non portable only if compiler back ends decide they
| > | > know better and don't trust the programmer preference.  Inline in C++
| > | > precisely to cut down the non-portability.  Inline in C++ does not
| > | > mean "hey back-end, optimize this as you want".
| > |
| > | The standard doesnt say something explicit about this. And current
| > | practice of most compilers I know is to either ignore "inline" or give it
| > | a boost in any heuristics they use. Most of them are weak in inlining
| > | decisions (or fail to honour "inline"),
| >
| > Not just because some can fail to do their jobs means GCC also should fail
| > as well. Others don't fail and GCC should be among those.  Give the
| > obvious meaning and trust the programmer.
| > If you actually do better than  obvious "inline" in most cases, then
| > the programmer will choose.  But the fact is, you don't.  Until you
| > do, give the programmer the obvious meaning so that she can
| > consistently make her decisions.
| >
| > inline is already there, we don't need a revinvention.
| 
| This is the answer only to those cases where existing compiler technology
| can decide already, namely for small functions falling out of abstraction
| and protection stuff.

but we're having this debate in part because that compiler decision
does match documented behaviour.

| I have lots of code where inlining a method blows up compile and hits
| executable size if "inline" is treated literally,

It seems like you want the compiler to decide for you, GCC seems to
have a flag for that.

|  but in one or two places
| this inlining is absolutely necessary to allow loop optimizations to take
| place. 

Then let's have the compiler honour inline, be consistent, most of of
the time predictable. It will cover those cases, and for the case
you're not sure, don't use "inline", let's the compiler decide for you.

| The C++ standard doesnt offer a solution to this problem other than
| perhaps wrapping those methods into funny dont-inline methods like Thomas
| Kunert proposed (but then, a smart compiler would inline noinline_f() as
| it contains only one function call and such resulting code is always
| smaller?).

I'll repeat what I said earlier:  If you think that C++ should offer
such thing, then you should submit a proposal or convince someone on
the committee to do so.

-- Gaby

Re: On inlining in C++

[Richard Guenther]

On 5 Aug 2003, Gabriel Dos Reis wrote:

> Richard Guenther <rguenth@tat.physik.uni-tuebingen.de> writes:
>
> | On 5 Aug 2003, Gabriel Dos Reis wrote:
> |
> | > Richard Guenther <rguenth@tat.physik.uni-tuebingen.de> writes:
> | >
> | > | The point is, all these "people will optimize" suggestions go against
> | > | portability to different compilers.
> | >
> | > It is going to be non portable only if compiler back ends decide they
> | > know better and don't trust the programmer preference.  Inline in C++
> | > precisely to cut down the non-portability.  Inline in C++ does not
> | > mean "hey back-end, optimize this as you want".
> |
> | The standard doesnt say something explicit about this. And current
> | practice of most compilers I know is to either ignore "inline" or give it
> | a boost in any heuristics they use. Most of them are weak in inlining
> | decisions (or fail to honour "inline"),
>
> Not just because some can fail to do their jobs means GCC also should fail
> as well. Others don't fail and GCC should be among those.  Give the
> obvious meaning and trust the programmer.
> If you actually do better than  obvious "inline" in most cases, then
> the programmer will choose.  But the fact is, you don't.  Until you
> do, give the programmer the obvious meaning so that she can
> consistently make her decisions.
>
> inline is already there, we don't need a revinvention.

This is the answer only to those cases where existing compiler technology
can decide already, namely for small functions falling out of abstraction
and protection stuff.

I have lots of code where inlining a method blows up compile and hits
executable size if "inline" is treated literally, but in one or two places
this inlining is absolutely necessary to allow loop optimizations to take
place. The C++ standard doesnt offer a solution to this problem other than
perhaps wrapping those methods into funny dont-inline methods like Thomas
Kunert proposed (but then, a smart compiler would inline noinline_f() as
it contains only one function call and such resulting code is always
smaller?).

Richard.

--
Richard Guenther <richard dot guenther at uni-tuebingen dot de>
WWW: http://www.tat.physik.uni-tuebingen.de/~rguenth/

Re: On inlining in C++

[Gabriel Dos Reis]

Richard Guenther <rguenth@tat.physik.uni-tuebingen.de> writes:

| On 5 Aug 2003, Gabriel Dos Reis wrote:
| 
| > Richard Guenther <rguenth@tat.physik.uni-tuebingen.de> writes:
| >
| > | The point is, all these "people will optimize" suggestions go against
| > | portability to different compilers.
| >
| > It is going to be non portable only if compiler back ends decide they
| > know better and don't trust the programmer preference.  Inline in C++
| > precisely to cut down the non-portability.  Inline in C++ does not
| > mean "hey back-end, optimize this as you want".
| 
| The standard doesnt say something explicit about this. And current
| practice of most compilers I know is to either ignore "inline" or give it
| a boost in any heuristics they use. Most of them are weak in inlining
| decisions (or fail to honour "inline"),

Not just because some can fail to do their jobs means GCC also should fail
as well. Others don't fail and GCC should be among those.  Give the
obvious meaning and trust the programmer.  
If you actually do better than  obvious "inline" in most cases, then
the programmer will choose.  But the fact is, you don't.  Until you
do, give the programmer the obvious meaning so that she can
consistently make her decisions.  

inline is already there, we don't need a revinvention.

-- Gaby

Re: On inlining in C++

[Richard Guenther]

On 5 Aug 2003, Gabriel Dos Reis wrote:

> Richard Guenther <rguenth@tat.physik.uni-tuebingen.de> writes:
>
> | The point is, all these "people will optimize" suggestions go against
> | portability to different compilers.
>
> It is going to be non portable only if compiler back ends decide they
> know better and don't trust the programmer preference.  Inline in C++
> precisely to cut down the non-portability.  Inline in C++ does not
> mean "hey back-end, optimize this as you want".

The standard doesnt say something explicit about this. And current
practice of most compilers I know is to either ignore "inline" or give it
a boost in any heuristics they use. Most of them are weak in inlining
decisions (or fail to honour "inline"), so they fall on their face trying
to vectorize expression template code and drop from GFLOPS to MFLOPS
performance...

But at least most of them have constructs like #pragma inline or
#pragma inline complete to give control about inlining per call.
They also are a lot better with their decisions given profiling data.

Richard.

--
Richard Guenther <richard dot guenther at uni-tuebingen dot de>
WWW: http://www.tat.physik.uni-tuebingen.de/~rguenth/

Re: On inlining in C++

[Gabriel Dos Reis]

Richard Guenther <rguenth@tat.physik.uni-tuebingen.de> writes:

| The point is, all these "people will optimize" suggestions go against
| portability to different compilers.

It is going to be non portable only if compiler back ends decide they
know better and don't trust the programmer preference.  Inline in C++
precisely to cut down the non-portability.  Inline in C++ does not
mean "hey back-end, optimize this as you want".

-- Gaby

Re: On inlining in C++

[Richard Guenther]

Matthias Benkmann wrote:

> One thing that is often overlooked is that most programs written today
> (for desktop platforms, not embedded systems!) do not need inlining
> optimization AT ALL. All of the programs I've written so far perform
> adequately regardless of whether I compile them with -Os, -O1, -O2 or -O3,
> -finline-functions, -whatever. The importance of optimization is vastly
> overrated. There are very few applications for which optimization makes a
> major difference (e.g. software MPEG-decoders). And these applications are
> usually carefully examined and maintained by capable people. These people
> should have a portable way of making their own inlining decisions. These
> are the people who complain if they can't do so. These are the people who
> complain if a new GCC version has a regression in the automatic inliner.
> These are the people GCC should be optimized for.
>
> The vast majority of developers won't notice the difference either way.
> But even they will be more happy if they look at the assembly of their
> compiled program and see that the compiler has inlined the functions they
> declared inline. It gives them the reassuring feeling that they are in
> charge.

The point is, all these "people will optimize" suggestions go against
portability to different compilers.  Optimizing inlining in a portable
way ist just not possible - neither the C++ standard, nor compilers
practice of interpreting it helps you at this task.

So to say it in other words: The only way to get good performance with
regard to inlining out of "portable" C++ programs is to improve the
automatic inlining heuristics of the _compiler_. You just cannot apply the
same heuristics wrt placing the "inline" keyword for gcc on ia32 and f.i.
the C++ compiler on a Hitachi SR8000 pseudo-vector computer. This is
the world of HPC and not about micro-optimizing your mpeg player.

Richard.

--
Richard Guenther <richard dot guenther at uni-tuebingen dot de>
WWW: http://www.tat.physik.uni-tuebingen.de/~rguenth/

Re: On inlining in C++

[Matthias Benkmann]

On 05 Aug 2003 08:39:39 +0100 Richard Sandiford <rsandifo@redhat.com>
wrote:

> I'd have thought the burden was (almost entirely) on the people
> defending g++'s current behaviour.  Suppose that, as an experiment,
> someone changes g++ to interpret inline in the "traditional"[*] way.
> And then someone shows that this leads to worse performance for program
> X on target Y.  I don't think we can then say that the compiler is right
> to behave is it does now.  Perhaps whoever wrote program X didn't care
> about the performance on target Y, or perhaps s/he simply used "inline"
> poorly.

I don't think this will happen.

> Both are possible, and it's not the sort of thing you're going to get
> from a simple statistical analysis 

I think that statistics is fine to resolve this, but I suggest a different
statistical measure. We've had lots of complaints about GCC not inlining
well (and in the cases I remember it was always that GCC didn't inline a
function the programmer wanted to be inlined, never the other way around).
If the new strategy results in fewer complaints, it is good.

GCC's technical qualities are irrelevant IMHO. "Customer" satisfaction is
the only thing that counts. A GCC that optimizes well in 90% of cases and
produces lots of complaints due to the remaining 10% where it is abysmal,
is not as good as a GCC that optimizes well in 10% of cases and doesn't
produce complaints because in the other 90% of cases it performs
adequately.

One thing that is often overlooked is that most programs written today
(for desktop platforms, not embedded systems!) do not need inlining
optimization AT ALL. All of the programs I've written so far perform
adequately regardless of whether I compile them with -Os, -O1, -O2 or -O3,
-finline-functions, -whatever. The importance of optimization is vastly
overrated. There are very few applications for which optimization makes a
major difference (e.g. software MPEG-decoders). And these applications are
usually carefully examined and maintained by capable people. These people
should have a portable way of making their own inlining decisions. These
are the people who complain if they can't do so. These are the people who
complain if a new GCC version has a regression in the automatic inliner.
These are the people GCC should be optimized for.

The vast majority of developers won't notice the difference either way.
But even they will be more happy if they look at the assembly of their
compiled program and see that the compiler has inlined the functions they
declared inline. It gives them the reassuring feeling that they are in
charge. Maybe the inlining decision was bad for the cache, but who cares
if the program (like most applications) has to wait for network, disk or
user most of the time or spends most of its time in a system library
(maintained again by the capable people mentioned above)?

MSB

-- 
Ask a silly person, get a silly answer.

Re: On inlining in C++

[Richard Guenther]

On 5 Aug 2003, Gabriel Dos Reis wrote:

> Richard Guenther <rguenth@tat.physik.uni-tuebingen.de> writes:
>
> | Of course - but this looks like a workaround for a C++ defect, not like a
> | good design principle ;) I'd rather like
> |
> | void f(int) { ... }
> |
> | void g(int i) {
> |   inline f(5);
> |   f(i);
> | }
> |
> | to have one call inlined, not the other. But of course this aint C++...
>
> Please, let's separate new language features design from implementation
> of existing ones.

Of course - I was just thinking in public, as maybe such syntax would be
legal but without defined semantics. But in general a portable way to
specify such would be appreciated.

> The next C++ standards committee meeting is in September in Kona.  If
> you think that is something C++ should have, please submit a proposal.

I dont have time to do so and I'm not familiar with the process and I even
dont know C++ enough to think of all effects of such.

Richard.

--
Richard Guenther <richard dot guenther at uni-tuebingen dot de>
WWW: http://www.tat.physik.uni-tuebingen.de/~rguenth/

Re: On inlining in C++

[Gabriel Dos Reis]

Richard Guenther <rguenth@tat.physik.uni-tuebingen.de> writes:

| Of course - but this looks like a workaround for a C++ defect, not like a
| good design principle ;) I'd rather like
| 
| void f(int) { ... }
| 
| void g(int i) {
|   inline f(5);
|   f(i);
| }
| 
| to have one call inlined, not the other. But of course this aint C++...

Please, let's separate new language features design from implementation
of existing ones.  

The next C++ standards committee meeting is in September in Kona.  If
you think that is something C++ should have, please submit a proposal.  

-- Gaby

Re: On inlining in C++

[Richard Guenther]

On Tue, 5 Aug 2003, Thomas Kunert wrote:

> Richard Guenther wrote:
> >>- 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.
> >
> >
> > For the last two points you made the problem is, that there is no
> > (portable) way to tell the compiler to inline into certain positions or in
> > certain cases.
>
> Of course there is:
>
> inline void inline_f()
> {
>     // actual code
> }
>
> void noinline_f()
> {
>     inline_f();
> }
>
> Then you can decide at each call if you want inlining or not. Or take
> the pow() example from the beginning of the thread. It doesn't really matter
> if it gets inlined for constant exponents, say pow(x,2), because everybody
> already has functions pow2(x), pow3(x), ... :-)

Of course - but this looks like a workaround for a C++ defect, not like a
good design principle ;) I'd rather like

void f(int) { ... }

void g(int i) {
  inline f(5);
  f(i);
}

to have one call inlined, not the other. But of course this aint C++...

Maybe

void g(int i) {
  inline void (&f_inline)(int) = f;
  f_inline(5);
  f(i);
}

yields

inline2.cpp: In function `void g(int)':
inline2.cpp:5: `f_inline' declared as an `inline' variable

shouldnt an inline variable declaration look like

  void (inline &f_inline)(int) = f;

? So the warning is bogous... (but of course this aint C++ either).

Richard.

--
Richard Guenther <richard dot guenther at uni-tuebingen dot de>
WWW: http://www.tat.physik.uni-tuebingen.de/~rguenth/

Re: On inlining in C++

[Thomas Kunert]

Richard Guenther wrote:
>>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.
> 
> 
> In general the compiler could know, at least if including profiling
> feedback.
> 

Sure, in principle. In theory. But that doesn't help today. I am with you
when the compiler can _prove_ its decisions.

> 
>>- 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.
> 
> 
> No, its the other way around - if the time spent in the function is very
> short, its a good candidate for inlining (because function call overhead
> may be comparable to actual runtime).
> 

I talked about the total time over the full run of the program. If one saves
half of a micro second, it is not worth the trouble.

> 
>>- 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.
> 
> 
> For the last two points you made the problem is, that there is no
> (portable) way to tell the compiler to inline into certain positions or in
> certain cases. 

Of course there is:

inline void inline_f() 
{
    // actual code
}

void noinline_f()
{
    inline_f();
}

Then you can decide at each call if you want inlining or not. Or take
the pow() example from the beginning of the thread. It doesn't really matter
if it gets inlined for constant exponents, say pow(x,2), because everybody
already has functions pow2(x), pow3(x), ... :-)

Thomas Kunert

Re: On inlining in C++

[Steven Bosscher]

Op di 05-08-2003, om 09:39 schreef Richard Sandiford:
> So (IMO) if g++ is going to ignore inline requests for "inlineable"
> functions, the data in favour of that should be overwhelming.  It's a
> bit worrying that g++ is already doing this and that no-one seems to
> have a large body of existing data to justify it.

See http://gcc.gnu.org/ml/gcc/2003-07/msg02138.html for a patch that
tells the tree inliner to disregard limits for C++ if the function is
declared `inline'.

This effectively forces `inline' functions to be inlined (unless of
course there are other reasons why inlining is not possible, such as
calls to alloca(), or if the function body isn't available yet).

So far, no-one has actually tried it and produced numbers.

> Even if we change gcc in the way that Gaby suggests, we could still
> provide the existing behaviour as a flag. 

Yup, it's easy enough.

Gr.
Steven

Re: On inlining in C++

[Richard Guenther]

> 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.

In general the compiler could know, at least if including profiling
feedback.

> - 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.

For constants it knows, for others we'd have value range profiling.

>- 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.

No, its the other way around - if the time spent in the function is very
short, its a good candidate for inlining (because function call overhead
may be comparable to actual runtime).

>- 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.

For the last two points you made the problem is, that there is no
(portable) way to tell the compiler to inline into certain positions or in
certain cases. It is only the compiler that can do this sort of context
dependend inlining decision.

> 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.

The C++ standard does not specify a way to tell (or hint) the compiler to
inline a certain function call. So for a large amount of cases you
absolutely _have_ to rely on the compiler to decide. Or you'll pay for at
different places.

Richard.

--
Richard Guenther <richard dot guenther at uni-tuebingen dot de>
WWW: http://www.tat.physik.uni-tuebingen.de/~rguenth/

Re: On inlining in C++

[Richard Sandiford]

dewar@gnat.com (Robert Dewar) writes:
> > 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.
> 
> Well there is a burden of demonstration on both sides I would say, in terms
> of showing behavior on actual code.

I'd have thought the burden was (almost entirely) on the people
defending g++'s current behaviour.  Suppose that, as an experiment,
someone changes g++ to interpret inline in the "traditional"[*] way.
And then someone shows that this leads to worse performance for program
X on target Y.  I don't think we can then say that the compiler is right
to behave is it does now.  Perhaps whoever wrote program X didn't care
about the performance on target Y, or perhaps s/he simply used "inline"
poorly.

Both are possible, and it's not the sort of thing you're going to get
from a simple statistical analysis (said in response to: "we need more
data", from another message).

So (IMO) if g++ is going to ignore inline requests for "inlineable"
functions, the data in favour of that should be overwhelming.  It's a
bit worrying that g++ is already doing this and that no-one seems to
have a large body of existing data to justify it.

Even if we change gcc in the way that Gaby suggests, we could still
provide the existing behaviour as a flag.  A sort of restricted
-finline-functions.  It's not like we have to lose the existing
behaviour entirely.

Richard

PS. OK, so "principle of least surprise" was shorter ;)

[*] the one that Gaby quoted.

Re: On inlining in C++

[Joe Buck]

On Mon, Aug 04, 2003 at 11:45:36AM -0700, Geoff Keating wrote:
I wrote:

> > Option 1:[honor inline]
> > 
> > Option 2: a version of GNU C++ that uses the smartest heuristics that the
> > "ignore inline" advocates can come up with.
> 
> I completely agree.
> 
> However, I claim that option (2) will always win or tie.  Why?
> Because you can always use heuristics that are "inline exactly when
> option (1) would have inlined".

Well, certainly if #2 == #1, then you tie.

However, you don't win or tie if you get the same code, but the compiler
runs slower.

Re: On inlining in C++

[Geoff Keating]

Joe Buck <jbuck@synopsys.com> writes:

> On Mon, Aug 04, 2003 at 12:35:48PM -0400, Robert Dewar wrote:
> > > 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.
> > 
> > Well there is a burden of demonstration on both sides I would say, in terms
> > of showing behavior on actual code.
> 
> Don't forget that the biggest complaint we have about GCC is how slow the
> compiler is.  Ignoring or partially ignoring "inline", and doing analysis
> instead, costs time.
> 
> I suggest resolving this argument by doing an experiment.
> 
> Option 1: a version of GNU C++ that
> 
> * honors the "inline" keyword in all situations where the compiler is
>   capable of inlining the call
> * does the same for functions defined in the class body
> * when -Winline is given, issues a warning and explanation about why
>   a call is not inlined
> * avoids computing any metrics related to inlining decisions (unless -O3)
> 
> Option 2: a version of GNU C++ that uses the smartest heuristics that the
> "ignore inline" advocates can come up with.

I completely agree.

However, I claim that option (2) will always win or tie.  Why?
Because you can always use heuristics that are "inline exactly when
option (1) would have inlined".

In fact, I will go further, and claim that option (2) will win.
Saying that option (2) will tie is equivalent to saying that every
case of inlining triggered by option (1) is neutral or good for
performance, and I know that this is not true.  You can start by
rejecting cases that cannot possibly be good for performance.

> Now, build a lot of C++ code with -O2 for both options.  Measure compiler
> speed as well as speed and space of the final code.  If option 2 is
> consistently better, I surrender.  If option 2 is better only for one or
> two programs, and it turns out that these programs use "inline" in
> inappropriate ways, then the programs should be fixed.

Don't forget to test on multiple targets!

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

Re: On inlining in C++

[Bernd Schmidt]

On Mon, 4 Aug 2003, Robert Dewar wrote:

> > Perhaps there is, but the Principle of Least Surprise favours a
> > fairly literal interpretation of "inline".
>
> I don't agree, a huge blow up in size, resulting in slower execution because
> of icache overload, can also qualify as a surprise.
>
> Indeed we find that customers are quite often surprised to find that -O3
> is slower than -O2 (as well as generating lots of code).

Which seems to prove the point that compiler heuristics aren't working well
in practice.  Hence, explicit control is necessary.


Bernd

Re: On inlining in C++

[Gabriel Dos Reis]

Daniel Jacobowitz <drow@mvista.com> writes:

| On Mon, Aug 04, 2003 at 07:47:42PM +0200, Gabriel Dos Reis wrote:
| > dewar@gnat.com (Robert Dewar) writes:
| > 
| > | > Inline as I have described is close to what has been documented for
| > | > two decades in official C++ manuals.
| > | 
| > | Well if you really believe that C++ programmers read "official C++
| > | manuals" then you are talking about a different population of programmers
| > | entirely.
| > 
| > "The C++ Programming Language" -- ranging from the first edition to
| > the special edition -- by Bjarne Stroustrup is such a document and
| > given the number of sales[1], I think I have pretty good data.
| > 
| > [1]http://www.research.att.com/~bs/3rd.html
| 
| I posit that the average amount read or understood per purchased copy
| of that (excellent) book is nowhere near enough to make informed
| decisions about this topic.

Certainly you don't need to understand the whole book before
understanding what inline is designed for.  Furthermore articles[1]
published regularly for broad public explain most of the key
functionalities, i.e. you don't need to purchase the book before
knowing about inlining and why it is part of the language.


[1] http://www.research.att.com/~bs/papers.html
[2] http://www.research.att.com/~bs/wrapper.pdf

-- Gaby

Re: On inlining in C++

[Daniel Jacobowitz]

On Mon, Aug 04, 2003 at 07:47:42PM +0200, Gabriel Dos Reis wrote:
> dewar@gnat.com (Robert Dewar) writes:
> 
> | > Inline as I have described is close to what has been documented for
> | > two decades in official C++ manuals.
> | 
> | Well if you really believe that C++ programmers read "official C++
> | manuals" then you are talking about a different population of programmers
> | entirely.
> 
> "The C++ Programming Language" -- ranging from the first edition to
> the special edition -- by Bjarne Stroustrup is such a document and
> given the number of sales[1], I think I have pretty good data.
> 
> [1]http://www.research.att.com/~bs/3rd.html

I posit that the average amount read or understood per purchased copy
of that (excellent) book is nowhere near enough to make informed
decisions about this topic.

-- 
Daniel Jacobowitz
MontaVista Software                         Debian GNU/Linux Developer

Re: On inlining in C++

[Daniel Berlin]

On Mon, 4 Aug 2003, Joe Buck wrote:

> On Mon, Aug 04, 2003 at 12:35:48PM -0400, Robert Dewar wrote:
> > > 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.
> >
> > Well there is a burden of demonstration on both sides I would say, in terms
> > of showing behavior on actual code.
>
> Don't forget that the biggest complaint we have about GCC is how slow the
> compiler is.  Ignoring or partially ignoring "inline", and doing analysis
> instead, costs time.

Most good compilers don't do either Option 1 or Option 2, they do a
combination like so:

Honor inline except when not possible
Perform analysis and use heuristics to determine what non-inline
functions to inline.

The time taken by doing the necessary analysis for inlining decisions is
not as high as you seem to think, because most of the same analysis
(callgraph construction, etc) is required for other things we want to do
anyway.

Certainly, right now, we inline when we should partially inline or clone,
assuming we have the necessary profile info or estimate it.

But, as an example, Intel's compiler does the following when not given
profile information:

"If you do not use profile-guided optimizations with -ip or -ipo, the
compiler uses less aggressive inlining heuristics:

Inline a function if the inline expansion will not increase the size of
the final program.

Inline a function if it is declared with the inline or __inline keywords.
"

Note that is still a combination of your option 1 and 2, becuase it does
inlining for functions not declared inline.

Re: On inlining in C++

[Gabriel Dos Reis]

dewar@gnat.com (Robert Dewar) writes:

| > Inline as I have described is close to what has been documented for
| > two decades in official C++ manuals.
| 
| Well if you really believe that C++ programmers read "official C++
| manuals" then you are talking about a different population of programmers
| entirely.

"The C++ Programming Language" -- ranging from the first edition to
the special edition -- by Bjarne Stroustrup is such a document and
given the number of sales[1], I think I have pretty good data.

[1]http://www.research.att.com/~bs/3rd.html

-- Gaby

Re: On inlining in C++

[Gabriel Dos Reis]

dewar@gnat.com (Robert Dewar) writes:

| > 
| > You should refrain from making such hash assertions about C++
| > programmers.  "inline" like any other C++ features is documented and
| > here is not the right place to transmute a meaning of an ISO
| > standardized language.
| 
| They are not hash (rash?) assertions, they are simply obsrevations. I have
| dealt with a LOT of C++ code written by a lot of people.
| 
| If you refer to the ISO standardized language, you are on thin ground, since
| it has little to say that is meaningful in this area. 

I'm referring to both ISO standardized and documentation of the
feature, practice since its introduction in C++ (1981).  

-- Gaby

Re: On inlining in C++

[Gabriel Dos Reis]

dewar@gnat.com (Robert Dewar) writes:

| > Again, this is an issue about C++ meaning of inline.  Not Ada's.
| 
| That's just plain wrong. mY comment:
| 
| > | Well I prefer to rely on my experience (which is that I have seen a lot
| > | of cases in which users are surprised to find that inlining slows things
| > | down), than your belief :-)
| 
| This comment is about inlining in general. 

The subject of this thread is "On inlining in C++", and we should try
our best not to make it degenerate into arguing about inlining in general.

-- Gaby

Re: On inlining in C++

[Robert Dewar]

> 
> You should refrain from making such hash assertions about C++
> programmers.  "inline" like any other C++ features is documented and
> here is not the right place to transmute a meaning of an ISO
> standardized language.

They are not hash (rash?) assertions, they are simply obsrevations. I have
dealt with a LOT of C++ code written by a lot of people.

If you refer to the ISO standardized language, you are on thin ground, since
it has little to say that is meaningful in this area. 

This is not about standard conformance at all, this is about what is
pragmatically best from a code generation point of view, something
the standard is not concerned with. As far as the standard is concerned
you can do multiplication by repeated addition :-)

Re: On inlining in C++

[Gabriel Dos Reis]

dewar@gnat.com (Robert Dewar) writes:

| > "I do not believe that would be a surprise to anyone who thought about
| > it for a minute."
| 
| You are assuming a model of someone who understands the possible effects
| of inlining and knows what an instruction cache is and how it works. The

You should refrain from making such hash assertions about C++
programmers.  "inline" like any other C++ features is documented and
here is not the right place to transmute a meaning of an ISO
standardized language.

-- Gaby

Re: On inlining in C++

[Robert Dewar]

> 
> Option 1: a version of GNU C++ that
> 
> * honors the "inline" keyword in all situations where the compiler is
>   capable of inlining the call
> * does the same for functions defined in the class body
> * when -Winline is given, issues a warning and explanation about why
>   a call is not inlined
> * avoids computing any metrics related to inlining decisions (unless -O3)
> 
> Option 2: a version of GNU C++ that uses the smartest heuristics that the
> "ignore inline" advocates can come up with.

Indeed, this is exactly the experiment that is required, and I suspect the
best resolution is to have this controllable by a switch. The issue of
what the best setting for the switch is is another discussion, and for
example depends on how well gdb handles inlining.

Re: On inlining in C++

[Robert Dewar]

> Inline as I have described is close to what has been documented for
> two decades in official C++ manuals.

Well if you really believe that C++ programmers read "official C++
manuals" then you are talking about a different population of programmers
entirely.

Re: On inlining in C++

[Robert Dewar]

> Again, this is an issue about C++ meaning of inline.  Not Ada's.

That's just plain wrong. mY comment:

> | Well I prefer to rely on my experience (which is that I have seen a lot
> | of cases in which users are surprised to find that inlining slows things
> | down), than your belief :-)

This comment is about inlining in general. It is not about Ada or about C++.
A lot of programmers have a pretty naive view of machine language, if they
have any view at all. For many programmers, the view of inlining is that
it must save time because it saves the time of the call and return. This
is of course entirely naive wrt super scalar machines with small icaches.

So you are misinterpreting the scope of my comment completely.

Re: On inlining in C++

[Joe Buck]

On Mon, Aug 04, 2003 at 12:35:48PM -0400, Robert Dewar wrote:
> > 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.
> 
> Well there is a burden of demonstration on both sides I would say, in terms
> of showing behavior on actual code.

Don't forget that the biggest complaint we have about GCC is how slow the
compiler is.  Ignoring or partially ignoring "inline", and doing analysis
instead, costs time.

I suggest resolving this argument by doing an experiment.

Option 1: a version of GNU C++ that

* honors the "inline" keyword in all situations where the compiler is
  capable of inlining the call
* does the same for functions defined in the class body
* when -Winline is given, issues a warning and explanation about why
  a call is not inlined
* avoids computing any metrics related to inlining decisions (unless -O3)

Option 2: a version of GNU C++ that uses the smartest heuristics that the
"ignore inline" advocates can come up with.

Part of the work for the experiment is to have a libstdc++ that is
as nearly clean with respect to -Winline (without resorting to suppressing
messages from system headers) as it can be made.

The switch between the two modes can be done by a flag, an ifdef,
whatever.  I don't care, because I suspect we'll wind up shipping only one
choice.

Now, build a lot of C++ code with -O2 for both options.  Measure compiler
speed as well as speed and space of the final code.  If option 2 is
consistently better, I surrender.  If option 2 is better only for one or
two programs, and it turns out that these programs use "inline" in
inappropriate ways, then the programs should be fixed.

My prediction is that option 1 will be better by every measure (though the
compile time difference may be small).

Re: On inlining in C++

[Robert Dewar]

> People are looking at this problem from two different angles:
> 
> a.  What will, on average, give the best performance?
> b.  What will, on average, cause the least trouble?
> 
> Andrew.

Right, those two angles always have to be considered. Note that the decision
in gcc to default to -O0 clearly is more concerned with consideration b than
a. This is probably reasonable, although it often costs gcc in benchmarks
against other compilers where optimization is the default (we have seen
behcnmarking protocols which require the default switches to be used, yes
that's silly, but it happens!)

> 
> "I do not believe that would be a surprise to anyone who thought about
> it for a minute."

You are assuming a model of someone who understands the possible effects
of inlining and knows what an instruction cache is and how it works. The
readership and writership of this list is hardly a representative cross-
section of "in the trenches" C++ programmers, who in my experience have
very little awarness of what is going on at the machine level.

Re: On inlining in C++

[Gabriel Dos Reis]

dewar@gnat.com (Robert Dewar) writes:

| > C++ is not Ada and Ada is not C++.  
| > If you want to argue about C++ inline, please do consider C++
| > semantics, practice. 
| 
| My comment was on C++ practice as I see it in the real world.

But you did not answer the question "More convenient way of doing what?"

Inline as I have described is close to what has been documented for
two decades in official C++ manuals.

-- Gaby

Re: On inlining in C++

[Robert Dewar]

> C++ is not Ada and Ada is not C++.  
> If you want to argue about C++ inline, please do consider C++
> semantics, practice. 

My comment was on C++ practice as I see it in the real world.

Re: On inlining in C++

[Gabriel Dos Reis]

dewar@gnat.com (Robert Dewar) writes:

| > I do not believe that would be a surprise to anyone who thought about
| > it for a minute.
| 
| 
| Well I prefer to rely on my experience (which is that I have seen a lot
| of cases in which users are surprised to find that inlining slows things
| down), than your belief :-)

Again, this is an issue about C++ meaning of inline.  Not Ada's.

-- Gaby

Re: On inlining in C++

[Andrew Haley]

Robert Dewar writes:
 > > I do not believe that would be a surprise to anyone who thought about
 > > it for a minute.
 > 
 > 
 > Well I prefer to rely on my experience (which is that I have seen a lot
 > of cases in which users are surprised to find that inlining slows things
 > down), than your belief :-)

"we find that customers are quite often surprised to find that -O3
is slower than -O2 (as well as generating lots of code)."

and

"I do not believe that would be a surprise to anyone who thought about
it for a minute."

don't conflict.

 > Again, what is really needed is data. We have lots of data on this
 > issue in the Ada world, surely there are useful examples in the C++
 > world that could argue the case more effectively than people
 > stating what they believe to be the case?

People are looking at this problem from two different angles:

a.  What will, on average, give the best performance?
b.  What will, on average, cause the least trouble?

Andrew.

Re: On inlining in C++

[Gabriel Dos Reis]

dewar@gnat.com (Robert Dewar) writes:

| In C++ the practice of writing simple functions in the header is not just

in C++, there is distinction between putting something in header and
requesting inlining.  Certainly requesting inlining implies making the
function available in every translation unit that uses it, but
putting something in a header file does not mean inlining is requested.

| a matter of the programmer "requesting inline explicitly", but also it
| is just the more convenient way of doing things, and doing otherwise may
| be undesirable for structural and documentation purposes.

More convenient way of doing what?  

C++ is not Ada and Ada is not C++.  
If you want to argue about C++ inline, please do consider C++
semantics, practice. 

-- Gaby

Re: On inlining in C++

[Robert Dewar]

> I do not believe that would be a surprise to anyone who thought about
> it for a minute.


Well I prefer to rely on my experience (which is that I have seen a lot
of cases in which users are surprised to find that inlining slows things
down), than your belief :-)

Again, what is really needed is data. We have lots of data on this issue
in the Ada world, surely there are useful examples in the C++ world that
could argue the case more effectively than people stating what they
believe to be the case?

Re: On inlining in C++

[Robert Dewar]

> For most targets, the only difference between -O2 and -O3 is that, with
> the latter, we find more functions to inline, beyond those explicitly
> marked as inline.  I read Gaby's argument as describing the behavior of
> -O2, not of -O3 (for which we will still need heuristics to drive inlining
> decisions).

Well of course the term "explicitly marked" is a bit contentious in this 
thread :-)

The point I was making is that indeed excessive inlining can be harmful.

In C++ the practice of writing simple functions in the header is not just
a matter of the programmer "requesting inline explicitly", but also it
is just the more convenient way of doing things, and doing otherwise may
be undesirable for structural and documentation purposes.

So to think that a C++ programmer is always conciously expecting and 
requesting inline when the keyword is not explicitly used seems a bit of
a dubious claim to me.

Certainly the most convincing evidence would be specific examples of
real applications compiled and run both ways. This thread seems short on
such examples.

Re: On inlining in C++

[Andrew Haley]

Robert Dewar writes:
 > > Perhaps there is, but the Principle of Least Surprise favours a
 > > fairly literal interpretation of "inline".
 > 
 > I don't agree, a huge blow up in size, resulting in slower
 > execution because of icache overload, can also qualify as a
 > surprise.

I do not believe that would be a surprise to anyone who thought about
it for a minute.

The Principle of Least Surprise suggests that inline functions will
often increase code size.  A little knowledge about multi-level memory
architecture suggests that this might reduce execution speed.

 > Indeed we find that customers are quite often surprised to find
 > that -O3 is slower than -O2 (as well as generating lots of code).

Well, that's different: we weren't talking about -O3, where the
compiler looks for functions to inline.  We're talking about functions
explicitly marked inline by the programmer.  A naive interpretation of
-O3 is "optimize more (i.e. better) than -O2".  But we know that -O3
doesn't strictly speaking mean that.

No, the burden of evidence is surely on those who want inline to do
something other than what a fairly literal interpretation of "inline"
(and the gcc docs) would suggest.

Andrew.

Re: On inlining in C++

[Joe Buck]

On Mon, Aug 04, 2003 at 12:44:52PM -0400, Robert Dewar wrote:
> > Perhaps there is, but the Principle of Least Surprise favours a
> > fairly literal interpretation of "inline".
> 
> I don't agree, a huge blow up in size, resulting in slower execution because
> of icache overload, can also qualify as a surprise.
> 
> Indeed we find that customers are quite often surprised to find that -O3
> is slower than -O2 (as well as generating lots of code).

For most targets, the only difference between -O2 and -O3 is that, with
the latter, we find more functions to inline, beyond those explicitly
marked as inline.  I read Gaby's argument as describing the behavior of
-O2, not of -O3 (for which we will still need heuristics to drive inlining
decisions).

Re: On inlining in C++

[Robert Dewar]

> Perhaps there is, but the Principle of Least Surprise favours a
> fairly literal interpretation of "inline".

I don't agree, a huge blow up in size, resulting in slower execution because
of icache overload, can also qualify as a surprise.

Indeed we find that customers are quite often surprised to find that -O3
is slower than -O2 (as well as generating lots of code).

Re: On inlining in C++

[Andrew Haley]

Robert Dewar writes:
 > > 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.
 > 
 > Well there is a burden of demonstration on both sides I would say, in terms
 > of showing behavior on actual code.

Perhaps there is, but the Principle of Least Surprise favours a
fairly literal interpretation of "inline".

Andrew.

Re: On inlining in C++

[Robert Dewar]

> 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.

Well there is a burden of demonstration on both sides I would say, in terms
of showing behavior on actual code.