Issues in Numerical Computing With Java


This is a summary of issues raised during the first meeting of the Numerics Working Group of the Java Grande Forum held in Palo Alto on March 1, 1998. This is a working document and is under constant revision. Please direct any comments or suggestions to Roldan Pozo or Ron Boisvert.

Language Features

Floating-point Issues Arrays Standard Interfaces


Language Features

Complex Numbers

Issue Complex numbers are extremely important for numerical computing and should be available in Java. Their use should be convenient and operations on them should be efficient as fundamental data types (e.g. double).
Solution A Create the obvious Complex class and make it a standard API.
Pros This is easy to do and can be done immediately.
Cons Leads to unreadable and inefficient code.
Solution B Modify the Java language to include complex as a base type.
Pros Leads to natural, readable code which is easily optimized by compilers and runtime JITs.
Cons Requires a major modification to the Java language to satisfy a relatively small segment of Java users.
Solution C Introduce "lightweight" and operator overloading to Java. Lightweight (or value-based) classes would be designed to not suffer from the usual object overhead (e.g. have support in the language and/or VM to minimize heap allocation). A lightweight complex class would, presumably, be more efficient than a regular class, and operator overloading could make its use as natural as for the base arithmetic types double and float.
Pros This represents a good compromise, and the new language features required would benefit many other fundamental numerical classes which share the need for efficiency and usability.
Cons This requires two major changes to the Java language: lightweight classes and operator overloading.

Note: in either solution, existing APIs must be extended, e.g. Math.abs(), Math.cos(), etc. to work with complex numbers.

Other Arithmetic Data Types

Issue Other arithmetic data types are of considerable interest to the numerical community. The two most often cited are interval arithmetic, and (arbitrary) multiple precision arithmetic.
Solution Add intervals and arbitrary precision floats as base types in Java.
Pros This will make these important types most easily accessible to the community.
Cons This requires significant modification to the language to satisfy a small community of Java users.
Solution Define standard classes for interval and multiple precision arithmetic. Implement as "lightweight" classes and use operator overloading to make programs using these comprehensible.
Pros This is a good compromise, satisfying the numerical community while only requiring new language features (lightweight classes and operator overloading) which benefit a much wider range of user.
Cons This requires significant new additions to the language.

Operator Overloading

Issue Java's wordy syntax is excessively burdensome when used to define elementary mathematical classes such as complex arithmetic and array operations.
Solution Add operator overloading to Java.
Pros Operator overloading not only enables a natural and elegant syntax for complex arithmetic and arithmetic on arrays, but extends to elements of any algebraic field, including extended precision numbers, rational numbers, matrices, vectors, tensors, grids, etc. (java.Math already includes BigDecimal and BigInter classes that could benefit from operator overloading).
Cons Operator overloading can be abused to generate hard-to-read code by redefining familiar symbols into unintuitive operations.

Templates

Issue Code management and reuse in numerical programs is very difficult without a powerful and standardized preprocessor.
Solution Add a mechanism similar to C++ templates to Java. Even a simplified version could still provide many advantages.
Pros One obvious use of templates is in developing float and double versions of the same numerical routine. But more important is the ability to describe a numerical algorithm, say an iterative linear equation solver, in an "generic" way, without explicit mention of the matrix structure or storage details. Finally, advanced techniques like template expressions can be used to deal efficiently with array/vector operations, unroll loops, and fuse large array expressions into a single loop.
Cons Template mechanisms introduce tremendous complexity into the language. This diminishes one of the key attractive features of Java -- its simplicity. Templates also have a series of practical problems, mostly related to their implementation. Template codes can often lead to code bloat (since a separate routine is generated for each instantiation). They can be difficult to debug, depending on how well the debugger understands instantiations. Nested templated also present implementation problems. A quick read of the messages related to template problems in C++ news groups should give one a good idea of what to expect.


Floating-point Issues

Use of IEEE Extended Precision

Issue Requiring that Java programs produce bitwise identical floating-point results in every JVM seems to be not only unrealizable in practice, but also inhibits efficient floating-point processing on some platforms. For example, it precludes the efficient use of floating-point hardware on Intel processors which utilize extended precision in registers.
Solution A Relax the requirement of reproducibility for floating-point, admitting the use of IEEE extended in any intermediate computation.
Pros This corresponds to existing practice in the numerical community, allows the use of extended precision hardware, and and provides improved results in most cases.
Cons The certainty of exact reproducibility must be given up. This may be a burden for a few extreme cases in which absolute control of floating-point computation is necessary.
Solution B Provide a parameter within the JVM which allows users to permit the use of extended precision in intermediate computations.
Pros This allows the current Java specification to remain as the default, but allows it to be overridden by the user for high-performance applications.
Cons It will be difficult for the user to communicate this parameter to JVMs which are buried within other applications (e.g., Web browsers). This requires that JVMs implement two different types of floating-point arithmetic for hardware that has IEEE extended precision.
Solution C Introduce a new class and methods modifier looseNumerics, which permits JVMs to use IEEE extended precision in intermediate results while executing methods in its scope.
Pros This allows the existing Java specification to remain the default, while allowing developers to specify that higher performance is more important than exact reproducibility for the given class.
Cons The looseNumerics will be used on most classes which heavily use floating-point arithmetic, and hence the converse solution would be simpler (see below). This requires that JVMs implement two different types of floating-point arithmetic for hardware that has IEEE extended precision.
Solution D Relax the requirement of reproducibility for floating-point, admitting the use of IEEE extended in any intermediate computation. Introduce a new class and method modifier strictNumerics, which requires JVMs to the existing Java specification while executing the methods within its scope.
Pros This corresponds to current practice in the numerical community, while providing the ability to impose stricter floating-point requirements for those few applications that may need it.
Cons This requires that JVMs implement two different types of floating-point arithmetic for hardware that has IEEE extended precision.

Compiler Optimization of Expressions

Note that the optimizations in the first example are unsafe. If a is NaN or Inf or if 4*b overflows then then a different results is obtained at runtime with the optimization applied.
Issue Requiring that Java programs produce bitwise identical floating-point results in every JVM prevents use of certain aggressive compiler optimizations that can lead to more efficient code. Examples include the following
  • Performing arithmetic at compile time, e.g. converting 0*a to 0, 4*b/2 to 2*b, or c/10 to c*0.1
  • Applying the associative law to change order of computation i.e. x+y+z = x+(y+z)
Solution A Provide a parameter within the JVM which allows users to permit the use of aggressive compiler optimizations of this type.
Pros This allows the current Java specification to remain as the default, but allows it to be overridden by the user for high-performance applications.
Cons It will be difficult for the user to communicate this parameter to JVMs which are buried within other applications (e.g., Web browsers).
Solution B Introduce a new class and method modifier idealizedNumerics, which permits JVMs to use optimizations of this type while executing the methods within its scope.
Pros This allows the existing Java specification to remain the default, while allowing developers to specify that higher performance is more important than exact reproducibility for the given class.

Rounding

Issue Round-to-nearest is the only IEEE 754 rounding mode recognized by Java. While this is adequate in most cases, some specialized processing, such as interval arithmetic, would benefit greatly from more explicit control of the rounding mode (i.e., round up, round down, round to nearest) in specific instances.
Solution A Provide a procedure which allows one to select the global rounding mode.
Pros This provides easy control of the global rounding mode, and requires no significant change to the language.
Cons When the rounding mode is important to control, it is necessary to control it at a much finer level. This is awkward to do with a global switch.
Solution B Provide new language syntax that provides finer control of the scope of rounding modes, e.g.
round(up) { x = y+z; }
Pros Provides tighter control on the scope of the rounding mode.
Cons Requires new language syntax and semantics to implement.
Solution C Provide a new standard package that implements the elementary arithmetic operations with each rounding mode. For example
x = roundUp.add(y,z);
Pros This provides very tight control of the scope of the rounding mode, allowing different modes in a single expression. Compiler inlining or "lightweight" classes could make such operations fairly efficient.
Cons Expressions using controlled rounding modes are difficult to read.

IEEE Floating-point Exceptions

Issue Currently Java admits only default actions when IEEE floating-point exceptions occur. Thus, for example, 1/0 produces Inf, 0/0 produces NaN, etc. and, since, arithmetic on these special quantities is completely defined, no trapping occurs. This, again, is sufficient for most applications. However, it is sometimes crucial to know if one of these special events has occurred.
Solution Allow hardware trapping on user-selected IEEE floating-point exceptions.
Pros Enabling floating-point traps which terminate a program is quite useful for debugging.
Cons Providing a reasonable exception handler for such low level traps is difficult for users. Optimizing code in the presence of such traps is very difficult for compilers.
Solution Provide standard methods to determine whether a given IEEE floating-point exception has been raised, and to clear exceptions once tested.
Pros The latter is easy to implement exploit by working programs.
Cons This does not help in debugging.

NaNs

Issue Java defines a single specific bit pattern to represent NaN. This is contrary to IEEE 754 which specifies a range of values, all of which represent NaN. This Java restriction is unnecessary.
Solution Simply remove the restriction, allowing all NaN representation admitted by IEEE 754.
Pros This will allow for more efficient programs, since NaNs will not have to be trapped and fixed.
Cons This add s yet another ambiguity which undermines the goal of producing bitwise identical results on all JVMs..


Arrays

Multidimensional Arrays

Issue Numerical software designers typically take information about the physical layout of data in memory into account when designing algorithms to achieve high performance. For example, LAPACK uses block-oriented algorithms and the Level 2 and 3 BLAS to localize references for efficiency in modern cache-based systems. The fact that Fortran requires two-dimensional arrays be stored contiguously by columns is explicitly used in the design of these algorithms.

Unfortunately, there is no similar requirement for multidimensional arrays in Java. Here, a two-dimensional array is an array of one-dimensional arrays. Although we might expect that elements of rows are stored contiguously, one cannot depend upon the rows themselves being stored contiguously. In fact, there is no way to check whether rows have been stored contiguously after they have been allocated. The possible non-contiguity of rows implies that the effectiveness of block-oriented algorithms may be highly dependent on the particular implementation of the JVM as well as the current state of the memory manager.

Solution A Define a new multidimensional array data type for Java whose memory layout would be defined (contiguous storage, rowwise, for example). Such arrays would use multidimensional array indexing syntax (i.e. A[i,j] rather than A[i][j]) to distinguish them from Java arrays of arrays. Three-dimensional arrays are also quite common in applications and could be similarly included.
Pros This will provide programmers with a higher degree of certainty that data is laid out in a way that is optimal for their algorithm. Compilers will be able to exploit the data layout to optimize indexing in expressions involving arrays.
Cons This is a significant change to the Java language specification. Early evidence indeed shows that block-oriented algorithms can show significant performance increases with good JITs. While contiguity of rows may be the ideal case, its absence does not necessarily preclude improvement in performance for block algorithms. In one experiment with a blocked matrix multiply, the computation rate dropped from 82 Mflops to about 55 Mflops when rows were randomly permuted. On the other hand, for a naive non-blocked row-oriented matrix multiply, the original 11 Mflop rate was unchanged when the rows were permuted. The important issue is reusing data that lies in cache. Noncontiguity of rows only means that the cache may be filled in smaller increments.
Solution B Define standard classes which house contiguously stored multidimensional arrays. These would be physically stored in a singly dimensioned Java array, with get and put methods that accessed individual elements based on two indices.
Pros This requires no change to the Java language.
Cons It is doubtful that such classes could be made as efficient as true multidimensional Java arrays. The classes would have to be "lightweight" and it would be very difficult for compilers to eliminate the overhead of explicit indexing.
Solution C Define an alternate "new" operation for arrays which required contiguous allocation.
Pros This requires only a small change to the Java language.
Cons This requires new functionality in the VM. For certain types of garbage collection, this would cause lead to more frequent failure to allocate arrays.

Access to Subarrays Without Copying

Issue In Fortran, subarrays of multidimensional arrays can be logically passed into subprograms by passing in the address of the first element along with subarray dimensions. Internally to the subprogram the subarray acts just like a multidimensional array. This greatly eases the implementation of many algorithms in numerical linear algebra, for example. Subarrays cannot be delivered to methods in this way in Java.
Solution A The subarray is first copied to a new appropriately sized array, and the new array is passed to the method.
Pros The procedure receives a real Java array and need not handle any special cases.
Cons Much inefficient data copying is performed.
Solution The entire array is passed to the method along with explicit index ranges which define the subarray.
Pros No explicit array recopying is required.
Cons Variants of methods that explicitly operate on subarrays must be developed; the coding and efficiency of these methods will be complicated by complex indexing computations.

Long Integer Indices

Issue Some high-performance applications require extremely long arrays. Java's integer data type may not provide indices large enough to handle such arrays.
Solution Add a long integer data type to Java and allow it to be used in array indexing.
Pros This will simplify coding of applications with extremely large data sets.
Cons This will add a new data type to the Java language.

Array Expressions

Issue Fortran 90 and MATLAB each allow array expressions for computation on entire arrays. They also use a very convenient notation to denote computation on subarrays, such as A(1:5) = B(2:6) + C(10:14). The usability of Java would be greatly enhanced with similar features.
Solution Extend the Java language to admit arithmetic expressions on full arrays, and introduce a notation like Fortran 90's for denoting subarrays for use in expressions.
Pros Such features greatly ease scientific computation which are typically heavily array oriented. They also provide an easier way for compilers to discover useful optimizations. This would provide a syntactic device for passing subarrays to procedures.
Cons This would be a significant new addition to the Java language. Passing subarrays to procedures this way is contrary to the object model on which Java is based. Thus, passing subarrays would probably have to be done as pass-by-value, which would be greatly inefficient.

Array Bounds Checking

Issue Array boundary checks can result in reduced performance.
Solution Add a "no-boundary-check" switch.
Pros This can be used to speed the performance for debugged applications. This already done in IBM's high performance Java compiler
Cons Boundary checks are one of the major reasons for the stability and security of Java code. Good compiler optimization might be able to prove a priori that all index expressions that occur inside of a given loop will be inside of array boundaries. Run time optimizations can be used to overlap bounds checks with floating point computations. Some studies have shown that such optimizations can lead to bounds checks which lead to only moderate overhead (e.g. 20%) to numerical computations.

Resizing and Composing of Arrays

Issue (any volunteers to write this?)
Solution
Pros
Cons


Standard Interfaces

Numeric Objects

Issue Basic data structures such as arrays, vectors, matrices, etc. are so fundamental to numerical computing, that there should be some consistent interface to these objects. This would avoid having each person to define their own.
Solution Provide a limited set of APIs for basic numeric objects.
Pros This is perhaps one of the most practical contributions we can make to the numerical community. Looking at C++, there are too many numerics codes that define their Vector objects, etc. These yield redundant, yet often incompatible class definitions.
Cons Not every one of these classes has a canonical representation. In particular, things like "Matrix" can have a multitude of meanings: a 2D array of doubles, an abstract linear operator, a sparse structure, etc. Some care in design has to be taken to provide a usable framework.

Integrating with Fortran Codes

Issue The large body of Fortran scientific applications and libraries are not immediately available in Java. How can we best access them?
Solution A Provide a generic Fortran to Java translator.
Pros This would provide a 100% Java solution and retain the portability advantages of language and runtime system.
Cons Developing such a translator is very challenging, particularly for separate Fortran libraries. (One complication, among many, is that Java routines must reference the original array when passing subarrays through functions.)
Solution B Use JNI to integrate native methods.
Pros This is even easier with JNI component of JDK 1.1. One could also provide a specific API with objects like FortranArray2D, FortranArray3D, etc., and corresponding set(i,j)/get(i,j) methods to simplify Java codes that interfaced with Fortran.
Cons This has the same portability problems Fortran/C codes:
  • makes specific requirements on the user's environment
  • still need to deal with makefiles, configure, etc.
  • cannot use reliably in Web applets
  • impacts security model
Solution C Develop Java versions of these libraries.
Pros 100% pure Java. Performance with latest JITs about 50% of optimized Fortran/C. (NIST is currently doing this with a tiny subset of the BLAS and LAPACK -- see http://math.nist.gov/javanumerics/blas.html.)
Cons Writing libraries is lot of work. Performance with latest JITs is only about 50% of optimized Fortran/C.


[ Back ] to the JavaNumerics home page.

Last change to this page: April22, 1998