Subject: Draft Response to Gosling's Proposals

From: [email-masked] (Ronald F Boisvert)
Date: Fri, 12 Jun 1998 17:54:31 -0400

Attached is a draft response to James Gosling's proposals based on
discussions at the last Java Grande Forum meeting..

Please submit any comments that you have to this mailing list ASAP.
We plan to revise this next week and circulate it more widely, still
as a draft.

(NOTE: Numerics Working Group members have already received a 
       copy of this.  I am simply increasing its circulation
       to the entire Forum.)

Ron Boisvert

=====================================================================

Response to Gosling's
The Evolution of Numerical Computing in Java

Numerical Working Group
Java Grande Forum

This document responds to each of the points in James Gosling's
document "The Evolution of Numerical Computing in Java", as
downloaded from the URL http://www.javasoft.com/people/jag/FP.html on
May 9, 1998.  This response is fairly terse; it is meant to be read
in conjunction with the main position statement of the Numerics
Working Group of the Java Grande Forum.

NUMERICAL PRECISION and ALLOWABLE COMPILER OPTIMIZATIONS

The numerical community requires that the most efficient facilities
of local processors be fully exploitable in their Java classes.
Thus, we applaud the move to admit the use of IEEE extended precision
and certain compiler optimizations in the Java VM.  However, we feel
that the proposed solution is unnecessarily complicated and not
ideally suited to the task.  In particular, we see no compelling
reason to distinguish between these two issues and provide separate
mechanisms for resolving them.  The key issue in each case is whether
Java VMs are allowed to sacrifice Java's strict numerics model in the
interest of improving performance of floating-point computations.

We are comfortable with having the current Java floating-point model,
even with its implication of bitwise reproducibility of results, as
the default behavior of all Java VMs.  We also agree that users
should be required to take explicit actions in order to override this
behavior.  For example, JVM's might include -loosen to relax the
requirement that the results of all floating-point operations be
truncated to float or double.  (This would permit the use of IEEE
extended on Intel processor and fused multiply-add instructions on
the PowerPC, for example.)  Java VM's might also provide
user-settable flags to describe the levels of optimization, i.e.,
-O1, -O2, etc., whose application compromise the Java reproducibility
specification, but whose application may increase performance
significantly.  It is not necessary to standardize these flags, only
to allow Java VM's to provide them and users to select them.

We do NOT feel that the introduction of new method and class
modifiers such as looseNumerics or idealizedNumerics is warranted.
In fact, we feel that introducing these will be counterproductive.
There are several reasons for this.

  (1) Software developers who want floating-point intensive code to 
      run fast (we believe that this includes virtually all developers)
      will add looseNumerics and idealizedNumerics to ALL of their
      classes. This is, at best, an inconvenience, but also indicates
      that it may not be the most simple and elegant of solutions.

  (2) It is not clear assigning the scope of looseNumerics and
      idealizedNumerics to be static is workable.  A procedure that
      invokes a "loose" or "idealized" method can no longer expect
      to produce equivalent results on all Java VMs.  It would then
      not be correct for it to portray itself as strict to its users.
      One would want efficient implementations of core numerical
      libraries, and hence all classes that employed reuse would, in
      effect, become loose or idealized.  Providing both loose and
      strict core libraries not only doubles their size, but requires
      that class authors staticly select which version to use; this
      severely limits the use of their classes, and will inevitably
      lead to an explosion in the number of classes.  

  (3) By specifying such modifiers, authors in effect assert that any       
      transformation of their code will be safe.  This is a very strong 
      statement; no mathematical software is warranted in this way 
      today. This could lead to most authors of reusable components to 
      take a conservative approach and not make these assertions. The
      poor performance of the resulting software will discourage reuse.
 
Thus, it is our position that looseNumerics and idealizedNumerics
should NOT be added as class modifiers.  Runtime Java VM switches
provide a much simpler way to obtain the desired effect.

There are some cases in which the author is performing a computation
which is particularly sensitive and has taken great care in setting
out a particular order of operations. Such authors need to be able to
protect such segments of code from rearrangement by aggressive
compiler optimization. It is probably sufficient to protect such code
at the method level.  We propose that a method (and possibly class)
modifier strictNumerics be added to the language.  Methods employing
strictNumerics would always be subject to the default Java
floating-point model, and hence protected from optimizations
introduced by use of flags to the Java VM at run time.

STANDARD LIBRARY EXTENSIONS

We agree that providing float versions of the elementary functions is
needed.

The behavior of the elementary functions in Java is not carefully
defined. Reproducibility of results is compromised, for example,
unless these functions are themselves defined in Java.  Fast, native
versions could be substituted by Java VMs when users set optimization
flags (see above).  These reference implementations should use the
most accurate and efficient known algorithms in each case; in many
cases methods are known which are accurate to a few ulps.

EFFICIENT CLASSES

The provision of value-based classes is crucial to the efficiency of
core numerics classes such as complex arithmetic, interval
arithmetic, etc.  For this community it is important that Java VMs
are able to completely eliminate object overhead associated with such
classes (e.g.  heap allocation).  Without such classes Java will not
be considered for use by the numerical community.  Thus, we strongly
support the effort to introduce efficient classes in Java.

Objects of efficient classes must also behave just like float and
double.  In particular, the following must be true.

  * They are passed by value.
  * They must be initialized (i.e. they have a non-null address).
  * They cannot be compared or assigned to null.
  * The == operator performs a value compare. 

COMPLEX NUMBERS

We prefer that complex numbers be added as and additional base data
type in the Java language.  If this does not occur, then providing
the "obvious class" is acceptable, provided that an efficient class
mechanism and a rudimentary operator overloading facility are added
to the language.

The Numerics Working Group of the Java Grande Forum intends to make a
detailed proposal for a Complex class.

OPERATOR OVERLOADING

Operator overloading is essential in order for the Java language to
be useable for numerical computing.  Not only does it help solve the
problem of complex arithmetic, but it also provides a facility to
define other arithmetics such as interval and multiprecision in a
natural and elegant way.

For our purposes it is not necessary to define a completely general
facility to define arbitrary operators.  It is only necessary to be
able to overload the elementary arithmetic operations (+, -, *, /),
the assignment operator (=), the in-place compute-assignment
operators (+=, -=, *=, /=), as well as the logical operators (==, >,
<, >=, <=).  It is also necessary for the overloading facility to
apply to the [] operator with multiple included commas to allow for
the development of multidimensional arrays, e.g. a[i,j]=b[i,j,k]
transformed to a.set(i,j,b.get(i,j,k)).

It is important that overloaded operators be allowed to be
commutative so that they may interact with the primitive types.  To
do this, names for reverse operations should be provided as indicated
in the proposal.

It is unimportant what standardized names are used to define the
methods which define these operators.

ROUNDING

The numerical community is disappointed that the full facilities of
IEEE arithmetic are not available using Java.  Selecting the rounding
mode is one such facility.  While this facility is only needed in
fairly specialized cases, when it is needed it is absolutely
crucial.  Providing access to the rounding mode on a fine level via a
standard package with differently rounded versions of the elementary
arithmetic operations is sufficient.

EXCEPTIONS

The numerical community is disappointed that the full facilities of
IEEE arithmetic are not available using Java.  Java programs should,
at the very least, have access to all IEEE 754 floating-point flags
so that they can be checked and reset.

NaN

We agree.  The IEEE 754 standard should apply, admitting a range of
bit patterns to represent NaN.

MATRICES

Note on terminology: In mathematics, the term matrix is applied to a
specific object with a certain defined algebra (i.e. a representation
of a linear operator in a vector space).  When writing programs one
typically IMPLEMENTS a matrix using a two-dimensional array.  The
issues addessed in this section are more generally applicable to
multidimensional arrays.  Thus, we we feel that less confusion will
result if we use this terminology instead.

Multidimensional arrays are of prime importance in numerical
computation.  The current facility for defining arrays of arrays is
inadequate since it has several side effects which inhibit safe and
efficient implementation.

  * Rows may be of different lengths.
  * Rows may be aliased.
  * Non-contiguous layout of elements in memory leads to more
    complicated addressing and poorer use of cache.

We strongly urge the adoption of standard array classes as described
in the proposal.  Constructors for this class would allocate a single
block of memory to be used for multidimensional arrays.  It is
important that elements of such arrays be referred to using notation
such as a[i,j].  The provision of operator overloading and efficient
classes should provide acceptable behavior.

The multidimensional array class should support the following.

  * Options for arrays laid out both row-wise and columnwise (as in 
    Fortran).
  * Methods to convert from row-wise storage to column-wise storage
    and vice versa.
  * Methods to reshape arrays; for example, to re-interpret an 8x10
    array as a 5x16 array.
  * Methods implementing elementary arithmetic operations to arrays
    elementwise.

The Numerics Working Group of the Java Grande Forum intends to make a
detailed proposal for a multidimensional array class.

SUBSCRIPT CHECKING

The requirement of runtime subscript checking can incur a significant
runtime cost for high performance applications.  While it would be
desireable to have a no-subscript-checking option on the Java VM which
users could opt for at run time, it is acceptable if Java compilers
be allow to do the following.

  * Eliminate run-time checks if static analysis shows array references 
    to be safe.
  * Eliminate explicit element-wise run-time checks if run-time analysis
    shows such references to be safe.

If these are done, and JITs can overlap bounds checking with other 
computation, then the effect of subscript checking can be reduced to
an acceptable level.

MEMORY HIERARCHY

The concerns of the numerical community on this issue will be greatly
reduced provided multidimensional arrays are added to Java as described
above.  One continuing concern is that the Java specification is silent
on the layout of arrays of primitive types (e.g. double).  For optimal
performance, these should be contiguous in memory whenever possible.

High performance numerical algorithms (e.g. linear algebra software in
LAPACK) is parameterized based upon an optimal block size for cache
reuse.  Today, such parameters must be determined a prioi and stored
staticly in an implementation.  This does not make sense for Java.
To determine optimal parameters at run-time, inquiry functions that
return information about the current environment, such as number of
cache levels, cache sizes, and main memory size are necessary.