GNAT Optimization of Constant Expressions

GNAT Optimization of Constant Expressions

[David Smith]

In running some benchmarks between Ada, C, and Fortran, I came across
a bizarre situation with GNAT.  The same algorithm ran 10x slower in
Ada, so I surmised that the constant math expressions in the code
below were being precomputed by the compiler in C and Fortran, but not
in Ada.  To test my hypothesis, I defined the commented-out constants
and replaced the math functions with the appropriate constant.  This
worked, and the Ada code was then as fast at the others.  The
bizarreness came out when I put the math expressions back in but left
in the constant declarations.  The code was still fast!  I'm not even
using the constants, but somehow they are helping the compiler
optimize the code.

In short, when I un-comment the constants, the code is super fast, but
when commented out, the code is slow, even though I never use them.

Does anyone know why this could be?

I've looked through tons of documentation but haven't found anything
like this.

Listing:
-------------------------------------------------------------------------------
with Ada.Text_IO;
with Ada.Numerics.Generic_Elementary_Functions;

procedure Bench is

   type Real is digits 15;
   type Real_Array is array(Integer range <>) of Real;

   package RMath is new
Ada.Numerics.Generic_Elementary_Functions(Real);
   use RMath;

   N : constant Natural := 10_000;

   --SINX : constant Real := Sin(0.5);
   --SINY : constant Real := Sin(1.0);
   --SINZ : constant Real := Sin(1.5);
   --LOGX : constant Real := Log(0.5);
   --LOGY : constant Real := Log(1.0);
   --LOGZ : constant Real := Log(1.5);
   --SQRTX : constant Real := Sqrt(0.5);
   --SQRTY : constant Real := Sqrt(1.0);
   --SQRTZ : constant Real := Sqrt(1.5);

   X, Y, Z : Real_Array(1 .. N) := (others => 0.0);

begin
   for J in 1 .. 10_000 loop
      for I in 1 .. N loop
         X(I) := X(I) + Real(J) + Sin(0.5)/1.5 + Log(0.5)/2.5 +
Sqrt(0.5)/3.3;
         Y(I) := Y(I) + Real(J) + Log(1.0)/1.5 + Sqrt(1.0)/2.5 +
Sin(1.0)/3.3;
         Z(I) := Z(I) + Real(J) + Sqrt(1.5)/1.5 + Sin(1.5)/2.5 +
Log(1.5)/3.3;
      end loop;
   end loop;

   Ada.Text_IO.Put_Line(Real'Image(X(N)) & Real'Image(Y(N)) &
Real'Image(Z(N)));
end Bench;

Re: GNAT Optimization of Constant Expressions

[Randy Brukardt]

"David Smith" <david.smith@gmail.com> wrote in message
news:1179355028.624745.258370@q75g2000hsh.googlegroups.com...
> In running some benchmarks between Ada, C, and Fortran, I came across
> a bizarre situation with GNAT.  The same algorithm ran 10x slower in
> Ada, so I surmised that the constant math expressions in the code
> below were being precomputed by the compiler in C and Fortran, but not
> in Ada.  To test my hypothesis, I defined the commented-out constants
> and replaced the math functions with the appropriate constant.  This
> worked, and the Ada code was then as fast at the others.  The
> bizarreness came out when I put the math expressions back in but left
> in the constant declarations.  The code was still fast!  I'm not even
> using the constants, but somehow they are helping the compiler
> optimize the code.
>
> In short, when I un-comment the constants, the code is super fast, but
> when commented out, the code is slow, even though I never use them.
>
> Does anyone know why this could be?

It doesn't surprise me in the least; I'd expect Janus/Ada to work similarly,
in fact.

First of all, Sin and the like are regular functions in Ada; they're never
built in. I suspect that is different in your typical Fortran compiler. The
only thing that the compiler is likely to know about them in Ada is that
they are Pure, which means that the compiler can assume that two calls with
the same arguments return the same result.

As such, the compiler has to do a loop-hoisting optimization in order to
pre-evaluate these function calls. I suspect that from your results, Gnat
doesn't do such an optimization in this case. That doesn't surprise me, a
loop hoist can make the program run slower if the loop is never executed. I
don't think we do them at all. I would expect that Gnat does in some
circumstances, but for some reason it doesn't notice that the loops are
going to execute far more than zero times.

Anyway, if you explicitly declare the constants, the situation changes.
First of all, these sorts of constants will most likely be implemented much
like initialized variables (the value being stored in memory). That's one
probably one of the reasons why Gnat doesn't do the optimization (extra
memory use). But if you explicitly declare them, there no longer is any
extra memory.

Moreover, doing so changes the optimization from loop hoisting (which is
done in limited circumstances) to common subexpression elimination (which is
done whenever possible). [I'm speaking about these optimizations in
Janus/Ada here, I have no knowledge of how Gnat/GCC divide up these
optimizations; but I'd expect it to be similar.] Since these are Pure
function calls, the compiler can replace the later uses by your explicitly
declared constants, and thus get your observed speedup.

Without the constants, the compiler would have to effectively declare them
itself, and there are a number of reasons that the compiler might not choose
to do that (as previously mentioned). In any case, the best rule for a
compiler optimizer is to implement what was written if you cannot be sure
that the optimization will be faster/smaller. So I'm not surprised.

After all, your original code is written to make a bunch of very expensive
calls ("Sin(0.5)", for instance) many times. Expecting the compiler to
remove those calls is asking a lot; it is much better to avoid making extra
calls with appropriate constant declarations. (I'd have that advice for any
language; why force the optimizer to work hard and possibly fail??)

                            Randy.

Re: GNAT Optimization of Constant Expressions

[Martin Krischik]

David Smith wrote:

> comp.lang.ada
> In running some benchmarks between Ada, C, and Fortran, I came across
> a bizarre situation with GNAT.

Which compiler version? I ask because this is not the first time we noticed
some strange effect - where compiler versions did make some difference.
Read:

http://gnuada.sourceforge.net/pmwiki.php/Main/Performance

It's a Wiki, you are welcome to add your experiences. A quote of the Fortran
and C code - along with the compiler options -  might be helpfull as well.

Note that we also issued bug in bugzilla.

Martin
-- 
mailto://krischik@users.sourceforge.net
Ada programming at: http://ada.krischik.com

Re: GNAT Optimization of Constant Expressions

[Gautier]

Randy:

[a brilliant dissertation about optimization]
> After all, your original code is written to make a bunch of very expensive
> calls ("Sin(0.5)", for instance) many times. Expecting the compiler to
> remove those calls is asking a lot;

I agree for any function call, but in the special case of functions from 
Generic_Elementary_Functions, it is _not_ asking a lot! A decent compiler 
should perform optimizations around these functions as well as around 
arithmetic operators.

> it is much better to avoid making extra
> calls with appropriate constant declarations. (I'd have that advice for any
> language; why force the optimizer to work hard and possibly fail??)

Obviously, there are compilers where the optimizer is working hard for the 
programmer, and other ones where the programmer has to work hard to make the 
optimizer work!

______________________________________________________________
Gautier         -- http://www.mysunrise.ch/users/gdm/index.htm
Ada programming -- http://www.mysunrise.ch/users/gdm/gsoft.htm

NB: For a direct answer, e-mail address on the Web site!

Re: GNAT Optimization of Constant Expressions

[Randy Brukardt]

"Gautier" <gautier@fakeaddress.nil> wrote in message
news:464cb4cd$1_3@news.bluewin.ch...
> Randy:
>
> [a brilliant dissertation about optimization]
> > After all, your original code is written to make a bunch of very
expensive
> > calls ("Sin(0.5)", for instance) many times. Expecting the compiler to
> > remove those calls is asking a lot;
>
> I agree for any function call, but in the special case of functions from
> Generic_Elementary_Functions, it is _not_ asking a lot! A decent compiler
> should perform optimizations around these functions as well as around
> arithmetic operators.

It is reasonable for the fact that these are pure functions to be detected
and used, but that is about it. (And that has nothing special to do with
these functions, it is true for just about all pure functions.)

Keep in mind that floating point optimization is very hard; most of the
typical optimizations that you do on integer types would change the result
of a floating point expression. And, if those are carefully crafted
numerical expressions, the "optimization" could actually cause the code to
fail.

One example is:
     Y := (X - 0.5) - 0.5;

You might think that replacing this with
    Y := X - 1.0;
would be a good idea, but actually it reduces the accuracy of the result -- 
which is probably the reason that the programmer wrote the above in the
first place. Similarly, changing
   X + (Y + Z) into (X + Y) + Z can change the accurracy a lot.

The net effect is, with a truly good compiler, you have to write the
floating point expression that you mean and expect limited optimizations.
Either that or decide you don't care about accuracy (which is how C
compilers tend to handle this). I know that Gnat worries about these issues
a lot (I've heard Robert Dewar talk about them on many occassions).

There are optimizations that you can do safely, like common subexpression
evaluation, but there are many fewer of them than you have with integer
optimizations. Luckily, most of the code in a program (any program, once you
take address calculations like array indexing into account) is integer code.
It is very important to do a good job on integer expressions, much less
valuable of float ones (because of the limited things that you can do).

> > it is much better to avoid making extra
> > calls with appropriate constant declarations. (I'd have that advice for
any
> > language; why force the optimizer to work hard and possibly fail??)
>
> Obviously, there are compilers where the optimizer is working hard for the
> programmer, and other ones where the programmer has to work hard to make
the
> optimizer work!

<Grin>. But that wasn't the point. The point was that a careful compiler
*must* not do much optimization on float expressions, because doing so would
change the results and break carefully crafted numeric code. So it is
necessary to *write* what you mean, since the compiler can only help you if
it is sloppy (and thus will cause trouble later).

                            Randy.

Re: GNAT Optimization of Constant Expressions

[David Smith]

> > I agree for any function call, but in the special case of functions from
> > Generic_Elementary_Functions, it is _not_ asking a lot! A decent compiler
> > should perform optimizations around these functions as well as around
> > arithmetic operators.

The purpose in leaving them in was to test this aspect of the
optimization process.  This is a very common expression to see in
legacy scientific codes written by novices, and I wanted to know if
GNAT can handle naive structures as well as Fortran compilers do.  If
it can't, then many scientists and potential Ada converts will be
turned off because they'll write a naive bit of code for a benchmark
and find that Ada is much slower than Fortran without trying to
understand why.

I understand that the FP ops are not associative, but doesn't the gcc -
O3 imply that the user chooses speed over accuracy?  And especially if
the user passes -ffast-math the compiler should get the hint.

> There are optimizations that you can do safely, like common subexpression
> evaluation, but there are many fewer of them than you have with integer
> optimizations. Luckily, most of the code in a program (any program, once you
> take address calculations like array indexing into account) is integer code.
> It is very important to do a good job on integer expressions, much less
> valuable of float ones (because of the limited things that you can do).

This may be true, but FP ops are very expensive, so trimming those can
potentially save more than you might think.    In this example, the
common expression elimination speeds the code up by a factor of 10,
roughly.

-Dave

Re: GNAT Optimization of Constant Expressions

[Randy Brukardt]

"David Smith" <david.smith@gmail.com> wrote in message
news:1179442153.169828.109970@l77g2000hsb.googlegroups.com...
>
> > > I agree for any function call, but in the special case of functions
from
> > > Generic_Elementary_Functions, it is _not_ asking a lot! A decent
compiler
> > > should perform optimizations around these functions as well as around
> > > arithmetic operators.
>
> The purpose in leaving them in was to test this aspect of the
> optimization process.  This is a very common expression to see in
> legacy scientific codes written by novices, and I wanted to know if
> GNAT can handle naive structures as well as Fortran compilers do.  If
> it can't, then many scientists and potential Ada converts will be
> turned off because they'll write a naive bit of code for a benchmark
> and find that Ada is much slower than Fortran without trying to
> understand why.

Fair enough, but this seems to be the wrong question to ask. The question is
whether it is fast enough for the application, not whether it is as fast as
some other language that doesn't have the same requirements. Anything else
is premature optimization. And, in addition, can the code be made fast if it
actually matters. (I have serious doubts about the value of "naive"
numerical code, but I'll leave that rant for some other time...)

> I understand that the FP ops are not associative, but doesn't the gcc -
> O3 imply that the user chooses speed over accuracy?  And especially if
> the user passes -ffast-math the compiler should get the hint.

I don't agree. Ada has fairly strict requirements on accuracy that C and
Fortran don't have. An optimizer shouldn't be providing the *wrong* answer
in order to make code fast; so I doubt that -O3 would have that effect on an
Ada program (where it might for C).. I realize that Ada 95 made those
accuracy requirements optional, but I think that most Ada compilers (which
have Ada 83 roots) make the strict mode their default. And since the strict
mode necessarily encorporates any relaxed mode, it's quite likely that they
never deviate from it. I don't know Gnat well enough to comment on whether
it has a separate relaxed mode.

> > There are optimizations that you can do safely, like common
subexpression
> > evaluation, but there are many fewer of them than you have with integer
> > optimizations. Luckily, most of the code in a program (any program, once
you
> > take address calculations like array indexing into account) is integer
code.
> > It is very important to do a good job on integer expressions, much less
> > valuable of float ones (because of the limited things that you can do).
>
> This may be true, but FP ops are very expensive, so trimming those can
> potentially save more than you might think.    In this example, the
> common expression elimination speeds the code up by a factor of 10,
> roughly.

No, FP isn't very expensive. "Elementary function" library calls that may
execute hundreds of lines of code are expensive! (Keep in mind that Ada's
accuracy rules prevent Ada compilers from using the hardware support for
Sin/Cos/Tan -- it's not accurate enough.) You can write a lot of interesting
FP code (statistics, for instance) without using any elementary functions
other than Sqrt. And the use of constants as arguments to those expensive
routines is pretty silly. (Besides, good Ada practice would be to name your
constants, and when you did that, you got essentially the same code as with
Fortran.)

None of which is to say that common subs shouldn't be handled, but there is
a big difference between hoisting expressions and simply avoiding duplicate
evaluations. The former can make code larger and slower if done
inappropriately. It may simply not be worth doing, if it doesn't help most
programs. Of course, you can always write a program that it does help (like
yours), but one has to allocate ones resources based on the value to all
customers and all programs, not just one.

(And please remember I know nothing at all about Gnat's actual optimization
technology. This might just be a bug in something that is supposed to work.)

                                Randy.

Re: GNAT Optimization of Constant Expressions

[Dmitry A. Kazakov]

On Thu, 17 May 2007 18:38:34 -0500, Randy Brukardt wrote:

[...]
> And the use of constants as arguments to those expensive
> routines is pretty silly. (Besides, good Ada practice would be to name your
> constants, and when you did that, you got essentially the same code as with
> Fortran.)

I think that it not a good idea to rely on good practice. There is a
language problem of specifying that the calls to a function with static
constant shall yield static result. This is not just sin (Pi/3.0), but also

   for ... loop
      if Match (Text, <pattern-expression>) then

or

   Create_Combo_Box ("ada" + "c" +  "c++" + ...);

or

   5.0 * m + 10.0 * feet

Folding self-descriptive expressions into constants declared miles away
from their only use is not a good style.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: GNAT Optimization of Constant Expressions

[Markus E Leypold]

Randy Brukardt wrote:
> "David Smith" <david.smith@gmail.com> wrote in message
> news:1179355028.624745.258370@q75g2000hsh.googlegroups.com...

<lots of interesting stuff>

Wow. That was instructive. Thanks.

Regards -- Markus

Re: GNAT Optimization of Constant Expressions

[Florian Weimer]

* Randy Brukardt:

> As such, the compiler has to do a loop-hoisting optimization in order to
> pre-evaluate these function calls. I suspect that from your results, Gnat
> doesn't do such an optimization in this case. That doesn't surprise me, a
> loop hoist can make the program run slower if the loop is never executed.

Not really.  I suppose GCC special-cases the zero times case anyway
because it transforms the loop into a do-while-style loop, which is
easier to optimize.

It's more likely that the run-time library lacks a few Pure_Function
pragmas, so the compiler does not know that it's a constant
expression.  Ideally, GNAT would translate the function calls to GCC
built-in calls, so that they can be expanded at compile time.  This
optimization probably kicks in for C and Fortran, whose front ends are
more closely aligned with the rest of the compiler.

Re: GNAT Optimization of Constant Expressions

[Duncan Sands]

> In running some benchmarks between Ada, C, and Fortran, I came across
> a bizarre situation with GNAT. ...

Can you please post your C equivalent.

Thanks,

Duncan.

Re: GNAT Optimization of Constant Expressions

[Georg Bauhaus]

On Thu, 2007-05-17 at 18:38 -0500, Randy Brukardt wrote:

>  Ada has fairly strict requirements on accuracy that C and
> Fortran don't have. An optimizer shouldn't be providing the *wrong* answer
> in order to make code fast;

An Apple employee once recommended using the then new FPT
optimizations and to see whether the optimized program will meet
the expectations. ("You can always sell speed".) So maybe accurate
computation is a far reaching requirement for some software
markets.

Re: GNAT Optimization of Constant Expressions

[Duncan Sands]

> ...  Ideally, GNAT would translate the function calls to GCC
> built-in calls, so that they can be expanded at compile time.  This
> optimization probably kicks in for C and Fortran, whose front ends are
> more closely aligned with the rest of the compiler.

This seems to be close to the truth.  If I use llvm-gcc to compile the
testcase (at -O3) then the calls to sin etc are removed altogether:
they are evaluated at compile time.  Why?  Well, because llvm-gcc doesn't
handle inline floating point assembler on x86, I modified the elementary
functions package to call the implementations of sin etc in the C library.
The LLVM optimizers recognize these C library functions and precompute them.
So why doesn't GNAT use the C library functions?  Presumably because they don't
satisfy the accuracy requirements of the Ada standard [*].  Instead, for each
platform, GNAT implements them itself, hopefully more accurately.  This usually
means reducing arguments down to a range in which the processor's floating point
instructions give accurate results, then executing that instruction.  I think
the GNAT approach is a mistake: instead of using inline assembler, it should call
the corresponding C library function at that point.  Thus it would do range
reduction then call the C routine.  This means that constants would be evaluated
at compile time etc for free, while keeping accuracy.

Ciao,

Duncan.

[*] It is not clear to me if this is true nowadays.  A quick peek shows the C
routines using a quick but maybe inaccurate implementation only if "fast math"
is enabled.

Re: GNAT Optimization of Constant Expressions

[David Smith]

Thanks for the interesting discussion.  I always learn so much on this
group.

> Can you please post your C equivalent.

Of course:

#include <stdio.h>
#include <math.h>

int
main()
{
   const int N = 10000;
   int i, j;
   double x[N], y[N], z[N];
   //const double sinx = sin(0.5);
   //const double siny = sin(2.0*0.5);
   //const double sinz = sin(3.0*0.5);
   //const double logx = log(0.5);
   //const double logy = log(2.0*0.5);
   //const double logz = log(3.0*0.5);
   //const double sqrtx = sqrt(0.5);
   //const double sqrty = sqrt(2.0*0.5);
   //const double sqrtz = sqrt(3.0*0.5);

   for (j=1; j<=10000; ++j)
      for (i=0; i<N; ++i)
      {
         x[i] += j + sin(0.5)/1.5 + log(0.5)/2.5 +
                 sqrt(0.5)/3.3 ;
         y[i] += j + log(2.0*0.5)/1.5 + sqrt(2.0*0.5)/2.5 +
                 sin(2.0*0.5)/3.3 ;
         z[i] += j + sqrt(3.0*0.5)/1.5 + sin(3.0*0.5)/2.5 +
                 log(3.0*0.5)/3.3 ;
      }

   printf("%g %g %g\n", x[N-1], y[N-1], z[N-1]);

   return 0;
}

Re: GNAT Optimization of Constant Expressions

[Ray Blaak]

"Randy Brukardt" <randy@rrsoftware.com> writes:
> One example is:
>      Y := (X - 0.5) - 0.5;
> 
> You might think that replacing this with
>     Y := X - 1.0;
> would be a good idea, but actually it reduces the accuracy of the result

I don't understand this. Both 0.5 and 1.0 have "exact" binary representations
right? 

Can you give a value of X where this would hold?

-- 
Cheers,                                        The Rhythm is around me,
                                               The Rhythm has control.
Ray Blaak                                      The Rhythm is inside me,
rAYblaaK@STRIPCAPStelus.net                    The Rhythm has my soul.

Re: GNAT Optimization of Constant Expressions

[Duncan Sands]

> > Can you please post your C equivalent.
> 
> Of course:

Thanks.  As expected, the sin etc function calls have
been replaced with explicit constants before the real gcc
optimizers even run!  "Fold" is responsible.  The difference
with Ada is that the Ada sin etc functions are not recognized
by fold.

Ciao,

Duncan.

Re: GNAT Optimization of Constant Expressions

[Randy Brukardt]

"Florian Weimer" <fw@deneb.enyo.de> wrote in message
news:87k5v631kp.fsf@mid.deneb.enyo.de...
...
> It's more likely that the run-time library lacks a few Pure_Function
> pragmas, so the compiler does not know that it's a constant
> expression.  Ideally, GNAT would translate the function calls to GCC
> built-in calls, so that they can be expanded at compile time.  This
> optimization probably kicks in for C and Fortran, whose front ends are
> more closely aligned with the rest of the compiler.

That doesn't match the OP's original description of the problem. He said
that declaring constants in front of the expression made it run fast, even
if they were *not used* in the expression in the loop. That could only
happen if the compiler did a common subexpression elimination in that case,
and a common subexpression elimination is *only* valid on a function call if
it is Pure. (Other functions could have significant side effects that
eliminating the extra calls would make the program incorrect, for example if
the function is a random number generator.)

I think it is more likely that it didn't recognize the functions as being
worth hoisting (there is only one instance of each in the original program)
or it didn't do so because of other concerns. In thinking about it now, the
former is probably more likely.

                         Randy.

Re: GNAT Optimization of Constant Expressions

[Randy Brukardt]

"Georg Bauhaus" <bauhaus@futureapps.de> wrote in message
news:1179487665.6721.7.camel@localhost.localdomain...
> On Thu, 2007-05-17 at 18:38 -0500, Randy Brukardt wrote:
>
> >  Ada has fairly strict requirements on accuracy that C and
> > Fortran don't have. An optimizer shouldn't be providing the *wrong*
answer
> > in order to make code fast;
>
> An Apple employee once recommended using the then new FPT
> optimizations and to see whether the optimized program will meet
> the expectations. ("You can always sell speed".) So maybe accurate
> computation is a far reaching requirement for some software
> markets.

I think it is generally agreed these days that the Ada accuracy requirements
were a mistake, because they put Ada at a competitive disadvantage compared
to other languages for floating point math. Indeed, that is why they were
moved into "strict mode" in Ada 95. The problem is, faced with the need to
implement strict mode anyway, implementers have tended to avoid implementing
relaxed modes, because extra modes simply doubles the implementation and
testing effort - the fewer modes the better. And the argument is "who wants
less accuracy anyway?".

We talked briefly about dropping the accuracy requirements altogether this
time, but its obvious that would screw anyone that was depending on them.
And that didn't seem like a good idea. So Ada is rather stuck with its
slower but predictably accurate math. (In practice, this really only matters
in programs with intensive FP, like the OP's example.)

                      Randy.

Re: GNAT Optimization of Constant Expressions

[Duncan Sands]

PS: If you disable fold, then the function calls are hoisted
out of the loop if you mark sin etc with attribute "const",
but not if you mark them as "pure".  Now why aren't they
being marked "const" in the Ada case?  The gcc notion "const"
corresponds pretty much to Ada's notion of Pure.  In decl.c,
there is logic to mark a function as "const" if Is_Pure (an
internal Ada attribute) is true.  However Is_Pure is returning
false for the math functions.  Why?  I will investigate - but
whatever the reason it's basically a front-end bug.

Ciao,

Duncan.

Re: GNAT Optimization of Constant Expressions

[Duncan Sands]

Hi Randy,

> That doesn't match the OP's original description of the problem. He said
> that declaring constants in front of the expression made it run fast, even
> if they were *not used* in the expression in the loop. That could only
> happen if the compiler did a common subexpression elimination in that case,
> and a common subexpression elimination is *only* valid on a function call if
> it is Pure. (Other functions could have significant side effects that
> eliminating the extra calls would make the program incorrect, for example if
> the function is a random number generator.)
> 
> I think it is more likely that it didn't recognize the functions as being
> worth hoisting (there is only one instance of each in the original program)
> or it didn't do so because of other concerns. In thinking about it now, the
> former is probably more likely.

while what you say is very logical, unfortunately it seems to be wrong: I
checked and these functions are not being marked pure.  So how come declaring
a constant helps?  I don't know - I didn't look into it yet.

Ciao,

Duncan.

Re: GNAT Optimization of Constant Expressions

[Randy Brukardt]

"Ray Blaak" <rAYblaaK@STRIPCAPStelus.net> wrote in message
news:u1whep09x.fsf@STRIPCAPStelus.net...
> "Randy Brukardt" <randy@rrsoftware.com> writes:
> > One example is:
> >      Y := (X - 0.5) - 0.5;
> >
> > You might think that replacing this with
> >     Y := X - 1.0;
> > would be a good idea, but actually it reduces the accuracy of the result
>
> I don't understand this. Both 0.5 and 1.0 have "exact" binary
representations
> right?
>
> Can you give a value of X where this would hold?

I'm not a numerical analysist, I only play at one when implementing
compilers... ;-) but let me give my understanding.

If the machine does not keep extra precision between operations (that is,
the floating point registers are the same size as the in-memory
representation), and abs X is < 1.0, then
    (X - 0.5) - 0.5
will have one more bit of precision than
    X - 1.0
will. That occurs because in order to add or subtract, the smaller value has
to be shifted to match the larger value, which will cause bits to fall off
the end of the smaller value. 1.0 requires more shifting than 0.5 does. This
sort of expression is common in trig. libraries (for instance, in a software
implementation of Sin). And a trig. library is the last place that you would
want a hair-brained optimizer losing accuracy!

It should be pointed out that on Intel hardware, the original condition does
not hold (extra precision *may* be kept between operations). However, it
still might hold if common subexpressions are preevaluated into memory (as
in the OP's program with the unused constants). Thus, the optimizer still
has to be wary of reordering (and most optimizers are designed to work on a
variety of hardware, not just Intel chips.).

                           Randy.

Re: GNAT Optimization of Constant Expressions

[Duncan Sands]

> while what you say is very logical, unfortunately it seems to be wrong: I
> checked and these functions are not being marked pure.  So how come declaring
> a constant helps?  I don't know - I didn't look into it yet.

I took a quick look.  At -O2 defining constants makes no difference (in the
C case "const" functions are hoisted out of the loop at -O2) but with -O3
the calls are hoisted.  This is presumably because gcc inlines the bodies
for sin etc at -O3 and sees that in fact they have no side-effects, but
for some reason doesn't hoist them unless the constants have been defined.

Ciao,

Duncan.

Re: GNAT Optimization of Constant Expressions

[Adam Beneschan]

On May 18, 10:40 am, "Randy Brukardt" <r...@rrsoftware.com> wrote:

> I'm not a numerical analysist, I only play at one when implementing
> compilers... ;-) but let me give my understanding.
>
> If the machine does not keep extra precision between operations (that is,
> the floating point registers are the same size as the in-memory
> representation), and abs X is < 1.0, then
>     (X - 0.5) - 0.5
> will have one more bit of precision than
>     X - 1.0
> will. That occurs because in order to add or subtract, the smaller value has
> to be shifted to match the larger value, which will cause bits to fall off
> the end of the smaller value. 1.0 requires more shifting than 0.5 does.

I tried it with an imaginary machine that supports only an 8-bit
mantissa, so that floating-point numbers have the form 1.abcdefgh *
(2**exponent).  Suppose X has an exponent of -4, so that the value of
X is essentially 0.0001abcdefgh.  Now, when we subtract 1.0, and we
line things up, the efgh bits will fall off, giving

       0.0001abcd
     - 1.00000000

with the result being negative (0.1110a'b'c'd' + .00000001); I'm using
' to indicate the complement of a bit.  To normalize the result, it
needs to be shifted one bit to the left; the question is, what bit
gets shifted in on the right?  Is it related to "e", or is it always
0, or what?  I don't know that much about the details of floating-
point hardware, so I don't know the answer to this.

If we subtract 0.5, then only fgh will fall off:

       0.0001abcde
     - 0.100000000  (since there will be 8 bits of mantissa after the
first 1)

with the result being negative (0.0110a'b'c'd'e' + 0.000000001).  As
before, when we normalize this result, some other bit will be shifted
in on the right.  Then, since this is negative, when we subtract 0.5
again we're really adding 0.5; when we line things up, whatever bit
just got shifted in, will be shifted out again:

      (0.0110a'b'c'd'e' + 0.000000001)
     + 0.10000 0 0 0 0

giving 0.1110a'b'c'd'e' + 0.000000001.

So I suspect Randy is right, but I'm not sure.  If the hardware keeps
just one extra mantissa bit internally when it does the subtraction,
and uses the extra bit when it shifts left to normalize the result,
then I think the two expressions will always produce the same result.

I could have easily screwed up the math in the above.  Hopefully I
didn't.

                      -- Adam

Re: GNAT Optimization of Constant Expressions

[Randy Brukardt]

"Adam Beneschan" <adam@irvine.com> wrote in message
news:1179528686.946797.189500@w5g2000hsg.googlegroups.com...
> On May 18, 10:40 am, "Randy Brukardt" <r...@rrsoftware.com> wrote:
....
> So I suspect Randy is right, but I'm not sure.  If the hardware keeps
> just one extra mantissa bit internally when it does the subtraction,
> and uses the extra bit when it shifts left to normalize the result,
> then I think the two expressions will always produce the same result.

No, I think you have it right. The point is that if you subtract 1.0, you
depend on the hardware to do the right thing to preserve the last bit (which
is shifted out, then back in), whereas if you subtract 0.5 twice, you always
get the most accurate possible answer without worrying about what the
hardware does. Thus hardcore numerical programs do things like this so that
they don't depend on the characteristics of the hardware. Assuming an
optimizer doesn't screw that up...

Of course, if the hardware takes pains to preserve that extra bit (and a lot
of it does), none of this matters that much. Since most optimizers are at
least partially machine independent, however, they need to be careful; and
in any case, they need to avoid any optmizations which have the potential of
losing more bits.

                               Randy.