Subject: design approach for numerical data structures

From: Urs Schreiber <[email-masked]>
Date: Sat, 31 Jul 1999 18:45:58 +0200

Hello,

having already introduced myself with a fashionable "test - please
ignore" message, I would now like to say a few more words.
I am a physics student at University of Essen/Germany. For two years now
I have been doing Java software development, and now that I am about to
do scientific computing I am interested in if and how Java can be used
for this task. I have studied what can be found on the net about
numerical and high performance Java and would like to hear other
people's  comments on an idea I had myself while reading (see below). I
hope that this mailing list is suitable for such proposals and
discussions - if not, please excuse and ignore again...

Urs Schreiber

Summary: Proposal for a design approach for numerical,
high performance Java that decreases the number of object
constructions thus increasing performance and making lightweight
classes obsolete.

Java is said to have some major drawbacks when it comes to high
performance numerical computing. One of a few changes to the language
found necessary to overcome these disadvantages is the introduction of
"lightweight" classes that would not reside in the heap like common
"heavyweight" objects but would rather be treated like the primitive
int, double, etc. types, this way requiring less memory management.

A modification of the language should of course only be considered if
the present features do not allow to implement the desired
functionality with a reasonable amount of effort. There may be a way,
though, by following a simple design paradigm, to accomplish fast
(that is: with little amount of object construction/allocation),
convenient types like Complex with and within the common heavyweight
class concept.

(If the following is nothing new and already done somewhere else
please give me a reference, otherwise please let me know what you think
about
it.)

I will give a description of the idea, an illustrative example and a
discussion of the pros and cons: 
(To avoid misunderstandings: When referring to "methods", "functions" or
"routines" in the following I mean only those that do some numerical
work or
are otherwise integrated in the "high performance" part of the
implementation.)

Description:
------------

The approach is based on applying the following two simple design
principles:

1) Pass result containers to methods.
A method that calls subroutines within its body
has, in general, more information about the need for the allocation of
new
(possibly temporary) objects by these routines than the subroutines
themselves. Thus the decision whether or not to allocate a new object
for the
result returned by a method should be made before calling the method.
This
means: In addition to the normal parameters passed to a method, always
pass
an object to store the result (a "result container"). Let not the method
construct a new data structure for the return value but let the caller
ensure
that such an object exists.

As a result of (1), every method needs to pass result containers to its
subroutines. But constructing these objects each time time the method
itself
is called would make (1) pointless, thus:

2) Wrap up single methods in classes.
Provide for the necessary result accepting and other temporary objects
by
declaring private objects to those classes. Call the methods by creating
an
object of the wrapper class (once!) and then calling the object's
method.
(Note that this approach is thread save and no "synchronized"
declarations are
necessary because every thread creates its own instance of the method's
class.)

By utilizing these two principles the number of objects
constructed/allocated after initialization can be reduced to a minimum.
Before going into a more detailed discussion of the concept I will give
a code
example.

Example:
--------

The following defines a class Matrix (as a representative for any
non primitive numeric data structure) that offers the usual basic
operations
plus two methods doing resource intensive calculations that would
normally
involve several Matrix objects being constructed and thus a lot of
memory
(re)allocation and array copying. The implementation follows the above
conventions, most notably by defining a subclass "IntensiveCalculation1"
which
wraps a method doing a lot of numerical processing on temporary objects.
The
"main" method starts a number of threads, each doing such a calculation.

/**
 * A common definition of a class Matrix, but with a special result
 * containing parameter to every method.
 */
class Matrix {
        double[][] array;       
        Matrix(int n, int m) {
                array = new double[n][m];
        }
        Matrix add(Matrix a,Matrix b, Matrix result) {
                 /*write a+b into result, return result*/ ...
        }       
        Matrix invert(Matrix a, Matrix result) {
                /* write inverse of a into result, return result */...
        }
        Matrix someDecomposition(Matrix a, Matrix result) {
                /* store some decomposition of a into result, return
                result*/
         }      
        [...]

        /**
         * a wrapper for a resource intensive method
         */
        static class IntensiveCalculation1 {
                Matrix cache; 
                [...]
                Matrix do(Matrix a, Matrix b, Matrix result) {
                        //* do some heavy computation by possibly
                        //* calling further subroutines, maybe 
                        //* passing "cache" as result container 
                        //* (see IntensiveCalculation2 below)
                }
        }       
        /* Note: To avoid name clashes and allow for a well structured
        code it is surely desirable to have method wrappers being
        subclasses. One should then, of course, declare them "static"
        to facilitate usage of these subclasses independently of
        an instance of the enclosing class (if possible and
        desired). */
        [...] 
}

class Runnit extends Runnable {
        Thread thread;

        /**
         * a second resource intensive method (which is not provided by
         * the Matrix class)
         */
        static class IntensiveCalculation2 {
                //* two private Matrix instances to be used as temporary 
                //* objects by do()
                //* allocated once for every thread
                Matrix cache = new Matrix(3,3);
                Matrix cache2 = new Matrix(3,3);

                //* an instance of the subroutine to be called inside
                //* do(...)
                IntensiveCalculation1 calc1 = 
                        new Matrix.IntensiveCalculation1();

                //* the method itself, performing some major calculation
                Matrix do(Matrix a, Matrix b, Matrix result) {          
                        Matrix.someDecomposition(a,cache2);             
                        Matrix.add(cache2,b,cache); 
                        for (int i = 1; i<999; ++i) {
                                Matrix.someDecomposition(cache,cache2);
                                Matrix.add(cache2,b,cache);
                        }
                        return calc1.do(cache,a,result);        }
        }

        /* 
         * "main" starts a few threads, each doing calculations
         */
        public static void main(String[] args) {
                for (int i=0; i<99; ++i)
                        new Runnit();
        }

        Runnit() {
                thread = new Thread(this);
                thread.start();
        }

        /**
         * Creates a random input and a Matrix to keep the result to be 
         * calculated. Then constructs an instance of the calculation
         * wrapper and calls its single method.
         */ 
        public void run() {
                Matrix a = new RandomMatrix(3,3);  //some matrix
                Matrix b = new RandomMatrix(3,3);
                Matrix result = new Matrix(3,3);
                IntensiveCalulation2 calc = new IntensiveCalculation2();
                System.out.println(a + " intenseop "+b+ " = " + 
                        calc.do(a,b,result));
        }
}

Discussion:
-----------

The advantages:

-  The above way of doing numeric Java has all the performance
advantages
that utilization of lightweight classes would have. It is fast and
requires
a  minimal amount of heap (re)allocation. (Of course one would not
necessarily have a lightweight 3x3 Matrix. The Matrix class above was
just an
example, you might as well think of a class Complex or the like.) It may
be
even faster than using larger lightweight classes because the maximum
size of
a parameter is that of a normal object reference whereas a lightweight
complex would be larger.

- Wrapping up methods in individual classes is also not too much a
workaround but rather suffices the object oriented paradigm in general.
It
may even proof to be a design paradigm  worth for its own sake: For
example a
method (i.e. its wrapper object) could keep information about the
method's
usage (e.g. number of times being called) or provide information about
its 
properties (like "String getDescription()" or "getRange()",
"getDomain()"
etc.) Furthermore, wrapping methods is Java's way of declaring function
pointers. By having all methods wrapped up like above with possibly some
useful hereditary relation between the wrappers, it becomes possible to
pass functions as parameters. 

- Lightweight classes would have to be restricted in various ways. Most
importantly, one could not derive a descendant class from a lightweight
class.
This restriction is loosened somewhat in the above approach. Of course,
if a
method expects a result containing Matrix featuring a 3x3 array it
cannot
process a derived Matrix2times2 that only offers a 2x2 data structure.
But
the derived class is still allowed to have its own virtual method
implementation. One could, for example, implement an abstract class
Complex
which offers access to its value by means of getReal(), getImaginary(),
getAbsValue(), getAngle() and the respective setXXX() methods. Then,
depending on the task, it may be desirable to save the complex value
either
as real+i*imaginary or as absVal*exp(i*angle). One could derive a
CartesianComplex and a PolarComplex from Complex, implement the accessor
methods appropriately and pass either of both classes to any method
accepting
Complex parameters. This is of course simply the well known advantage of
object oriented programming, but with lightweight classes it would not
be
possible.

-  Then, of course, there are no lightweight classes yet. The above 
uses present Java features to accomplish tasks that an extension of the
language has been found necessary for.

- The commonly used "calculate-and-assign" methods equivalent to += or
*=, like
Complex.add(Complex add), of course need not create an object to keep
the
return value either, but they are somewhat restricted. Once a class is
defined it would require creating a subclass to add a formerly not
provided
"calculate and assign" method.

The disadvantages:      

- The number of class definitions is increased.

- The code for complex arithmetic expressions becomes still a little
more
cumbersome by having an extra parameter for every method call. Possibly
upcoming operator overloading would not be usable with the above
approach
because this extra parameter could not be passed. One can hear that this
is a
big issue for people doing numeric Java, but I do not think so myself.
This
is because I believe that no number of operators being overloadable
(even
when using unicode characters) will give you enough short hands to make
mathematical code readable. Math just is best written and read the way
it is
done on paper - and in formula editors. Thus I would prefer to write a
simple viewer/editor, a source-to-source-compiler in this case, that
lets you read
and write programming code with all the mathematical short hands,
pretty printed formulas and the like as you wish. Once there is a set of
approved and standardized Java packages for numerical computing a simple
translator from MathML to Java source and vice versa would do the job.

This is as far as I have gotten in pondering the issue. I would be glad
about
receiving any comments.

[email-masked]