Re: Algorithm Optimization

From	Thomas Koenig <tkoenig@netcologne.de>
Newsgroups	comp.compilers
Subject	Re: Algorithm Optimization
Date	2020-09-17 06:39 +0000
Organization	news.netcologne.de
Message-ID	<20-09-043@comp.compilers> (permalink)
References	<20-09-032@comp.compilers> <20-09-037@comp.compilers> <20-09-040@comp.compilers>

Show all headers | View raw

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.

Back to comp.compilers | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

Algorithm Optimization "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2020-09-13 13:00 -0400
  Re: Algorithm Optimization Elijah Stone <elronnd@elronnd.net> - 2020-09-14 20:47 -0700
    Re: Algorithm Optimization "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2020-09-15 00:42 -0400
  Re: Algorithm Optimization "Derek M. Jones" <derek@_NOSPAM_knosof.co.uk> - 2020-09-15 14:29 +0100
    Re: Algorithm Optimization gah4 <gah4@u.washington.edu> - 2020-09-15 22:25 -0700
      Re: Algorithm Optimization "Derek M. Jones" <derek@_NOSPAM_knosof.co.uk> - 2020-09-16 20:11 +0100
      Re: Algorithm Optimization Richard Harnden <richard.nospam@gmail.com> - 2020-09-16 22:45 +0100
      Re: Algorithm Optimization Hans-Peter Diettrich <DrDiettrich1@netscape.net> - 2020-09-17 06:35 +0200
        Re: Algorithm Optimization "A. K." <minforth@arcor.de> - 2020-09-21 02:12 -0700
      Re: Algorithm Optimization "Johann 'Myrkraverk' Oskarsson" <johann@myrkraverk.com> - 2021-04-21 16:29 +0000
  Re: Algorithm Optimization "mwmarkland@gmail.com" <mwmarkland@gmail.com> - 2020-09-16 07:57 -0700
    Re: Algorithm Optimization "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2020-09-16 11:44 -0400
    Re: Algorithm Optimization gah4 <gah4@u.washington.edu> - 2020-09-16 13:59 -0700
      Re: Algorithm Optimization Thomas Koenig <tkoenig@netcologne.de> - 2020-09-17 06:39 +0000
  Re: Algorithm Optimization Hans-Peter Diettrich <DrDiettrich1@netscape.net> - 2020-12-13 23:13 +0100
    Re: Algorithm Optimization gah4 <gah4@u.washington.edu> - 2020-12-20 22:45 -0800

csiph-web