Subject: Re: associativefp vs idealized numerics

From: [email-masked]
Date: Mon, 14 Sep 1998 14:39:49 -0400

Your reply does not address the fundamental question I raised: do we want
to prohibit a compiler from replacing
x*2 with x+x or x*7-6*x with x, or x^2 with x*x?  All those are
optimizations commonly done by current compilers, all those make a
significant improvement
in the performance of some codes, all those are disallowed by the
associatefp rules.  My point is not that I want compilers to replace an n^3
matrix product with
Strassen's algorithm, my point is more prosaic: I don't want to disable
common optimizations.  Associativefp is an arbitrary choice that has
nothing to do with current compiler practice, and
nothing to do with any numerical stability considerations.  We either are
willing to leave to compiler writers the choice of resonable optimizations
(I don't think that current practice is so bad), or we do a serious effort
to pick up benign transformations that do not (usually?) introduce numeric
instabilities, and that make a significant difference in performance.  But
we do not draw an arbitrary line in the sand.

> 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.

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.

> 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.

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.

> Since Java has a strict mode, I see no point in trying to legislate in
> detail how relaxed is the relaxed mode

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

>  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.

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]

---

From: [email-masked]
Date: Tue, 15 Sep 1998 17:41:18 -0400

> Two of these transformations are legal even using strict floating
> point semantics.  Under IEEE 754 floating point, 2*x is equivalent to
> x+x.  Likewise, x*x is the same as x^2.  The legality of both of these
> transformations follow from the IEEE 754 standard section 5;
> conceptually, each IEEE operation acts as if it computed the exact
....
> Of course, all the transformations legal under strict semantics are
> also legal under associativefp.

Wrong.  The issue is not what IEEE 754 says, the issue is what the Java
standard says.
Replacement of x^2 (expressed in Java via the corresponding call to the
math library)
with the expression x*x is clearly illegal.

...
> Associativefp is neither arbitrary, capricious, nor ignorant of
> transformations compilers need to perform to make code run fast.

It is clearly ignorant of many transformations that are that are routinely
doen by current compilers.

---

From: "Joseph D. Darcy" <[email-masked]>
Date: Wed, 16 Sep 1998 13:20:38 -0700 (PDT)

Forwarded message:
>From darcy Wed Sep 16 13:18:56 1998
Subject: Re: associativefp vs idealized numerics
To: [email-masked]
Date: Wed, 16 Sep 1998 13:18:56 -0700 (PDT)
In-Reply-To: <[email-masked]> from "[email-masked]" at Sep 15, 98 05:41:18 pm
X-Mailer: ELM [version 2.4 PL25]
MIME-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 8bit
Content-Length: 2044      

> Wrong.  The issue is not what IEEE 754 says, the issue is what the Java

The Java standard says to use IEEE 754 arithmetic.  Java standard says
to use the FDLIBM algorithms for the pow, sin, cos, etc.

> with the expression x*x is clearly illegal.

The FDLIBM algorithm for pow returns the correctly rounded value for
squaring.  Therefore, replacing Math.pow(x, 2.0) by x*x in Java *is*
legal.  Likewise, Math.pow(x, -1.0) can be replaced by 1.0/x.  For the
pow used in Java, if both the arguments are integers and the result is
also an integer, the pow method returns this integer value as long as
it is representable in the floating point format.

> doen by current compilers.

When designing a language (or most anything else) it is necessary to
make tradeoffs between different aspects of the final product.  For
example, the designers of Java wanted a simple, predictable
language.  Java's omission of parametric polymorphism and operator
overloading does not imply the Java designers were "ignorant" of these
features; rather, in their estimation, including those features would
compromise other goals of the design, such as simplicity.   While
their  decision can be debated, it should not be ascribed to
ignorance.

Over four decades ago, John Bachus felt compelled to make speed,
FORTRAN's overriding design goal to try to ensure people would use
FORTRAN in favor of of assembly language.  Times change.  Languages
today can and should have different goals than FORTRAN.  Not using
FORTRAN's semantics does not imply ignorance of FORTRAN optimization
techniques.

-Joe Darcy
[email-masked]

---

From: [email-masked]
Date: Tue, 22 Sep 1998 23:26:30 -0400

> replacing x = pow(y,2) with x= y*y is legal, ....

You are probably right, in principle, and I am probably wrong, in
principle. Just for the heck of it, I tried the following program, using
JDK 1.1.6 on Win95.

------------------------------------------------------------
import java.util.*;

public class Try{
     public static void main(String[] args) {
     double x = 1.0;
     double y = 0.0;
     Random seed = new Random();
     while(y == 0.0){
          x = seed.nextDouble();
          y = x*x - Math.pow(x,2.0);
          }
     System.out.println(x);
     System.out.println(y);
     }
}
-------------------------------------------------

It halted pretty fast, with the output

0.15461503094828766
3.469446951953614E-18

next attempt gives

0.391663617019943
-2.7755575615628914E-17

So reality is not yet where we want it to be.
---------------------------------------------------

> However, for Java to change, the needs of those writing webpage
> applets must be taken into account as well.  I do not think the
> majority of Java users are well served by the indeterminate floating
> point semantics of Fortran, regardless of how fast their programs
> might run.

What we have proposed is that the majority of Java servers would continue
to see the current strict Java semantics.  Any relaxation in floating point
semantics would obtain only if it is allowed by the program developer
(using IdealizedNumerics attribute), and if it is enabled by the JVM
environment.  So, our proposal involves STRICTER semantics for the majority
of Java users, and more flexibility for the minority that cares. The
argument is not about the default semantics, it is about allowing more
aggressive optimizations AS AN OPTION.

---------------------------------------------------------------------------
--

It seems that we are in agreement on the facts:
() associativefp can prevent performance enhancing compiler optimizations
that are currently used in other languages
() idealizedNumerics allows program transformations that cause loss of
precision, beyond what is already allowed by associativefp.
() any high-level program transformation that a compiler can do, a
programmer can do as well

We disagree on the consequences of these facts. I believe that disallowing
optimizations currently done by compilers, even as an option,
is a step backward. You seem to believe it is a step forward, because it
leads to a more controlled environment.

I am afraid that a continuation of the argument is unlikely to lead to a
convergence of oppinion.
Since both of us probably have better things to do, I suggest that we halt
here.

---

From: [email-masked] (Ronald F Boisvert)
Date: Wed, 23 Sep 1998 11:22:02 -0400

Marc and Joe,

Your debate in the JGF maining list has been quite illuminating.
I agree with Marc that the differences voiced are based on
fundamental philosphical principles, and that they are unlikely
to be resolved by email.  

I do not want the JavaGrande process to be stalled by this,
so I agree that we should call a halt for the time being.

The Numerics Working Group has been working on a consensus basis,
and, since there does not seem to be consensus on this issue, I
plan to adjust the report to state as much and try to summarize
the main points on each side.  It is my hope to do this in the
next week.  The report will be made into a "public draft" at that
point.

Ron Boisvert