Floating point optimizations

Floating point optimizations

[Christian Keil]

Hi,

we are currently investigating some numerical algorithms and the claim
appeared that a C statement like
  x = c - (c - a);
would be easily transformed into
  x = a;
by the compiler. Now investigating this with a vanilla GCC 4.1.2 failed
to support the claim. Compiling the below program with -O3 -ffast-math
keeps the computation of x. The output shows x is different from a. The
question is, is there some compiler switch or the like to get GCC to
make the above transformation? I searched the docs but had the
impression that all relevant flags should be included in the above two
(especially ffast-math).

Please let me know if you need any additional information or if this is
the wrong list for this kind of question.

Cheers,
Christian

------8<--------
#include <stdio.h>
#include <stdlib.h>

int
main(void)
{
  double a, x;
  double c;

  scanf("%lf", &a);
  c = ((1 << 27) + 1) * a;
  x = c - (c - a);

  printf("a = %e(%a)\n", a, a);
  printf("x = %e(%a)\n", x, x);
}
------8<--------

-- 
Christian Keil                        /"\
Institute for Reliable Computing      \ /    ASCII Ribbon Campaign
Hamburg University of Technology       X  against HTML email & vCards
mail:c.keil@tu-harburg.de             / \

Re: Floating point optimizations

[John Fine]

The general concept of optimizations is to preserve the answer while 
reducing the time needed to compute the answer.  There are some cases in 
which an optimization fails to preserve the answer, but those usually 
occur in complex situations where the designer of the optimization had 
no practical way to avoid the difference.

As you noted c-(c-a) is routinely different from a.  Anyone designing 
optimizations would understand that.  So making that optimization would 
violate the general principle of optimization.

I don't know of any gcc option that might turn on that questionable 
"optimization".  I doubt that there is one, but I'm not certain there isn't.


Christian Keil wrote:

>Hi,
>
>we are currently investigating some numerical algorithms and the claim
>appeared that a C statement like
>  x = c - (c - a);
>would be easily transformed into
>  x = a;
>by the compiler. Now investigating this with a vanilla GCC 4.1.2 failed
>to support the claim. Compiling the below program with -O3 -ffast-math
>keeps the computation of x. The output shows x is different from a. The
>question is, is there some compiler switch or the like to get GCC to
>make the above transformation? I searched the docs but had the
>impression that all relevant flags should be included in the above two
>(especially ffast-math).
>
>Please let me know if you need any additional information or if this is
>the wrong list for this kind of question.
>
>Cheers,
>Christian
>
>------8<--------
>#include <stdio.h>
>#include <stdlib.h>
>
>int
>main(void)
>{
>  double a, x;
>  double c;
>
>  scanf("%lf", &a);
>  c = ((1 << 27) + 1) * a;
>  x = c - (c - a);
>
>  printf("a = %e(%a)\n", a, a);
>  printf("x = %e(%a)\n", x, x);
>}
>------8<--------
>
>  
>

Re: Floating point optimizations

[Alexander Monakov]

> we are currently investigating some numerical algorithms and the claim
> appeared that a C statement like
>   x = c - (c - a);
> would be easily transformed into
>   x = a;
> by the compiler. Now investigating this with a vanilla GCC 4.1.2 failed
> to support the claim. Compiling the below program with -O3 -ffast-math
> keeps the computation of x. The output shows x is different from a. The
> question is, is there some compiler switch or the like to get GCC to
> make the above transformation? I searched the docs but had the
> impression that all relevant flags should be included in the above two
> (especially ffast-math).

This transformation is indeed included into -ffast-math.  I checked with

$ gcc --version
gcc (GCC) 4.1.1 20070105 (Red Hat 4.1.1-52)

and it does eliminate the calculation.  What does generated assembly code look
like in your case?  Note you may as well check on this code:

double f(double a, double c)
{
  return c - (c - a);
}

HTH
--
Alexander Monakov

Re: Floating point optimizations

[Christian Keil]

John Fine schrieb:
> The general concept of optimizations is to preserve the answer while
> reducing the time needed to compute the answer.  There are some cases in
> which an optimization fails to preserve the answer, but those usually
> occur in complex situations where the designer of the optimization had
> no practical way to avoid the difference.
> 
> As you noted c-(c-a) is routinely different from a.  Anyone designing
> optimizations would understand that.  So making that optimization would
> violate the general principle of optimization.
I'm not quite sure about this claim.
What if the c-(c-a) appears as the result of some optimization of a more
complex expression? If someone writes this statement there is usually a
reason for doing this. But I'm not sure if this can be distinguished
from the case where it is an optimized version of a more complex expression.

> I don't know of any gcc option that might turn on that questionable
> "optimization".  I doubt that there is one, but I'm not certain there
> isn't.
Reading the documentation of -ffast-math I would have assumed it to do
exactly that
`-ffast-math'
     Sets `-fno-math-errno', `-funsafe-math-optimizations',
     `-fno-trapping-math', `-ffinite-math-only', `-fno-rounding-math',
     `-fno-signaling-nans' and `fcx-limited-range'.

     This option causes the preprocessor macro `__FAST_MATH__' to be
     defined.

     This option should never be turned on by any `-O' option since it
     can result in incorrect output for programs which depend on an
     exact implementation of IEEE or ISO rules/specifications for math
     functions.
You could imagine a (stupid) test for coming close to overflow f = f +
1.0 - 1.0. This isn't optimized away with O3 but -ffinite-math-only
removes it. So it seems to be connected to reassociation with floats.
This seems to be introduced at least into GCC 4.3.0 (see my answer to
Alexander Monakov).

Cheers,
Christian

-- 
Christian Keil                        /"\
Institute for Reliable Computing      \ /    ASCII Ribbon Campaign
Hamburg University of Technology       X  against HTML email & vCards
mail:c.keil@tu-harburg.de             / \

Re: Floating point optimizations

[Christian Keil]

Alexander Monakov schrieb:
> This transformation is indeed included into -ffast-math.  I checked with
> 
> $ gcc --version
> gcc (GCC) 4.1.1 20070105 (Red Hat 4.1.1-52)
> 
> and it does eliminate the calculation.  What does generated assembly code look
> like in your case?  Note you may as well check on this code:
> 
> double f(double a, double c)
> {
>   return c - (c - a);
> }
That's interesting. After your answer I checked with a gcc from Fedora
Core (Werewolf) and this removes it also. It seems like a backported
enhancement from vanilla gcc, version 4.3.0 does it as well.

Cheers,
Christian

-- 
Christian Keil                        /"\
Institute for Reliable Computing      \ /    ASCII Ribbon Campaign
Hamburg University of Technology       X  against HTML email & vCards
mail:c.keil@tu-harburg.de             / \

Re: Floating point optimizations

[Tim Prince]

Alexander Monakov wrote:
>> we are currently investigating some numerical algorithms and the claim
>> appeared that a C statement like
>>   x = c - (c - a);
>> would be easily transformed into
>>   x = a;
>> by the compiler. Now investigating this with a vanilla GCC 4.1.2 failed
>> to support the claim. Compiling the below program with -O3 -ffast-math
>> keeps the computation of x. The output shows x is different from a. The
>> question is, is there some compiler switch or the like to get GCC to
>> make the above transformation? I searched the docs but had the
>> impression that all relevant flags should be included in the above two
>> (especially ffast-math).
> 
> This transformation is indeed included into -ffast-math.  I checked with
> 
> $ gcc --version
> gcc (GCC) 4.1.1 20070105 (Red Hat 4.1.1-52)
> 
> and it does eliminate the calculation.  What does generated assembly code look
> like in your case?  Note you may as well check on this code:
> 
> double f(double a, double c)
> {
>
Normally, when such expressions are written in source code, there is a 
reasonable expectation that algebraic simplification will not be performed 
across parentheses.  That was one of the major changes between K&R style 
and the C89 standard, which adopted a convention which has been in Fortran 
since the f66 standard.  -ffast-math, or similar aggressive options in 
other compilers, are of diminished practical value without the ability to 
separate violation of parentheses from other optimizations.

Re: Floating point optimizations

[Andrew Haley]

Tim Prince wrote:
> Alexander Monakov wrote:
>>> we are currently investigating some numerical algorithms and the claim
>>> appeared that a C statement like
>>>   x = c - (c - a);
>>> would be easily transformed into
>>>   x = a;
>>> by the compiler. Now investigating this with a vanilla GCC 4.1.2 failed
>>> to support the claim. Compiling the below program with -O3 -ffast-math
>>> keeps the computation of x. The output shows x is different from a. The
>>> question is, is there some compiler switch or the like to get GCC to
>>> make the above transformation? I searched the docs but had the
>>> impression that all relevant flags should be included in the above two
>>> (especially ffast-math).
>>
>> This transformation is indeed included into -ffast-math.  I checked with
>>
>> $ gcc --version
>> gcc (GCC) 4.1.1 20070105 (Red Hat 4.1.1-52)
>>
>> and it does eliminate the calculation.  What does generated assembly
>> code look
>> like in your case?  Note you may as well check on this code:
>>
>> double f(double a, double c)
>> {
>>
> Normally, when such expressions are written in source code, there is a
> reasonable expectation that algebraic simplification will not be
> performed across parentheses.

There may well be such an expectation, but gcc only prevents re-association
across explicit parenthesis in FORTRAN, and it's only been doing that for
a few weeks.  

Andrew.

Re: Floating point optimizations

[NightStrike]

On 4/5/08, Andrew Haley <aph@redhat.com> wrote:
> Tim Prince wrote:
> > Alexander Monakov wrote:
> >>> we are currently investigating some numerical algorithms and the claim
> >>> appeared that a C statement like
> >>>   x = c - (c - a);
> >>> would be easily transformed into
> >>>   x = a;
> >>> by the compiler. Now investigating this with a vanilla GCC 4.1.2 failed
> >>> to support the claim. Compiling the below program with -O3 -ffast-math
> >>> keeps the computation of x. The output shows x is different from a. The
> >>> question is, is there some compiler switch or the like to get GCC to
> >>> make the above transformation? I searched the docs but had the
> >>> impression that all relevant flags should be included in the above two
> >>> (especially ffast-math).
> >>
> >> This transformation is indeed included into -ffast-math.  I checked with
> >>
> >> $ gcc --version
> >> gcc (GCC) 4.1.1 20070105 (Red Hat 4.1.1-52)
> >>
> >> and it does eliminate the calculation.  What does generated assembly
> >> code look
> >> like in your case?  Note you may as well check on this code:
> >>
> >> double f(double a, double c)
> >> {
> >>
> > Normally, when such expressions are written in source code, there is a
> > reasonable expectation that algebraic simplification will not be
> > performed across parentheses.
>
> There may well be such an expectation, but gcc only prevents re-association
> across explicit parenthesis in FORTRAN, and it's only been doing that for
> a few weeks.

Wait, so are things like "c - (c - a)" optimzed down to "a" or not?  I
use a lot of that in very time-intensive c++ code.

Re: Floating point optimizations

[Tim Prince]

NightStrike wrote:
> On 4/5/08, Andrew Haley <aph@redhat.com> wrote:
>> Tim Prince wrote:
>>> Alexander Monakov wrote:
>>>>> we are currently investigating some numerical algorithms and the claim
>>>>> appeared that a C statement like
>>>>>   x = c - (c - a);
>>>>> would be easily transformed into
>>>>>   x = a;
>>>>> by the compiler. Now investigating this with a vanilla GCC 4.1.2 failed
>>>>> to support the claim. Compiling the below program with -O3 -ffast-math
>>>>> keeps the computation of x. The output shows x is different from a. The
>>>>> question is, is there some compiler switch or the like to get GCC to
>>>>> make the above transformation? I searched the docs but had the
>>>>> impression that all relevant flags should be included in the above two
>>>>> (especially ffast-math).
>>>> This transformation is indeed included into -ffast-math.  I checked with
>>>>
>>>> $ gcc --version
>>>> gcc (GCC) 4.1.1 20070105 (Red Hat 4.1.1-52)
>>>>
>>>> and it does eliminate the calculation.  What does generated assembly
>>>> code look
>>>> like in your case?  Note you may as well check on this code:
>>>>
>>>> double f(double a, double c)
>>>> {
>>>>
>>> Normally, when such expressions are written in source code, there is a
>>> reasonable expectation that algebraic simplification will not be
>>> performed across parentheses.
>> There may well be such an expectation, but gcc only prevents re-association
>> across explicit parenthesis in FORTRAN, and it's only been doing that for
>> a few weeks.
> 
> Wait, so are things like "c - (c - a)" optimzed down to "a" or not?  I
> use a lot of that in very time-intensive c++ code.
Yes, for C and C++ with -ffast-math.

Re: Floating point optimizations

[me22]

On Sat, Apr 5, 2008 at 9:06 AM, NightStrike <nightstrike@gmail.com> wrote:
>  Wait, so are things like "c - (c - a)" optimized down to "a" or not?  I
>  use a lot of that in very time-intensive c++ code.
>

I think only if you tell it to be loose with requirements for applying
floating-point math optimizations (-ffast-math and related), since
DBL_MAX - (DBL_MAX-1) is, to the best of my knowledge, 0 --- not 1 ---
in IEEE math.

On the other hand, I managed to get >1 by adding DBL_EPSILON/10 to 1.0
repeatedly (though only on 1 of 4 computers on which I tried it) so my
intuitions could all be wrong.