Re: std::pow implementation

Re: std::pow implementation

[Robert Dewar]

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

This is often incorrect, because often code is written to be portable, and
the decision on what is profitable to inline is target dependent. Furthermore
deciding whether something is profitable to inline on a given target requires
detailed knowledge of the target architecture, knowledge that very few 
programmers have these days.

Re: std::pow implementation

[Richard Guenther]

On Wed, 30 Jul 2003, Robert Dewar wrote:

> > 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.
>
> This is often incorrect, because often code is written to be portable, and
> the decision on what is profitable to inline is target dependent. Furthermore
> deciding whether something is profitable to inline on a given target requires
> detailed knowledge of the target architecture, knowledge that very few
> programmers have these days.

Also portability is not only about different targets, but also about
different compilers! Declaring something inline for one compiler doesnt
necessary have the same desired semantics for inline for another one.

Richard.

Re: std::pow implementation

[Gabriel Dos Reis]

dewar@gnat.com (Robert Dewar) writes:

| > 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.
| 
| This is often incorrect, because often code is written to be portable, and

In which ways are you seeing portability here -- apart from the lock-in
syntax __attribute__((__always_inline__))?

The meaning of "inline" here is for C++, not for all languages
supported by GCC.

Programming in C++, especially using its standard library or libraries
using STL-like style -- which happens more often than you might
imagine --  relies on inlining.

| the decision on what is profitable to inline is target dependent. Furthermore
| deciding whether something is profitable to inline on a given target requires
| detailed knowledge of the target architecture, knowledge that very few 
| programmers have these days.

But the fact is that the compiler is not doing better by going its own
programmed logic.  We've not reached the same level of sophistication
as for register allocation.

-- Gaby

Re: std::pow implementation

[Alexandre Oliva]

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

> But the fact is that the compiler is not doing better by going its own
> programmed logic.  We've not reached the same level of sophistication
> as for register allocation.

And your solution for the problem is to dumb it down further such that
it doesn't even attempt to do a good job?  Heck, it seems obvious to
me that the right solution is to improve the logic, not take it out
and assume the programmer knows better.  The developer of the function
that is a candidate for inlining can seldom foretell whether it's
going to be profitable to inline or not in each and every potential
uses of the function.  The cases in which the developer does have such
complete information are rare, and we should optimize for the common
case.

-- 
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:
| 
| > But the fact is that the compiler is not doing better by going its own
| > programmed logic.  We've not reached the same level of sophistication
| > as for register allocation.
| 
| And your solution for the problem is to dumb it down further such that
| it doesn't even attempt to do a good job?

I'm not proposing to dumb it further.  
In fact, people like you who make bogus quote of the standard to claim
that inline is implicit in C++ have already push the compiler to its
dumbest state.  Their transmuting of "inline" does not leave room for
going dumb further.

In effect, I'm proposing to return to first principles where the C++
programmer is trusted, is listened to, not treated by the software
as a dumb person unable to make sensible decisions.

When, the programmed logic of your inliner will reach the
sophisticated level comparable to that of automatic register
allocation, then you will have evidence to have your software not to
trust the programmer.   But, *now*, we're far from that level.
It is refusing acknowledgment of that simple fact that is driving the
compiler straight into wall.

-- 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 30, 2003, Gabriel Dos Reis <gdr@integrable-solutions.net> wrote:
> | 
> | > But the fact is that the compiler is not doing better by going its own
> | > programmed logic.  We've not reached the same level of sophistication
> | > as for register allocation.
> | 
> | And your solution for the problem is to dumb it down further such that
> | it doesn't even attempt to do a good job?

> I'm not proposing to dumb it further.  

Oh.  `The compiler should do what the user tells it to (WRT inline),
no more, no less.'  Can you explain to me what room is left for the
compiler to be intelligent (WRT inline) given this proposition?

> In fact, people like you who make bogus quote of the standard to claim
> that inline is implicit in C++ have already push the compiler to its
> dumbest state.

I'm tempted to respond with something along the lines of `people like
you who refuse to accept obvious arguments claiming they're
unconvincing...', but I'll get out of this discussion now, before it
turns into a fight.  I've already exposed my arguments, and so far
your arguments have only shown that you only care about a small part
of the big picture.

> In effect, I'm proposing to return to first principles where the C++
> programmer is trusted, is listened to, not treated by the software
> as a dumb person unable to make sensible decisions.

If you're not reasonable when presented with a simple argument just
because it goes against your theory, why should I expect you to be
reasonable when tagging functions as inline?  If you won't listen to
me, why should I listen to you?  Why do you insist on making claims
that `old is good' while all the evidence we have is that, when using
the inlining heuristics that you propose, namely, that the compiler
should inline any function declared inline (explicit or implicitly, or
whatever term you'd rather use to describe the fact that a member
function defined inside a class body is regarded as inline), compile
time *and* run time got significantly worse.

The fact that you are careful about marking functions as inline only
when you guess it will be profitable to inline them (and I'm assuming
you do), in the scenarios in which you're using the functions, won't
make it so for every C++ developer in the world, no matter how much
you whine.  People in different scenarios than yours, in which full
knowledge about the users of classes is available and their platforms,
won't be able to make as perfect a judgement WRT marking functions as
to-be-inlined as you are.  For people writing reusable software
components, this is just not possible: they can't predict how a
software component is going to be used.  Of course, if you keep on
convinced that the context of use of a function can't possibly affect
whether it's profitable to inline the function, then the only person
who will have learned anything form this debate is me, and it's that
you're blinded by prejudice and/or pride.

> When, the programmed logic of your inliner will reach the
> sophisticated level comparable to that of automatic register
> allocation, then you will have evidence to have your software not to
> trust the programmer.

Removing the logic we have in place that attempts to do a better job,
but fails, won't help us get closer to it.  If you have any concrete
suggestions to improve it, please post the patches.  If you don't, go
at least do some research and re-discover that taking your approach to
inlining has been tried with real-life C++ code, and results were
disastrous.  Could we do better?  Sure.  But it's not by wasting time
on this debate that we will get there.  We're just rehashing an
argument that we've had at least twice in the past.  Nothing new was
brought in, and all you brought was a set of prejudicial personal
convictions that burden programmers with decisions computers are
better suited to make for them, except in very special cases.  When
you have facts to present that would add to the discussion, I'll be
hear eager to listen to you.  Meanwhile, I'll stop feeding the flame
war.  The only thing it has produced is heat.

-- 
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 30, 2003, Gabriel Dos Reis <gdr@integrable-solutions.net> wrote:
| > | 
| > | > But the fact is that the compiler is not doing better by going its own
| > | > programmed logic.  We've not reached the same level of sophistication
| > | > as for register allocation.
| > | 
| > | And your solution for the problem is to dumb it down further such that
| > | it doesn't even attempt to do a good job?
| 
| > I'm not proposing to dumb it further.  
| 
| Oh.  `The compiler should do what the user tells it to (WRT inline),
| no more, no less.'  Can you explain to me what room is left for the
| compiler to be intelligent (WRT inline) given this proposition?

Because it is not mine?

| > In fact, people like you who make bogus quote of the standard to claim
| > that inline is implicit in C++ have already push the compiler to its
| > dumbest state.
| 
| I'm tempted to respond with something along the lines of `people like
| you who refuse to accept obvious arguments claiming they're
| unconvincing...',

The "obvious arguments" is claiming that inline is implicit in C++ with
bogus quote of the standard?

| but I'll get out of this discussion now, before it
| turns into a fight.  I've already exposed my arguments, and so far
| your arguments have only shown that you only care about a small part
| of the big picture.

No, I do not only care about a small part of the big picture, or else
I would adhere to your view.

| > In effect, I'm proposing to return to first principles where the C++
| > programmer is trusted, is listened to, not treated by the software
| > as a dumb person unable to make sensible decisions.
| 
| If you're not reasonable when presented with a simple argument just
| because it goes against your theory,

And being reasonable means adhereing to your view? 

-- Gaby

Re: std::pow implementation

[Gabriel Dos Reis]

Alexandre Oliva <aoliva@redhat.com> writes:

[...]

| because it goes against your theory, why should I expect you to be
| reasonable when tagging functions as inline?

Because it is not you who write my programs.

| If you won't listen to me, why should I listen to you?

Obviously, if you could you have already.

|  Why do you insist on making claims
| that `old is good' while all the evidence we have is that, when using

I'm not claiming "old is good" against all the evidence.  I'm claiming
the "new" is not mature enough to replace the "old".  That is not
speculation. Obviously, if the new were mature enough to replace the
"old", we would not have been having all this discussion.

-- Gaby

Re: std::pow implementation

[Robert Dewar]

> > pretty hard to do for the great majority of C++ (or Ada for that matter)
> > programmers who have not the slightest awareness of machine language or
> > its implications.
> 
> so since some programmers are imperfect,
> none of them should get nice sharp tools?  please, no!
> 
> C/C++, at least, have never shied from enough-rope features.
> 
> regards, mark hahn.

Well I am not sure it is a matter of rope here. The idea that all class
definitions in C++ should be regarded as potentially highly target
instruction set dependent since the programmer is expected to analyze
for a particular architecture what should and should not be inlined
seems a bit gruesome.

There are times when programming oblivious to the details of the target
architecture is exactly the right thing to do, and that should surely be
most of the time when using a language like C++ (otherwise why not write
in ASM to start with).

Re: std::pow implementation

[Robert Dewar]

> I did appeal to two sources: both the ISO standard and "The Design and
> Evolution of C++".  I included the ISO standard definition because it
> gives the wording on the current C++ definition and it is the result
> long elaboration on wordings that took many resources, just to make
> sure that thee substitution meaning is conveyed.  I did also appeal
> to the D&E because it does give references to the raison d'etre of
> inline in C++.  You might choose to ignore that C++ is an "evolved"
> language and ignore its history, but that is a not mistake I would
> like GCC to make.  C++ simply is not Ada.

The standard is a stand alone document, approved by ISO as such. It's meaning
if it has any meaning must be able to be deduced from its intrinsic content
like any other language standard. You cannot apply "history" to its
interpretation. This is just as true of Ada as of C++ (Ada has a long,
over 20 year, history too you know), and it is aqlso true that an Ada
compiler writer must be fully informed by this history.

For example, when we write

   type x (A : Natural) is record
      Y : String (1 .. A);
   end record;

in Ada, there is a difficult and significant question of how this is
implemented, and whether a given implementation will accept this particular
declaration. The Ada standard has absolutely nothing to say on this issue,
since it is one of implementation and code generation rather than semantics.

The Ada standard does have a useful innovation from a pragmatic point of view
in having sections called Implementation Advice, which are allowed to say
things that not strictly meaningful from a formal semantic point of view, but
which are useful pragmatically (of course these sections are not normative).

So referring to the ISO C++ standard is simply not relevant from a formal
point of view. Indeed the question on what code to generate should be
addressed from a pragmatic point of view, and of course this viewpoint must
include what C++ programmers expect historically (note that this is different
from what Gaby or any one person might believe about such expectations!)

Gaby's absolute position that any compiler that does not always inline 
everything is incorrect (presumably his intelligent C++ programmer would
expect inifinite compile time or a blowup in the case of a recursion???)
is to me highly contentious. I assume Gaby would also describe the (to me
very reasonable) strategy of the Intel compiler as incorrect.

I really think the only useful continuation of this discussoin is to have
some actual data, based on the absolutely-on-target suggestions made 
earlier this morning. 

I for one am signing off this thread till i see some data :-)

Re: std::pow implementation

[Gabriel Dos Reis]

dewar@gnat.com (Robert Dewar) writes:

| > I did appeal to two sources: both the ISO standard and "The Design and
| > Evolution of C++".  I included the ISO standard definition because it
| > gives the wording on the current C++ definition and it is the result
| > long elaboration on wordings that took many resources, just to make
| > sure that thee substitution meaning is conveyed.  I did also appeal
| > to the D&E because it does give references to the raison d'etre of
| > inline in C++.  You might choose to ignore that C++ is an "evolved"
| > language and ignore its history, but that is a not mistake I would
| > like GCC to make.  C++ simply is not Ada.
| 
| The standard is a stand alone document, approved by ISO as such. It's meaning
| if it has any meaning must be able to be deduced from its intrinsic content
| like any other language standard. You cannot apply "history" to its
| interpretation. 

I do not appeal to its history for interpretation.  I do appeal to its
story to make sure that people arguing for "inlining in general" do
have all the context in mind.  And no, the ISO standard does not
contain all the context of every feature.  If you don't know history,
you know nothing.

[...]

| The Ada standard does have a useful innovation from a pragmatic point of view

C++ is not Ada and Ada is C++. 

-- Gaby

Re: std::pow implementation

[Robert Dewar]

> It is an "as-if" rule only because that is the way it is described in
> standardese.   In the C++ community, we do care about history and
> documented behaviour.   You won't change that, just because you want
> C++ inline to have a less language specific meaning.

It's the only possibloe description in standardese here.

The point is that appealing to the ISO standard (as you did a few msgs ago)
is not particularly helpful, since the standard really has nothing to say.
This is a matter that must be decided, as with any code generation issue,
on the basis of what is pragnmatically best.

Re: std::pow implementation

[Gabriel Dos Reis]

dewar@gnat.com (Robert Dewar) writes:

| > It is an "as-if" rule only because that is the way it is described in
| > standardese.   In the C++ community, we do care about history and
| > documented behaviour.   You won't change that, just because you want
| > C++ inline to have a less language specific meaning.
| 
| It's the only possibloe description in standardese here.
| 
| The point is that appealing to the ISO standard (as you did a few msgs ago)
| is not particularly helpful, since the standard really has nothing to say.

I did appeal to two sources: both the ISO standard and "The Design and
Evolution of C++".  I included the ISO standard definition because it
gives the wording on the current C++ definition and it is the result
long elaboration on wordings that took many resources, just to make
sure that thee substitution meaning is conveyed.  I did also appeal
to the D&E because it does give references to the raison d'etre of
inline in C++.  You might choose to ignore that C++ is an "evolved"
language and ignore its history, but that is a not mistake I would
like GCC to make.  C++ simply is not Ada.

| This is a matter that must be decided, as with any code generation issue,
| on the basis of what is pragnmatically best.

This is matter of providing what has always been documented for two
decades. 

-- Gaby

Re: std::pow implementation

[Robert Dewar]

> I won't insist on the "as-if" rule: the longstanding promise in the GCC
> manual that "an inlined function is as fast as a macro" will do for me
> as a spec.  If you can achieve that without actually doing the inlining,
> go for it.

That's a problematic spec, it is not at all clear that you cam make
this guarantee. In our experience, you often get some junk from the
inlining process in gcc that is eliminated if you do macro expansion.

In fact we recently implemented front end inlining in GNAT (the -gnatN
switch) which gives something closer to C macro behavior, and we often
find that we get better code.

Re: std::pow implementation

[Robert Dewar]

> I do insist on the fact that it is not just an "as-if" rule.

You can insist all you like, but every rule in a standard of this kind
is an as-if rule. It would require a formal apparatus and set of definitions
far beyond what the C++ standard attempts for it to be otherwise.

The standard describes the meaning of a program in formal semantic terms
by giving a formal semantics to C++ programs. It does not specify what
code should be generated, only what that code must mean when it is executed.

Re: std::pow implementation

[Gabriel Dos Reis]

dewar@gnat.com (Robert Dewar) writes:

| > I do insist on the fact that it is not just an "as-if" rule.
| 
| You can insist all you like, but every rule in a standard of this kind
| is an as-if rule.

It is an "as-if" rule only because that is the way it is described in
standardese.   In the C++ community, we do care about history and
documented behaviour.   You won't change that, just because you want
C++ inline to have a less language specific meaning.

-- Gaby

Re: std::pow implementation

[Robert Dewar]

> Defining a member function within a class declaration has exactly the
> same meaning.  And that has been documented in every manual since 1981.

Yes, we all agree that the as-if standard meaning is the same, that is
never in dispute. A compiler that ignores all inlining is perfectly
well in conformance, and that might make sense on a machine which favors
this approach, e.g. the transputer where a call is much faster than a jump.

Re: std::pow implementation

[Gabriel Dos Reis]

dewar@gnat.com (Robert Dewar) writes:

| > Defining a member function within a class declaration has exactly the
| > same meaning.  And that has been documented in every manual since 1981.
| 
| Yes, we all agree that the as-if standard meaning is the same, that is
| never in dispute.

I do insist on the fact that it is not just an "as-if" rule.

-- Gaby

Re: std::pow implementation

[Joe Buck]

On Mon, Aug 04, 2003 at 07:51:55PM +0200, Gabriel Dos Reis wrote:
> dewar@gnat.com (Robert Dewar) writes:
> 
> | > Defining a member function within a class declaration has exactly the
> | > same meaning.  And that has been documented in every manual since 1981.
> | 
> | Yes, we all agree that the as-if standard meaning is the same, that is
> | never in dispute.
> 
> I do insist on the fact that it is not just an "as-if" rule.

I won't insist on the "as-if" rule: the longstanding promise in the GCC
manual that "an inlined function is as fast as a macro" will do for me
as a spec.  If you can achieve that without actually doing the inlining,
go for it.

Re: std::pow implementation

[Robert Dewar]

> You should not underestimate C++ programmers ability to make considerations.

I think you make the mistake of overestimating!

Re: std::pow implementation

[Gabriel Dos Reis]

dewar@gnat.com (Robert Dewar) writes:

| > You should not underestimate C++ programmers ability to make considerations.
| 
| I think you make the mistake of overestimating!

No, I don't.  I provide documented behaviour.  The C++ programmer is
an intelligent person.

-- Gaby

Re: std::pow implementation

[Robert Dewar]

> Sigh.  In C++, the programmer has already done the needed analysis, and
> has attached the keyword "inline" or defined the function in the class
> body.  Certainly, with -O3 the kind of analysis you describe would be
> appropriate, though possibly expensive.


This claim is made repeatedly, but without any evidence. I think a lot of
C++ programmers decide whether to put thins in the class body on the basis
of other considerations than whether to inline -- a consideration that is
pretty hard to do for the great majority of C++ (or Ada for that matter)
programmers who have not the slightest awareness of machine language or
its implications.

I do agree that if the programmer has attached the keyword "inline" then
that shows at least some thought, though whether it is well informed or
not can often be an issue.

Re: std::pow implementation

[Joe Buck]

On Mon, Aug 04, 2003 at 01:26:40PM -0400, Robert Dewar wrote:
> > Sigh.  In C++, the programmer has already done the needed analysis, and
> > has attached the keyword "inline" or defined the function in the class
> > body.  Certainly, with -O3 the kind of analysis you describe would be
> > appropriate, though possibly expensive.
> 
> 
> This claim is made repeatedly, but without any evidence.

OK, so let's gather some evidence now.

Re: std::pow implementation

[Gabriel Dos Reis]

dewar@gnat.com (Robert Dewar) writes:

| > Sigh.  In C++, the programmer has already done the needed analysis, and
| > has attached the keyword "inline" or defined the function in the class
| > body.  Certainly, with -O3 the kind of analysis you describe would be
| > appropriate, though possibly expensive.
| 
| 
| This claim is made repeatedly, but without any evidence. I think a lot of
| C++ programmers decide whether to put thins in the class body on the basis
| of other considerations than whether to inline -- a consideration that is
| pretty hard to do for the great majority of C++ (or Ada for that matter)
| programmers who have not the slightest awareness of machine language or
| its implications.

You should not underestimate C++ programmers ability to make considerations.

| I do agree that if the programmer has attached the keyword "inline" then
| that shows at least some thought, though whether it is well informed or
| not can often be an issue.

Defining a member function within a class declaration has exactly the
same meaning.  And that has been documented in every manual since 1981.

-- Gaby

Re: std::pow implementation

[Mark Hahn]

> pretty hard to do for the great majority of C++ (or Ada for that matter)
> programmers who have not the slightest awareness of machine language or
> its implications.

so since some programmers are imperfect,
none of them should get nice sharp tools?  please, no!

C/C++, at least, have never shied from enough-rope features.

regards, mark hahn.

Re: std::pow implementation

[tm_gccmail]

On Mon, 4 Aug 2003, Mark Hahn wrote:

> > pretty hard to do for the great majority of C++ (or Ada for that matter)
> > programmers who have not the slightest awareness of machine language or
> > its implications.
> 
> so since some programmers are imperfect,
> none of them should get nice sharp tools?  please, no!
> 
> C/C++, at least, have never shied from enough-rope features.
> 
> regards, mark hahn.
> 
> 

Re: std::pow implementation

[Robert Dewar]

> (*) 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)


I would add

- doing the inlining as requested increases both the space and execution time
of the program, the former very substantially.

Of course, the question is

1. Does this happen often in practice (certainly as I Have noted before we
often see that -O3 slows things down compared to -O2: speed = space in the
land of icaches).

2. Can the compiler really usefully tell this is the case, or does it make
so many mistakes trying to be helpful in this way that it actually hurts.

With regard to the "collapsing code" issue, clearly the best strategy is
to do parameter substitution and collapse the code *before* deciding whether
to inline it. Of course this is not so easy to do.

Re: std::pow implementation

[Joe Buck]

> > (*) Reasons why I'd accept inline not being honoured:

On Mon, Aug 04, 2003 at 12:53:09PM -0400, Robert Dewar wrote:
> I would add
> 
> - doing the inlining as requested increases both the space and execution time
> of the program, the former very substantially.

Nope.  It is appropriate for the compiler to do what the user said.  In
C++, inline functions are for the most part so tiny that the inlined
function takes up less space than the call.  Having the compiler compute
metrics for all these functions in an effort to second-guess the
programmer only slows the compiler down.

If the user asks for very large functions to be inlined, the user loses.
But the good news is that the fix is easy.

> Of course, the question is
> 
> 1. Does this happen often in practice (certainly as I Have noted before we
> often see that -O3 slows things down compared to -O2: speed = space in the
> land of icaches).

-O3 is irrelevant: with -O3, we ask the compiler to find additional
functions to inline.  The slowdown with -O3 shows that the compiler is
not doing a good job making its own choices.

> 2. Can the compiler really usefully tell this is the case, or does it make
> so many mistakes trying to be helpful in this way that it actually hurts.

See above.

> With regard to the "collapsing code" issue, clearly the best strategy is
> to do parameter substitution and collapse the code *before* deciding whether
> to inline it. Of course this is not so easy to do.

Sigh.  In C++, the programmer has already done the needed analysis, and
has attached the keyword "inline" or defined the function in the class
body.  Certainly, with -O3 the kind of analysis you describe would be
appropriate, though possibly expensive.

Re: std::pow implementation

[Richard Earnshaw]

> > > (*) Reasons why I'd accept inline not being honoured:
> 
> On Mon, Aug 04, 2003 at 12:53:09PM -0400, Robert Dewar wrote:
> > I would add
> > 
> > - doing the inlining as requested increases both the space and execution time
> > of the program, the former very substantially.
> 
> Nope.  It is appropriate for the compiler to do what the user said.  In
> C++, inline functions are for the most part so tiny that the inlined
> function takes up less space than the call.  Having the compiler compute
> metrics for all these functions in an effort to second-guess the
> programmer only slows the compiler down.

Not necessarily.  The benefit might be more than repaid in terms of less 
time spent in CSE if the function turned out to be large.

> If the user asks for very large functions to be inlined, the user loses.
> But the good news is that the fix is easy.

Think portability.  Having to change the code every time you compile on a 
different platform breaks the whole concept of using high-level languages 
to get away from the machine abstraction.

The issue here isn't what to do with really tiny functions, or even what 
to to with really enormous ones: it's entirely to do with the boundary 
between the two -- how does the compiler decide that it has crossed from 
one to the other?  A smart compiler can work that out based on its 
knowledge of the machine.  A dumb one can't.  Do we want gcc to be smart 
or dumb?

R.

Re: std::pow implementation

[Gabriel Dos Reis]

Richard Earnshaw <rearnsha@arm.com> writes:

[...]

| The issue here isn't what to do with really tiny functions, or even what 
| to to with really enormous ones: it's entirely to do with the boundary 
| between the two -- how does the compiler decide that it has crossed from 
| one to the other?  A smart compiler can work that out based on its 
| knowledge of the machine.  A dumb one can't.  Do we want gcc to be smart 
| or dumb?

The question is really, do we want GCC be usable now or maby usable
only in two decades or so?

I'm all for research.  But I would like GCC be usable now, given
simple implementations on traditional systems. 

-- Gaby

Re: std::pow implementation

[Bernd Schmidt]

On Mon, 4 Aug 2003, Richard Earnshaw wrote:

> The issue here isn't what to do with really tiny functions, or even what
> to to with really enormous ones: it's entirely to do with the boundary
> between the two -- how does the compiler decide that it has crossed from
> one to the other?  A smart compiler can work that out based on its
> knowledge of the machine.  A dumb one can't.  Do we want gcc to be smart
> or dumb?

It's not about we want.  Wishful thinking doesn't help.  It's about two
facts:
 a) gcc is currently dumb
 b) the inline keyword has only one reasonable meaning, regardless of
    whether the compiler is smart or dumb.

To repeat the argument:
If we have a dumb compiler, the choices it makes are effectively random.
The programmer can get a big improvement by using inline carefully, iff
the compiler honours it.  If it makes another random choice, the keyword
is effectively useless.
If we have a smart compiler, we can rely on it making good choices in
almost every case.  We don't generally need to use inline, but there may
be cases where a human could demonstrate that it can improve code, iff
the compiler honours it.

The only imaginable alternative, for a really smart compiler, is to treat
the inline keyword as having no meaning at all, like register.  So far, no
one has demonstrated the existence of a sufficiently smart algorithm.


Bernd

Re: std::pow implementation

[Richard Guenther]

On Mon, 4 Aug 2003, Bernd Schmidt wrote:

> On Mon, 4 Aug 2003, Richard Earnshaw wrote:
>
> > The issue here isn't what to do with really tiny functions, or even what
> > to to with really enormous ones: it's entirely to do with the boundary
> > between the two -- how does the compiler decide that it has crossed from
> > one to the other?  A smart compiler can work that out based on its
> > knowledge of the machine.  A dumb one can't.  Do we want gcc to be smart
> > or dumb?
>
> It's not about we want.  Wishful thinking doesn't help.  It's about two
> facts:
>  a) gcc is currently dumb

GCC 3.3 and older (with tree-inlining) are dumb. GCC 3.4 is much smarter
and will usually come very close to Gaby's requirements (in result, not in
specification, of course).

Try some experiments, folks.

Or do some simple patches, like making the inlining limits default values
frontend dependend.

Richard.

Re: std::pow implementation

[Robert Dewar]

> Please do be careful about the fact that I'm not proposing that g++
> should not inline a function not marked inline.

your sentences have impossibly many negatives. I can't even make an
attempt to understand what a sentence like the above means or is
meant to mean.

Re: std::pow implementation

[Gabriel Dos Reis]

dewar@gnat.com (Robert Dewar) writes:

| > Please do be careful about the fact that I'm not proposing that g++
| > should not inline a function not marked inline.
| 
| your sentences have impossibly many negatives. I can't even make an
| attempt to understand what a sentence like the above means or is
| meant to mean.

Fair enough.

-- Gaby

Re: std::pow implementation

[Robert Dewar]

> Martin is right that there is a lack of being able to express what one
> means. And which this lack you cannot be sure if the programmer with
> "inline" meant inline or maybe inline. You cannot even be sure if he meant
> do not inline if he omitted inline. It doesnt help that _you_ mean inline
> if you write it.

Note that in GNAT we have added pragma Inline_Always which says you absolutely
must inline, and it is an error if you cannot do so. pragma Inline means
that it is desirable to inline if it makes sense and is technically possible,
and not saying anything leaves the compiler free to inline if it thinks this
is a good idea (with most Ada code, this does not help much).

Re: std::pow implementation

[Richard Guenther]

 Martin Reinecke <martin@mpa-garching.mpg.de> writes:

 | Gabriel Dos Reis wrote:
 |
 | > 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".
 |
 | Yes, you should listen to the programmer. But unless the programmer
 | has a chance to express his intent _exactly_, there is no way to find
 | out what he really meant. And he cannot do so in the discussed situation.

  How to be sure there would not be another quibble about whether he
  really wanted to express exactly his intent?  something like

     [P] inline
     [C] do you inline mean inline?
     [P] Yes
     [C] Are you sure you really mean inline?
     [P] Yes
     [C] Did you mean the last answer?
     [P] ...

Ah, come on, stop whining and making this list look like a Kindergarten.

  That way lies infinite recursion with no way of getting started,
  i.e. no productive work.  We don't need complication to get decent
  results.  KCC didn't need a hierarchy of intent of inline before
  producing much better code.  When we will reach the level where the
  compiler trusts the programmer, we could start worrying about what is
  next.  Like they say here, Paris is built in one day.
  First, start trusting the programmer; when you're good at that job, you
  would be able to handle subtile  distinctions.

Martin is right that there is a lack of being able to express what one
means. And which this lack you cannot be sure if the programmer with
"inline" meant inline or maybe inline. You cannot even be sure if he meant
do not inline if he omitted inline. It doesnt help that _you_ mean inline
if you write it.

So face it - gcc _has_ to map both "inline" and not "inline" to
maybe-inline. There are (non portable) ways to specify do not inline
(attribute noinline) and do always inline (attribute always_inline).
The way out of this discussion is to make gcc's heuristics better, not to
force it into any static notion about "inline" or not "inline".

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:

|  Martin Reinecke <martin@mpa-garching.mpg.de> writes:
| 
|  | Gabriel Dos Reis wrote:
|  |
|  | > 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".
|  |
|  | Yes, you should listen to the programmer. But unless the programmer
|  | has a chance to express his intent _exactly_, there is no way to find
|  | out what he really meant. And he cannot do so in the discussed situation.
| 
|   How to be sure there would not be another quibble about whether he
|   really wanted to express exactly his intent?  something like
| 
|      [P] inline
|      [C] do you inline mean inline?
|      [P] Yes
|      [C] Are you sure you really mean inline?
|      [P] Yes
|      [C] Did you mean the last answer?
|      [P] ...
| 
| Ah, come on, stop whining and making this list look like a Kindergarten.

because it is :-)

|   That way lies infinite recursion with no way of getting started,
|   i.e. no productive work.  We don't need complication to get decent
|   results.  KCC didn't need a hierarchy of intent of inline before
|   producing much better code.  When we will reach the level where the
|   compiler trusts the programmer, we could start worrying about what is
|   next.  Like they say here, Paris is built in one day.
|   First, start trusting the programmer; when you're good at that job, you
|   would be able to handle subtile  distinctions.
| 
| Martin is right that there is a lack of being able to express what one
| means.

I'm not saying he is wrong.  I'm saying, let's tackle that tower latter
when we know how to build a two floor house, because getting two-floor
house good now is a more urgent issue than building a babel tomorrow.

| And which this lack you cannot be sure if the programmer with
| "inline" meant inline or maybe inline. 

And you won't be sure either that the three stage is sufficient for the
programmer.  We're not at the stage of designing a language from scratch.

| You cannot even be sure if he meant
| do not inline if he omitted inline. It doesnt help that _you_ mean inline
| if you write it.
| 
| So face it - gcc _has_ to map both "inline" and not "inline" to
| maybe-inline. There are (non portable) ways to specify do not inline
| (attribute noinline) and do always inline (attribute always_inline).
| The way out of this discussion is to make gcc's heuristics better, not to
| force it into any static notion about "inline" or not "inline".

Please do be careful about the fact that I'm not proposing that g++
should not inline a function not marked inline.

-- Gaby

RE: std::pow implementation

[Rob Taylor]

I've been following this thread, and i'm strating to get confused about
exactly who's arguing for what!!

as is read it, there seem to be 3 positions:

1) every function has to be maybe-inlinable for good optimisation, so we
should ignore the inline keyword

2)  every function has to be maybe-inlinable for good optimisation, but the
inline keyword gives good hinting and should be used.

3) every function has to be maybe-inlinable for good optimisation, but those
declared inline should have a non-contextual rule for inlining, as opposed
to a contextual analysis approach for those not declared inline. <not sure
of my analysis here>

Is this correct? and who's in which court? what have i missed out?

Thanks,

Rob Taylor



> -----Original Message-----
> From: gcc-owner@gcc.gnu.org [mailto:gcc-owner@gcc.gnu.org]On Behalf Of
> Richard Guenther
> Sent: 31 July 2003 11:02
> To: Gabriel Dos Reis
> Cc: Martin Reinecke; gcc@gcc.gnu.org
> Subject: Re: std::pow implementation
>
>
>  Martin Reinecke <martin@mpa-garching.mpg.de> writes:
>
>  | Gabriel Dos Reis wrote:
>  |
>  | > 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".
>  |
>  | Yes, you should listen to the programmer. But unless the programmer
>  | has a chance to express his intent _exactly_, there is no way to find
>  | out what he really meant. And he cannot do so in the discussed
> situation.
>
>   How to be sure there would not be another quibble about whether he
>   really wanted to express exactly his intent?  something like
>
>      [P] inline
>      [C] do you inline mean inline?
>      [P] Yes
>      [C] Are you sure you really mean inline?
>      [P] Yes
>      [C] Did you mean the last answer?
>      [P] ...
>
> Ah, come on, stop whining and making this list look like a Kindergarten.
>
>   That way lies infinite recursion with no way of getting started,
>   i.e. no productive work.  We don't need complication to get decent
>   results.  KCC didn't need a hierarchy of intent of inline before
>   producing much better code.  When we will reach the level where the
>   compiler trusts the programmer, we could start worrying about what is
>   next.  Like they say here, Paris is built in one day.
>   First, start trusting the programmer; when you're good at that job, you
>   would be able to handle subtile  distinctions.
>
> Martin is right that there is a lack of being able to express what one
> means. And which this lack you cannot be sure if the programmer with
> "inline" meant inline or maybe inline. You cannot even be sure if he meant
> do not inline if he omitted inline. It doesnt help that _you_ mean inline
> if you write it.
>
> So face it - gcc _has_ to map both "inline" and not "inline" to
> maybe-inline. There are (non portable) ways to specify do not inline
> (attribute noinline) and do always inline (attribute always_inline).
> The way out of this discussion is to make gcc's heuristics better, not to
> force it into any static notion about "inline" or not "inline".
>
> Richard.
>
> --
> Richard Guenther <richard dot guenther at uni-tuebingen dot de>
> WWW: http://www.tat.physik.uni-tuebingen.de/~rguenth/
>

Re: std::pow implementation

[Scott Robert Ladd]

Rob Taylor wrote:
> 2)  every function has to be maybe-inlinable for good optimisation, but the
> inline keyword gives good hinting and should be used.

That's close to my position on the matter.

1) The compiler should be able to determine which functions it can 
effectively inline for a given circumstance.

2) The compiler should respect "inline" directives from the programmer, 
generating inline code when it is specified, unless doing so is 
technically impossible or blatantly inefficient.

3) If the compiler rejects an "inline" request, it should clearly state 
why it did so. After all, if the compiler is smart enough to 
second-guess me, it should also be able to explain itself. ;)

Such an approach gives the compiler maximum flexibility while respecting 
the choices of the programmer.

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

Re: std::pow implementation

[Gabriel Dos Reis]

Scott Robert Ladd <coyote@coyotegulch.com> writes:

| Rob Taylor wrote:
| > 2)  every function has to be maybe-inlinable for good optimisation, but the
| > inline keyword gives good hinting and should be used.
| 
| That's close to my position on the matter.
| 
| 1) The compiler should be able to determine which functions it can
| effectively inline for a given circumstance.
| 
| 2) The compiler should respect "inline" directives from the
| programmer, generating inline code when it is specified, unless doing
| so is technically impossible or blatantly inefficient.
| 
| 3) If the compiler rejects an "inline" request, it should clearly
| state why it did so. After all, if the compiler is smart enough to
| second-guess me, it should also be able to explain itself. ;)
| 
| Such an approach gives the compiler maximum flexibility while
| respecting the choices of the programmer.

that is close to

   A function declaration (8.3.5, 9.3, 11.4) with an inline
   specifier declares an inline function. The inline specifier
   indicates to the implementation that *inline substitution* of the
   function body at the point of call *is to be preferred* to the usual
   function call mechanism. An implementation is not required to
   perform this inline substitution at the point of call; 

-- Gaby

Re: std::pow implementation

[Steven Bosscher]

Op do 31-07-2003, om 15:11 schreef Scott Robert Ladd:
> 2) The compiler should respect "inline" directives from the programmer, 
> generating inline code when it is specified, unless doing so is 
> technically impossible or blatantly inefficient.

I thought that the whole point in this discussion is that some people
argue that the compiler cannot know when inlining an `inline' declared
function is blatantly inefficient.

Gr.
Steven

Re: std::pow implementation

[Scott Robert Ladd]

Steven Bosscher wrote:
>>2) The compiler should respect "inline" directives from the programmer, 
>>generating inline code when it is specified, unless doing so is 
>>technically impossible or blatantly inefficient.
> 
> I thought that the whole point in this discussion is that some people
> argue that the compiler cannot know when inlining an `inline' declared
> function is blatantly inefficient.

A decent compiler should be able to recognize patterns (e.g., big 
functions that can't be reduced) that render inlining inefficient.  And 
rejecting silly (i.e., undefined) requests, such as inlining "main", is 
to be expected.

In an ideal universe, explicit "inline" shouldn't be required (or even 
desirable.) Alas, current compiler technology is far from that ideal, 
and so responsibility for intelligent choices should fall to the 
programmer, not the compiler.

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

Re: std::pow implementation

[Martin Reinecke]

Gabriel Dos Reis wrote:

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

Yes, you should listen to the programmer. But unless the programmer
has a chance to express his intent _exactly_, there is no way to find
out what he really meant. And he cannot do so in the discussed situation.

When writing a member function, the programmer has to adress the question
"Should this function be inlined?", and you agreed that there are three
valid answers: "yes", "no", and "it depends; let the compiler decide".

But current g++ only allows two ansers:
  "yes" (i.e. make the function inline), and
  "no"  (i.e. define the function in some .cc file)

If the programmer can only choose two of three alternatives, it is not
possible to determine whether he didn't actually want to say "it depends".
If he says "no", he most certainly means "no", because then g++ has not much
chance of inlining the function if it's not defined in the current translation
unit.
But if he says "yes", how can you be sure he really meant "yes" and not
"it depends"? The language practically forces him to lie, and therefore
you can't trust him blindly.

My opinion is that if the programmer says "yes", the only thing you can be sure
about is that he didn't mean "no", but that's not enough to determine whether
g++ should unconditionally inline or not.

Of course, this argument breaks down if there is some way to say "it depends".
I don't know of any. If there is, please show me!

Martin

Re: std::pow implementation

[Gabriel Dos Reis]

Martin Reinecke <martin@mpa-garching.mpg.de> writes:

| Gabriel Dos Reis wrote:
| 
| > 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".
| 
| Yes, you should listen to the programmer. But unless the programmer
| has a chance to express his intent _exactly_, there is no way to find
| out what he really meant. And he cannot do so in the discussed situation.

How to be sure there would not be another quibble about whether he
really wanted to express exactly his intent?  something like

   [P] inline
   [C] do you inline mean inline?
   [P] Yes
   [C] Are you sure you really mean inline?
   [P] Yes
   [C] Did you mean the last answer?
   [P] ...

That way lies infinite recursion with no way of getting started,
i.e. no productive work.  We don't need complication to get decent
results.  KCC didn't need a hierarchy of intent of inline before
producing much better code.  When we will reach the level where the
compiler trusts the programmer, we could start worrying about what is
next.  Like they say here, Paris is built in one day.  
First, start trusting the programmer; when you're good at that job, you
would be able to handle subtile  distinctions.

-- Gaby

Re: std::pow implementation

[Robert Dewar]

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

That would be very hard for a standard to say, given that standards describe
as-if semantics and are not in the business of telling you what sequences
of instructions may or may not be used to implement these semantics.

Re: std::pow implementation

[Robert Dewar]

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


Note thjat this is even more the case in Ada, where the normal way of doing
conditional compilation is by the use of constant booleans (there is no
macro preprocessing defined in Ada).

Re: std::pow implementation

[Robert Dewar]

> | In fact, the liberal use of inline tends to *prevent* premature optimization
> 
> That might be true for Ada, I'm doubteful it translates to C++ word-for-word.


I really don't see a difference, other than that Ada programmers have been
used to using inline liberally for twenty years :-)

Re: std::pow implementation

[Robert Dewar]

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

I strongly disagree with this. Profiling is simply not an effective way of
identifying functions that benefit from inlining. Profiling is a very crude
tool that is helpful in eliminating hot spots but that's all.

The reason for not taking this view of inlining is that unless you get in the
mindset that inlining will be done routinely by the compiler (at your direction)
then you will tend to shy away from the use of trivial abstraction functions
because you will worry about efficiency.

The quote about premature optimization here is wrong I think. What Knuth
was talking about (go back and look at what he really said, not just the
sound bite) was distorting the code prematurely and unnecessarily in the
interests of optimization.

In fact, the liberal use of inline tends to *prevent* premature optimization
(of the kind I mentioned above, avoidance of abstraction), and certainly does
not distort the code.

Re: std::pow implementation

[Gabriel Dos Reis]

dewar@gnat.com (Robert Dewar) writes:

| The reason for not taking this view of inlining is that unless you
| get in the mindset that inlining will be done routinely by the
| compiler (at your direction) then you will tend to shy away from the
| use of trivial abstraction functions because you will worry about efficiency.

In effect, I find that it is the view that the C++ compiler always knows
better than the programmer that creates that sort of situation.
Should I use this compiler?  No! It does not listen to the
programmer.  Fear.
Will the compiler inline this simple function? I'm not sure, it just
keeps on doing what he thinks is best for me.  Uncertainty.
Should I program in C++ and use this compiler? Maybe not, some C++
compilers are notorously known not to inline inline function.  Doubt.

| The quote about premature optimization here is wrong I think. What Knuth
| was talking about (go back and look at what he really said, not just the
| sound bite) was distorting the code prematurely and unnecessarily in the
| interests of optimization.
| 

| In fact, the liberal use of inline tends to *prevent* premature optimization

That might be true for Ada, I'm doubteful it translates to C++ word-for-word.

-- Gaby

Re: std::pow implementation

[Scott Robert Ladd]

Robert Dewar wrote:
>>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.

> I strongly disagree with this. Profiling is simply not an effective way of
> identifying functions that benefit from inlining. Profiling is a very crude
> tool that is helpful in eliminating hot spots but that's all.

The value of profiling depends on its sophistication. There are many 
ways to instrument a program...

> The reason for not taking this view of inlining is that unless you get in the
> mindset that inlining will be done routinely by the compiler (at your direction)
> then you will tend to shy away from the use of trivial abstraction functions
> because you will worry about efficiency.

Note that I said "in all but the most obvious and trivial cases (e.g. 
assignment)"; in other words, a good programmer will inline "trivial 
abstraction functions" because they know that such provide conceptual 
value without an efficiency hit.

> The quote about premature optimization here is wrong I think. What Knuth
> was talking about (go back and look at what he really said, not just the
> sound bite) was distorting the code prematurely and unnecessarily in the
> interests of optimization.

Using "inline" willy-nilly is distorting code, in my opinion. You are 
telling the compiler to do something without evidence of inlining's 
efficacy.

> In fact, the liberal use of inline tends to *prevent* premature optimization
> (of the kind I mentioned above, avoidance of abstraction), and certainly does
> not distort the code.

I think we actually agree here! :) I'm strongly against anyone using 
"inline" unless they have a reason for doing so; indeed, indescriminate 
inlining is a Bad Thing. A good programmer isn't going apply inline 
without good reason, and the compiler shouldn't silently veto those 
decisions.

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

Re: std::pow implementation

[Felix Lee]

dewar@gnat.com (Robert Dewar):
> The reason for not taking this view of inlining is that unless
> you get in the mindset that inlining will be done routinely by
> the compiler (at your direction) then you will tend to shy away
> from the use of trivial abstraction functions because you will
> worry about efficiency.

Ah, then the problem is not premature optimization, it's
premature worrying about efficiency. :)

Seriously, I find I have to struggle against my own programming
habits that were acquired years ago.  There's a cycle
in programming:
   1. write "natural" code
   2. check the program's performance
   3. modify the code to increase performance

Since this is rather time-consuming, an efficient programmer
learns what techniques found in step 3 are often a good idea, and
starts using them naturally in step 1.

I'm discovering that this cycle of learning is itself a premature
optimization, mainly because of Moore's Law and the increases in
speed and complexity of computer systems.  Habits like "avoid
trivial functions because function calls are expensive" are a
waste of time.  Ten years later, all the costs are going to be
different again.

I suspect the only time-optimization technique that's worth
learning is: a) identify the code paths and data paths that are
followed most often, b) reduce those paths as much as possible.

This implies a need for better program analysis tools.
Traditional profiling is focused on the units of code path called
"functions", but that's becoming increasingly irrelevant.

I think I want tools that will make steps 2-3 efficient,
and tools that I can ask to collapse code paths for me.
("inline" is pretty much worthless for that.  "leafify" is
better.)
--

Re: std::pow implementation

[Robert Dewar]

note that one of the most important reasons for inlining *on some architectures*
is to deal with cache thrashing when a function is called within a loop. This of
course is something that is out of reach of analysis by the programmer or
the compiler, but it can often mean that inlining helps even though to a
simple minded analysis it does not seem to.

Re: std::pow implementation

[Richard Guenther]

> Something seems fundamentally wrong here, and I think it is C++'s property
> to automatically put the "inline" tag on all functions defined in a class
> body, even if they don't have the "inline" keyword. But I see no chance
> to get this changed.

-fno-default-inline is your friend.

Richard.

Re: std::pow implementation

[Martin Reinecke]

On Wed, Jul 30, 2003 at 05:44:48PM +0200, Richard Guenther wrote:

> -fno-default-inline is your friend.

Yes, but I'd prefer a portable solution :)

Martin

Re: std::pow implementation

[Robert Dewar]

> If we assume for now that intermodule optimization is not done (and that's
> the current situation),

For the record, intermodule inlining is considered a critically important
optimziation in the Ada world.

Re: std::pow implementation

[Gabriel Dos Reis]

dewar@gnat.com (Robert Dewar) writes:

| > If we assume for now that intermodule optimization is not done (and that's
| > the current situation),
| 
| For the record, intermodule inlining is considered a critically important
| optimziation in the Ada world.

Certainly. I don't what the Ada compilation is, but C++ (and C) tend
to have a very rude compilation model.
Before we go that level of machinery, let's get it right for
translation units. 

-- Gaby

Re: std::pow implementation

[Robert Dewar]

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

I think one reason that the treatment of inline has been much more successful
in Ada than in C++ (at least in the gcc environment) is precisely that Ada
programmers are very used to using inline extensively, and assuming that
the compiler will pay significant attention to their input. In fact we find
that -O3 often damages performance in Ada, since the programmer has done
a pretty good job of selecting what needs inlining.

So anything that discourages the use of the inline directive is unfortunate

Re: std::pow implementation

[Gabriel Dos Reis]

dewar@gnat.com (Robert Dewar) writes:

| > 
| > 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".
| 
| I think one reason that the treatment of inline has been much more successful
| in Ada than in C++ (at least in the gcc environment) is precisely that Ada
| programmers are very used to using inline extensively, and assuming that
| the compiler will pay significant attention to their input.

only some (C++) implementors have decided that they know better than
the programmer and they should not listen to the programmer assuming
that their uses of inline is nonsensical.  Other C++ implemetors have
done it different and made good compilers that were known for their
paying attention to the programmer's input.

-- Gaby

Re: std::pow implementation

[Paolo Carlini]

Gabriel Dos Reis wrote:

>only some (C++) implementors have decided that they know better than
>the programmer and they should not listen to the programmer assuming
>that their uses of inline is nonsensical.
>
Hi everyone... My 2 cents, or even 0 cents if someone already mentioned 
what I'm going to say...

Gaby, your concept of "know better than the programmer..." reminds me 
something I read years ago about the keyword "register". Is there 
something we can learn from that? At the time I was convinced that the 
programmer is not as good as Chaitin's register allocators ;) ...

Paolo.

Re: std::pow implementation

[Joe Buck]

Gabriel Dos Reis wrote:
> >only some (C++) implementors have decided that they know better than
> >the programmer and they should not listen to the programmer assuming
> >that their uses of inline is nonsensical.

On Wed, Jul 30, 2003 at 04:33:59PM +0200, Paolo Carlini wrote:
> Gaby, your concept of "know better than the programmer..." reminds me 
> something I read years ago about the keyword "register". Is there 
> something we can learn from that? At the time I was convinced that the 
> programmer is not as good as Chaitin's register allocators ;) ...

The analogy between the keywords "inline" and "register" is often made,
but I think that it is inappropriate.  The reason is that we can do very
good register allocation based only on local information, where the same
is not true of many inlining decisions, which involve a more complicated
set of tradeoffs (other than for very small functions; for such cases the
compiler can reliably determine that an inlined call will be better by
every measure than a non-inlined call).  When the goal is optimization
for speed, detailed information about the cache and the execution profile
will be needed in many cases for an accurate decision.

In any case, at this stage in the state of the art of compiler
development, we are not even close to the day where it's a good idea
to just ignore the inline keyword.

Re: std::pow implementation

[Richard Earnshaw]

> The analogy between the keywords "inline" and "register" is often made,
> but I think that it is inappropriate.  The reason is that we can do very
> good register allocation based only on local information, where the same
> is not true of many inlining decisions, which involve a more complicated
> set of tradeoffs (other than for very small functions; for such cases the
> compiler can reliably determine that an inlined call will be better by
> every measure than a non-inlined call).  When the goal is optimization
> for speed, detailed information about the cache and the execution profile
> will be needed in many cases for an accurate decision.

It's true that the similarities are weak, but there are similarites.  The 
most significant difference, as I see it, is that "inline" does introduce 
more information for the compiler to make use of (it provides the 
definition as well as the interface).

> In any case, at this stage in the state of the art of compiler
> development, we are not even close to the day where it's a good idea
> to just ignore the inline keyword.

I don't believe that we can ever entirely ignore "inline" in the way we 
ignore "register" because it does introduce (especially in C90) subtle 
changes of meaning for the code.  So the issue isn't really a matter of 
ignoring as much as "deciding" that in the current context calling an 
out-of-line copy is the more optimal solution.

This entire debate is really about how, and when, that decision gets made 
and what the heuristics for deciding it need to be.  The argument is so 
hot because there are occasions when trivial inline functions are not 
being inlined, but cranking up the metrics is leading to pathological 
behaviour.  Currently, GCC's heuristics are fairly dumb (a static count of 
the number of un-optimized tree nodes that are introduced).  A much better 
choice could probably be achieved if we did some optimization on the 
inline candidate before we made a decision the more optimizations the more 
likely we are to get a good choice (for example -- duplicate the tree, 
feed in the arguments from the current call site, run the tree-level 
optimizations and look at the size of the result.  If we've fed in 
constant arguments then the size of the result may be a tiny fraction of 
the original tree).

Maybe we should just have an option "-fdumb-inlining" and give the user 
the final choice (to quote an advert here in the UK "it does exactly what 
it says on the tin").  Eventually, we could probably make smart inlining 
so much better that nobody would need the "dumb" option.

R.

Re: std::pow implementation

[Robert Dewar]

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

None of these three semantics make sense to me. The only one that makes sense
is the one I gave before.

Speed up calls to this function, by doing optimizations (most obviously by
inlining the call) that speed up execution, even if it results in extra space
for generated code.

(the comment here is suggestive, not normative, in standards terms, but we
know perfectly well what it means as implementors).

Re: std::pow implementation

[Richard Earnshaw]

> > 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.
> 
> None of these three semantics make sense to me. The only one that makes sense
> is the one I gave before.
> 
> Speed up calls to this function, by doing optimizations (most obviously by
> inlining the call) that speed up execution, even if it results in extra space
> for generated code.

If I'm compiling some code with -Ospace I really don't want that 
definition.  Instead, I'd want "Optimize the call overhead away if that 
will result in smaller code".

Optimization is about trying to meet certain goals with a "cost metric".  
What that cost metric is can vary from use to use; it's important that we 
don't blind ourselves to the situations when that isn't "maximum 
performance".

> (the comment here is suggestive, not normative, in standards terms, but we
> know perfectly well what it means as implementors).

Ditto.

R.

Re: std::pow implementation

[Richard Guenther]

On Wed, 30 Jul 2003, Robert Dewar 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.
>
> None of these three semantics make sense to me. The only one that makes sense
> is the one I gave before.

These are clearly defined semantics suitable for a standards document,
yours below falls to #3, obviously.

> Speed up calls to this function, by doing optimizations (most obviously by
> inlining the call) that speed up execution, even if it results in extra space
> for generated code.

This is of course what we have in mind if specifying "inline". But I would
expect the compiler doing similar things if only specifying -O2 globally
and not -Os.

Richard.

Re: std::pow implementation

[Robert Dewar]

> Also portability is not only about different targets, but also about
> different compilers! Declaring something inline for one compiler doesnt
> necessary have the same desired semantics for inline for another one.

good point ...

Re: std::pow implementation

[Richard Guenther]

On Wed, 30 Jul 2003, Robert Dewar wrote:

> > Also portability is not only about different targets, but also about
> > different compilers! Declaring something inline for one compiler doesnt
> > necessary have the same desired semantics for inline for another one.
>
> good point ...
>

Which equals to the point that gcc should be able to produce equally good
code for any inline semantics the code was written for.

Richard.

Re: std::pow implementation

[Robert Dewar]

> He can profile.

Profiling is of limited use here. It may find hotspots, but the issue of
how to treat large numbers of small functions that should be inlined cannot
be addressed by profiling, since you may have situations where you have many
such functions and no one function shows up as a hot spot. For an example
look at the set of pragma Inlines for the Ada units sinfo.ads and einfo.ads.

Basically in Ada, we regard pragma Inline as meaning: this function is pretty
small and I call it quite often and I would like the calls to be efficient.
Feel free to optimize in a way that improves time performance even if more
space is generated. I am guessing that it would make sense to inline calls
(I know the standard doesn't formally define this, but you know what I mean).

What we do in practice is to mark the function as inlinable, and use a higher
than usual threshhold for deciding to inline it, which seems to work pretty
well.

Re: std::pow implementation

[Gabriel Dos Reis]

dewar@gnat.com (Robert Dewar) writes:

[...]

| Basically in Ada, we regard pragma Inline as meaning: this function is pretty
| small and I call it quite often and I would like the calls to be efficient.

That is not too far from the intent of inline in C++.

| Feel free to optimize in a way that improves time performance even if more
| space is generated. I am guessing that it would make sense to inline calls
| (I know the standard doesn't formally define this, but you know what I mean).

Yes, the standard does not legislate, but we know how and why the
language evolved to introduce that feature.

-- Gaby

Re: std::pow implementation

[Robert Dewar]

> But this implies an "inline" directive
> which would more or less _force_ the compiler to always inline the code.

Yes, but there is nothing in the standard or in common sense that requires
you to treat this implicit inline the same way you would treat other inlines,
since the compiler has plenty of freedom in its handling of inline.

Re: std::pow implementation

[Gabriel Dos Reis]

dewar@gnat.com (Robert Dewar) writes:

| > But this implies an "inline" directive
| > which would more or less _force_ the compiler to always inline the code.
| 
| Yes, but there is nothing in the standard or in common sense that requires
| you to treat this implicit inline the same way you would treat other inlines,

there is nothing like "implicit" inline and other inlines in C++.

-- Gaby

Re: std::pow implementation

[Robert Dewar]

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

And of course this approach is impractical, since whether inlining helps
in a specific case is target dependent.

Re: std::pow implementation

[Richard Guenther]

On Wed, 30 Jul 2003, Robert Dewar 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.
>
> And of course this approach is impractical, since whether inlining helps
> in a specific case is target dependent.

This discussion is all about the semantics of the inline keyword. But as
inline is a keyword defined by the standard without giving it strict
semantics it is quite useless. So for portability we are forced to keep
loose semantics. We can always provide the user with extensions with more
useful/strict semantics if he needs - and he does.

Richard.

Re: std::pow implementation

[Robert Dewar]

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

In fact in a language standard, you really can't define the notion of
"inlining" as such, since the standard is not in the business of
describing details about the generated code. So the formal meaning of
inline is most certainly "speed up execution of this function if possible
at the expense of extra space". Yes, notes in the standard and the name
chosen for this hint is strongly evocative, but not normative :-)

Re: std::pow implementation

[Martin Reinecke]

Gabriel Dos Reis wrote:

 > Do trust the programmer.

This is certainly a valid point of view, but I think that C++, as it exists
at the moment, just _doesn't give_ the programmer the possibility of specifying
what exactly (s)he wants.

I think it is not generally possible for a programmer to decide whether a function
should be inlined or not (see below).

The only exceptions are functions like std::string::end()
that probably even *save space* when they are inlined.

But imagine, for example, a function foo() with about 50 lines of code, somewhere in a C++
library. If this function is going to be used in the following context

amax = 100000000;
[...]
for (int a=0; a<=amax; ++a)
   foo();

then it should most definitely be inlined, because not much space is wasted, and the
calling overhead is gone, which pays off if amax is large.
The problem is that gcc usually cannot determine how large amax is going to be, so it
doesn't know what the right solution is, no matter how good the inlining heuristics are.

On the other hand, if foo() is called from many different places but only once, like this:

[...]
foo();
[...]
foo();
and so on,

then inlining probably doesn't make much sense.

In other words: the author of foo() _cannot_ decide whether foo() should be inlined or not,
because he doesn't know to what kind of uses it will be put by other people (unless he is the
only user of foo(), of course). Whatever the author of foo() specifies (inline or not),
he's going to get it wrong in some cases.

In most cases, the user who calls foo() knows much better if foo() should be inlined.
Wouldn't it therefore be much more sensible to give the compiler an inlining hint at the place
where foo() is called, e.g.

for (int a=0; a<=amax; ++a)
#pragma inline
   foo();

or

#pragma noinline
{
[...]
foo();
[...]
foo();
}

Of course it would be much nicer if C++ supported this natively ...

Please ignore me if I didn't make any sense.

Cheers,
   Martin

Re: std::pow implementation

[Gabriel Dos Reis]

Martin Reinecke <martin@MPA-Garching.MPG.DE> writes:

| Gabriel Dos Reis wrote:
| 
|  > Do trust the programmer.
| 
| This is certainly a valid point of view, but I think that C++, as it exists
| at the moment, just _doesn't give_ the programmer the possibility of specifying
| what exactly (s)he wants.

But taking out the only lever the programmer currently has is even far
worse. 

| I think it is not generally possible for a programmer to decide
| whether a function should be inlined or not (see below).

I reckon that there are conner cases that "inline" does not cover.
But, I'm worrying about the common situations -- and those that ave
been subject of PRs.

However, in lieu of pragmas, I will point out that current C++
gives the programmer means to express, in many corner cases, the
intention of not inlining, by combining inline and noninline
definitions and object functions. 

[...]

| Of course it would be much nicer if C++ supported this natively ...
| 
| Please ignore me if I didn't make any sense.

Your input is meaningful, I don't see why it should be ignored :-)

-- Gaby

Re: std::pow implementation

[Martin Reinecke]

Gabriel Dos Reis wrote:
> Martin Reinecke <martin@MPA-Garching.MPG.DE> writes:
> 
> | This is certainly a valid point of view, but I think that C++, as it exists
> | at the moment, just _doesn't give_ the programmer the possibility of specifying
> | what exactly (s)he wants.
> 
> But taking out the only lever the programmer currently has is even far
> worse. 

Right, but that's exactly the dilemma with C++'s "implicit" inline:
if you want the compiler to _be able_ to inline a function, you should put
it in the class definition. But this implies an "inline" directive
which would more or less _force_ the compiler to always inline the code.
So, if inline was as strict as you'd like to see it, there would be no
way to tell gcc "here's a function that might be probably worthwhile to
inline". I could only say "inline this" or "don't inline".

This could change if gcc starts to inline functions across translation units,
but currently it doesn't (I believe).

> | I think it is not generally possible for a programmer to decide
> | whether a function should be inlined or not (see below).
> 
> I reckon that there are conner cases that "inline" does not cover.
> But, I'm worrying about the common situations -- and those that ave
> been subject of PRs.

I've encountered the example I gave a few times in real-life code,
but in the frame of standard C++ nothing can be done about it, so
I cannot file a PR.

> However, in lieu of pragmas, I will point out that current C++
> gives the programmer means to express, in many corner cases, the
> intention of not inlining, by combining inline and noninline
> definitions and object functions. 

You're right. It's not too beautiful and makes maintenance a bit harder,
but on the other hand it shouldn't happen too often.

Martin

Re: std::pow implementation

[Andrew Pinski]

On Wednesday, Jul 30, 2003, at 09:19 US/Eastern, Martin Reinecke wrote:
> This could change if gcc starts to inline functions across translation 
> units,
> but currently it doesn't (I believe).

It does in the mainline if you put all the files as arguments to gcc.
Example:

gcc temp.cc temp1.cc temp2.cc -o temp.o
gcc temp.o -o temp

This will cause intermodular optimizations.

This was put on the mainline in July 11, 2003.

Thanks,
Andrew Pinski

Re: std::pow implementation

[Steven Bosscher]

Op wo 30-07-2003, om 15:24 schreef Andrew Pinski:
> On Wednesday, Jul 30, 2003, at 09:19 US/Eastern, Martin Reinecke wrote:
> > This could change if gcc starts to inline functions across translation 
> > units,
> > but currently it doesn't (I believe).
> 
> It does in the mainline if you put all the files as arguments to gcc.
> Example:
> 
> gcc temp.cc temp1.cc temp2.cc -o temp.o
> gcc temp.o -o temp
> 
> This will cause intermodular optimizations.

But not yet for C++

Re: std::pow implementation

[Martin Reinecke]

Steven Bosscher wrote:
> Op wo 30-07-2003, om 15:24 schreef Andrew Pinski:
> 
>>On Wednesday, Jul 30, 2003, at 09:19 US/Eastern, Martin Reinecke wrote:
>>
>>>This could change if gcc starts to inline functions across translation 
>>>units,
>>>but currently it doesn't (I believe).
>>
>>It does in the mainline if you put all the files as arguments to gcc.
>>Example:
>>
>>gcc temp.cc temp1.cc temp2.cc -o temp.o
>>gcc temp.o -o temp
>>
>>This will cause intermodular optimizations.
> 
> 
> But not yet for C++

Even if we had it for C++ it wouldn't help when I link
against libraries, i.e. the optimizations are only done
at the source code level. Once I have only object files
and libraries, I'm out of luck. So it means that for a large
application I'd need the full source code of all used
libraries and compile them with a single call to gcc.
This is for various reasons, rather unrealistic.

Cheers,
   Martin

Re: std::pow implementation

[Gabriel Dos Reis]

Martin Reinecke <martin@MPA-Garching.MPG.DE> writes:

| Gabriel Dos Reis wrote:
| > Martin Reinecke <martin@MPA-Garching.MPG.DE> writes:
| > | This is certainly a valid point of view, but I think that C++, as
| > it exists
| > | at the moment, just _doesn't give_ the programmer the possibility of specifying
| > | what exactly (s)he wants.
| > But taking out the only lever the programmer currently has is even
| > far
| > worse.
| 
| Right, but that's exactly the dilemma with C++'s "implicit" inline:
| if you want the compiler to _be able_ to inline a function, you should put
| it in the class definition.

Please note that there is no "implicit" inline in C++.  The only thing
that is present is that function definition within a class declaration
is an inline definition, because that is the orginal syntax before
inlining nonmember function was implemented.  A function defined
within a class is as inline as a function defined with the "inline"
keyword outside a class.

| But this implies an "inline" directive
| which would more or less _force_ the compiler to always inline the code.
| So, if inline was as strict as you'd like to see it, there would be no
| way to tell gcc "here's a function that might be probably worthwhile to
| inline". I could only say "inline this" or "don't inline".
| 
| This could change if gcc starts to inline functions across translation units,
| but currently it doesn't (I believe).

That "worthwhile inlining" could subject to higher optimiations
("-O3") if it is so that we've reached the level of sophistication
where automatic inline supersedes traditional "inline".

But I see on concrete real world codes that the "inline" meaning
transmutation GCC operates does cause more grief that it does good.

| > | I think it is not generally possible for a programmer to decide
| > | whether a function should be inlined or not (see below).
| > I reckon that there are conner cases that "inline" does not cover.
| > But, I'm worrying about the common situations -- and those that ave
| > been subject of PRs.
| 
| I've encountered the example I gave a few times in real-life code,
| but in the frame of standard C++ nothing can be done about it, so
| I cannot file a PR.
| 
| > However, in lieu of pragmas, I will point out that current C++
| > gives the programmer means to express, in many corner cases, the
| > intention of not inlining, by combining inline and noninline
| > definitions and object functions.
| 
| You're right. It's not too beautiful and makes maintenance a bit harder,
| but on the other hand it shouldn't happen too often.

and is expressed with standard constructs.

-- Gaby

Re: std::pow implementation

[Martin Reinecke]

Gabriel Dos Reis wrote:

> Please note that there is no "implicit" inline in C++.  The only thing
> that is present is that function definition within a class declaration
> is an inline definition, because that is the orginal syntax before
> inlining nonmember function was implemented.  A function defined
> within a class is as inline as a function defined with the "inline"
> keyword outside a class.

I know; this is why I put "implicit" in quotes. But this doesn't help, I think.

Say I write the following

==========foo.h

class foo
   {
   inline void bar();
   };

==========foo.cc

inline void foo::bar() {...}

No current g++ will inline foo::bar() (and most other compilers won't either) when I
call it from, say, baz.cc. So there is a practical difference between defining
a function in the class body, and declaring it as inline and defining it in a
separate .cc file.

If we assume for now that intermodule optimization is not done (and that's
the current situation), there is no way to tell the C++ compiler
"this function might be useful to inline", because it has to see the function
body before it can decide whether to inline it or not. And it can't see
it because it's in a different translation unit.

AFAIK, it's ill-formed to write

=========foo.h

class foo
   {
   void bar();
   };

void foo::bar() {...}

=========end of foo.h

I think this is only OK if I explicitly declare bar() as inline.
If not, I run into trouble with the ODR.

> | But this implies an "inline" directive
> | which would more or less _force_ the compiler to always inline the code.
> | So, if inline was as strict as you'd like to see it, there would be no
> | way to tell gcc "here's a function that might be probably worthwhile to
> | inline". I could only say "inline this" or "don't inline".
> | 
> | This could change if gcc starts to inline functions across translation units,
> | but currently it doesn't (I believe).
> 
> That "worthwhile inlining" could subject to higher optimiations
> ("-O3") if it is so that we've reached the level of sophistication
> where automatic inline supersedes traditional "inline".

I'll be happy with this as soon as intermodule optimization works
well. Without it, we have not gained anything, as the example shows.

> But I see on concrete real world codes that the "inline" meaning
> transmutation GCC operates does cause more grief that it does good.

Probably. I just think it was caused by the fact that C++ compilers
have been imperfect (i.e. lacking intermodule inlining) for a long time.
And because so many codes exist that were written with the "transmuted"
meaning in mind, there will be a terrible lot of breakage if the meaning
is reset abruptly.

> | You're right. It's not too beautiful and makes maintenance a bit harder,
> | but on the other hand it shouldn't happen too often.
> 
> and is expressed with standard constructs.

Agreed. I was arguing for a possible extension of the standard itself, not
for introducing new pragmas.

Martin

Re: std::pow implementation

[Gabriel Dos Reis]

Martin Reinecke <martin@MPA-Garching.MPG.DE> writes:

[...]

| Say I write the following
| 
| ==========foo.h
| 
| class foo
|    {
|    inline void bar();
|    };
| 
| ==========foo.cc
| 
| inline void foo::bar() {...}
| 
| No current g++ will inline foo::bar() (and most other compilers won't either) when I
| call it from, say, baz.cc.

The standard does mandate that the definition of an inline function
be available in every translation unit that uses it.

[...]

| > But I see on concrete real world codes that the "inline" meaning
| > transmutation GCC operates does cause more grief that it does good.
| 
| Probably. I just think it was caused by the fact that C++ compilers
| have been imperfect (i.e. lacking intermodule inlining) for a long time.

KCC did better, even with no inter translation-unit optimization, on
real world codes.

| And because so many codes exist that were written with the "transmuted"
| meaning in mind, there will be a terrible lot of breakage if the meaning
| is reset abruptly.
| 
| > | You're right. It's not too beautiful and makes maintenance a bit harder,
| > | but on the other hand it shouldn't happen too often.
| > and is expressed with standard constructs.
| 
| Agreed. I was arguing for a possible extension of the standard itself, not
| for introducing new pragmas.

I see, but that tends to confuse the debate.

-- Gaby

Re: std::pow implementation

[Martin Reinecke]

Gabriel Dos Reis wrote:

> The standard does mandate that the definition of an inline function
> be available in every translation unit that uses it.

Thanks for the clarification. But I think there is still no way to expose
the definition of a not-explicitely-inline function to all
translation units where it is used.

The fundamental problem is that there are three classes of functions:
  - functions that should always be inlined
  - functions where the compiler should decide
  - functions that should never be inlined

The first category must have its definition in a header file.
The second category should have its definition in a header file also,
to give the compiler a chance of inlining it. But C++ won't let us,
because all functions with their definition in a header automatically
belong to the first category.

Something seems fundamentally wrong here, and I think it is C++'s property
to automatically put the "inline" tag on all functions defined in a class
body, even if they don't have the "inline" keyword. But I see no chance
to get this changed.

Maybe the discussion is so intense because there is no real solution?

Martin

Re: std::pow implementation

[Gabriel Dos Reis]

Martin Reinecke <martin@mpa-garching.mpg.de> writes:

| Gabriel Dos Reis wrote:
| 
| > The standard does mandate that the definition of an inline function
| > be available in every translation unit that uses it.
| 
| Thanks for the clarification. But I think there is still no way to expose
| the definition of a not-explicitely-inline function to all
| translation units where it is used.

Yes.

I do not see those as pressing as getting inlining of those declared
inline good.

| The fundamental problem is that there are three classes of functions:
|   - functions that should always be inlined
|   - functions where the compiler should decide
|   - functions that should never be inlined

I can agree with that categorization.

| The first category must have its definition in a header file.
| The second category should have its definition in a header file also,
| to give the compiler a chance of inlining it. But C++ won't let us,
| because all functions with their definition in a header automatically
| belong to the first category.

Not actually.  Not just because a function definition is put in a
header file -- or more accurately, is avalaible in translation unit
means that inlining is requested for that function.

(I may suggest "mutable inline" for the second category and ~inline
for the third :-)

| Something seems fundamentally wrong here, and I think it is C++'s property
| to automatically put the "inline" tag on all functions defined in a class
| body, even if they don't have the "inline" keyword. But I see no chance
| to get this changed.

That is the way inlining is introduced in C++.  Fundamentally, I think
that decision is not wrong.

| Maybe the discussion is so intense because there is no real solution?

I'm confident that we can read a useful point, if we're careful enough
not to turn it into a flame war -- we're not going to take the habit
of turning every discussion about "inline" into a flame war, right? :-)

-- Gaby

Re: std::pow implementation

[Martin Reinecke]

On Wed, Jul 30, 2003 at 04:51:01PM +0200, Gabriel Dos Reis wrote:

> Not actually.  Not just because a function definition is put in a
> header file -- or more accurately, is avalaible in translation unit
> means that inlining is requested for that function.

I just can't think of a way how to do that without breaking some
C++ rule; could you please give a short example?
If the definition can be made available in more than one translation unit
without requesting inlining, I'm perfectly happy.

> (I may suggest "mutable inline" for the second category and ~inline
> for the third :-)

Nice ;)

Martin

Re: std::pow implementation

[Theodore Papadopoulo]

	Sorry, I'm certainly replying a bit late...


gdr@integrable-solutions.net said:
> | > 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. 

Well to be honest at the time the inline-limit was put into gcc, gcc 
was much better than KCC (in terms of inlining not in terms of 
overall efficiency of the compiled code). A simple program like:

template <int N>
struct A {

   void f() {
      A<N-1>::f();
      A<N-1>::f();
   }
};

template <>
struct A<0> {
   void f() { }
};

int main()
{
   A<32>::f();
}

was causing a real memory hog with gcc (which inlined everything and 
not realizing that the functions were empty !!) 
while KCC was stopping after a few inlining levels. At that time, 
inlining was done on RTL was quite fast and the inlining limit was
very high...

Then a lot of things changed, garbage collection was introduced, tree 
based inlining was introduced, function-at-a-time and now even 
unit-at-a-time strategy, a new standard C++ library came in, ...
(this list is certainly not intented to be used as a list of guilty
changes) ... and inlining (presumably among other things) started to
be really slow. 

Then, someone noticed, that one way to reduce the time the compiler 
was spending in doing inlining was simply to reduce the inlining 
limit (and even to introduces new ones). And there were some 
convincing examples to show that the overall performance of the 
programs were not decreased (at least too much). Unfortunately, with 
more testing, this has proved to be not entirely true.

So saying that KCC was better than gcc because it inlined more was 
simply not true (at the time where this story begins), KCC was still 
often better than gcc and gcc was inlining everything it could (ie 
marked as inline either explicit or implicit).

The main conclusions this leads to, are (IMHO):

- The simple example above shows clearly that some limit has to exist 
and to be put by the compiler (of course here the function is empty 
and the compiler could have figured it out, but imagine if it were 
not).

- At some point (egcs times, around 1998), even while inlining much 
much more than today gcc was faster and consumed less memory (and 
certainly had also difficult memory management related bugs...). So 
the scheme that Gaby describes worked (with some very high limits) at 
some point in the past and people were not complaining...

- The current limitting strategy is coming from a very practical point of 
view (restrict the compilation time of the released 
compiler) and might not be considered as the definitive answer on the 
problem all the more that users have reported that the inlining 
limits consequences are varying a lot depending on the langage in use,
the type of the code, etc.

- The inlining strategy plays some important role. In the function 
above, gcc which (at that time) was doing top-down inlining (ie from 
A<32> down to A<0>) had to inline everything before being able to 
realize that the function was empty. I think Nathan or Zack proposed 
a bottom-up experimental patch around that time. From what I read here, 
it seems that the ideal inlining strategy still has to be found (or 
more likely approximated).

- Context (in conjunction of optimization and inlining strategy) is
also certainly important (Imagine if you could prove that f() is empty
in the example above). I hope that tree based optimisation will allow
partial optimization of functions after inlining, so that the metrics of
the costs will be more meaningfull...

Final point: it has been reported here (and it is also my 
experience), that for some C++ code, sometimes -Os (which I believe 
restricts the amount of inlining) results with more efficient code 
than all over -O[0123] choices. This with timings that can go for 
about 12s at -O0 down to 1.2s for -Os and about 2.5s for -O2 (numbers 
are approximative and pre-date the unit-at-a-time patch but I'm not 
sure how this interferes, all functions were small). This tends to 
show that 

- it is the metrics that are used to determine the efficiency 
of the code that need some work.

- certainly, at some point the compiler will know better what to 
inline (sorry Gaby) and what to keep as a function. And I also buy, 
all the portability arguments that have been raised along this 
discussion.


It really seems that this inlining problem is much more difficult to 
cope with than it was expected... I wish I had a good idea...

I just hope that SSA based optimisations and the work Jan just did on 
metrics and unit-at-a-time, will really make effective some of the 
infrastructure work (like function-at-a-time and tree based inlining) 
that might need tree based optimisation. Here I certainly show how 
little I know about how inlining interferes with other optimizations
(now and the past RTL based scheme).



--------------------------------------------------------------------
Theodore Papadopoulo
Email: Theodore.Papadopoulo@sophia.inria.fr Tel: (33) 04 92 38 76 01
 --------------------------------------------------------------------

Re: std::pow implementation

[Gabriel Dos Reis]

Theodore Papadopoulo <Theodore.Papadopoulo@sophia.inria.fr> writes:

| 	Sorry, I'm certainly replying a bit late...
| 
| 
| gdr@integrable-solutions.net said:
| > | > 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. 
| 
| Well to be honest at the time the inline-limit was put into gcc, gcc 
| was much better than KCC (in terms of inlining not in terms of 
| overall efficiency of the compiled code).

As I noted elswhere, just inlining does not solve all problems.  There
is no dispute on that.  But KCC's honouring the inline keyword was
most certainly part of the efficacy of codes produced by KCC.
Inlining can expose opportunities for better optimization, like
constant propagation, dead code elimination or reference shrinking.

[...]

| Then a lot of things changed, garbage collection was introduced, tree 
| based inlining was introduced, function-at-a-time and now even 
| unit-at-a-time strategy, a new standard C++ library came in, ...

listing the (new) standard library in this discussion will create more
confusion than helps sort out the issue.

[...]

| So saying that KCC was better than gcc because it inlined more was 
| simply not true (at the time where this story begins), KCC was still 
| often better than gcc and gcc was inlining everything it could (ie 
| marked as inline either explicit or implicit).

Please do be careful in your rephrasing.  I'm specifically concerned
about honouring the inline request and -not- "inlining more".  And I'm
not saying GCC should inline everything.  Part of the confusion in
this debate came from the fact that people are considering that
honouring the inline request means inlining everything.

[...]

| - The inlining strategy plays some important role. In the function 

Equally important is considering the language-specific semantics.

[...]

| Final point: it has been reported here (and it is also my 
| experience), that for some C++ code, sometimes -Os (which I believe 
| restricts the amount of inlining) results with more efficient code 
| than all over -O[0123] choices.

You seem to be confusing "inline" with "optimize".

[...]

| - certainly, at some point the compiler will know better what to 
| inline

at that point, "inline" could go the way of "register", but we're
not at that level yet.

I'll send in a moment a text I intended to send some time ago.

-- Gaby

Re: std::pow implementation

[Theodore Papadopoulo]

gdr@integrable-solutions.net said:
> listing the (new) standard library in this discussion will create more
> confusion than helps sort out the issue.

That was not my point, I listed some of the big (necessary and/or good) changes
in the C++ context. The bigger library was often associated with bigger compile times, 
but as I said the list is certainly not changes that have to be 
accused for the compile times.

> | So saying that KCC was better than gcc because it inlined more was
> | simply not true (at the time where this story begins), KCC was still
>  | often better than gcc and gcc was inlining everything it could (ie
> | marked as inline either explicit or implicit).

> Please do be careful in your rephrasing.  I'm specifically concerned
> about honouring the inline request and -not- "inlining more".  And I'm
> not saying GCC should inline everything.  Part of the confusion in
> this debate came from the fact that people are considering that
> honouring the inline request means inlining everything.

Agreed. But, at that time gcc was "honouring the inline request" even 
better than KCC was. That is what the more refers to... When I say 
that gcc inlined everything it could means that it was "honouring the
inline request in all places where it could".

> | - The inlining strategy plays some important role. In the function 
> Equally important is considering the language-specific semantics.

Totally agreeing. I think, I basically say the same things somewhere 
else in the text.

> | Final point: it has been reported here (and it is also my  |
> experience), that for some C++ code, sometimes -Os (which I believe  |
> restricts the amount of inlining) results with more efficient code  |
> than all over -O[0123] choices.
> You seem to be confusing "inline" with "optimize".

Well, I agree that the example is not as clear as I would have wished...
Certainly -Os has consequences on the inlining limits but I agree 
this might be drawn in many other program transformations.

> I'll send in a moment a text I intended to send some time ago. 

I'll read it.


Note that my point was not to discuss how inline should be honoured. 
I gave just many contradicting facts:

- when gcc honored inline like you would like it did, it worked and 
was faster than it is now (not sure about the compiled code speed but 
it was not that bad in my recollections).

- Some limits on the "honoring" just have to exist.

- on the other hand, as mentioned elsewhere in the thread, just 
saying that the programmer knows what it does is simply not quite 
true... And the portability makes things even worse.

My guess (but this is just that) is that the situtation is bad for 
C++ because:

- inlining is now tree-based but most other optimizations are 
RTL-based.

- general speed has decreased (at least up to recently).

- most inlining limits were set based on too narrow testing (I 
believe it was mostly C programs). I agree that C and C++ need 
different treatment.

Now if I have to say something abou the topic, I believe that, 
unfortunately, because of the compilation times, I not quite sure that gcc is 
ready for the old "honor mostly every inline up to some extremely 
high limit"... that is why I said that the current situation is just 
a pragmatic move rather than a definitive answer.

As you said, to really realize the full benefits of inlining, one has 
to embed somehow inlining with other optimizations (cprop, dce, ...), 
currently (correct me if I'm wrong), the situation is doomed because 
inlining decisions are made on trees and most of these optimisations 
come later on RTL so that the metrics used to decide if inlining is 
a profitable choice cannot take account of the further optimizations
the inlining may allow. As I said my hope is that the SSA stuff will 
change the overall picture and will made the "compiler made" 
decisions a better alternative than it is now. Will the code size 
decrease (and hopefully the memory consumption and speed) be enough to 
"honour" all inline hints as you argue (provided it is better than 
the choices made by the compiler) I do not know.

My main conclusion is that inlining limits are just a trick to make 
the compiler fast enough to convince people to use it. They must be 
reconsidered regularly and IMHO made specific to each language (to 
better cope with the language expectations).
This is unfortunate and just a pragmatic conclusion and I place my 
hopes in SSA for a better answer to the problem.

Please correct me if I'm wrong in my expectations !!!




--------------------------------------------------------------------
Theodore Papadopoulo
Email: Theodore.Papadopoulo@sophia.inria.fr Tel: (33) 04 92 38 76 01
 --------------------------------------------------------------------

Re: std::pow implementation

[Gabriel Dos Reis]

Theodore Papadopoulo <Theodore.Papadopoulo@sophia.inria.fr> writes:

| > I'll send in a moment a text I intended to send some time ago. 
| 
| I'll read it.
| 
| 
| Note that my point was not to discuss how inline should be honoured. 
| I gave just many contradicting facts:

and I appreciate them.

| - when gcc honored inline like you would like it did, it worked and 
| was faster than it is now (not sure about the compiled code speed but 
| it was not that bad in my recollections).
| 
| - Some limits on the "honoring" just have to exist.

I explicitly acknowledge "pathological" cases, but surely no simple,
short expression is pathological.

| - on the other hand, as mentioned elsewhere in the thread, just 
| saying that the programmer knows what it does is simply not quite 
| true... And the portability makes things even worse.

We're talking about C++ where we already trust the programmer in many
many more circumstances.  

| My guess (but this is just that) is that the situtation is bad for 
| C++ because:
| 
| - inlining is now tree-based but most other optimizations are 
| RTL-based.
| 
| - general speed has decreased (at least up to recently).
| 
| - most inlining limits were set based on too narrow testing (I 
| believe it was mostly C programs). I agree that C and C++ need 
| different treatment.

If we base only on semantics, I will say C needs different
treatment.  However I'm not arguing about how C should be treated. 
For the time being, I'm concerned about C++.

I think many notions of "inlining" are being confused and C++'s is
lost in the process.  At least we have: 

  (1) language specific (C++).  This, ideally, should happen very early
      in the program translation.

  (2) more-or-less language-neutral, e.g. middle end or back ends,
      meaning "optimize for whatever" 

Currenly, what we're doing is much closer to (2) than (1).  I do not
believe they should be mutually exclusive.  The compiler is free to
inline any non-inline function that helps "optimize for whatever".
I don't think we should ban an RTL inliner just because we have a
tree inliner.  Both can be useful.  Of course there are more chance
for a tree-based inliner to understand language-specific semantics
much easier than an RTL inliner. 

If you take somthing like

    template<class T>
      struct vector_iterator {
         T* ptr;
         // ...
      };

    template<class T>
      inline bool
      operator==(vector_iterator<T> p, vector_iterator<T> q)
      { return p.ptr == q.ptr; }

we should make it so that use like p == q be as efficient as a
compariason between scalars p_ptr == q_ptr.  If you don't inline, then
you will be forced to use usual function call ABI dictated by the
target and you may loose performance, especially if the comparison is
done in a tight loop and the target ABI requires using stack for
structrures. 

Similarly, inlining something like

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

helps to identify and remove spurious references.

I would like to emphasize that I'm not claiming that inlining
everything will solve all optimization problems we have.

[...]

| My main conclusion is that inlining limits are just a trick to make 
| the compiler fast enough to convince people to use it. They must be 

If the compiler is "fast enough" but does not produce "acceptable"
codes, people won't use it.  Some people are still sticking with 2.95
because they think it is doing better (inling) job.

Not just because I'm arguing for language specific meaning for C++ inline
means I'm not pragmatic or I do not understand what purpose heuristics
might serve.

-- Gaby

Re: std::pow implementation

[Daniel Berlin]

Hey guys, maybe we can rename this thread to "The Zen of Optimizing C++ - What
is the sound of one compiler inlining?" or something, rather than "std::pow
implementation", since it  stopped being about std::pow maybe 90 messages
ago?

> Theodore Papadopoulo <Theodore.Papadopoulo@sophia.inria.fr> writes:
>
> | > I'll send in a moment a text I intended to send some time ago.
> |
> | I'll read it.
> |
> |
> | Note that my point was not to discuss how inline should be honoured.
> | I gave just many contradicting facts:
>
> and I appreciate them.

Re: std::pow implementation

[Scott Robert Ladd]

Martin Reinecke wrote:
> Gabriel Dos Reis wrote:
> 
>  > Do trust the programmer.
> 
> This is certainly a valid point of view, but I think that C++, as it exists
> at the moment, just _doesn't give_ the programmer the possibility of 
> specifying what exactly (s)he wants.

No high-level language "gives a programmer what they want." Which is one 
reason some of us still use assembler languages from time to time.

Any compiler worth its weight in bits will translate written code based 
on analysis; I vigorously support intelligent compilation. What I do 
*not* support is trying to be smarter than the programmer. A fine line 
line, to be sure, but a line nonetheless.

If I explicitly define a variable type or a structure packing, I expect 
the compiler to honor my wishes; if I say "inline", I mean "inline", 
within the physical limits of the compiler (i.e., memory use during 
compilation, etc.)

At the very least, a compiler should report when it has made a choice 
counter to the programmer's wishes. If I declare a function inline, and 
the compiler decides otherwise, it should inform me of its rebellion. 
Perhaps I'll even agree with it -- but I want to know when my tools make 
choices for me. I am writing the program, not the compiler.

-- 
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:43 schreef Scott Robert Ladd:
> At the very least, a compiler should report when it has made a choice 
> counter to the programmer's wishes. If I declare a function inline, and 
> the compiler decides otherwise, it should inform me of its rebellion. 
> Perhaps I'll even agree with it -- but I want to know when my tools make 
> choices for me. I am writing the program, not the compiler.

I plan to split the function body size estimate code out in a separate
function (if no-one does so before me), that would be a first step
towards improving the messages you get from -Winline. Right now it just
tells you that it didn't inline something, but not why, so it's not very
helpful.

Gr.
Steven

Re: std::pow implementation

[Scott Robert Ladd]

Steven Bosscher wrote:
> I plan to split the function body size estimate code out in a separate
> function (if no-one does so before me), that would be a first step
> towards improving the messages you get from -Winline. Right now it just
> tells you that it didn't inline something, but not why, so it's not very
> helpful.

*That* would be lovely.

..Scott

Re: std::pow implementation

[Stephan T. Lavavej]

It should be noted that the only way to make a library that is entirely
implemented in its header files is to declare *everything* inline.  Thus,
sometimes inline is used without the programmer intending it to mean
anything about performance one way or the other.

Stephan T. Lavavej
http://stl.caltech.edu

Re: std::pow implementation

[Gabriel Dos Reis]

"Stephan T. Lavavej" <stl@caltech.edu> writes:

| It should be noted that the only way to make a library that is entirely
| implemented in its header files is to declare *everything* inline. 

Not really.  How often do you have the cases where you 

  (1) want to have everything in a header 
  (2) don't want inlining
  (3) can't make them static

?

If you're attempting to tell me that a determined programmer can abuse of
"inline".  Yes, he can.  Just as he can for any other functionnality
of the language, but that is no sufficient excuse for changing the
meaning of inline.  We don't change the meaning of ther
functionalities because some programmer can abuse of them.

-- Gaby

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.

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