std::pow implementation

std::pow implementation

[Richard Guenther]

Hi!

The current std::pow implementation causes very weak code to be emitted
for the overloads pow(T, int) for both gcc 3.3 and gcc 3.4. These powers
are computed going through the std::__power_helper() function template
which ends up emitting a call to std::__cmath_power() always. For
reference:

  template<typename _Tp>
    inline _Tp
    __pow_helper(_Tp __x, int __n)
    {
      return __n < 0
        ? _Tp(1)/__cmath_power(__x, -__n)
        : __cmath_power(__x, __n);
    }

If we change this to read like

  template<typename _Tp>
    inline _Tp __attribute__((always_inline))
    __power_helper(_Tp __x, int __n)
    {
      if (__builtin_constant_p(__n)) {
          switch (__n) {
          case 0:
                return 1;
          case 1:
                return __x;
          case 2:
                return __x*__x;
#if ! __OPTIMIZE_SIZE__
          case 3:
                return __x*__x*__x;
          case 4: {
                _Tp __y = __x*__x;
                return __y*__y;
          }
          /* etc. */
#endif
          }
      }
      return __n < 0
        ? _Tp(1)/std::__cmath_power(__x, -__n)
        : std::__cmath_power(__x, __n);
    }

we will win a lot.

Can such be done for 3.4 and possibly 3.3, too?

Thanks,

Richard.

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

Re: std::pow implementation

[Gabriel Dos Reis]

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

| Can such be done for 3.4 and possibly 3.3, too?

This is mainly an inlining problem with the compiler.  Please fix the
compiler, don't obfuscate the library.

-- Gaby

Re: std::pow implementation

[Richard Guenther]

On 29 Jul 2003, Gabriel Dos Reis wrote:

> Richard Guenther <rguenth@tat.physik.uni-tuebingen.de> writes:
>
> | Can such be done for 3.4 and possibly 3.3, too?
>
> This is mainly an inlining problem with the compiler.  Please fix the
> compiler, don't obfuscate the library.

cmath.tcc:std::__cmath_power is not even declared inline. So how do you
expect the compiler to optimize the very common std::pow(x, 2) without
-O3? And even with -O3 I cannot get gcc to optimize the simple

double foo(double x)
{
  std::pow(x, 2);
}

to something avoiding the call to std::__cmath_power. And I dont
expect inlining heuristics to consider constant arguments even for
tree-ssa in 3.5 timeframe.

Richard.

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

Re: std::pow implementation

[Gabriel Dos Reis]

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

| On 29 Jul 2003, Gabriel Dos Reis wrote:
| 
| > Richard Guenther <rguenth@tat.physik.uni-tuebingen.de> writes:
| >
| > | Can such be done for 3.4 and possibly 3.3, too?
| >
| > This is mainly an inlining problem with the compiler.  Please fix the
| > compiler, don't obfuscate the library.
| 
| cmath.tcc:std::__cmath_power is not even declared inline.

That can be fixed if I'm given enough data ways to reproduce them.
(The body of that function is already available in any translation
unit that use it)

[...]

| to something avoiding the call to std::__cmath_power. And I dont
| expect inlining heuristics to consider constant arguments even for
| tree-ssa in 3.5 timeframe.

Assume __cmath_power is defined inline, then if GCC refuses to
inline it is because it is broken: it thinks it knows better than the
programmer whereas it does not.

-- Gaby

Re: std::pow implementation

[Richard Guenther]

On 29 Jul 2003, Gabriel Dos Reis wrote:

> Richard Guenther <rguenth@tat.physik.uni-tuebingen.de> writes:
>
> | On 29 Jul 2003, Gabriel Dos Reis wrote:
> |
> | > Richard Guenther <rguenth@tat.physik.uni-tuebingen.de> writes:
> | >
> | > | Can such be done for 3.4 and possibly 3.3, too?
> | >
> | > This is mainly an inlining problem with the compiler.  Please fix the
> | > compiler, don't obfuscate the library.
> |
> | cmath.tcc:std::__cmath_power is not even declared inline.
>
> That can be fixed if I'm given enough data ways to reproduce them.
> (The body of that function is already available in any translation
> unit that use it)

Testcase would be:

double foo(double x, int n)
{
   switch (n) {
   case 0:
      return std::pow(x, 0);
   case 1:
      return std::pow(x, 1);
   case 2:
      return std::pow(x, 2);
   default:
      return 0.0;
   }
}

And scan for the call to std::__cmath_power. It should be absent for
-O2.

> | to something avoiding the call to std::__cmath_power. And I dont
> | expect inlining heuristics to consider constant arguments even for
> | tree-ssa in 3.5 timeframe.
>
> Assume __cmath_power is defined inline, then if GCC refuses to
> inline it is because it is broken: it thinks it knows better than the
> programmer whereas it does not.

I know. But its easy to fix the common case with existing gcc
infrastructure and it gets me away from

Flat profile:
Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total
 time   seconds   seconds    calls  ms/call  ms/call  name
  9.50      1.67     1.67 105523470     0.00     0.00  double std::__cmath_power<double>(double, unsigned)

for my scientific app. If this ends up the same way as the
__attribute__((leafify)) discussion, I'll stop complaining now and instead
just file a PR for the record.

Richard.

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

Re: std::pow implementation

[Gabriel Dos Reis]

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

| for my scientific app. If this ends up the same way as the
| __attribute__((leafify)) discussion, I'll stop complaining now and instead
| just file a PR for the record.

I bet your application will benefit much more from a better inlining
support in the compiler than obfuscating the library.
(Note that it need not be a sophisticated inliner).  We get to that point
because, at some point it was decided that the compiler knows better
than the programmer.

-- Gaby

Re: std::pow implementation

[Richard Guenther]

On 29 Jul 2003, Gabriel Dos Reis wrote:

> Richard Guenther <rguenth@tat.physik.uni-tuebingen.de> writes:
>
> | for my scientific app. If this ends up the same way as the
> | __attribute__((leafify)) discussion, I'll stop complaining now and instead
> | just file a PR for the record.
>
> I bet your application will benefit much more from a better inlining
> support in the compiler than obfuscating the library.
> (Note that it need not be a sophisticated inliner).  We get to that point
> because, at some point it was decided that the compiler knows better
> than the programmer.

Of course, and the recent changes in inlining heuristics and the
unit-at-a-time support for C++ in 3.4 got it a huge boost. But it still
gets nowhere near the code I manage to get by giving the leafify hint to
the compiler at exactly three locations. At some point the user _will_
know better - why do you think we have __attribute__((always_inline)) and
__attribute__((noinline))? Why do we have means to control the inlining
heuristics at all? Do you expect us to arrive to a point where all these
are unnecessary?

The std::pow stuff is now libstdc++/11706 and my local gcc tree now has
one extra patch.

Thanks,

Richard.

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

Re: std::pow implementation

[Gabriel Dos Reis]

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

|                                          At some point the user _will_
| know better - why do you think we have __attribute__((always_inline)) and
| __attribute__((noinline))?

We got __attribute__((always_inline)) because it was decided that the
compiler knows better than the programmer and the obvious syntax
"inline" should be a comment.  Then people reinvented "inline" with a
different syntax. 

| Why do we have means to control the inlining
| heuristics at all? Do you expect us to arrive to a point where all these
| are unnecessary?

If I think "inline" should be void of semantics, I would not have
written the lines above.

-- Gaby

Re: std::pow implementation

[Alexandre Oliva]

On Jul 29, 2003, Gabriel Dos Reis <gdr@integrable-solutions.net> wrote:

> Richard Guenther <rguenth@tat.physik.uni-tuebingen.de> writes:
> |                                          At some point the user _will_
> | know better - why do you think we have __attribute__((always_inline)) and
> | __attribute__((noinline))?

> We got __attribute__((always_inline)) because it was decided that the
> compiler knows better than the programmer and the obvious syntax
> "inline" should be a comment.  Then people reinvented "inline" with a
> different syntax. 

Nope.  always_inline was introduced for situations in which, if
inlining does not happen, the program won't run, as it is the case in
early bootstrapping cases in the dynamic loader and in kernels, where
issuing a function call will fail because the code hasn't been
relocated yet.  IIRC noinline was introduced for similar (but
opposite) reasons: i.e., where inlining must *not* occur because
otherwise the program would break, e.g., low-level functions that need
the return address of their caller, and not of their caller's caller.

They are not designed to tune inlining, they're designed to impose
requirements on the compiler's behavior.  If they're abused for other
purposes, there's unfortunately nothing we can do about it other than
try to educate people about their intended uses.

-- 
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: std::pow implementation

[Gabriel Dos Reis]

Alexandre Oliva <aoliva@redhat.com> writes:

| On Jul 29, 2003, Gabriel Dos Reis <gdr@integrable-solutions.net> wrote:
| 
| > Richard Guenther <rguenth@tat.physik.uni-tuebingen.de> writes:
| > |                                          At some point the user _will_
| > | know better - why do you think we have __attribute__((always_inline)) and
| > | __attribute__((noinline))?
| 
| > We got __attribute__((always_inline)) because it was decided that the
| > compiler knows better than the programmer and the obvious syntax
| > "inline" should be a comment.  Then people reinvented "inline" with a
| > different syntax. 
| 
| Nope.  always_inline was introduced for situations in which, if
| inlining does not happen, the program won't run, as it is the case in
| early bootstrapping cases in the dynamic loader and in kernels, where
| issuing a function call will fail because the code hasn't been
| relocated yet.

If you give inline its original meaning, you won't run into the risk
of the situation you're describing.

[...]

| They are not designed to tune inlining, they're designed to impose
| requirements on the compiler's behavior.  If they're abused for other
| purposes, there's unfortunately nothing we can do about it other than
| try to educate people about their intended uses.

Why do you think "inline" is different?

-- Gaby

Re: std::pow implementation

[Alexandre Oliva]

On Jul 30, 2003, Gabriel Dos Reis <gdr@integrable-solutions.net> wrote:

> If you give inline its original meaning, you won't run into the risk
> of the situation you're describing.

Which meaning are you talking about?  The meaning assigned to inline
in C++98 or in C99?  They have very different meanings, besides the
issue on whether inline affects the linkage of a function in C.

> | They are not designed to tune inlining, they're designed to impose
> | requirements on the compiler's behavior.  If they're abused for other
> | purposes, there's unfortunately nothing we can do about it other than
> | try to educate people about their intended uses.

> Why do you think "inline" is different?

Because at least in C99, inline is defined as a hint to make the
function call be fast, not as a requirement that inline substitution
be made.  Quoting the ISO C99 standard:

  [...] Making a function an inline function suggests that calls to the
  function be as fast as possible.  The extent to which such
  suggestions are effective is implementation-defined.  [6.7.4]/#5

If performing ``inline substitution'', that is one of the *example*
mechanisms mentioned in a footnote that explains what `as fast as
possible' is, doesn't make it faster than an out-of-line call, the
inline suggestion should be taken as a directive to keep it
out-of-line.

In order for a compiler to strictly follow the standard requirement
about inlining, it should be able to tell whether inline substitution
will actually speed things up.  Solving this problem can be
particularly tricky if the choice depends on arguments whose values
are not known at compile time.

-- 
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: std::pow implementation

[Gabriel Dos Reis]

Alexandre Oliva <aoliva@redhat.com> writes:

| On Jul 30, 2003, Gabriel Dos Reis <gdr@integrable-solutions.net> wrote:
| 
| > If you give inline its original meaning, you won't run into the risk
| > of the situation you're describing.
| 
| Which meaning are you talking about? 

The meaning of "inline" when it was originally introduced in C++.  I'm
quoting here "The Design and Evolution of C++" (also part of an
article I intented to send to a broader audience), section "Run-Time
Efficiency":   

  The general reason for the introduction of inline functions was
  concern that the cost of crossing a protection barrier would cause
  people to refrain  from using classes to hide representation.  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 application, crossing
  the protection barrier had to be free.

  [...]

  2.4.1 Inlining

  Inlining was considered important for the utility of classes.
  Therefore, the issue was more /how/ to provide it than /whether/ to
  provide it.  Two arguments won the day for the notion of having the
  programmer select which functions the compiler should try to inline.
  First, I had poor experiences with languages that left the job of
  inlining to compilers "because clearly the compiler knows best."
  The compiler only knows best if it has been programmed to inline and
  it has a notion of time/space optimization that agrees with mine.  My
  experience with other languages was that only "the next release"
  would actually inline, and it would do so according to an internal
  logic that a programmer couldn't effectively control. [...]
  Furthermore, techniques that require global analysis, such as
  automatic inlining without user support, tend not to scale well to
  very large programs.  C with Classes was designed to deliver
  efficient code given a simple, portable implementation on
  traditional systems.  Given that, the programmer had to help.  Even
  today, the choice seems right.


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

Never forget that inlining is a *key* feature for the effective use
and utsefulness of classes.  "Inline" was introduced to give control
to the programmer.  The experiences reported by Stroustrup were about
more than twenty years ago;  however, they sound so familiar, to
contemporary today.  Please do give "inline" its ogirinal and obvious
meaning.  We don't need to reinvent "inline" and the obvious syntax is
already available.  Transmuting the meaning of "inline" does bring
nothing except Fear, Uncertainty and Doubt.  Keep it simple.

| The meaning assigned to inline
| in C++98 or in C99?  They have very different meanings, besides the
| issue on whether inline affects the linkage of a function in C.

The issue, as you certainly have noted if you followed the discussion,
is much more C++ specific than C specific.  I'll let C people decide
whether they wanted implementors to treat "inline" as void of semantics.

| > | They are not designed to tune inlining, they're designed to impose
| > | requirements on the compiler's behavior.  If they're abused for other
| > | purposes, there's unfortunately nothing we can do about it other than
| > | try to educate people about their intended uses.
| 
| > Why do you think "inline" is different?
| 
| Because at least in C99, inline is defined as a hint to make the

The C++/C99 standard do not mandate a useful implementation.
Surely, when we're talking about compiler performance you're not going
to quote C++/C99 standard, right?

-- Gaby

Re: std::pow implementation

[Richard Earnshaw]

> Alexandre Oliva <aoliva@redhat.com> writes:
> 
> | On Jul 30, 2003, Gabriel Dos Reis <gdr@integrable-solutions.net> wrote:
> | 
> | > If you give inline its original meaning, you won't run into the risk
> | > of the situation you're describing.
> | 
> | Which meaning are you talking about? 
> 
> The meaning of "inline" when it was originally introduced in C++.  I'm
> quoting here "The Design and Evolution of C++" (also part of an
> article I intented to send to a broader audience), section "Run-Time
> Efficiency":   
> 
>   The general reason for the introduction of inline functions was
>   concern that the cost of crossing a protection barrier would cause
>   people to refrain  from using classes to hide representation.  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 application, crossing
>   the protection barrier had to be free.
> 

This is talking specifically about *very small* functions ("one or two 
assignments").  It says nothing about what happens if the programmer 
decides to put a 2000 line monstrosity in the middle of a class definition 
(which would be legal, if somewhat stupid).  A practical compiler 
eventually has to say "enough is enough", or it is likely to crash, run 
out of memory or whatever.

>   [...]
> 
>   2.4.1 Inlining
> 
>   Inlining was considered important for the utility of classes.
>   Therefore, the issue was more /how/ to provide it than /whether/ to
>   provide it.  Two arguments won the day for the notion of having the
>   programmer select which functions the compiler should try to inline.

Note the word "try" in the line above.

>   First, I had poor experiences with languages that left the job of
>   inlining to compilers "because clearly the compiler knows best."
>   The compiler only knows best if it has been programmed to inline and
>   it has a notion of time/space optimization that agrees with mine.  My
>   experience with other languages was that only "the next release"
>   would actually inline, and it would do so according to an internal
>   logic that a programmer couldn't effectively control. [...]
>   Furthermore, techniques that require global analysis, such as
>   automatic inlining without user support, tend not to scale well to
>   very large programs.  C with Classes was designed to deliver
>   efficient code given a simple, portable implementation on
>   traditional systems.  Given that, the programmer had to help.  Even
>   today, the choice seems right.
> 
> 
> Reference [Stroustrup, 1982b] is
>  Bjarne Stroustrup: "Adding Classes to C: An Exercise in Language
>                      Evolution".  Bell Laboratories Compuer Science
>                      internal document.  April 1982.  
>                      Software: Practice & Experience, Vol 13. 1983
>   
> 
> Never forget that inlining is a *key* feature for the effective use
> and utsefulness of classes. 

Not disputed.

> "Inline" was introduced to give control
> to the programmer.

I disagree.  What really counts is that the compiler has sufficient 
information to do a good job when compiling the code (ie to reduce, and 
hopefully eliminate, the abstraction penalty).  What constitutes a "good 
job" is up to the compiler and we can spend as much time as we want 
disputing whether the compiler has reached that standard; however, to 
reach it does not necessarily have to mean that it conceptually 
substitutes every statement from the body of an "inline" function into the 
caller.

Careful use of inline by the programmer will aid the compiler in achieving 
that goal.

R.

Re: std::pow implementation

[Gabriel Dos Reis]

Richard Earnshaw <rearnsha@arm.com> writes:

| > Alexandre Oliva <aoliva@redhat.com> writes:
| > 
| > | On Jul 30, 2003, Gabriel Dos Reis <gdr@integrable-solutions.net> wrote:
| > | 
| > | > If you give inline its original meaning, you won't run into the risk
| > | > of the situation you're describing.
| > | 
| > | Which meaning are you talking about? 
| > 
| > The meaning of "inline" when it was originally introduced in C++.  I'm
| > quoting here "The Design and Evolution of C++" (also part of an
| > article I intented to send to a broader audience), section "Run-Time
| > Efficiency":   
| > 
| >   The general reason for the introduction of inline functions was
| >   concern that the cost of crossing a protection barrier would cause
| >   people to refrain  from using classes to hide representation.  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 application, crossing
| >   the protection barrier had to be free.
| > 
| 
| This is talking specifically about *very small* functions ("one or two 
| assignments").

Do you think 'std::string::end() const' is not very small?
I certainly think it is.

| It says nothing about what happens if the programmer 
| decides to put a 2000 line monstrosity in the middle of a class definition 
| (which would be legal, if somewhat stupid).

Firstly, I do not trust you that counting lines is sensical mesure for
inlining.  Secondly, it is up to the programmer to decide whether he
wants the 2000 lines in the middle his class.  Whether it is stupid
depends on what he is doing and *you* have no cluie to know that.

Do trust the programmer.

|  A practical compiler 
| eventually has to say "enough is enough", or it is likely to crash, run 
| out of memory or whatever.

That compiler is broken then.  More specifically you don't have any
clue in foreseeing that.  Or else you end reinventing "inline" with a
different syntax, namely __attribute__((__always_inline__)) or
-fobey-inline.  With no pruposes (apart from offerind a lock-in syntax).

| >   [...]
| > 
| >   2.4.1 Inlining
| > 
| >   Inlining was considered important for the utility of classes.
| >   Therefore, the issue was more /how/ to provide it than /whether/ to
| >   provide it.  Two arguments won the day for the notion of having the
| >   programmer select which functions the compiler should try to inline.
| 
| Note the word "try" in the line above.

Yes, I noted it.  But "try" don't not imply "give up because you think
you know better than the programmer".

| >   First, I had poor experiences with languages that left the job of
| >   inlining to compilers "because clearly the compiler knows best."
| >   The compiler only knows best if it has been programmed to inline and
| >   it has a notion of time/space optimization that agrees with mine.  My
| >   experience with other languages was that only "the next release"
| >   would actually inline, and it would do so according to an internal
| >   logic that a programmer couldn't effectively control. [...]
| >   Furthermore, techniques that require global analysis, such as
| >   automatic inlining without user support, tend not to scale well to
| >   very large programs.  C with Classes was designed to deliver
| >   efficient code given a simple, portable implementation on
| >   traditional systems.  Given that, the programmer had to help.  Even
| >   today, the choice seems right.
| > 
| > 
| > Reference [Stroustrup, 1982b] is
| >  Bjarne Stroustrup: "Adding Classes to C: An Exercise in Language
| >                      Evolution".  Bell Laboratories Compuer Science
| >                      internal document.  April 1982.  
| >                      Software: Practice & Experience, Vol 13. 1983
| >   
| > 
| > Never forget that inlining is a *key* feature for the effective use
| > and utsefulness of classes. 
| 
| Not disputed.

But that is the root of the disagreement!

[...]

| Careful use of inline by the programmer will aid the compiler in achieving 
| that goal.

But when the compiler thinks he knows better than the programmer and
implementors insist on transmuting the original meaning of the
keyword, the compiler won't achieve its goal.

-- Gaby

Re: std::pow implementation

[Steven Bosscher]

Op wo 30-07-2003, om 13:30 schreef Gabriel Dos Reis:
> Do trust the programmer.

Post a patch and show that it improves most real world code.

Gr.
Steven

Re: std::pow implementation

[Gabriel Dos Reis]

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

| Op wo 30-07-2003, om 13:30 schreef Gabriel Dos Reis:
| > Do trust the programmer.
| 
| Post a patch and show that it improves most real world code.

It suffices to point out that (defunct) KCC did outperform GCC on most
real world code.

-- Gaby

Re: std::pow implementation

[Steven Bosscher]

Op wo 30-07-2003, om 13:45 schreef Gabriel Dos Reis:
> Steven Bosscher <s.bosscher@student.tudelft.nl> writes:
> 
> | Op wo 30-07-2003, om 13:30 schreef Gabriel Dos Reis:
> | > Do trust the programmer.
> | 
> | Post a patch and show that it improves most real world code.
> 
> It suffices to point out that (defunct) KCC did outperform GCC on most
> real world code.

Then you must be glad, I'm sure, that you're going to contribute a
serious improvement to G++ :-)

Seriously though, this discussion is turning into just another flame war
over inline, and without the hard numbers there's no real way of telling
what the effects would be of implementing your ideas.

It shouldn't be that hard to implement what you're suggesting: Just
learn tree-inline.c to ignore limits when compiling C++, and learn
cgraphunit to inline functions with DECL_INLINE set in its first pass
(when it's inlining always_inline functions).

Let's see what happens.

Gr.
Steven

Re: std::pow implementation

[Gabriel Dos Reis]

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

| Op wo 30-07-2003, om 13:45 schreef Gabriel Dos Reis:
| > Steven Bosscher <s.bosscher@student.tudelft.nl> writes:
| > 
| > | Op wo 30-07-2003, om 13:30 schreef Gabriel Dos Reis:
| > | > Do trust the programmer.
| > | 
| > | Post a patch and show that it improves most real world code.
| > 
| > It suffices to point out that (defunct) KCC did outperform GCC on most
| > real world code.
| 
| Then you must be glad, I'm sure, that you're going to contribute a
| serious improvement to G++ :-)

I'm taking this issue seriously in case you have some doubt.

You (steven Bosscher) are  trying to turn it into a flame war, to have
an excuse to ignore the issue.  Sigh.

-- Gaby

Re: std::pow implementation

[Steven Bosscher]

Op wo 30-07-2003, om 14:10 schreef Gabriel Dos Reis:
> Steven Bosscher <s.bosscher@student.tudelft.nl> writes:
> | > It suffices to point out that (defunct) KCC did outperform GCC on most
> | > real world code.
> | 
> | Then you must be glad, I'm sure, that you're going to contribute a
> | serious improvement to G++ :-)
> 
> I'm taking this issue seriously in case you have some doubt.

I don't doubt it all.  You're obviously very passionate about this. 


> You (steven Bosscher) are  trying to turn it into a flame war, to have
> an excuse to ignore the issue.  Sigh.

I'm not trying to turn anything into a flame war, I'm asking you to
_show_ you're right, not to just claim you are.  I even tried to be
helpful with some suggestions because I don't know how well you know
tree-inline and cgraphunit.  If you think that this is "trying to turn
it into a flame war" then, well, let's just say you've got me puzzled.

So a retry:

You keep saying ``Please do give "inline" its original meaning'', but
apparently the people who you're asking to do so disagree with your
ideas and therfore are probably not going to do it.

In a case like this, it is the way of open source software development
that you provide a patch yourself and show that it is an improvement.

Heck, who can tell wether you're right or wrong!?  I don't think you are
right, but I can't prove that.  So all I ask is that if you are
convinced you're right, you should try to prove it.

Gr.
Steven

Re: std::pow implementation

[Gabriel Dos Reis]

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

| Op wo 30-07-2003, om 14:10 schreef Gabriel Dos Reis:
| > Steven Bosscher <s.bosscher@student.tudelft.nl> writes:
| > | > It suffices to point out that (defunct) KCC did outperform GCC on most
| > | > real world code.
| > | 
| > | Then you must be glad, I'm sure, that you're going to contribute a
| > | serious improvement to G++ :-)
| > 
| > I'm taking this issue seriously in case you have some doubt.
| 
| I don't doubt it all.  You're obviously very passionate about this. 

I distinguish between being serious and being passionate.  
The later does not require argumentation.

| > You (steven Bosscher) are  trying to turn it into a flame war, to have
| > an excuse to ignore the issue.  Sigh.
| 
| I'm not trying to turn anything into a flame war,

I beg to be doubtful given the number of times you attempted to side
track the discussion.

[...]

| You keep saying ``Please do give "inline" its original meaning'', but
| apparently the people who you're asking to do so disagree with your
| ideas and therfore are probably not going to do it.

They disagreed with me and the reasons they gave were most (all?)
unfounded ranging from bogus quotes to the standard to assuming that
the programmer's use of "inline" is most of the time nonsensible.

[...]

| Heck, who can tell wether you're right or wrong!?  I don't think you are
| right, but I can't prove that.  So all I ask is that if you are
| convinced you're right, you should try to prove it.

Please, refrain from putting words in my month.  
(Did you say you're not attempting to turn this into a flame war?)

-- Gaby

Re: std::pow implementation

[Richard Guenther]

On 30 Jul 2003, Gabriel Dos Reis wrote:

> Steven Bosscher <s.bosscher@student.tudelft.nl> writes:
>
> | Op wo 30-07-2003, om 13:30 schreef Gabriel Dos Reis:
> | > Do trust the programmer.
> |
> | Post a patch and show that it improves most real world code.
>
> It suffices to point out that (defunct) KCC did outperform GCC on most
> real world code.

But surely not due to honouring the inline keyword. Take a look at
modestly large C++ code bases and figure out that neither implicit inline
declarations are used in a sensible way, nor are explicit ones. You could
argue this is the users fault, but I'd argue the compiler is (or
should be) better at deciding this based on function size (which may
depend upon parameters passed).

Of course being able to hint the compiler some more can be useful to
overcome weakness in the compilers inlining decision implementation as
that never will be perfect.

Richard.

Re: std::pow implementation

[Gabriel Dos Reis]

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

| On 30 Jul 2003, Gabriel Dos Reis wrote:
| 
| > Steven Bosscher <s.bosscher@student.tudelft.nl> writes:
| >
| > | Op wo 30-07-2003, om 13:30 schreef Gabriel Dos Reis:
| > | > Do trust the programmer.
| > |
| > | Post a patch and show that it improves most real world code.
| >
| > It suffices to point out that (defunct) KCC did outperform GCC on most
| > real world code.
| 
| But surely not due to honouring the inline keyword. 

Its honouring the inline keyword was most certainly part of that.

I do distinctly remember having made measurements and having friends
report similar observations no many real world codes.  There are still
websites around showing the differences.

| Take a look at
| modestly large C++ code bases and figure out that neither implicit inline
| declarations are used in a sensible way, nor are explicit ones.

I do find that most of the uses of inline sensible in most code bases.

And the notion of "implicit inline declaration" is an invention of some
implementors to excuse their ill-founded transmuting the meaning of
"inline".  

[...]

| Of course being able to hint the compiler some more can be useful to
| overcome weakness in the compilers inlining decision implementation as
| that never will be perfect.

It takes first abandoning the idea that the compiler always knows
better than the programmer and the programmer's use of "inline" is
most of the time nonsensical.  The programmer does provide hint.  The
compiler choses not to listen.

-- Gaby

Re: std::pow implementation

[Richard Guenther]

On 30 Jul 2003, Gabriel Dos Reis wrote:

> Richard Guenther <rguenth@tat.physik.uni-tuebingen.de> writes:
>
> | Of course being able to hint the compiler some more can be useful to
> | overcome weakness in the compilers inlining decision implementation as
> | that never will be perfect.
>
> It takes first abandoning the idea that the compiler always knows
> better than the programmer and the programmer's use of "inline" is
> most of the time nonsensical.  The programmer does provide hint.  The
> compiler choses not to listen.

Well, the point is you question that inline should be a hint, but take it
as the same as __attribute__((always_inline)) is defined. The compiler is
free to ignore hints if it thinks the hint is against the task it is
performing (take f.i. a inline declared modestly sized function when
compiling with -Os).

I'd argue for the inline keyword makeing the compiler think twice before
not inlining a function and -finline-functions on by default (if inline is
a hint to inline, why should no inline force the compiler not to inline?).

Richard.

Re: std::pow implementation

[Steven Bosscher]

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

Op wo 30-07-2003, om 14:22 schreef Richard Guenther:
> On 30 Jul 2003, Gabriel Dos Reis wrote:
> 
> > Richard Guenther <rguenth@tat.physik.uni-tuebingen.de> writes:
> >
> > | Of course being able to hint the compiler some more can be useful to
> > | overcome weakness in the compilers inlining decision implementation as
> > | that never will be perfect.
> >
> > It takes first abandoning the idea that the compiler always knows
> > better than the programmer and the programmer's use of "inline" is
> > most of the time nonsensical.  The programmer does provide hint.  The
> > compiler choses not to listen.
> 
> Well, the point is you question that inline should be a hint, but take it
> as the same as __attribute__((always_inline)) is defined. The compiler is
> free to ignore hints if it thinks the hint is against the task it is
> performing (take f.i. a inline declared modestly sized function when
> compiling with -Os).

No, always_inline also implies inlining functions that call alloca, so 
it's a bit stronger than that.

The attached patch makes C++ ignore inline limits if the function was
declared with "inline".  Maybe you can try and see what it does for you?

> I'd argue for the inline keyword makeing the compiler think twice before
> not inlining a function and -finline-functions on by default (if inline is
> a hint to inline, why should no inline force the compiler not to inline?).

That could be done by setting max-inline-insns-single to a larger value
for C++.  This has been discussed many times and your numbers show it
would help, but at an unacceptable cost of compiler speed.  IIRC a lot
of the slowdown was in expand, so with tree-ssa we could give this
another try (assuming tree-inline can clean up a lot of cruft before
expanding...).

Gr.
Steven



[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: inline_patch.diff --]
[-- Type: text/x-patch; name=inline_patch.diff; charset=, Size: 1539 bytes --]

Index: cp-lang.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cp/cp-lang.c,v
retrieving revision 1.57
diff -c -3 -p -r1.57 cp-lang.c
*** cp-lang.c	22 Jul 2003 23:30:13 -0000	1.57
--- cp-lang.c	30 Jul 2003 12:49:58 -0000
*************** static bool cxx_warn_unused_global_decl 
*** 38,43 ****
--- 38,44 ----
  static tree cp_expr_size (tree);
  static size_t cp_tree_size (enum tree_code);
  static bool cp_var_mod_type_p (tree);
+ static int cp_disregard_inline_limits (tree fn);
  
  #undef LANG_HOOKS_NAME
  #define LANG_HOOKS_NAME "GNU C++"
*************** static bool cp_var_mod_type_p (tree);
*** 124,129 ****
--- 125,133 ----
  #undef LANG_HOOKS_TREE_INLINING_CANNOT_INLINE_TREE_FN
  #define LANG_HOOKS_TREE_INLINING_CANNOT_INLINE_TREE_FN \
    cp_cannot_inline_tree_fn
+ #undef LANG_HOOKS_TREE_INLINING_DISREGARD_INLINE_LIMITS
+ #define LANG_HOOKS_TREE_INLINING_DISREGARD_INLINE_LIMITS \
+   cp_disregard_inline_limits
  #undef LANG_HOOKS_TREE_INLINING_ADD_PENDING_FN_DECLS
  #define LANG_HOOKS_TREE_INLINING_ADD_PENDING_FN_DECLS \
    cp_add_pending_fn_decls
*************** cp_var_mod_type_p (tree type)
*** 370,375 ****
--- 374,386 ----
  
    /* All other types are not variably modified.  */
    return false;
+ }
+ 
+ /* Force inlining of functions declared inline.  */
+ int
+ cp_disregard_inline_limits (tree fn)
+ {
+   return DECL_DECLARED_INLINE_P (fn);
  }
  
  /* Stub routine to tell people that this doesn't work yet.  */

Re: std::pow implementation

[Richard Guenther]

On 30 Jul 2003, Steven Bosscher wrote:

> Op wo 30-07-2003, om 14:22 schreef Richard Guenther:
> > On 30 Jul 2003, Gabriel Dos Reis wrote:
> >
> > > Richard Guenther <rguenth@tat.physik.uni-tuebingen.de> writes:
> > >
> > > | Of course being able to hint the compiler some more can be useful to
> > > | overcome weakness in the compilers inlining decision implementation as
> > > | that never will be perfect.
> > >
> > > It takes first abandoning the idea that the compiler always knows
> > > better than the programmer and the programmer's use of "inline" is
> > > most of the time nonsensical.  The programmer does provide hint.  The
> > > compiler choses not to listen.
> >
> > Well, the point is you question that inline should be a hint, but take it
> > as the same as __attribute__((always_inline)) is defined. The compiler is
> > free to ignore hints if it thinks the hint is against the task it is
> > performing (take f.i. a inline declared modestly sized function when
> > compiling with -Os).
>
> No, always_inline also implies inlining functions that call alloca, so
> it's a bit stronger than that.
>
> The attached patch makes C++ ignore inline limits if the function was
> declared with "inline".  Maybe you can try and see what it does for you?

It does no good, as it is certainly worse than #define inline
__attribute__((always_inline)) and that made compile times and code size
go through the roof last time I checked, but read on ...

> > I'd argue for the inline keyword makeing the compiler think twice before
> > not inlining a function and -finline-functions on by default (if inline is
> > a hint to inline, why should no inline force the compiler not to inline?).
>
> That could be done by setting max-inline-insns-single to a larger value
> for C++.  This has been discussed many times and your numbers show it
> would help, but at an unacceptable cost of compiler speed.

Note that with recent function size estimate changes and callgraph
inlining the world is very much better now.

Tuning the limits doesnt help the semantic misbalance of the inline hint
which is a hint for inlining only, but omitting it is an order not to
inline (if -finline-function is not specified, otherwise its meaningless
anyway). Oh - and we have -fno-default-inline, too, which I think we
should drop as it seems to be against the quoted standards.

>  IIRC a lot
> of the slowdown was in expand, so with tree-ssa we could give this
> another try (assuming tree-inline can clean up a lot of cruft before
> expanding...).

Yes, these problems were fixed with patches from Mark and the callgraph
stuff from Jan. The things left are the ability to fine-tune inlining like
suggested in another post:

- #pragma inline
- #pragma noinline
- #pragma inline complete  or  __attribute__((leafify))

most compilers for HPC platforms support these notions and they are indeed
useful.

Richard.

Re: std::pow implementation

[Gabriel Dos Reis]

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

[...]

| > No, always_inline also implies inlining functions that call alloca, so
| > it's a bit stronger than that.
| >
| > The attached patch makes C++ ignore inline limits if the function was
| > declared with "inline".  Maybe you can try and see what it does for you?
| 
| It does no good, as it is certainly worse than #define inline
| __attribute__((always_inline)) and that made compile times and code size
| go through the roof last time I checked, but read on ...

Without decent constant propagation and dead code elimination, it does
not suffice -- as you have seen it in a PR your reported.

-- Gaby

Re: std::pow implementation

[Karel Gardas]

On Wed, 30 Jul 2003, Gabriel Dos Reis wrote:

> Firstly, I do not trust you that counting lines is sensical mesure for
> inlining.  Secondly, it is up to the programmer to decide whether he
> wants the 2000 lines in the middle his class.  Whether it is stupid
> depends on what he is doing and *you* have no cluie to know that.
>
> Do trust the programmer.

As a gcc user, I would just like to say, that it would be nice, if there
is some kind of ``wrong inline'' warning which might teach programmers
about what compiler thinks about inline - of course compiler should honour
inline even in the case of wrong usage... The programmer is responsible
for removing it in this case...

Anyway, thanks for working on GCC!

Karel
--
Karel Gardas                  kgardas@objectsecurity.com
ObjectSecurity Ltd.           http://www.objectsecurity.com

Re: std::pow implementation

[Gabriel Dos Reis]

Karel Gardas <kgardas@objectsecurity.com> writes:

| On Wed, 30 Jul 2003, Gabriel Dos Reis wrote:
| 
| > Firstly, I do not trust you that counting lines is sensical mesure for
| > inlining.  Secondly, it is up to the programmer to decide whether he
| > wants the 2000 lines in the middle his class.  Whether it is stupid
| > depends on what he is doing and *you* have no cluie to know that.
| >
| > Do trust the programmer.
| 
| As a gcc user, I would just like to say, that it would be nice, if there
| is some kind of ``wrong inline'' warning which might teach programmers
| about what compiler thinks about inline - of course compiler should honour
| inline even in the case of wrong usage... The programmer is responsible
| for removing it in this case...

GCC has a switch named -Winline that is supposed to give a warning
about functions it can't inline and the reason why.  But, currently it
is not really helpful because of the inlining strategy.   
But your suggestion about something like -frank-my-usage-of-inline
might also be helpful also.

-- Gaby

Re: std::pow implementation

[Richard Earnshaw]

> On Wed, 30 Jul 2003, Gabriel Dos Reis wrote:
> 
> > Firstly, I do not trust you that counting lines is sensical mesure for
> > inlining.  Secondly, it is up to the programmer to decide whether he
> > wants the 2000 lines in the middle his class.  Whether it is stupid
> > depends on what he is doing and *you* have no cluie to know that.
> >
> > Do trust the programmer.
> 
> As a gcc user, I would just like to say, that it would be nice, if there
> is some kind of ``wrong inline'' warning which might teach programmers
> about what compiler thinks about inline - of course compiler should honour
> inline even in the case of wrong usage... The programmer is responsible
> for removing it in this case...
> 

The problem here is that there is no clear point at which a  "right" 
inline becomes a "wrong" inline.  Sometimes it may be right and sometimes 
not.  It depends on many things, such as the optimization goals, the 
processor in question, the context of use, etc, etc.

For example, consider this case:

class foo{
  int _a;
public:
  void f (int a, int b)
		{
		  if (a != 1) {
		    // 100 lines of complex code
	          } else
		    _a = b;
	        }

};

Now clearly, if a is the constant literal 1, it's good to inline this, 
since it collapses to a single assignment.  If a is not one, then the case 
for doing so is much less compelling.  The benefits of doing so are far 
less clear (indeed, better code might result on some processors if the 
code is not inlined, because of register pressure etc).  Even if the code 
is not inlined, the compiler might still be able to use the definition to 
improve the way CSE is done, for example, since now the compiler can see 
what sub-expressions might be killed by the function call.

Now, assume that the amount of code in the a!=1 case is reduced.  At what 
point does it become beneficial to always inline?  Can the programmer 
tell?  Should he write the code in a separate function, or should he leave 
it to the compiler to decide?  What happens if the code is ported to 
another machine with twice as many registers?

With Gaby's suggested interpretation, the compiler has *no* choice; it 
must obey the inlining constraint because the programmer always knows 
better...  Even when prepared to admit that he doesn't.

R.

Re: std::pow implementation

[Gabriel Dos Reis]

Richard Earnshaw <rearnsha@arm.com> writes:

[...]

| Now, assume that the amount of code in the a!=1 case is reduced.  At what 
| point does it become beneficial to always inline?  Can the programmer 
| tell?

He can profile.

|  Should he write the code in a separate function, or should he leave 
| it to the compiler to decide?  What happens if the code is ported to 
| another machine with twice as many registers?

Let's not have the compiler speculate about the future plateform the
programmer will run his program on -- it has no clue.

| With Gaby's suggested interpretation, the compiler has *no* choice; it 
| must obey the inlining constraint because the programmer always knows 
| better...  Even when prepared to admit that he doesn't.

That assertion is wrong.

-- Gaby

Re: std::pow implementation

[Richard Earnshaw]

> Richard Earnshaw <rearnsha@arm.com> writes:
> 
> [...]
> 
> | Now, assume that the amount of code in the a!=1 case is reduced.  At what 
> | point does it become beneficial to always inline?  Can the programmer 
> | tell?
> 
> He can profile.

Profiling doesn't help if the answer comes back as "sometimes" (function 
foo's use of bar is best inlined, function wibble's use of bar is best not 
inlined).

> 
> |  Should he write the code in a separate function, or should he leave 
> | it to the compiler to decide?  What happens if the code is ported to 
> | another machine with twice as many registers?
> 
> Let's not have the compiler speculate about the future plateform the
> programmer will run his program on -- it has no clue.

And nor, necessarily, can the programmer who writes a class definition.  
Don't forget that it may end up being used by other programmers who have 
no power to change the class interface.

> 
> | With Gaby's suggested interpretation, the compiler has *no* choice; it 
> | must obey the inlining constraint because the programmer always knows 
> | better...  Even when prepared to admit that he doesn't.
> 
> That assertion is wrong.

Which bit of it?  It's what I understand you to be suggesting.

R.

Re: std::pow implementation

[Gabriel Dos Reis]

Richard Earnshaw <rearnsha@arm.com> writes:

| > Richard Earnshaw <rearnsha@arm.com> writes:
| > 
| > [...]
| > 
| > | Now, assume that the amount of code in the a!=1 case is reduced.  At what 
| > | point does it become beneficial to always inline?  Can the programmer 
| > | tell?
| > 
| > He can profile.
| 
| Profiling doesn't help if the answer comes back as "sometimes" (function 
| foo's use of bar is best inlined, function wibble's use of bar is best not 
| inlined).

The cases where it most does not help is when the compiler decides it
knows better and goes on using his own programmed logic.

[...]

| > | With Gaby's suggested interpretation, the compiler has *no* choice; it 
| > | must obey the inlining constraint because the programmer always knows 
| > | better...  Even when prepared to admit that he doesn't.
| > 
| > That assertion is wrong.
| 
| Which bit of it?  It's what I understand you to be suggesting.

As I've repeatedly said, there are pathological cases where the
compiler simply cannot inline.  Secondly, I'm saying that the
compiler does not always know better than the programmer.  And in fact,
the programmer most of the time declares "inline" on purpose.  

Transmuting the meaning of "inline" is creating more fear, uncertainty
and doubt than we needed.

-- Gaby

Re: std::pow implementation

[Richard Guenther]

On 30 Jul 2003, Gabriel Dos Reis wrote:

> Richard Earnshaw <rearnsha@arm.com> writes:
>
> | > Richard Earnshaw <rearnsha@arm.com> writes:
> | >
> | > [...]
> | >
> | > | Now, assume that the amount of code in the a!=1 case is reduced.  At what
> | > | point does it become beneficial to always inline?  Can the programmer
> | > | tell?
> | >
> | > He can profile.
> |
> | Profiling doesn't help if the answer comes back as "sometimes" (function
> | foo's use of bar is best inlined, function wibble's use of bar is best not
> | inlined).
>
> The cases where it most does not help is when the compiler decides it
> knows better and goes on using his own programmed logic.

Oh - I thought you meant profile directed inlining decisions by the
compiler, not by the user. The latter is not useful.

> | > | With Gaby's suggested interpretation, the compiler has *no* choice; it
> | > | must obey the inlining constraint because the programmer always knows
> | > | better...  Even when prepared to admit that he doesn't.
> | >
> | > That assertion is wrong.
> |
> | Which bit of it?  It's what I understand you to be suggesting.
>
> As I've repeatedly said, there are pathological cases where the
> compiler simply cannot inline.  Secondly, I'm saying that the
> compiler does not always know better than the programmer.  And in fact,
> the programmer most of the time declares "inline" on purpose.
>
> Transmuting the meaning of "inline" is creating more fear, uncertainty
> and doubt than we needed.

So what are the semantics of the "inline" keyword you propose? What I read
into your statements is something like "the compiler should inline a
function if I want it to be inline, and he should read my mind for
deciding this."

The only sane possible semantics I see are:

1. inline declared functions are inlined always if technically possible
2. the inline keyword has no effect
3. inline is handled in an implementation defined manner (as stated in the
   standard), maybe by adjusting the set of functions considered for inlining,
   as gcc does.

I argue we cannot go away from #3 without portability problems (to other
compilers and architectures).

Richard.

Re: std::pow implementation

[Richard Guenther]

On Wed, 30 Jul 2003, Richard Guenther wrote:

> The only sane possible semantics I see are:
>
> 1. inline declared functions are inlined always if technically possible
> 2. the inline keyword has no effect
> 3. inline is handled in an implementation defined manner (as stated in the
>    standard), maybe by adjusting the set of functions considered for inlining,
>    as gcc does.
>
> I argue we cannot go away from #3 without portability problems (to other
> compilers and architectures).

Of course I see gcc's usage of #3 can be improved by, f.i. giving
inlining limits a boost for functions declared inline.

Richard.

Re: std::pow implementation

[Gabriel Dos Reis]

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

| On 30 Jul 2003, Gabriel Dos Reis wrote:
| 
| > Richard Earnshaw <rearnsha@arm.com> writes:
| >
| > | > Richard Earnshaw <rearnsha@arm.com> writes:
| > | >
| > | > [...]
| > | >
| > | > | Now, assume that the amount of code in the a!=1 case is reduced.  At what
| > | > | point does it become beneficial to always inline?  Can the programmer
| > | > | tell?
| > | >
| > | > He can profile.
| > |
| > | Profiling doesn't help if the answer comes back as "sometimes" (function
| > | foo's use of bar is best inlined, function wibble's use of bar is best not
| > | inlined).
| >
| > The cases where it most does not help is when the compiler decides it
| > knows better and goes on using his own programmed logic.
| 
| Oh - I thought you meant profile directed inlining decisions by the
| compiler, not by the user. The latter is not useful.

I'm not excluding profile directed inlining. But we don't have
architecture in place for that yet.

[...]

| The only sane possible semantics I see are:
| 
| 1. inline declared functions are inlined always if technically possible
| 2. the inline keyword has no effect
| 3. inline is handled in an implementation defined manner (as stated in the
|    standard), maybe by adjusting the set of functions considered for inlining,
|    as gcc does.

I'm arguing for #1 and #3 combined.  Meaning, inline simple functions
at low optimization level, try hard at higher level + compiler
parameter adjustement.

-- Gaby

Re: std::pow implementation

[Richard Guenther]

> | The only sane possible semantics I see are:
> |
> | 1. inline declared functions are inlined always if technically possible
> | 2. the inline keyword has no effect
> | 3. inline is handled in an implementation defined manner (as stated in the
> |    standard), maybe by adjusting the set of functions considered for inlining,
> |    as gcc does.
>
> I'm arguing for #1 and #3 combined.  Meaning, inline simple functions
> at low optimization level, try hard at higher level + compiler
> parameter adjustement.

Thats what we have now - generally we go with #3, for small functions we
go with #1 (tune what is small with --param min-inline-insns=XXX).

Richard.

Re: std::pow implementation

[Gabriel Dos Reis]

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

| > | The only sane possible semantics I see are:
| > |
| > | 1. inline declared functions are inlined always if technically possible
| > | 2. the inline keyword has no effect
| > | 3. inline is handled in an implementation defined manner (as stated in the
| > |    standard), maybe by adjusting the set of functions considered for inlining,
| > |    as gcc does.
| >
| > I'm arguing for #1 and #3 combined.  Meaning, inline simple functions
| > at low optimization level, try hard at higher level + compiler
| > parameter adjustement.
| 
| Thats what we have now - generally we go with #3, for small functions we
| go with #1 (tune what is small with --param min-inline-insns=XXX).

What I'm arguing for is not what have.  For example, something like  
'std::string() const' does not need fiddling with --param -- that is,
its inlining should not depend on the context of use.

-- Gaby

Re: std::pow implementation

[Richard Guenther]

On 30 Jul 2003, Gabriel Dos Reis wrote:

> Richard Guenther <rguenth@tat.physik.uni-tuebingen.de> writes:
>
> | > | The only sane possible semantics I see are:
> | > |
> | > | 1. inline declared functions are inlined always if technically possible
> | > | 2. the inline keyword has no effect
> | > | 3. inline is handled in an implementation defined manner (as stated in the
> | > |    standard), maybe by adjusting the set of functions considered for inlining,
> | > |    as gcc does.
> | >
> | > I'm arguing for #1 and #3 combined.  Meaning, inline simple functions
> | > at low optimization level, try hard at higher level + compiler
> | > parameter adjustement.
> |
> | Thats what we have now - generally we go with #3, for small functions we
> | go with #1 (tune what is small with --param min-inline-insns=XXX).
>
> What I'm arguing for is not what have.  For example, something like
> 'std::string() const' does not need fiddling with --param -- that is,
> its inlining should not depend on the context of use.

Its inlining doesnt depend on the context of use if it is small enough. Of
course now we are at the point where the compiler needs to decide how
large a function is - and this area vastly improved a few weeks ago. If
this is still not your point you need to start defining what a "small"
function is. Apart from being a function whose inlining is profitable, of
course ;)

Richard.

Re: std::pow implementation

[Richard B. Kreckel]

Hi,

On Wed, 30 Jul 2003, Richard Guenther wrote:
> On 30 Jul 2003, Gabriel Dos Reis wrote:
> > Richard Earnshaw <rearnsha@arm.com> writes:
> > | > Richard Earnshaw <rearnsha@arm.com> writes:
> > | > [...]
> > | > | Now, assume that the amount of code in the a!=1 case is reduced.  At what
> > | > | point does it become beneficial to always inline?  Can the programmer
> > | > | tell?
> > | >
> > | > He can profile.
> > |
> > | Profiling doesn't help if the answer comes back as "sometimes" (function
> > | foo's use of bar is best inlined, function wibble's use of bar is best not
> > | inlined).
> >
> > The cases where it most does not help is when the compiler decides it
> > knows better and goes on using his own programmed logic.
>
> Oh - I thought you meant profile directed inlining decisions by the
> compiler, not by the user. The latter is not useful.

Sometimes, the latter *is* useful.  For a project where speed was quite
essential I have once gone through the whole cycle (trial inline) ->
(compile)  -> (benchmark/profile/read the disassembled output) several
dozen times till I found out some good inlining patterns.  Without profile
directed inlining at a global level there isn't any alternative in extreme
cases.

Transmuting the meaning of "inline" *is* counterproductive.  The compiler
should trust the programmer.

[...]
> The only sane possible semantics I see are:
>
> 1. inline declared functions are inlined always if technically possible
> 2. the inline keyword has no effect
> 3. inline is handled in an implementation defined manner (as stated in the
>    standard), maybe by adjusting the set of functions considered for inlining,
>    as gcc does.
>
> I argue we cannot go away from #3 without portability problems (to other
> compilers and architectures).

I cannot agree.  Sticking to the original meaning of "inline" (a
combination of #1 and #3, as Gaby proposed) will definitely reduce
portability problems, to other compilers at least.  The fact that many
compilers come up with their own semantics is quite sad.

Regards
     -richy.
-- 
Richard B. Kreckel
<Richard.Kreckel@GiNaC.DE>
<http://www.ginac.de/~kreckel/>

Re: std::pow implementation

[Richard Earnshaw]

> | Profiling doesn't help if the answer comes back as "sometimes" (function 
> | foo's use of bar is best inlined, function wibble's use of bar is best not 
> | inlined).
> 
> The cases where it most does not help is when the compiler decides it
> knows better and goes on using his own programmed logic.

You've lost me... If the compiler can decide that not inlining things is 
better, how does that differ from what we have now?

> | > | With Gaby's suggested interpretation, the compiler has *no* choice; it 
> | > | must obey the inlining constraint because the programmer always knows 
> | > | better...  Even when prepared to admit that he doesn't.
> | > 
> | > That assertion is wrong.
> | 
> | Which bit of it?  It's what I understand you to be suggesting.
> 
> As I've repeatedly said, there are pathological cases where the
> compiler simply cannot inline.  Secondly, I'm saying that the
> compiler does not always know better than the programmer.  And in fact,
> the programmer most of the time declares "inline" on purpose.  
> 
> Transmuting the meaning of "inline" is creating more fear, uncertainty
> and doubt than we needed.

Suggesting that a programmer must only use inline when they are convinced 
that better code will always result (ie that using inline when it may only 
sometimes produce better code is "dangerous") sounds even more like 
spreading FUD to me.  You're going to get people saying "Never use inline, 
it can make your code worse".

R.

Re: std::pow implementation

[Gabriel Dos Reis]

Richard Earnshaw <rearnsha@arm.com> writes:

| > | > | With Gaby's suggested interpretation, the compiler has *no* choice; it 
| > | > | must obey the inlining constraint because the programmer always knows 
| > | > | better...  Even when prepared to admit that he doesn't.
| > | > 
| > | > That assertion is wrong.
| > | 
| > | Which bit of it?  It's what I understand you to be suggesting.
| > 
| > As I've repeatedly said, there are pathological cases where the
| > compiler simply cannot inline.  Secondly, I'm saying that the
| > compiler does not always know better than the programmer.  And in fact,
| > the programmer most of the time declares "inline" on purpose.  
| > 
| > Transmuting the meaning of "inline" is creating more fear, uncertainty
| > and doubt than we needed.
| 
| Suggesting that a programmer must only use inline when they are convinced 
| that better code will always result (ie that using inline when it may only 
| sometimes produce better code is "dangerous") sounds even more like 
| spreading FUD to me.  You're going to get people saying "Never use inline, 
| it can make your code worse".

Please, I didn't suggest that.

-- Gaby

Re: std::pow implementation

[Scott Robert Ladd]

Richard Earnshaw wrote:
> Profiling doesn't help if the answer comes back as "sometimes"
> (function foo's use of bar is best inlined, function wibble's use of
> bar is best not inlined).

Inlining is an optimization; in all but the most obvious and trivial
cases (e.g., simple assignments), it should be performed by a programmer 
*after* profiling, and not before. "Premature optimization is the root 
of all evil", according to Hoare and Knuth; in code reviews, I tend to 
grumble about people who insist on inlining and using cute tricks, when 
they haven't done any analysis as to how their choices affect code 
quality and performance.

The programmer, not the compiler, has the responsibility to create an 
effective program.

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

Re: std::pow implementation

[Richard Guenther]

On 30 Jul 2003, Gabriel Dos Reis wrote:

> Richard Earnshaw <rearnsha@arm.com> writes:
>
> | Now, assume that the amount of code in the a!=1 case is reduced.  At what
> | point does it become beneficial to always inline?  Can the programmer
> | tell?
>
> He can profile.

We dont do profile directed inlining. Obviously I would very much
appreciate this! Even simple function size estimate feedback from the
backend used in a two-stage compile would be useful.

> | With Gaby's suggested interpretation, the compiler has *no* choice; it
> | must obey the inlining constraint because the programmer always knows
> | better...  Even when prepared to admit that he doesn't.
>
> That assertion is wrong.

Which one? That the compiler has no choice?

Richard.

Re: std::pow implementation

[Gabriel Dos Reis]

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

| > | With Gaby's suggested interpretation, the compiler has *no* choice; it
| > | must obey the inlining constraint because the programmer always knows
| > | better...  Even when prepared to admit that he doesn't.
| >
| > That assertion is wrong.
| 
| Which one? That the compiler has no choice?

Mostly.  See my answer to (the other) Richard.

-- Gaby

Re: std::pow implementation

[Scott Robert Ladd]

Richard Earnshaw wrote:
> This is talking specifically about *very small* functions ("one or two 
> assignments").  It says nothing about what happens if the programmer 
> decides to put a 2000 line monstrosity in the middle of a class definition 
> (which would be legal, if somewhat stupid).  A practical compiler 
> eventually has to say "enough is enough", or it is likely to crash, run 
> out of memory or whatever.

I do not want my freedom limited by the stupidity of others. If someone 
explicitly inlines a 2000-line function, let them; the wisdom of such a 
choice (or lack thereof) is an issue for code review and the marketplace.

Let's say that I use a little shell sort in a program; should the 
compiler decide to replace my explicit choice of algorithm with 
quicksort, even though I have determined that shell sort is better?

When I say "inline", I mean inline, regardless of other opinions 
(including those of the compiler).

> I disagree.  What really counts is that the compiler has sufficient 
> information to do a good job when compiling the code (ie to reduce, and 
> hopefully eliminate, the abstraction penalty).  What constitutes a "good 
> job" is up to the compiler...

No.

What constitutes a "good job" is defined by a human mind, not a piece of 
technology that lacks any concept of "good." Over the years, I've found 
many arrogant tools (and not just from Microsoft) -- tools that assume, 
*incorrectly*, that their "wisdom" exceeds mine.

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

Re: std::pow implementation

[Richard Earnshaw]

> Richard Earnshaw wrote:
> > This is talking specifically about *very small* functions ("one or two 
> > assignments").  It says nothing about what happens if the programmer 
> > decides to put a 2000 line monstrosity in the middle of a class definition 
> > (which would be legal, if somewhat stupid).  A practical compiler 
> > eventually has to say "enough is enough", or it is likely to crash, run 
> > out of memory or whatever.
> 
> I do not want my freedom limited by the stupidity of others. If someone 
> explicitly inlines a 2000-line function, let them; the wisdom of such a 
> choice (or lack thereof) is an issue for code review and the marketplace.
> 
> Let's say that I use a little shell sort in a program; should the 
> compiler decide to replace my explicit choice of algorithm with 
> quicksort, even though I have determined that shell sort is better?
> 
> When I say "inline", I mean inline, regardless of other opinions 
> (including those of the compiler).

Really? And when you say "register" do you really mean that?  If so, then 
I'm sorry, but you are in for a big disappointment when using gcc -- it 
completely ignores the register keyword when optimizing and has done since 
~forever.

> 
> > I disagree.  What really counts is that the compiler has sufficient 
> > information to do a good job when compiling the code (ie to reduce, and 
> > hopefully eliminate, the abstraction penalty).  What constitutes a "good 
> > job" is up to the compiler...
> 
> No.
> 
> What constitutes a "good job" is defined by a human mind, not a piece of 
> technology that lacks any concept of "good." Over the years, I've found 
> many arrogant tools (and not just from Microsoft) -- tools that assume, 
> *incorrectly*, that their "wisdom" exceeds mine.
> 

I've already given examples of when the compiler can make use of context 
to give better inlining than can be determined statically.  Your 
"arrogant" assertion that inline must always and unconditionally mean 
inline impliess that programmers can never take advantage of those cases.

R.

Re: std::pow implementation

[Gabriel Dos Reis]

Richard Earnshaw <rearnsha@arm.com> writes:

[...]

| > When I say "inline", I mean inline, regardless of other opinions 
| > (including those of the compiler).
| 
| Really? And when you say "register" do you really mean that? 

It is tempting to make the analogy with "register", but you have to
acknowledge the fact that inlining strategy is not at the same level
of sophistication as register allocation.  Therefore, any answer you
get for the question above is irrelevant to whether you should decide
whether your programmed inliner always knows better than the
programmer.   Until then, please listen to the programmer.  Don't
transmute "inline".

-- Gaby

Re: std::pow implementation

[Richard Earnshaw]

> Richard Earnshaw <rearnsha@arm.com> writes:
> 
> [...]
> 
> | > When I say "inline", I mean inline, regardless of other opinions 
> | > (including those of the compiler).
> | 
> | Really? And when you say "register" do you really mean that? 
> 
> It is tempting to make the analogy with "register", but you have to
> acknowledge the fact that inlining strategy is not at the same level
> of sophistication as register allocation.  Therefore, any answer you
> get for the question above is irrelevant to whether you should decide
> whether your programmed inliner always knows better than the
> programmer.   Until then, please listen to the programmer.  Don't
> transmute "inline".

I'm not arguing that the current implementation of inline is perfect (it's 
clearly not), just that the intent of the two keywords are conceptually 
similar -- it's an indication to the compiler of the programmer's intent.

If the original C specification had said that "register" meant "register" 
unconditionally, then the situation wouldn't have been any different -- 
the compiler would have to obey the user, even if the compiler could do 
better.  The same is also conceptually true with inline; if its meaning 
becomes "you, the compiler, have no choice in this decision" then it 
doesn't matter how smart the compiler can become it still has to obey the 
directive.  This, IMO, is clearly incompatible with the intent of inline, 
even as Stroustrup originally intended it.

R.

Re: std::pow implementation

[Gabriel Dos Reis]

Richard Earnshaw <rearnsha@arm.com> writes:

| If the original C specification had said that "register" meant "register" 
| unconditionally, then the situation wouldn't have been any different -- 
| the compiler would have to obey the user, even if the compiler could do 
| better.  The same is also conceptually true with inline; if its meaning 
| becomes "you, the compiler, have no choice in this decision" then it 
| doesn't matter how smart the compiler can become it still has to obey the 
| directive.  This, IMO, is clearly incompatible with the intent of inline, 
| even as Stroustrup originally intended it.

The point of disagreement is that from "The same is also conceptually
true with inline", the compiler is jumping to "the same is also
practically true with inline" without even reaching that level of
sophistication.  If the compiler reaches that level, I'm pretty sure
Stroustrup will agree with you :-)  But till then....

-- Gaby

Re: std::pow implementation

[Scott Robert Ladd]

Richard Earnshaw wrote:
>> When I say "inline", I mean inline, regardless of other opinions 
>> (including those of the compiler).
> 
> Really? And when you say "register" do you really mean that?  If so,
> then I'm sorry, but you are in for a big disappointment when using
> gcc -- it completely ignores the register keyword when optimizing and
> has done since ~forever.

Yes -- but as others have pointed out, automatic register allocation is
a well-defined discipline that has proven itself. I have seen much
evidence (including the original basis for this thread) that automatic
inliners are still primitive.

One root of this dicussion is differences in definitions (and 
expectations) between C, Ada, and C++.

> I've already given examples of when the compiler can make use of
> context to give better inlining than can be determined statically.
> Your "arrogant" assertion that inline must always and unconditionally
> mean inline impliess that programmers can never take advantage of
> those cases.

No; I imply that a C++ compiler should do as it's told, and explain 
itself when it makes a contrary decision. I don't doubt that the 
compiler can find optimizations that are beyond my analysis; I also know 
compilers can (and do) generate bad code.

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

Re: std::pow implementation

[tm_gccmail]

On Wed, 30 Jul 2003, Richard Earnshaw wrote:

> Really? And when you say "register" do you really mean that?  If so, then 
> I'm sorry, but you are in for a big disappointment when using gcc -- it 
> completely ignores the register keyword when optimizing and has done since 
> ~forever.

We don't ignore it; we use it for alias analysis, iirc.

Toshi

Re: std::pow implementation

[Joe Buck]

On Wed, Jul 30, 2003 at 11:37:03AM +0100, Richard Earnshaw wrote:
> This is talking specifically about *very small* functions ("one or two 
> assignments").  It says nothing about what happens if the programmer 
> decides to put a 2000 line monstrosity in the middle of a class definition 
> (which would be legal, if somewhat stupid).

The answer is to do what the programmer says, if possible.  It may well
turn out that the programmer is not as stupid as you think, because
constant propagation winds up throwing away 1980 of those lines and the
call is in an inner loop.  And if the programmer really is stupid, he or
she will learn something.

gcc do not consider the head file change when compiling???

[Mojx]

Hi 

    When I modified a head file(*.h), gcc can't know it, to solve the issue, I have to make clean and make all again, is there any way to solve it?

Re: gcc do not consider the head file change when compiling???

[Gerald Pfeifer]

On Wed, 30 Jul 2003, Mojx wrote:
> When I modified a head file(*.h), gcc can't know it, to solve the
> issue, I have to make clean and make all again, is there any way to
> solve it?

This question is (way) outside of the scope of this list, but it seems
your Makefiles lack proper dependencies.

I suggest you study the documentation for your implementation of make
and add suitable dependencies.

Gerald
-- 
Gerald Pfeifer (Jerry)   gerald@pfeifer.com   http://www.pfeifer.com/gerald/

Re: gcc do not consider the head file change when compiling???

[Zack Weinberg]

"Mojx" <mojx@fulltop.com> writes:

> Hi When I modified a head file(*.h), gcc can't know it, to solve the
> issue, I have to make clean and make all again, is there any way to
> solve it?

This question is off topic for this list, which is about the
development _of_ gcc, not _using_ gcc to build other programs.

gcc just does what make tells it to do.  You have to list dependencies
of the .o files on all the relevant .h files in the makefile.  gcc can
help you generate these lists.  See the CPP and Make manuals for
details.

zw

Re: std::pow implementation

[Steven Bosscher]

Op di 29-07-2003, om 14:04 schreef Gabriel Dos Reis:
> Richard Guenther <rguenth@tat.physik.uni-tuebingen.de> writes:
> 
> | for my scientific app. If this ends up the same way as the
> | __attribute__((leafify)) discussion, I'll stop complaining now and instead
> | just file a PR for the record.
> 
> I bet your application will benefit much more from a better inlining
> support in the compiler than obfuscating the library.
> (Note that it need not be a sophisticated inliner).  We get to that point
> because, at some point it was decided that the compiler knows better
> than the programmer.

Can you stop bashing and be reasonable for once?  If you were so great
you would have declated __cmath_power inline in the first place.

If I do that, and compile with the tree-ssa branch at -O3 for this test
case:

=============================================
namespace std 
{
  // NB inline keyword which is not in libstdc++v3 __cmath_power
  template<typename _Tp>
    inline _Tp
    __cmath_power(_Tp __x, unsigned int __n)
    {
      _Tp __y = __n % 2 ? __x : 1;

      while (__n >>= 1)
        {
          __x = __x * __x;
          if (__n % 2)
            __y = __y * __x;
        }

      return __y;
    }

  template<typename _Tp>
    inline _Tp
    __pow_helper(_Tp __x, int __n)
    {
      return __n < 0
        ? _Tp(1)/__cmath_power(__x, -__n)
        : __cmath_power(__x, __n);
    }

  inline double 
  pow(double __x, int __i)
  { return __pow_helper(__x, __i); }
} 

double foo(double x)
{
  return std::pow(x, 2);
}
=============================================

I get the following tree dump after inlining:

=============================================
;; Function double foo(double) (_Z3food)

double foo(double) (x)
{
  double retval.12;
  double retval.11;
  double retval.10;
  double retval.9;

  {
    {
      int __i;
      double __x;
      double <UVb60>;

      __x = x;
      __i = 2;
      {
        double T.1;

        {
          {
            int __n;
            double __x;
            double <UVe70>;

            __x = __x;
            __n = __i;
            {
              double iftmp.4;
              int T.5;
              unsigned int T.6;
              double T.7;
              unsigned int __n.8;

              {
                if (__n < 0)
                  {
                    T.5 = -__n;
                    T.6 = (unsigned int)T.5;
                    {
                      unsigned int __n;
                      double __x;
                      double <UV5380>;

                      __x = __x;
                      __n = T.6;
                      {
                        double iftmp.2;
                        unsigned int T.3;

                        {
                          double __y;

                          T.3 = __n % 2;
                          if (T.3 != 0)
                            {
                              iftmp.2 = __x
                            }
                          else
                            {
                              iftmp.2 = 1.0e+0
                            };
                          __y = iftmp.2;
                          while (1)
                            {
                              __n = __n >> 1;
                              if (__n == 0)
                                {
                                  goto <UL5540>;
                                }
                              else
                                {
                                  (void)0
                                };
                              {
                                {
                                  __x = __x * __x;
                                  {
                                    T.3 = __n % 2;
                                    if (T.3 != 0)
                                      {
                                        {
                                          __y = __y * __x
                                        }
                                      }
                                    else
                                      {
                                        (void)0
                                      }
                                  }
                                }
                              }
                            };
                          <UL5540>:;;
                          {
                            <UV5380> = __y;
                            goto <UL5310>;
                          }
                        }
                      };
                      <UL5310>:;;
                      retval.11 = <UV5380>
                    };
                    T.7 = retval.11;
                    iftmp.4 = 1.0e+0 / T.7
                  }
                else
                  {
                    __n.8 = (unsigned int)__n;
                    {
                      unsigned int __n;
                      double __x;
                      double <UV57e0>;

                      __x = __x;
                      __n = __n.8;
                      {
                        double iftmp.2;
                        unsigned int T.3;

                        {
                          double __y;

                          T.3 = __n % 2;
                          if (T.3 != 0)
                            {
                              iftmp.2 = __x
                            }
                          else
                            {
                              iftmp.2 = 1.0e+0
                            };
                          __y = iftmp.2;
                          while (1)
                            {
                              __n = __n >> 1;
                              if (__n == 0)
                                {
                                  goto <UL59a0>;
                                }
                              else
                                {
                                  (void)0
                                };
                              {
                                {
                                  __x = __x * __x;
                                  {
                                    T.3 = __n % 2;
                                    if (T.3 != 0)
                                      {
                                        {
                                          __y = __y * __x
                                        }
                                      }
                                    else
                                      {
                                        (void)0
                                      }
                                  }
                                }
                              }
                            };
                          <UL59a0>:;;
                          {
                            <UV57e0> = __y;
                            goto <UL5770>;
                          }
                        }
                      };
                      <UL5770>:;;
                      retval.12 = <UV57e0>
                    };
                    iftmp.4 = retval.12
                  };
                (void)0;
                {
                  <UVe70> = iftmp.4;
                  goto <ULe00>;
                }
              }
            };
            <ULe00>:;;
            retval.10 = <UVe70>
          };
          T.1 = retval.10;
          (void)0;
          {
            <UVb60> = T.1;
            goto <ULaf0>;
          }
        }
      };
      <ULaf0>:;;
      retval.9 = <UVb60>
    };
    return retval.9;
  }
}
=============================================

which looks like this after tree-optimizing:

=============================================

;; Function double foo(double) (_Z3food)

double foo(double) (x)
{
  {
    {
      if (0)
        {
          {
            (void)0
          }
        }
      else
        {
          {
            unsigned int __n;
            double __x;

            {
              unsigned int T.3;

              {
                double __y;

                __x = x;
                __y = 1.0e+0;
                __n = 2;
                while (1)
                  {
                    __n = __n >> 1;
                    if (__n == 0)
                      {
                        goto <UL59a0>;
                      }
                    else
                      {
                        (void)0
                      };
                    __x = __x * __x;
                    T.3 = __n % 2;
                    if (T.3 != 0)
                      {
                        __y = __y * __x
                      }
                    else
                      {
                        (void)0
                      }
                  };
                <UL59a0>:;
              }
            };
            <UL5770>:;
          }
        };
      <ULe00>:;
    };
    <ULaf0>:;
  };
  return __y;
}
=============================================


Now cut away all the redundant labels and other cruft, and you end up
with:


;; Function double foo(double) (_Z3food)

double foo(double) (x)
{
  unsigned int __n;
  double __x;
  unsigned int T.3;
  double __y;

  __x = x;
  __y = 1.0e+0;
  __n = 2;
  while (1)
    {
      __n = __n >> 1;
      if (__n == 0)
	goto <UL59a0>;

      __x = __x * __x;
      T.3 = __n % 2;

      if (T.3 != 0)
	__y = __y * __x
    }
  <UL59a0>:;
  return __y;
}

which is exactly what you want, is it not??

Gr.
Steven

Re: std::pow implementation

[Gabriel Dos Reis]

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

| Can you stop bashing and be reasonable for once?

I'm reasonable.  Being reasonable does not imply not recognizing that
the original meaning of "inline" has been transmuted.

| If you were so great you would have declated __cmath_power inline in
| the first place. 

Did I claim I am "great" or "so great"?  
There are reasons I didn't declare __cmath_power inline in the first place. 
That is why I asked for data and ways to reproduce them.

[...]

| Now cut away all the redundant labels and other cruft, and you end up
| with:

In short, you have demonstrated that if "inline" is given its obvious
meaning, the compiler can do a better job.  That is what I claimed in
the first place.

-- Gaby

Re: std::pow implementation

[Richard Guenther]

On 29 Jul 2003, Gabriel Dos Reis wrote:

> Steven Bosscher <s.bosscher@student.tudelft.nl> writes:
>
> | If you were so great you would have declated __cmath_power inline in
> | the first place.
>
> Did I claim I am "great" or "so great"?
> There are reasons I didn't declare __cmath_power inline in the first place.
> That is why I asked for data and ways to reproduce them.

To show you some of the performance improve I get with my "hacked"
__pow_helper(), the average time for one iteration of my scientific
app dropped from 2.6s to 1.8s - this is a 30% improvement. Not to say
I ever expected gcc (or libstdc++) to not create x*x out of std::pow(x,2).

> | Now cut away all the redundant labels and other cruft, and you end up
> | with:
>
> In short, you have demonstrated that if "inline" is given its obvious
> meaning, the compiler can do a better job.  That is what I claimed in
> the first place.

Note that Steven checked with -O3, so wether inline is specified here or
not should be meaningless(?).

Steven, does the code in your example optimize to the same as x*X?

Richard.

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

Re: std::pow implementation

[Steven Bosscher]

Op di 29-07-2003, om 14:43 schreef Richard Guenther:
> Steven, does the code in your example optimize to the same as x*X?

Not at the tree level because we don't have loop unrolling there.  I
would expect that the RTL inliner can deduce the number of iterations
and unroll the loop.  All other code is dead at that point and you'd end
up with x*x.  But I haven't checked that.

Gr.
Steven

Re: std::pow implementation

[Paolo Carlini]

Steven Bosscher wrote:

>I would expect that the RTL inliner can deduce the number of iterations
>and unroll the loop.  All other code is dead at that point and you'd end
>up with x*x.
>
Cool!

Paolo.

Re: std::pow implementation

[Richard Guenther]

On Tue, 29 Jul 2003, Paolo Carlini wrote:

> Steven Bosscher wrote:
>
> >I would expect that the RTL inliner can deduce the number of iterations
> >and unroll the loop.  All other code is dead at that point and you'd end
> >up with x*x.
> >
> Cool!

Unfortunately not,

double foo2(double x)
{
  pow(x, 2);
}

gets to (with gcc3.4, __cmath_power declared inline, -O2 -funroll-loops
-ffast-math)

_Z4foo2d:
.LFB12:
        pushl   %ebp    #
.LCFI4:
        movl    %esp, %ebp      #,
.LCFI5:
        fldl    8(%ebp) # x
        fld1
        movl    $1, %eax        #, __n
        jmp     .L62    #
        .p2align 4,,7
.L73:
        fxch    %st(1)  #
.L62:
        fxch    %st(1)  #
        testb   $1, %al #, __n
        fmul    %st(0), %st     #,
        je      .L59    #,
        fmul    %st, %st(1)     #,
.L59:
        shrl    %eax    # __n
        jne     .L73    #,
        fstp    %st(0)  #
        popl    %ebp    #
        ret

yay!

Richard.

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

Re: std::pow implementation

[Steven Bosscher]

Op di 29-07-2003, om 14:55 schreef Richard Guenther:
> double foo2(double x)
> {
>   pow(x, 2);
> }
> 
> gets to (with gcc3.4, __cmath_power declared inline, -O2 -funroll-loops
> -ffast-math)
> 
> _Z4foo2d:
> .LFB12:
>         pushl   %ebp    #
> .LCFI4:
>         movl    %esp, %ebp      #,
> .LCFI5:
>         fldl    8(%ebp) # x
>         fld1
>         movl    $1, %eax        #, __n
>         jmp     .L62    #
>         .p2align 4,,7
> .L73:
>         fxch    %st(1)  #
> .L62:
>         fxch    %st(1)  #
>         testb   $1, %al #, __n
>         fmul    %st(0), %st     #,
>         je      .L59    #,
>         fmul    %st, %st(1)     #,
> .L59:
>         shrl    %eax    # __n
>         jne     .L73    #,
>         fstp    %st(0)  #
>         popl    %ebp    #
>         ret
> 
> yay!

Not that it didn't even unroll the loop at all.

I have no idea if it makes any difference, I'm just curious: What
happens if you replace 

      while (__n >>= 1)

with
      while (__n = __n / 2)
?

Maybe the loop stuff can't handle shifts...

Gr.
Steven

Re: std::pow implementation

[Richard Guenther]

On 29 Jul 2003, Steven Bosscher wrote:

> Op di 29-07-2003, om 14:55 schreef Richard Guenther:
> > double foo2(double x)
> > {
> >   pow(x, 2);
> > }
> >
>
> Not that it didn't even unroll the loop at all.
>
> I have no idea if it makes any difference, I'm just curious: What
> happens if you replace
>
>       while (__n >>= 1)
>
> with
>       while (__n = __n / 2)
> ?
>
> Maybe the loop stuff can't handle shifts...

It doesnt handle __n /= 2 either. So we're lost in optimizing this, it
seems (-fold-unroll-loops is not better either).

Richard.

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

Re: std::pow implementation

[Richard Guenther]

On 29 Jul 2003, Steven Bosscher wrote:

> Op di 29-07-2003, om 14:55 schreef Richard Guenther:
> > double foo2(double x)
> > {
> >   pow(x, 2);
> > }
>
> Not that it didn't even unroll the loop at all.
>
> I have no idea if it makes any difference, I'm just curious: What
> happens if you replace
>
>       while (__n >>= 1)
>
> with
>       while (__n = __n / 2)
> ?
>
> Maybe the loop stuff can't handle shifts...

I get it to unroll with

  template<typename _Tp>
    inline _Tp
    __cmath_power(_Tp __x, unsigned int __n)
    {
      _Tp __y = __n & 1 ? __x : 1;
      const int ni = __n == 0 ? 0 : sizeof(unsigned int)*8 - __builtin_clz(__n);
      for (int i=0; i<ni; ++i)
        {
          __n >>= 1;
          __x = __x * __x;
          if (__n & 1)
            __y = __y * __x;
        }

      return __y;
    }

But neither the __n >>= 1; (or __n /= 2), not the following bit test
is constant folded and we end up with

_Z4foo2d:
.LFB12:
        pushl   %ebp    #
.LCFI4:
        movl    %esp, %ebp      #,
.LCFI5:
        fldl    8(%ebp) # x
        movl    $2, %eax        #, __n
        fld1
        fxch    %st(1)  #
        shrl    %eax    # tmp91
        movb    %al, %dl        #, tmp93
        fmul    %st(0), %st     #,
        andb    $1, %dl #, tmp93
        testb   %dl, %dl        # tmp93
        je      .L92    #,
        fmul    %st, %st(1)     #,
.L92:
        shrl    %eax    # __n
        movb    %al, %dl        #, tmp93
        fmul    %st(0), %st     #,
        andb    $1, %dl #, tmp93
        testb   %dl, %dl        # tmp93
        je      .L97    #,
        fmulp   %st, %st(1)     #,
        jmp     .L80    #
        .p2align 4,,7
.L97:
        fstp    %st(0)  #
.L80:
        popl    %ebp    #
        ret

It seems this fact is worth another PR.

Richard.

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

Re: std::pow implementation

[Andrew Pinski]

On Tuesday, Jul 29, 2003, at 08:43 US/Eastern, Richard Guenther wrote:
> On 29 Jul 2003, Gabriel Dos Reis wrote:
>
> To show you some of the performance improve I get with my "hacked"
> __pow_helper(), the average time for one iteration of my scientific
> app dropped from 2.6s to 1.8s - this is a 30% improvement. Not to say
> I ever expected gcc (or libstdc++) to not create x*x out of 
> std::pow(x,2).

If you use ::pow instead, gcc does change it to be x*x on the mainline 
at least.

Thanks,
Andrew Pinski

Re: std::pow implementation

[Richard Guenther]

On Tue, 29 Jul 2003, Andrew Pinski wrote:

> On Tuesday, Jul 29, 2003, at 08:43 US/Eastern, Richard Guenther wrote:
> > On 29 Jul 2003, Gabriel Dos Reis wrote:
> >
> > To show you some of the performance improve I get with my "hacked"
> > __pow_helper(), the average time for one iteration of my scientific
> > app dropped from 2.6s to 1.8s - this is a 30% improvement. Not to say
> > I ever expected gcc (or libstdc++) to not create x*x out of
> > std::pow(x,2).
>
> If you use ::pow instead, gcc does change it to be x*x on the mainline
> at least.

Why isnt this done for std::pow? Any particular reason?

Richard.

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

Re: std::pow implementation

[Andrew Pinski]

On Tuesday, Jul 29, 2003, at 08:57 US/Eastern, Richard Guenther wrote:

> On Tue, 29 Jul 2003, Andrew Pinski wrote:
>
>> On Tuesday, Jul 29, 2003, at 08:43 US/Eastern, Richard Guenther wrote:
>>> On 29 Jul 2003, Gabriel Dos Reis wrote:
>>>
>>> To show you some of the performance improve I get with my "hacked"
>>> __pow_helper(), the average time for one iteration of my scientific
>>> app dropped from 2.6s to 1.8s - this is a 30% improvement. Not to say
>>> I ever expected gcc (or libstdc++) to not create x*x out of
>>> std::pow(x,2).
>>
>> If you use ::pow instead, gcc does change it to be x*x on the mainline
>> at least.
>
> Why isnt this done for std::pow? Any particular reason?

I just think this is just a bug in GCC for the builtins matching but I 
do not know the exact reason.

Andrew

Re: std::pow implementation

[Gabriel Dos Reis]

Andrew Pinski <pinskia@physics.uc.edu> writes:

| > Why isnt this done for std::pow? Any particular reason?
| 
| I just think this is just a bug in GCC for the builtins matching but I
| do not know the exact reason.

The "C" versison is declared 

   double pow(double, double)

and C does not have pow that is declared to take an int as exponent.
That version is C++ specific.

-- Gaby

Re: std::pow implementation

[Gabriel Dos Reis]

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

| > | Now cut away all the redundant labels and other cruft, and you end up
| > | with:
| >
| > In short, you have demonstrated that if "inline" is given its obvious
| > meaning, the compiler can do a better job.  That is what I claimed in
| > the first place.
| 
| Note that Steven checked with -O3, so wether inline is specified here or
| not should be meaningless(?).

I'm not sure that should be meaningless.  At -O3, GCC does not inline
imaginable functions.

-- Gaby

Re: std::pow implementation

[Steven Bosscher]

Op di 29-07-2003, om 14:36 schreef Gabriel Dos Reis:
> Steven Bosscher <s.bosscher@student.tudelft.nl> writes:
> | If you were so great you would have declated __cmath_power inline in
> | the first place. 
> 
> Did I claim I am "great" or "so great"?  

No you did not and I am sorry I formulated things like that.

> There are reasons I didn't declare __cmath_power inline in the first place. 
> That is why I asked for data and ways to reproduce them.

What are those reasons?  Clearly it helps to add the inline keyword. 
Something in the standard???

> | Now cut away all the redundant labels and other cruft, and you end up
> | with:
> 
> In short, you have demonstrated that if "inline" is given its obvious
> meaning, the compiler can do a better job.  That is what I claimed in
> the first place.

No, I've shown that inline still has a meaning in GCC whereas you
claimed that "it was decided that the compiler knows better than the
programmer", i.e. the compiler overrules the user.  What I've shown is
that the compiler can take a hint.

If you look at the tree inliner, it still honours the inline keyword,
and last time I checked, inline functions still were twice as likely to
be inlined as non-inline functions (at -O2 anyway).

Gr.
Steven

Re: std::pow implementation

[Gabriel Dos Reis]

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

| > There are reasons I didn't declare __cmath_power inline in the first place. 
| > That is why I asked for data and ways to reproduce them.
| 
| What are those reasons?  Clearly it helps to add the inline keyword. 
| Something in the standard???
| 
| > | Now cut away all the redundant labels and other cruft, and you end up
| > | with:
| > 
| > In short, you have demonstrated that if "inline" is given its obvious
| > meaning, the compiler can do a better job.  That is what I claimed in
| > the first place.
| 
| No, I've shown that inline still has a meaning in GCC whereas you
| claimed that "it was decided that the compiler knows better than the
| programmer", i.e. the compiler overrules the user.

And what I claimed corresponds to reality.  See

   http://gcc.gnu.org/ml/libstdc++/2003-05/msg00014.html

for *facts* from mainline.  The compiler has decided it can ignore
inline when its counting of something has reached some limits, i.e. he
knows better than the programmer.

|  What I've shown is that the compiler can take a hint.

No, you've shown that on a branch development, the compiler appears to
give "inline" its obvious meaning.

| If you look at the tree inliner, it still honours the inline keyword,

I know how the tree inliner is treating the inline keyword.
It honours the keyword only when it thinks that matches its own view.

-- Gaby

Re: std::pow implementation

[Steven Bosscher]

Op di 29-07-2003, om 15:05 schreef Gabriel Dos Reis:
> | No, I've shown that inline still has a meaning in GCC whereas you
> | claimed that "it was decided that the compiler knows better than the
> | programmer", i.e. the compiler overrules the user.
> 
> And what I claimed corresponds to reality.  See
> 
>    http://gcc.gnu.org/ml/libstdc++/2003-05/msg00014.html

You're just pointing to a mail that shows that warnings appeared after
the fix for PR10180 and half a dozen duplicates went in (the first
report being almost as old as the hard-coded limits in tree-inline.c,
still cp/optimize.c back then).  Just because a warning switch has been
broken for two years does not mean that someone suddenly decided that
the compiler is smarter than us.  You would have noticed those warnings
way earlier if that warning had been fixed earlier.

> for *facts* from mainline.  The compiler has decided it can ignore
> inline when its counting of something has reached some limits, i.e. he
> knows better than the programmer.

Ah, well, then I take it you're now objecting to both the tree and rtl
inliners :-)  Did you know the RTL inliner also has inlining limits? 
And that icc has inlining limits?

AFAICT, the tree inliner has had limits since March 27, 2001, see
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/cp/optimize.c.diff?r1=1.51.2.8&r2=1.51.2.9&hideattic=0&f=h

*That* is a fact.

So if everyone has such limits, one might assume you need them to make
proper compilation possible.  It's a trade-off that you have to make:
amount of inlining vs. {code size, memory footprint, compiler
performance, etc}.  For C++ this may sometimes mean an abstraction
penalty (which we hope to minimize with the tree optimizers, right?),
but in most cases it works just fine.

So what are you suggesting?  Are you saying that inlining limits are
there for _no_ good reason, are you going to claim that "inline" should
just mean "inline no matter what"?  Then before you know it you have
them complaining about how slow GCC is blahblahblah.


Now, the one point you do have is that the limit is arbitrary and in
fact until recently the limits really made no sense at all.  But with
the new function body size estimates Jan implemented recently, we're
already doing a much better job, and there is still room for
improvements.  Take a look at that and try to improve it.  _That_ would
be helpful.


> |  What I've shown is that the compiler can take a hint.
> 
> No, you've shown that on a branch development, the compiler appears to
> give "inline" its obvious meaning.

BS.  The trunk does exactly the same thing, it's still the same tree
inliner.  You should have tried it before you made this absurd
statement.

Gr.
Steven

Re: std::pow implementation

[Gabriel Dos Reis]

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

| Op di 29-07-2003, om 15:05 schreef Gabriel Dos Reis:
| > | No, I've shown that inline still has a meaning in GCC whereas you
| > | claimed that "it was decided that the compiler knows better than the
| > | programmer", i.e. the compiler overrules the user.
| > 
| > And what I claimed corresponds to reality.  See
| > 
| >    http://gcc.gnu.org/ml/libstdc++/2003-05/msg00014.html
| 
| You're just pointing to a mail that shows that warnings appeared after
| the fix for PR10180 and half a dozen duplicates went in (the first
| report being almost as old as the hard-coded limits in tree-inline.c,
| still cp/optimize.c back then).

Please do focuse on the message, not the medium.

The warnings are just the symptoms of a deeper disease, and I'm not
talking about the symptoms.  But about the disease.

The deeper disease is explained in the follow-up to the link I gave.

    http://gcc.gnu.org/ml/libstdc++/2003-05/msg00012.html

-- Gaby

Re: std::pow implementation

[Gabriel Dos Reis]

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

|               Did you know the RTL inliner also has inlining limits? 

Yes, I do.  So?

[...]

| performance, etc}.  For C++ this may sometimes mean an abstraction
| penalty (which we hope to minimize with the tree optimizers, right?),
| but in most cases it works just fine.

"Abstraction penalty" is an oxymoron, invented to excuse the compiler
for not doing its job.

-- Gaby

Re: std::pow implementation

[Steven Bosscher]

Op di 29-07-2003, om 16:17 schreef Gabriel Dos Reis:
> Steven Bosscher <s.bosscher@student.tudelft.nl> writes:
> | performance, etc}.  For C++ this may sometimes mean an abstraction
> | penalty (which we hope to minimize with the tree optimizers, right?),
> | but in most cases it works just fine.
> 
> "Abstraction penalty" is an oxymoron, invented to excuse the compiler
> for not doing its job.

Well how do you suggest we make the compiler to its job better then? 
It's easy to say it's not all great now, but then you also have to come
up with ideas.

Gr.
Steven

Re: std::pow implementation

[Gabriel Dos Reis]

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

| Op di 29-07-2003, om 16:17 schreef Gabriel Dos Reis:
| > Steven Bosscher <s.bosscher@student.tudelft.nl> writes:
| > | performance, etc}.  For C++ this may sometimes mean an abstraction
| > | penalty (which we hope to minimize with the tree optimizers, right?),
| > | but in most cases it works just fine.
| > 
| > "Abstraction penalty" is an oxymoron, invented to excuse the compiler
| > for not doing its job.
| 
| Well how do you suggest we make the compiler to its job better then? 

Start with removing the requirement that whether a function should be
inlined depends on its context of use.

| It's easy to say it's not all great now, 

No, it is not easy at all.  It takes spending time with people like you.

-- Gaby

Re: std::pow implementation

[Michael Matz]

Hi,

On 29 Jul 2003, Gabriel Dos Reis wrote:

> | Well how do you suggest we make the compiler to its job better then?
>
> Start with removing the requirement that whether a function should be
> inlined depends on its context of use.

So it should be inlined independend of the context?  Well, that for sure
_is_ nonsense, sorry.

> No, it is not easy at all.  It takes spending time with people like you.

Yeah, sure.

Re: std::pow implementation

[Gabriel Dos Reis]

Michael Matz <matz@suse.de> writes:

| Hi,
| 
| On 29 Jul 2003, Gabriel Dos Reis wrote:
| 
| > | Well how do you suggest we make the compiler to its job better then?
| >
| > Start with removing the requirement that whether a function should be
| > inlined depends on its context of use.
| 
| So it should be inlined independend of the context?

You missed "of use".

|  Well, that for sure _is_ nonsense, sorry.

It is nonsense only after you have modified what I said.

A simple function like 'std::string::end() const' should be cost-free.
Providing a controled access to a protected data should be as efficient
as accessing that data directly.  Protection is a compile time notion.

-- Gaby

Re: std::pow implementation

[Michael Matz]

Hi,

On 29 Jul 2003, Gabriel Dos Reis wrote:

> | > Start with removing the requirement that whether a function should be
> | > inlined depends on its context of use.
> |
> | So it should be inlined independend of the context?
>
> You missed "of use".

No, only in my repetition.

> It is nonsense only after you have modified what I said.
>
> A simple function like 'std::string::end() const' should be cost-free.

You are speaking about a special case (one small function) to support your
suggestion (makeing it happen for all functions).

Re: std::pow implementation

[Gabriel Dos Reis]

Michael Matz <matz@suse.de> writes:

| > It is nonsense only after you have modified what I said.
| >
| > A simple function like 'std::string::end() const' should be cost-free.
| 
| You are speaking about a special case (one small function) to support your
| suggestion (makeing it happen for all functions).

I'm taking it as examplar of one of the various kinds of unfortunate
consequences that put people to believe that a public data member is
faster than private.  Because, somehow it was decided that the compiler
knows better.  The root is the same.

-- Gaby

RE: std::pow implementation

[Rob Taylor]

Go Gaby, I suspect most professional C++ coders are with you on this...

When i have used inline in my code (and i've written a lot of code) like
most coders i've generally assumed that it'll inline up to a sensible
limit(presumably dependant on target cache size/branch penalty tradeoff) and
if i write:

class bla
{
public:
  foo() {i=1;}
private:
  int i;
}

i damm well expect that foo() is inlined in all situations, cos its *always*
a win. If the new fancy inliner can't do this, it isn't worth its salt.


Rob Taylor
Senior Developer    robt at flyingpig dot com
Flying Pig Systems  http://www.flyingpig.com

Please avoid sending me Word or PowerPoint attachments.
See http://www.fsf.org/philosophy/no-word-attachments.html
> -----Original Message-----
> From: gcc-owner@gcc.gnu.org [mailto:gcc-owner@gcc.gnu.org]On Behalf Of
> Gabriel Dos Reis
> Sent: 29 July 2003 16:12
> To: Michael Matz
> Cc: Steven Bosscher; Richard Guenther; gcc@gcc.gnu.org
> Subject: Re: std::pow implementation
>
>
> Michael Matz <matz@suse.de> writes:
>
> | > It is nonsense only after you have modified what I said.
> | >
> | > A simple function like 'std::string::end() const' should be cost-free.
> |
> | You are speaking about a special case (one small function) to
> support your
> | suggestion (makeing it happen for all functions).
>
> I'm taking it as examplar of one of the various kinds of unfortunate
> consequences that put people to believe that a public data member is
> faster than private.  Because, somehow it was decided that the compiler
> knows better.  The root is the same.
>
> -- Gaby
>

Re: std::pow implementation

[Gabriel Dos Reis]

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

| So what are you suggesting?  Are you saying that inlining limits are
| there for _no_ good reason,

I'm not saying those numbers were put there for no reason.
Whether those reasons are good or bad is a matter of debate.

| are you going to claim that "inline" should
| just mean "inline no matter what"?  

I'm claiming that inline should be given its original and obvious meaning.
Of course, you can construct examples where it is difficult or
impossible to inline.  But for simple cases, inline should mean just that.
std::string::end() is an example.

| Now, the one point you do have is that the limit is arbitrary and in

Perhaps, if you dare to focus on the message not on the medium you'll
see more than that.  If you just focus on the medium, you'll miss the
point. 

-- Gaby

Re: std::pow implementation

[Richard Guenther]

If we go back to the original question, wether std::__pow_helper and
std::__cmath_power are good implementations, please.

It has been shown that the current gcc unroller is not able to
unroll the while loop in std::__cmath_power() and such even inlining
does not help to create good code. Also inlining the loop if it is
not unrolled and its contents not sufficiently cprop'ed is harmful.

Isnt what one would expect to inline for constant and small __n only?
This we can make work using __builtin_constant_p() as proposed. This would
work for gcc3.3, too. For gcc3.4 we may want to rely on __builtin_pow()
instead (which calls libc pow() for not expanded cases which may be
slower than the pow(T, int) overload for small n).

Richard.

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

Re: std::pow implementation

[Gabriel Dos Reis]

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

| It has been shown that the current gcc unroller is not able to
| unroll the while loop in std::__cmath_power() and such even inlining
| does not help to create good code. Also inlining the loop if it is
| not unrolled and its contents not sufficiently cprop'ed is harmful.

If you find that after inlining, the status of "constant expression"
is not recognized then I'd encourage you to fill a PR.

-- Gaby

Re: std::pow implementation

[Richard Guenther]

On 29 Jul 2003, Gabriel Dos Reis wrote:

> Richard Guenther <rguenth@tat.physik.uni-tuebingen.de> writes:
>
> | It has been shown that the current gcc unroller is not able to
> | unroll the while loop in std::__cmath_power() and such even inlining
> | does not help to create good code. Also inlining the loop if it is
> | not unrolled and its contents not sufficiently cprop'ed is harmful.
>
> If you find that after inlining, the status of "constant expression"
> is not recognized then I'd encourage you to fill a PR.

The problem is the loop optimizer not being able to compute the number of
iterations here. PR optimization/11710 - though unfortunately not a
regression. Can anyone check if this is fixed on rtlopt (one more reason
to merge it)?

Richard.

Re: std::pow implementation

[Gabriel Dos Reis]

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

| > |  What I've shown is that the compiler can take a hint.
| > 
| > No, you've shown that on a branch development, the compiler appears to
| > give "inline" its obvious meaning.
| 
| BS.  The trunk does exactly the same thing, it's still the same tree
| inliner.  You should have tried it before you made this absurd
| statement.

The point you seem to be missing is that whether a function is inlined
depends on the context of use -- not just on its intrinsinc complexity.
That is what is absurd.  Not the mere statement of that fact.

-- Gaby

Re: std::pow implementation

[Steven Bosscher]

Op di 29-07-2003, om 16:27 schreef Gabriel Dos Reis:
> The point you seem to be missing is that whether a function is inlined
> depends on the context of use -- not just on its intrinsinc complexity.
> That is what is absurd.  Not the mere statement of that fact.

I suppose you mean the sometimes unfortunate effects of the throttle? 
That is why unit-at-a-time can in theory do so much better, at least in
theory.

Gr.
Steven

Re: std::pow implementation

[Alexandre Oliva]

On Jul 29, 2003, Gabriel Dos Reis <gdr@integrable-solutions.net> wrote:

> The point you seem to be missing is that whether a function is inlined
> depends on the context of use -- not just on its intrinsinc complexity.
> That is what is absurd.  Not the mere statement of that fact.

The context of use can make a *lot* of difference on whether it's
worth to inline a function or not.  Consider a very complex function
that takes a boolean argument, used to enable or disable most of the
complexity in the function.  If the caller passes a false boolean
argument, the function would simplify to pretty much nothing.
Therefore claiming that the context of use shouldn't play any role in
deciding whether a function should be inlined is absurd.

-- 
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: std::pow implementation

[Gabriel Dos Reis]

Alexandre Oliva <aoliva@redhat.com> writes:

| On Jul 29, 2003, Gabriel Dos Reis <gdr@integrable-solutions.net> wrote:
| 
| > The point you seem to be missing is that whether a function is inlined
| > depends on the context of use -- not just on its intrinsinc complexity.
| > That is what is absurd.  Not the mere statement of that fact.
| 
| The context of use can make a *lot* of difference on whether it's
| worth to inline a function or not.

But, why don't you trust the programmer?  Why do you insist that you
know better than the programmer?

| Consider a very complex function
| that takes a boolean argument, used to enable or disable most of the
| complexity in the function.  If the caller passes a false boolean
| argument, the function would simplify to pretty much nothing.

This is not a convincing example.

| Therefore claiming that the context of use shouldn't play any role in
| deciding whether a function should be inlined is absurd.

No, what is absurb is the imaginary scenario you describ above.

-- Gaby

Re: std::pow implementation

[Alexandre Oliva]

On Jul 30, 2003, Gabriel Dos Reis <gdr@integrable-solutions.net> wrote:

> Alexandre Oliva <aoliva@redhat.com> writes:
> | On Jul 29, 2003, Gabriel Dos Reis <gdr@integrable-solutions.net> wrote:
> | 
> | > The point you seem to be missing is that whether a function is inlined
> | > depends on the context of use -- not just on its intrinsinc complexity.
> | > That is what is absurd.  Not the mere statement of that fact.
> | 
> | The context of use can make a *lot* of difference on whether it's
> | worth to inline a function or not.

> But, why don't you trust the programmer?  Why do you insist that you
> know better than the programmer?

Because (1) inline is implicit in C++, (2) inline's fate is probably
no different from that of `register', and (3) what's profitable to
inline on one architecture may not be on another, making inline's use
highly non-portable should the compiler blindly trust it.

> | Consider a very complex function
> | that takes a boolean argument, used to enable or disable most of the
> | complexity in the function.  If the caller passes a false boolean
> | argument, the function would simplify to pretty much nothing.

> This is not a convincing example.

You may want to try this argument line with the customer that
approached us with this very request :-)

> | Therefore claiming that the context of use shouldn't play any role in
> | deciding whether a function should be inlined is absurd.

> No, what is absurb is the imaginary scenario you describ above.

It's not imaginary.  It comes up in real life very often.  Not
necessarily with boolean arguments, but integer constants known at
compile time are often passed to functions, and this enables
significant simplifications.  I'm not making this up.  This is a
feature that would be very nice to have, but we don't have mechanisms
to do anything like `try inlining, see whether it enables significant
simplification and, if not, outline it.'

-- 
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: std::pow implementation

[Gabriel Dos Reis]

Alexandre Oliva <aoliva@redhat.com> writes:

| On Jul 30, 2003, Gabriel Dos Reis <gdr@integrable-solutions.net> wrote:
| 
| > Alexandre Oliva <aoliva@redhat.com> writes:
| > | On Jul 29, 2003, Gabriel Dos Reis <gdr@integrable-solutions.net> wrote:
| > | 
| > | > The point you seem to be missing is that whether a function is inlined
| > | > depends on the context of use -- not just on its intrinsinc complexity.
| > | > That is what is absurd.  Not the mere statement of that fact.
| > | 
| > | The context of use can make a *lot* of difference on whether it's
| > | worth to inline a function or not.
| 
| > But, why don't you trust the programmer?  Why do you insist that you
| > know better than the programmer?
| 
| Because (1) inline is implicit in C++,

No, that is *your* invention.  Inline is NOT implicit.  That is just
an invention of people like you who prefer to ignore the purpose of
"inline".  Please, do give inline its original and obvious meaning. 

| (2) inline's fate is probably no different from that of `register',

But the *fact* is that we're not at same the level of sophistication of
automatic register allocation as we're for inline.  Until, then,
please do trust the programmer, in the spirit of C and C++.

| and (3) what's profitable to inline on one architecture may not be
| on another, 

Let's the programmer decide.  It is *his* choice.  He has control do
decide. 

| making inline's use highly non-portable should the compiler blindly
| trust it. 

Only because you have decided to transmute the original meaning of C++.

Please don't spread Fear, Uncertainty and Doubt.  You don't need to.

-- Gaby

Re: std::pow implementation

[Alexandre Oliva]

On Jul 30, 2003, Gabriel Dos Reis <gdr@integrable-solutions.net> wrote:

> | Because (1) inline is implicit in C++,

> No, that is *your* invention.  Inline is NOT implicit.

For a member function defined inside the class body, it is.
[dcl.fct.spec]/3  Sorry that I wasn't clear.

> Only because you have decided to transmute the original meaning of C++.

I haven't chosen anything, I just quoted the C Standard.  It clearly
calls for compiler's effort towards fast execution over inline
substitution.  Compared with that, what you claim to be C++'s intended
meaning (inline even if the resulting code is worse) seems as a very
misguided idea.

-- 
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: std::pow implementation

[Gabriel Dos Reis]

Alexandre Oliva <aoliva@redhat.com> writes:

| On Jul 30, 2003, Gabriel Dos Reis <gdr@integrable-solutions.net> wrote:
| 
| > | Because (1) inline is implicit in C++,
| 
| > No, that is *your* invention.  Inline is NOT implicit.
| 
| For a member function defined inside the class body, it is.
| [dcl.fct.spec]/3  Sorry that I wasn't clear.

  A function defined within a class definition is an inline
  function. The inline specifier shall not appear on a block scope
  function declaration. 

only the *keyword* is implicit.  But then, that is a _deliberate_
decision. 

The *fact* is that when inline was originally introduced in C++, the
only way to declare a function to be inline is

  1) have it to be a member function
  2) define it within the class definition.

Again, quoting "The Design and Evolution of C++"

  In C with Classes, only member functions could be inlined and the
  only way to request a function to be inlined was to place its body
  within the class declaration.  For exemple:

   class stack {
       /* ... */
     char pop()
     { if (top <= min) error ("stack underflow");
        return *--top;
     }

  The fact that this made class declarations messier was observed at
  the time and seen as good thing in that it discourages overuse of
  inline functions.  The "inline" keyword and the ability to inline
  nonmember functions came with C++.  [...]


Please, do give inline its original and obvious meaning.

| > Only because you have decided to transmute the original meaning of C++.
| 
| I haven't chosen anything, I just quoted the C Standard.  It clearly
| calls for compiler's effort towards fast execution over inline
| substitution.  Compared with that, what you claim to be C++'s intended
| meaning (inline even if the resulting code is worse) seems as a very
| misguided idea.

It is a misguided idea for you only if you decide to ignore why inline.
I gave a quote of the purpose of inline in C++.  Let the programmer
make the choice.  Trust the programmer.

-- Gaby

Re: std::pow implementation

[Alexandre Oliva]

On Jul 30, 2003, Gabriel Dos Reis <gdr@integrable-solutions.net> wrote:

> I gave a quote of the purpose of inline in C++.

There is indeed one obvious use for inline, namely accessor
functions.  There are several other uses that are not that obvious, in
which the programmer can't possibly tell whether it's profitable to
inline the function at all locations where it is called, because
further optimizations enabled by inline substitution depend on the
arguments passed to the function.

Therefore, inline the way you describe it, is useful only for
functions that are *always* profitable to inline.  Any function that
might or might not be profitable to inline should not be declared
inline, and the compiler would never inline it.  This sounds silly to
me.  Why not let the user tell the compiler `hey, look, this function
is probably worth trying to inline', but letting the compiler decide
whether it's actually profitable or not, depending not only on the
context, but also on machine-dependent features?

You're arguing for a definition that was created 20 years ago, against
one that was come up with after at least 15 years of accumulation of
experience on the subject, just because you see one case in which that
old definition *might* suit some particular coding style better than
the new definition, even though, if the new definition is implemented
correctly, it can't possibly produce worse code?

-- 
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: std::pow implementation

[Gabriel Dos Reis]

Alexandre Oliva <aoliva@redhat.com> writes:

| On Jul 30, 2003, Gabriel Dos Reis <gdr@integrable-solutions.net> wrote:
| 
| > I gave a quote of the purpose of inline in C++.
| 
| There is indeed one obvious use for inline, namely accessor
| functions.  There are several other uses that are not that obvious, in
| which the programmer can't possibly tell whether it's profitable to

Defining a function inline is not a careless action.  If inlining
isn't profitable, the programmer will profile et remove the inline
definition.  You don't know better than the programmer.

[...]

| You're arguing for a definition that was created 20 years ago, against

I'm arguing for a definition that was created 20 yars ago, that still
describes contemporary situations, and more importantly that is part of
the language that was created more than 20 years ago and that is
subject of this discussion.

| one that was come up with after at least 15 years of accumulation of
| experience on the subject,

Yet, we're not at the level of sophistication that will make that
definition obsolete.  And the sade part of the history is that the
evidences that motivated the introduction of "inline" are still
contemporary. 

Please, don't transmute the meaning of "inline".

| just because you see one case in which that
| old definition *might* suit some particular coding style better than
| the new definition, even though, if the new definition is implemented
| correctly, it can't possibly produce worse code?

And the implementation of the "new definition" has always been for the
next version.  Whereas the old definition did and does what it is
designed for.  When you'll reach the state of maturity that makes your 
"new definition" always better than the "old definition", then at time
you may have legitimate reasons and evidences to make the
transmutation.  Not before.  Right now, the only things the "new
definition" offers is lock-in syntaxes.

Please do give "inline" its original meaning.

-- Gaby

Re: std::pow implementation

[Scott Robert Ladd]

Alexandre Oliva wrote:
> Therefore, inline the way you describe it, is useful only for 
> functions that are *always* profitable to inline.  Any function that 
> might or might not be profitable to inline should not be declared 
> inline, and the compiler would never inline it.  This sounds silly to
>  me.  Why not let the user tell the compiler `hey, look, this
> function is probably worth trying to inline', but letting the
> compiler decide whether it's actually profitable or not, depending
> not only on the context, but also on machine-dependent features?

IMNSHO, the keyword "inline" means precisely what it says: to inline the
code for a given function, if possible.

You are applying a different semantic concept to "inline" -- you want a
keyword that says "make this function as efficient as possible when
used". As such, it would be better to have a new keyword -- say
"optimize" -- that identifies a function important to performance,
explicitly handing decisions to the compiler.

"Inline", however, has a very precise and direct meaning, and it should
be fuddled with imprecise expectations.

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

Re: std::pow implementation

[Steven Bosscher]

Op wo 30-07-2003, om 17:28 schreef Scott Robert Ladd:
> Alexandre Oliva wrote:
> > Therefore, inline the way you describe it, is useful only for 
> > functions that are *always* profitable to inline.  Any function that 
> > might or might not be profitable to inline should not be declared 
> > inline, and the compiler would never inline it.  This sounds silly to
> >  me.  Why not let the user tell the compiler `hey, look, this
> > function is probably worth trying to inline', but letting the
> > compiler decide whether it's actually profitable or not, depending
> > not only on the context, but also on machine-dependent features?
> 
> IMNSHO, the keyword "inline" means precisely what it says: to inline the
> code for a given function, if possible.

Richard Guenther's experience with this meaning for "inline" are not
that positive: http://gcc.gnu.org/ml/gcc/2003-07/msg02140.html.
And then he's the guy who always wants more inlining :-p

Gr.
Steven

Re: std::pow implementation

[Richard Guenther]

On 30 Jul 2003, Steven Bosscher wrote:

> Op wo 30-07-2003, om 17:28 schreef Scott Robert Ladd:
> > Alexandre Oliva wrote:
> > > Therefore, inline the way you describe it, is useful only for
> > > functions that are *always* profitable to inline.  Any function that
> > > might or might not be profitable to inline should not be declared
> > > inline, and the compiler would never inline it.  This sounds silly to
> > >  me.  Why not let the user tell the compiler `hey, look, this
> > > function is probably worth trying to inline', but letting the
> > > compiler decide whether it's actually profitable or not, depending
> > > not only on the context, but also on machine-dependent features?
> >
> > IMNSHO, the keyword "inline" means precisely what it says: to inline the
> > code for a given function, if possible.
>
> Richard Guenther's experience with this meaning for "inline" are not
> that positive: http://gcc.gnu.org/ml/gcc/2003-07/msg02140.html.
> And then he's the guy who always wants more inlining :-p

Well - I always want more performance ;) And this can be achieved if
inlining the right functions at the right places... which translates also
to "the inline keyword as suggested by Gabriel doesnt fit my needs". The
suggested extra #pragmas or function attribute do, but of course a
"smarter" compiler doesnt hurt as well (though I doubt it will ever come
near the leafify attribute, at least not without profiling feedback).

Richard.

Re: std::pow implementation

[Gabriel Dos Reis]

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

| Op wo 30-07-2003, om 17:28 schreef Scott Robert Ladd:
| > Alexandre Oliva wrote:
| > > Therefore, inline the way you describe it, is useful only for 
| > > functions that are *always* profitable to inline.  Any function that 
| > > might or might not be profitable to inline should not be declared 
| > > inline, and the compiler would never inline it.  This sounds silly to
| > >  me.  Why not let the user tell the compiler `hey, look, this
| > > function is probably worth trying to inline', but letting the
| > > compiler decide whether it's actually profitable or not, depending
| > > not only on the context, but also on machine-dependent features?
| > 
| > IMNSHO, the keyword "inline" means precisely what it says: to inline the
| > code for a given function, if possible.
| 
| Richard Guenther's experience with this meaning for "inline" are not
| that positive: http://gcc.gnu.org/ml/gcc/2003-07/msg02140.html.

It is no surprise that inlinig with no proper constant propagation and
dead code elimination does not produce better code.

In effect, if you have a close look at the pattern of usage of C++,
you'll notice that after inlining, there are lots of opportunities for
the compiler to remove junks.  KCC understood that.

| And then he's the guy who always wants more inlining :-p

He does not want (rightly) "just" wants more inlining.

It helps just not to focuse on the medium, the message is more
important. 

-- Gaby

Re: std::pow implementation

[Steven Bosscher]

Op wo 30-07-2003, om 17:43 schreef Gabriel Dos Reis:
> Steven Bosscher <s.bosscher@student.tudelft.nl> writes:
> | Richard Guenther's experience with this meaning for "inline" are not
> | that positive: http://gcc.gnu.org/ml/gcc/2003-07/msg02140.html.
> 
> It is no surprise that inlinig with no proper constant propagation and
> dead code elimination does not produce better code.

Absolutely true.  See the example I posted yesterday from tree-ssa, you
can actually see it shrink from lots and lots of code to a trivial
function (and as a bonus it should also cut compile time because in
Richard's example, expand was a bottleneck, and we get rid of code
before expanding with tree-ssa)

But I think any properly optimizing compiler would be able to cut
functions down a lot after inlining.  The art is deciding what to inline
before you know how much of the inlined code will die after
optimizations.  That is what this discussion should be about...

> In effect, if you have a close look at the pattern of usage of C++,
> you'll notice that after inlining, there are lots of opportunities for
> the compiler to remove junks.  KCC understood that.

The question is, how did it know in advance what would turn into junk
and what would not.  That's the key.

> 
> | And then he's the guy who always wants more inlining :-p
> 
> He does not want (rightly) "just" wants more inlining.
> 
> It helps just not to focuse on the medium, the message is more
> important. 

Note the f*cking smiley.  I hope you'll develop a sense of humor some
day.

Gr.
Steven

Re: std::pow implementation

[Gabriel Dos Reis]

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

| > In effect, if you have a close look at the pattern of usage of C++,
| > you'll notice that after inlining, there are lots of opportunities for
| > the compiler to remove junks.  KCC understood that.
| 
| The question is, how did it know in advance what would turn into junk
| and what would not.  That's the key.

To some degree.  But above anything, they did honour "inline".  It is
harder to figure out without.

-- Gaby

Re: std::pow implementation

[Richard Guenther]

On 30 Jul 2003, Gabriel Dos Reis wrote:

> Steven Bosscher <s.bosscher@student.tudelft.nl> writes:
>
> | > IMNSHO, the keyword "inline" means precisely what it says: to inline the
> | > code for a given function, if possible.
> |
> | Richard Guenther's experience with this meaning for "inline" are not
> | that positive: http://gcc.gnu.org/ml/gcc/2003-07/msg02140.html.
>
> It is no surprise that inlinig with no proper constant propagation and
> dead code elimination does not produce better code.

I think this statement is way too harsh, as cprop and dce are quite good
with gcc - apart from some special cases such as your std::pow(T, int)
implementation (for which we need to blame the loop unroller, not cprop
or dce).

Richard.

Re: std::pow implementation

[Steven Bosscher]

Op wo 30-07-2003, om 17:52 schreef Richard Guenther:
> > It is no surprise that inlinig with no proper constant propagation and
> > dead code elimination does not produce better code.
> 
> I think this statement is way too harsh, as cprop and dce are quite good
> with gcc - apart from some special cases such as your std::pow(T, int)
> implementation (for which we need to blame the loop unroller, not cprop
> or dce).

True, but it happens too late for languages that build functions as
trees and inline trees.  One of the reasons why the inline limits have
been fairly low, was that expand would consume huge amounts of time, and
I've seen PRs for functions that blew up to as much as 1GB.

BTW Another reason was quadratic behavior in other parts of the compiler
(was it the scheduler???).

Gr.
Steven

Re: std::pow implementation

[Bernd Schmidt]

Whee.  I was wondering why my gcc inbox was getting so big.  Can I join
the party?

I realize I'm a bit late, but some of the arguments in this thread seem
so confused that I can't resist.

On Wed, 30 Jul 2003, Alexandre Oliva wrote:

> Therefore, inline the way you describe it, is useful only for
> functions that are *always* profitable to inline.  Any function that
> might or might not be profitable to inline should not be declared
> inline, and the compiler would never inline it.  This sounds silly to
> me.  Why not let the user tell the compiler `hey, look, this function
> is probably worth trying to inline', but letting the compiler decide
> whether it's actually profitable or not, depending not only on the
> context, but also on machine-dependent features?

We've had -finline-functions (aka -O3) for years; it does what you
suggest: let the compiler choose which functions to inline.  If we
assume that this option does a reasonable job, it can be used if you
want to write portable code and don't want to bother with performance
measurements and suchlike.

The question then becomes which effect the inline keyword should have?
I propose that it have the effect expected by most people who aren't
compiler hackers: let the function be inlined, if possible within
reasonable limits (*).  This is orthogonal to -finline-functions.
Otherwise, the inline keyword becomes meaningless and there is no
reason to use it - but people still want the functionality and must
resort to always_inline, which decreases portability.

Some people propose that inline should mean "I'd like this to go fast".
Do you propose that lack of inline means "I'd like this to go slow"?
This is a meaningless definition.  Either the compiler can make an
informed decision (possible in theory but not implemented in practice),
or it can't.  In the former case, inline is redundant.  In the latter
case, it is clearly better to trust the programmer (who is usually
an intelligent, sentient being) over the compiler (an unintelligent
entity using a bad algorithm).

Others come up with examples where the compiler could make a better
choice.  The fact of the matter is, it _doesn't_ make a better choice
today.  inline is unlike register; we do not have a good deciding
algorithm for it.  I cannot understand the attitude of "well, let
the compiler make a choice, it could have an algorithm that makes
reasonable choices" when noone has demonstrated the existence of such
an algorithm yet.  How about we make choices based on usefulness for
our users, rather than theoretical considerations?  We can't just
ignore the deficiencies of our current algorithms and handwave them
away with arguments of the "could" and "might" variety.


Let's take the example of a 2000 line function with a boolean argument.
If true, the function collapses to a one-liner, if false, it remains
a monster.  Proponents of inline-as-a-hint would have us believe that
we should let the compiler choose because it _could_, in theory, make
an informed decision.  In practice, the compiler's decision is random.

If you allow inline to direct the compiler to do what the user intends,
you can work around the problem by one or two wrapper functions (one
out-of-line one which inlines the monster, and another inline one
which passes true for the boolean and gets collapsed).  Such
techniques are common; I've used them myself, and I am very annoyed
that recent versions of gcc make a complete mess out of my code.


Let's take the other example of a 2000 line function that never collapses
to something short, but is marked inline.  We can assume inlining it
doesn't improve performance much.  It may even hurt.  This seems to be a
case of don't do that,  then.  If someone wants to write code this way,
let them - but don't take away my options just because a feature can be
misused.  Do you want the compiler to make "intelligent" decisiones
whether to transform an insertion sort you wrote into a quicksort?
Sometimes you want an insertion sort, and sometimes you want a function
to be always inlined.


Bernd

(*) Reasons why I'd accept inline not being honoured:
  - the function would become too big for the machine (or any other reason
    why the code wouldn't work)
  - recursive functions
  - alloca or some other feature that causes stack size explosions
    is used.  We should warn - this is a case for always_inline
    (Likewise for any dodgy GNU extensions I'm forgetting right now)
  - the compiler would explode due to lack of memory - we should make an
    effort this doesn't become a frequent reason
  - the programmer used -Os (and we can prove the code would get bigger)

Re: std::pow implementation

[Alexandre Oliva]

On Aug  4, 2003, Bernd Schmidt <bernds@redhat.com> wrote:

> We've had -finline-functions (aka -O3) for years; it does what you
> suggest: let the compiler choose which functions to inline.  If we
> assume that this option does a reasonable job, it can be used if you
> want to write portable code and don't want to bother with performance
> measurements and suchlike.

I'd promised I'd step away from the debate, but my argument is being
misunderstood, so I'll just clarify.  I'm not arguing for the compiler
to disregard inline entirely, in that, if you don't mark a function as
candidate for inlining, the compiler won't even consider the
possibility of inlining.  However, if you do, it will evaluate whether
it appears to make sense to inline it in order to improve performance,
or whether the inline marker was there just to make the body of the
function visible for the translation unit, in case inlining was found
to be profitable.  Unfortunately, the only way to make the body
visible without violating the ODR is by marking the function as
inline, either with the inline keyword or by defining it inside the
class body.

> I propose that it have the effect expected by most people who aren't
> compiler hackers: let the function be inlined, if possible within
> reasonable limits (*).

We agree here.  The trick is to define what reasonable limits are.
Not everybody agrees that it's reasonable to get compile time or
generated code size to explode even if the program would still work.

-- 
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: std::pow implementation

[Steven Bosscher]

Op wo 30-07-2003, om 08:38 schreef Gabriel Dos Reis:
> | > But, why don't you trust the programmer?  Why do you insist that you
> | > know better than the programmer?
> | 
> | Because (1) inline is implicit in C++,
> 
> No, that is *your* invention.  Inline is NOT implicit.  That is just
> an invention of people like you who prefer to ignore the purpose of
> "inline".  Please, do give inline its original and obvious meaning. 

Hmm I really don't follow you.  If "inline" is not implicit, would that
mean that for the (broken) example earlier in this thread:

class bla
{
public:
  foo() {i=1;}
private:
  int i;
}

a use of foo would _not_ be inlined because the user hasn't marked it
inline???

Gr.
Steven

Re: std::pow implementation

[Gabriel Dos Reis]

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

| Op wo 30-07-2003, om 08:38 schreef Gabriel Dos Reis:
| > | > But, why don't you trust the programmer?  Why do you insist that you
| > | > know better than the programmer?
| > | 
| > | Because (1) inline is implicit in C++,
| > 
| > No, that is *your* invention.  Inline is NOT implicit.  That is just
| > an invention of people like you who prefer to ignore the purpose of
| > "inline".  Please, do give inline its original and obvious meaning. 
| 
| Hmm I really don't follow you.  If "inline" is not implicit, would that
| mean that for the (broken) example earlier in this thread:
| 
| class bla
| {
| public:
|   foo() {i=1;}
| private:
|   int i;
| }
| 
| a use of foo would _not_ be inlined because the user hasn't marked it
| inline???

The point you're missing is that only the *keyword* is implicit.  Not
the fact that the function is *actually* declared inline.  In really,
when inline was originally introduced in C++, the above syntax was the
only one available.  See my answer to Alexandre who raised the same
syntactical issue.

There is more than syntax about it.

-- Gaby

Re: std::pow implementation

[Scott Robert Ladd]

Gabriel Dos Reis wrote:
> Let's the programmer decide.  It is *his* choice.  He has control do
> decide. 

I'm with Gabriel on this one. I've been doing C++ since it was "C with 
Classes," and it has always been clear to me that Stroustrup trusts the 
programmer over the compiler.

If you can't trust the programmer, the programmer shouldn't be writing 
code in C or (especially) C++.

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

Re: std::pow implementation

[Joe Buck]

On Wed, Jul 30, 2003 at 11:06:44AM -0400, Scott Robert Ladd wrote:
> Gabriel Dos Reis wrote:
> > Let's the programmer decide.  It is *his* choice.  He has control do
> > decide. 
> 
> I'm with Gabriel on this one. I've been doing C++ since it was "C with 
> Classes," and it has always been clear to me that Stroustrup trusts the 
> programmer over the compiler.

I agree, as a rule, that we should trust the programmer over the compiler
with regard to the "inline" keyword.

However, that doesn't get around the fact that we have an -O3 switch,
enabling a mode where the compiler has to make decisions to inline
additional functions.

In such cases, the compiler cannot ignore the effect of constant arguments
causing much of the code in a called function to disappear when the called
function is inlined.

Re: std::pow implementation

[Richard Guenther]

On Wed, 30 Jul 2003, Joe Buck wrote:

> However, that doesn't get around the fact that we have an -O3 switch,
> enabling a mode where the compiler has to make decisions to inline
> additional functions.
>
> In such cases, the compiler cannot ignore the effect of constant arguments
> causing much of the code in a called function to disappear when the called
> function is inlined.

We may be able to do this now with unit-at-a-time and callgraph by
duplicating the trees for function calls with constant arguments and
binding the constant arguments and doing the tree-optimizations on these
bodies before deciding inlining (and we may even just emit this new
function out of line if not inlined).

Richard.

Re: std::pow implementation

[Daniel Berlin]

On Wednesday, July 30, 2003, at 1:06 PM, Richard Guenther wrote:

> On Wed, 30 Jul 2003, Joe Buck wrote:
>
>> However, that doesn't get around the fact that we have an -O3 switch,
>> enabling a mode where the compiler has to make decisions to inline
>> additional functions.
>>
>> In such cases, the compiler cannot ignore the effect of constant 
>> arguments
>> causing much of the code in a called function to disappear when the 
>> called
>> function is inlined.
>
> We may be able to do this now with unit-at-a-time and callgraph by
> duplicating the trees for function calls with constant arguments and
> binding the constant arguments and doing the tree-optimizations on 
> these
> bodies before deciding inlining (and we may even just emit this new
> function out of line if not inlined).

Actually, the heuristic is usually something like:
If number of calls to function with constant arguments is estimated or 
actually high (IE function is on some critical performance path):
<clone and optimize>

Otherwise, you would waste so much time trying to determine what to 
clone, it's absurd.

>
> Richard.
>

Re: std::pow implementation

[Richard Guenther]

On Wed, 30 Jul 2003, Daniel Berlin wrote:

>
> On Wednesday, July 30, 2003, at 1:06 PM, Richard Guenther wrote:
>
> > On Wed, 30 Jul 2003, Joe Buck wrote:
> >
> >> However, that doesn't get around the fact that we have an -O3 switch,
> >> enabling a mode where the compiler has to make decisions to inline
> >> additional functions.
> >>
> >> In such cases, the compiler cannot ignore the effect of constant
> >> arguments
> >> causing much of the code in a called function to disappear when the
> >> called
> >> function is inlined.
> >
> > We may be able to do this now with unit-at-a-time and callgraph by
> > duplicating the trees for function calls with constant arguments and
> > binding the constant arguments and doing the tree-optimizations on
> > these
> > bodies before deciding inlining (and we may even just emit this new
> > function out of line if not inlined).
>
> Actually, the heuristic is usually something like:
> If number of calls to function with constant arguments is estimated or
> actually high (IE function is on some critical performance path):
> <clone and optimize>
>
> Otherwise, you would waste so much time trying to determine what to
> clone, it's absurd.

So this would be only practical with profiling feedback then?

Richard.

Re: std::pow implementation

[Daniel Berlin]

>>
>> Actually, the heuristic is usually something like:
>> If number of calls to function with constant arguments is estimated or
>> actually high (IE function is on some critical performance path):
>> <clone and optimize>
>>
>> Otherwise, you would waste so much time trying to determine what to
>> clone, it's absurd.
>
> So this would be only practical with profiling feedback then?

Or static profiling, to determine the number of calls and whatnot.

>
> Richard.
>

Re: std::pow implementation

[Joe Buck]

Alexandre Oliva wrote:
> | Consider a very complex function
> | that takes a boolean argument, used to enable or disable most of the
> | complexity in the function.  If the caller passes a false boolean
> | argument, the function would simplify to pretty much nothing.

On Wed, Jul 30, 2003 at 06:58:24AM +0200, Gabriel Dos Reis wrote:
> This is not a convincing example.

Ouch.  It is convincing to me!

> | Therefore claiming that the context of use shouldn't play any role in
> | deciding whether a function should be inlined is absurd.
> 
> No, what is absurb is the imaginary scenario you describ above.

Gaby, the scenario Alex describes is COMMON.  Constant propagation
frequently causes lots of code to be thrown away, and any automatic
inlining decision that doesn't take this effect into account is broken.

Re: std::pow implementation

[Gabriel Dos Reis]

Joe Buck <jbuck@synopsys.com> writes:

| Alexandre Oliva wrote:
| > | Consider a very complex function
| > | that takes a boolean argument, used to enable or disable most of the
| > | complexity in the function.  If the caller passes a false boolean
| > | argument, the function would simplify to pretty much nothing.
| 
| On Wed, Jul 30, 2003 at 06:58:24AM +0200, Gabriel Dos Reis wrote:
| > This is not a convincing example.
| 
| Ouch.  It is convincing to me!
| 
| > | Therefore claiming that the context of use shouldn't play any role in
| > | deciding whether a function should be inlined is absurd.
| > 
| > No, what is absurb is the imaginary scenario you describ above.
| 
| Gaby, the scenario Alex describes is COMMON.  Constant propagation
| frequently causes lots of code to be thrown away, and any automatic
| inlining decision that doesn't take this effect into account is broken.

I agree with your last sentence, but the context in which Alexandre
made his example does not make it a convincing one.  Which is what I
(attempted to) phrased above.

-- Gaby

Re: std::pow implementation

[Neil Booth]

Gabriel Dos Reis wrote:-

> don't obfuscate the library.

Heh, you're about 8 years late to that party.

Neil.

Re: std::pow implementation

[Gabriel Dos Reis]

Neil Booth <neil@daikokuya.co.uk> writes:

| Gabriel Dos Reis wrote:-
| 
| > don't obfuscate the library.
| 
| Heh, you're about 8 years late to that party.

Are excuses written by parents acceptable? ;-)

-- Gaby

Re: std::pow implementation

[Richard Guenther]

On 29 Jul 2003, Gabriel Dos Reis wrote:

> | Gabriel Dos Reis wrote:-
> |
> | > don't obfuscate the library.

I just checked what icc does to the loop in __cmath_power() and it is not
able to unroll it, too. I suspect this loop is already obfuscation of the
library to some degree then :)

But icc has the same problem with std::pow(T, int) due to similar
implementation. It does optimize ::pow(T, int) though, as we do.

Richard.

Re: std::pow implementation

[Gabriel Dos Reis]

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

| But icc has the same problem with std::pow(T, int) due to similar
| implementation. It does optimize ::pow(T, int) though, as we do.

Then we've got to do better optimization than icc :-)

-- Gaby