Subject: associativefp vs idealized numerics

From: [email-masked]
Date: Thu, 10 Sep 1998 22:47:37 -0400

There is, apparently, an attempt to distinguish between "algorithm
transformations", that should not be done by the compiler, and "compiler
transformation", such as using associativity, which are OK for compilers.
I have no idea what is the basis for this distinction.  Languages, such as
Fortran, that relax strict operation ordering, clearly allow any
transformation that would be valid assuming infinite precsision, when order
is relaxed.  (Order is relaxed, in Fortran, for expression evaluation.)
Thus, in Fortran, a compiler can replace x= y*10001 - y*10000 with x=y,
even though the two expressions may have very different rounding errors,
and very different overflow conditions.  Note that this transformation uses
distributivity, not associativity.  Similarly, a Fortran compiler can
replace the expression y*10001 - 10000*y with y -- this requires now both
commutativity and distributivity.  Any such transformation may introduce
numeric instabilities, if used carelessly, but any such transformation will
allow compilers to improve code performance significantly, in some cases.
Since Java has a strict mode, I see no point in trying to legislate in
detail how relaxed is the relaxed mode, and I see no clear boundary line
between using associativity or using other field identities. As long as the
user and the code developer have the option of disabling potentially
harmful compiler optimizations, compiler developers should not be barred
from providing additional code transformations.

---

From: "Joseph D. Darcy" <[email-masked]>
Date: Sun, 13 Sep 1998 17:34:27 -0700 (PDT)

> I have no idea what is the basis for this distinction.

In the latter case the programmer can have some idea of what
transformations the compiler will perform while in the former case
that is not possible.

Pattern matching and replacement in compilers has been done before and
there have been several problems.  For example, what algorithms should
be pattern matched for?  Well, the likeliest candidates (perhaps the
only candidates) are the algorithms that occur in popular benchmark
programs.  Pattern matching for benchmark programs has at least two
problems:

* Such optimizations are very "brittle," a slight change in a program
may cause a drastic slowdown for no apparent reason.  Even if
generalized slightly, the pattern matching done for a benchmark
program may not be applicable to other programs (see the discussion of
023.eqntott at http://www.spec.org/osg/news/articles/news9512/eqntott.html).

* If benchmark performance is the only goal, the optimization may be
incorrect when different input data is used.  The data used for a
benchmark often does not cover the entire domain of a function (or
even a set of representative points).

Therefore, pattern matching for algorithms will probably not speed up
user code as much as in indicated by benchmark performance.  When
going from SPEC92 to SPEC95, SPEC introduced many rules to prohibit
compilers that were basically only guaranteed to generate working code
for SPEC92.

> allow compilers to improve code performance significantly, in some cases.

If you don't care what is computed, why do you care how fast it is
computed?

The original Java makes the design decision that "exact
reproducibility" is more important than performance.  That goal is not
tenable.  However, predictability can largely be maintained even when
the semantics are somewhat loosened.

> detail how relaxed is the relaxed mode

Putting some limits on relaxed mode prevents certain classes of
errors.

>  As long as the

I think it boils down to division of labor, what the compiler is
expected to do and what the programmer is expected to do.  Clearly,
the compiler should be responsible for low-level details like
instruction selection and scheduling appropriate for a given
environment.  Therefore, I think the programmer should be responsible
for indicating what algorithms should be used.  Presumably, the
programmer has more knowledge of the indented use of the program (such
as the distribution of inputs) than the compiler.  (The programmer
might not have much idea either.)  For example, while insertion sort
is slow in general, on nearly sorted arrays insertion sort is very
fast.  Simple quick sort is fast on average but a sorted array it the
worst case for naive quick sort (more complicated variants of quick
sort ameliorate this problem).  Therefore, a programmer that knowingly
chose to use insertion sort because of its behavior on nearly sorted
arrays would be rather annoyed if naive quick sort was substituted.

The programmer cannot indicate (and might not know) all the properties
of the program that should be preserved.  Likewise, the distribution
of input data may not be known or communicated.  This sort of
knowledge can be taken advantage of by specifying an appropriate
algorithm.

Associativefp is a parsimonious choice to allow Java to take advantage
of system specific details of the floating point pipeline.  Matrix
multiply can go fast using associativefp.

-Joe Darcy
[email-masked]