Re: optimization problem with 1.0.3

[Craig Burley <burley at gnu dot org>]

>f(x) is less than f(y)
>AND
>f(y) is less than f(x)
>
>Surely _this_ is bad?

It's "bad", but, again, it's an expected result of knowing that ==/!=
aren't comparisons for algebraic equivalence in floating-point and
that compilers pick different methods of approximation even when
computing algebraically similar results via algebraically identical
calculations.

If you want to get such stuff to work, store every result you care
about referencing more than exactly once to a variable with the
type and precision you care about, and use `-ffloat-store'.  I've
referenced this option multiple times -- I strongly suggest you
read up on it, among other references on floating-point programming,
and take the advice (along with the performance hit).

And, again, though I'm less confident in my modifications of the
generated assembly code (I had to replace the two `fcompl'
instructions with two `fldt'/`fcompp' pairs, in addition to the
obvious changes), they did produce an executable that ran without
printing anything -- as did simply compiling with -O3.  And, again,
`-ffloat-store' had no effect, as I expected.

The former suggests that, again, my proposal, if implemented to
include return values of functions (so they are spilled as 80-bit
values if that's what they are implemented as, by the compiler,
regardless of whether they're `float' or `double'), would "fix" *this*
particular example, and similarly simple ones.

But, I still think it's unlikely we, or any popular compiler, can
completely avoid this sort of thing, given sufficiently complexity
of code and perhaps compilation methods as well.  (For example,
two identical f() functions given different names would probably
optimize slightly differently if one is compiled with optimization
while the other is not.)

The problem is that, generally, the compiler is not only *allowed* to use
more precision whenever it likes and reorder commutative and other
mathematically, but not necessarily computationally, identical operations
however it likes, on the x86 architecture it is practically *required*
to do some of these things (especially use more precision) to achieve
the expected performance.  But whether optional, or required via
optimization flags and the resulting analysis permitting the optimizations,
the predictability of such decisions is too low to assume that
mathematically identical evaluations, even on computational identical
inputs, produce computationally identical results.

That's why you don't compare for equality, and why you mustn't assume
that seemingly "identical", but separately computed, values are
going to be computationally equal.  Which is just what you've done
in this latest example!

It does seem we're having to get into a lot of explaining about the
vagaries of using floating-point here, vagaries that apply *regardless*
of the actual underlying technology used.  Even though egcs+x86 have
more such vagaries than some other combinations, making them more
easily exposed, I don't believe any floating-point technology combination
actually deployed today is both absent any such vagaries *and* considered
worth using, in terms of performance.

As far as I know, texts that explain that ==/!= cannot be assumed to work
"algebraically" do not turn around and explain that </> can be used as
simple-minded substitutes.  Instead, the good ones explain that tests for
equality should include tolerances.

So, given that we know about some problems we can fix and a whole *ton*
of others we can't (partly because there isn't agreement throughout the
entire industry on how to fix these)...

...could you please stop worrying about failures to handle equality
exactly as you expect, and instead focus on whether egcs handles
the *proper* tests, which take into account the inherent lack of
precision of such computing (which depends on the code, not just the
compiler and processor), correctly?

For example, do your examples still fail to work as you expect if the
equality tests (and, yes, `<' is an equality test *if* you're contrasting
it to the result of `>' on a *differently computed value*, which is exactly
the case in your example) are replaced with something like

  fx = f(x);
  fy = f(y);
  tol = .0000001;
  if ((fx - tol) < (fy + tol)
      && (fx + tol) > (fy - tol))
    printf ("equal\n");

??  I *suspect* egcs works fine in these cases, though even the
calculations of ranges (values plus tolerance(s)) are subject to
the same vagaries of floating-point if they aren't coded carefully
(though I think I've avoided those problems in this example, which
is limited to the cases you submitted -- calculation of 1./3. using
`double' precision -- and wouldn't work for many others due to
differences in the precisions and tolerance values).

In the meantime, if you find any high-quality texts describing
programming in floating-point that say that your examples should
always work, even when scaled up to highly complicated codes,
please send us references to them.  We might find they also explain
just how these results should be achieved by compilers producing
high-performance code on modern processors.

Failing that, I think there is no need for you to reinvent the wheel
as far as re-discovering what so many people already know about
the vagaries of floating-point, and have written so much about, in
textbooks, refereed journals, and on the Internet.  But you might
find researching that material quite enlightening.  In my opinion,
your learning about that would be, at this point, more productive
for everyone than continuing to ask egcs developers about the
vagaries of floating-point programming.

        tq vm, (burley)