Re: Algorithm Optimization

gah4 <gah4@u.washington.edu> schrieb:
> On Wednesday, September 16, 2020 at 8:14:44 AM UTC-7,
> mwmar...@gmail.com wrote:
>
> (snip)
>
>> This approaches the issue more from a "I want to replace serial
>> algorithms with parallel algorithms." if I recall correctly so it may
>> not be exactly what you are looking for.
>
> That might make more sense. So, an algorithm that it mathematically
> equivalent, but not necessarily numerically equivalent.


Hic sunt dracones.


Re-arranging mathematically equivalent operation can lead to
surprising side effects, and are prohibited by many language
standards. Yet, compilers very often have optimizations to switch
off the guarantees of these standards, and they are often used by
users ignorant of the issues (and for benchmarks).


An example is Kahan summation, which is an algorithm for reducing
numerical errors in summing up terms. It is mathematically
equivalent to straightforward summation, so a compiler which
operates on mathematical equivalence across statements
can in fact convert Kahan summation back to simple summation.


This, of course, loses the benefit that the programmer (presumably)
wanted.


Gcc, for example, will happily do that transformation if given
the -funsafe-math-optimization flag (which, despite what the name
implies, is neither fun nor safe). The problem is that this is one
of the flags enabled with the catch-all option with the suggestive
name -Ofast.

Return to the comp.compilers page.
Search the comp.compilers archives again.