Subject: Re: associativefp vs idealized numerics

From: [email-masked]
Date: Thu, 17 Sep 1998 10:12:04 -0400

replacing x = pow(y,2) with x= y*y is illegal, not because of different
rounding errors, but because of different exceptions that can arise.  A
compiler can make this substitution only if it can show that no exceptions
will be raised.  I think we both agree that associatevefp prevents the
replacement of x*2-x by x and other similar optimizations.  associatievefp
will not allow to replace a linear recurrence x[i+1] = a*x[i] +b with a
parallel prefix computation.

I don't think we make progress with this mail exchanges, we will need to
hash it our face to face.  Fundamentally, your position is that compilers
can do awful things, therefore, let's make sure they are forbidden to
manipulate the code.  My position is that compilers can do good things,
let's make sure they are not prevented from doing it.  I prefer to be
permissive rather than authoritarian, and let the market prune out bad
compilers.  This has nothing to do with good or bad language design, with
Java goals vs Fortran goals.

Marc Snir, Senior Manager
Scalable Parallel Systems
Tel: 914-945-3204 (8-862-3204)
Fax: 914-945-4425 (8-862-4425)
URL: http://www.research.ibm.com/people/s/snir

---

From: "Joseph D. Darcy" <[email-masked]>
Date: Sun, 20 Sep 1998 20:41:22 -0700 (PDT)

> rounding errors, but because of different exceptions that can arise.

By "exception" do you mean Java exception or IEEE 754 exception?  If
you mean Java exception, pow throws no checked exceptions and is not
described as throwing unchecked exceptions for any input. FDLIBM is C
code, or a Java port of C code, so there are no throw statements in
the code.  Additionally there are no integer divides, no object
allocation, and no calls to Java methods that could throw exceptions.
FDLIBM's pow checks for squaring as a special case and returns x*x.
(Other exponents like -1.0 and 1.0 are also special cased.)  No array
accesses occur along the path calculating x*x; the array accesses that
do occur could easily be translated into variable accesses.

If you mean IEEE exception there are two possibilities, traps or
flags.  Java forbids floating point traps and denies any access to the
sticky flags.  So, as far as Java is concerned, it doesn't matter if
the sticky flags set by x*x differ from those set by pow(x, 2.0) as
long as the returned value is the same.  Therefore, pow(x, 2.0) *can*
be replaced by x*x.

If a jit is doing this optimization, the jit can make sure the Math
class is loaded properly.  If the Java -> JVM compiler is doing the
optimization, there has to be an active use of the Math class before
any reflective services are called.

> replacement of x*2-x by x and other similar optimizations.

Yes, associativefp does not allow distributivity to be used.

>  associatievefp

But associativefp does not prevent the programmer from using a
parallel prefix algorithm.  There are cases where using parallel
prefix introduces numerical instabilities not present in the original
recurrence.  (See "On the Correctness of Some Bisection-like Parallel
Eigenvalue Algorithms in Floating Point," Electronic Transactions on
Numerical Analysis , Volume 3, 1995.)

In the recurrence you have given, if all that is desired is the n th
term there is a simple formula; however, this formula has much worse
roundoff properties for some values of "a" than using a loop to
calculate the answer.  For the loop in question, the calculated answer
is

(true value)*(1 + O(n)*eps)

where eps is the rounding threshold.  In other words, the calculated
answer is within a linear number of rounding errors of the true result
(assuming overflow and underflow don't occur).

If the recurrence is written out

b + a*(b + a*(b + a*(b + ... + a(b + a*0)...)))

using some algebra to come up with a formula gives

quick_result = b *(1 + a*(1 + a*(b + ... + a(b + a*0)...)))  =>

quick_result = b *(1 + a + a^2 + a^3 + ... + a^(n-1)) =>

quick_result = b *(a^n -1)/(a -1)

For even fairly moderate values of n, this new formula clearly uses
many fewer arithmetic operations than the loop (a^n can be calculated
efficiently via repeated squaring).  However, when a is near 1, this
formula has much worse rounding properties:

quick_x = (true x)(1 + O(n)*a^n*eps/(a-1))

If a is near 1, the (a-1) term amplifies the rounding error greatly.
The constant a could be near one if the formula is being used to, say,
calculate the balance of a savings account with regular deposits.

> manipulate the code.

My position is that compilers can do good things as well as bad
things.  They should be allowed to do the good but forbidden from
doing the bad.  There are metrics to judge a compiler other than the
speed of its generated code.

> compilers.

Does this imply Microsoft's compilers are best?  Programmers may have
to use compilers for many reasons other than their numerical quality.

>  This has nothing to do with good or bad language design, with

Language design is intimately connected to this discussion, namely,
what does the language specification say and why.  The original Java
specification states that an optimized expression must be "equivalent
in value and in its observable side effects" to the original.
Therefore, with a few caveats, a Java program should get the same
result even when optimized.  This is a language requirement not a
compiler implementation choice.  Many of the optimizations you would
like to use are forbidden by Java's semantics.  This is a legitimate
design choice in Java.  The intent of the Java specification is to
exactly define the language the compiler must accept, no more, no less.

Fortran (at least Fortran 77) takes a very different approach.
Fortran 77 specifies limits a legal program must meet but compilers
are free to extend the language.  For example, a standard-conforming
Fortran 77 program does not have more than 1320 characters in a
statement.  What can a Fortran compiler do if it gets a statement with
more than 1320 characters?  Whatever it likes.  Report an error,
accept and compile as expected, or even issue no warning and produce
incorrect code.  Such an imprecise approach leads to severe
portability problems.  A program can unintentionally be dependent on a
particular compiler's extensions; it fails to compile when used on a
different compiler.  Worse, since standard Fortran 77 lacked many
useful language features (e.g. dynamic memory allocation) different
compilers each added some of the omitted features in a different way.
I do not think Fortran sets a good example in this regard.

For floating point, Fortran semantics allow "any mathematically
equivalent" expression to be substitution where mathematically
equivalent means "assume floating point arithmetic is a field."
Different values can be generated and intermediate values of different
precisions can be used.  Fortran's semantics permit the optimizations
you have discussed, but this is not the only option.

Fortran is used by scientists, including computer scientists,
physicists, chemists, and others.  Java is aimed at many people,
including people who just want a flashy webpage.  The needs of these
groups are not the same.  Java Grande wants to evolve Java so that it
better meets the needs of those who have traditionally used Fortran.
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.

Programming languages are like cars; most people are better served by
a Volvo than a Porsche.

-Joe Darcy
[email-masked]