Subject: Comments on the "Report of the Numerics Working Group"

From: [email-masked]
Date: Thu, 10 Sep 1998 15:00:17 -0400

A few more comments, related to the "associativefp" modifier:

   Are "strictfp" and "associativefp" mutually exclusive? I guess they
   should be, since we cannot guarantee exact reproducibility if we allow
   associativity. I believe that it would make sense to explicitly state
   that in the proposal.

   Does the "associativefp" modifier relax the rules on the use of fused
   multiply accumulated? The rules described in the proposal are good for
   "avoiding surprises", but they do disable some optimizations.

   It is important to note that allowing associativity, with the
   "associativefp" modifier, does not enable as many optimizations as the
   "idealizedNumerics" modifier in Gosling's proposal. The
   "idealizedNumerics" allows any "mathematical equivalent" optimization.
   For instance, straightforward dot-product matrix multiply can be
   replaced by Strassen's algorithm. These algorithmic replacements will in
   general not be possible just with "associativefp". Of more immediate
   interest, the following transformation is performed by current Fortran
   compilers:

   the code

   do i = 1,n
      x[i] = float(i)
   end do

   is transformed to:

   xi = 0.0
   do i = 1,n
      xi = xi + 1.0
      x[i] = xi
   end do

   This is an important optimization, since it eliminates the need to keep
   the "i" index and replaces a type conversion by an addition. This
   optimization for Java would be legal under "idealizedNumerics" but not
   under "associativefp". Should we reconsider supporting the
   "idealizedNumerics" modifier?

In general, we have not discussed the issues of integer to floating-point
conversions in the proposal.

Jose E. Moreira
IBM Thomas J. Watson Research Center
Yorktown Heights, NY 10598-0218
[email-masked]

---

From: "Joseph D. Darcy" <[email-masked]>
Date: Thu, 10 Sep 1998 13:09:46 -0700 (PDT)

>    Are "strictfp" and "associativefp" mutually exclusive?

Yes, that should be stated explicitly.

>    "avoiding surprises", but they do disable some optimizations.

Do you have some particular optimization in mind?

>    "idealizedNumerics" modifier in Gosling's proposal.

That is intentional.  Many of Goling's optimizations (like
distributivity) can be expressed by the programmer in source code.  Of
course, different optimizations often enable one another so the
intermediate representation the compiler uses may be rather different
than the source code (or perhaps not even expressible as source).  I
would be interested in knowing of any empirical work measuring the
marginal improvement gained from different floating point
optimizations.

>    replaced by Strassen's algorithm.

Strassen's algorithm misbehaves for some floating point matrices that
behave well under normal matrix multiply.  In general, I (personally)
don't feel such algorithmic changes are the compiler's job; if the
programmer wants to use Strassen's, let him call "straseen" instead of
"dgemm."  The compiler cannot know a priori what properties of an
algorithm the programmer wants preserved.  For example, one
optimization to quick sort uses insertion sort for array segments
smaller than a certain size (say 8 elements).  If the well-meaning
compiler pattern matched insertion sort and replaced it with quick
sort in this case, a slower algorithm would result.  It could also be
a problem if a compiler replaced a stable sorting algorithm (where
equal elements are not re-ordered) with an unstable one (where equal
elements are reordered).  Recklessly replacing different string
matching algorithms can also be problematic.  Naive string matching is
slow.  The Knuth-Morris-Pratt algorithm is faster and there is third
algorithm (whose name escape me at the moment) that is faster still.
The compiler could pattern match KMP and replace it with the third
algorithm.  However, KMP has an important property that array
locations are accessed in monotonically non-decreasing order; if you
access location i you never again look at i-1 or earlier.  This "no
backing up" property is important for some buffer management schemes.
The third algorithm does not have the "no backup" property.

>    the "i" index and replaces a type conversion by an addition.

As long as the compiler knows how big n is (and can act accordingly)
this optimization can be performed in current Java.  For example, if n
is less than 2^(number of significand bits in the format of x) than
the transformation works fine.  However, if n is larger than this
value, the "optimized" code will just keep assigning the same number
to all subsequent array locations (adding 1.0 to xi will get rounded
away).  In the original code, the large integers will be rounded when
assigned to the array locations so the value of these locations can be
larger than the value in previous locations (i.e. for large i, every
other array location will be larger than the one before it, etc.).

-Joe Darcy
[email-masked]