\documentclass{llncs}
\sloppy
\begin{document}
\mainmatter
%
%============================================================
 
%\input epsf
%\epsfverbosetrue
\input{psfig}

\title{Complex numbers for Java}

\author{Michael Philippsen and Edwin G\"unthner}

\institute{
Computer Science Department, University of Karlsruhe\\
Am Fasanengarten 5, 76128 Karlsruhe, Germany\\
{\tt phlipp@ira.uka.de}, {\tt edwin.guenthner@gmx.de}\\
\texttt{http://wwwipd.ira.uka.de/JavaParty/}
}

\maketitle

%\vspace*{-6cm} \noindent \begin{minipage}[t]{\textwidth} \begin{sc}
%To appear in: Concurrency: Practice \& Experience, Vol. 11, 1999.\\
%~\\~\\
%\end{sc} \end{minipage} \vspace*{4cm}

\pagestyle{empty}
\pagenumbering{arabic}

\begin{abstract}

Efficient and elegant complex numbers are one of the preconditions for
the use of Java in scientific computing. This paper introduces a
preprocessor and its translation rules that map a new basic type {\tt
complex} and its operations to pure Java. For the mapping it is
insufficient to just replace one {\tt complex}-variable with two {\tt
double}-variables.

Compared to code that uses {\tt Complex} objects and method
invocations to express arithmetic operations the new basic type
increases readability and it is also executed faster. On average, the
versions of our benchmark programs that use the basic type outperform
the class-based versions by a factor of 2 up to 21 (depending on the
JVM used).
\end{abstract}

%\begin{keywords}
%\end{keywords}

\section{Introduction}

In regular Java there is just one reasonable way to use complex
numbers, namely to write a class {\tt Complex} containing two values
of type {\tt double}.  Arithmetic operations have to be expressed by
method invocations as shown in the following code fragment. The
alternative, to manually use two {\tt double}-variables where a
complex number is needed, is too error-prone and too cumbersome to be
acceptable.

\begin{verbatim}
        Complex a = new Complex(5,2);
        Complex b = a.plus(a);
\end{verbatim}

\noindent Class-based complex numbers have three disadvantages: Once
written without operator overloading, arithmetic operations are hard
to read and maintain. Second, since Java does not support so-called
value classes, object creation is slower and objects need more memory
than variables of a basic type. Arithmetic operations based on classes
are therefore much slower than arithmetics on built-in types.  Even
worse, method-based arithmetic causes frequent creation of temporary
objects to return values. To return temporary arithmetic results with
basic types, no such object creation is needed.  The third disadvantage
is that class-based complex numbers do not seamlessly blend with basic
types and their relationships.  For example, an assignment of a {\tt
double}-value to a {\tt Complex}-object will not cause an automatic
type cast -- although such a cast would be expected for a genuine
basic type {\tt complex}.  Additionally, there is no natural way to
express complex literals; instead a constructor call is needed.

The fraction of people using Java for scientific computing is
quite small, so it is unlikely that the Java Virtual Machine
(JVM) or the Java bytecode will be extended to support a basic type
{\tt complex} -- although this might be the best solution from a
technical point of view.  It is also hard to tell whether Java will
ever be extended to support operator overloading and value classes;
and if so, whether there will be efficient implementations.  But even
given such features our work would remain important because, first,
the same level of seamlessness cannot be achieved, see the above type
cast problem. And second, our work can still be used to rate the
efficiency of implementations of the general features.

The next section discusses the related work.  Section~\ref{ueberblick}
gives an overview of {\tt complex} numbers in the {\it cj\,}
preprocessor/compiler. The central ideas of the translation are
presented in Section~\ref{map}. Section~\ref{benchmark} shows the
quantitative results.

\section{Related work}

With support from Sun Microsystems, the Java Grande Forum
\cite{GrandeURL,Phlipp98k} strives to improve the suitability of Java
for scientific computing. The challenge is to identify and bundle the
needs of this small user group in such a way that they can be
respected in the continuing evolvement of Java although that is driven
by the main stream.

The Java Grande Forum is working on a reference implementation of a
class {\tt Complex} that can be used to express arithmetics on complex
numbers \cite{JavaGrandeComplex,Ninja99}. Special attention is paid to
problems of numerical stability.  IBM is extending their
Java-to-native compiler to recognize the use of this class
\cite{Moreira99}. By understanding the semantics of the {\tt Complex}
class, the compiler can optimize away method invocations and avoidable
temporary objects. Hence -- at least on some IBM machines --
high performance can be achieved even when using class-based
complex numbers.  However, the other disadvantages mentioned above
still hold, i.e.\ there is no operator overloading and {\tt Complex}
objects lack a seamless integration into the basic type system.

There are considerations to add value classes to the official Java
language \cite{GoslingFP,Steele98}. But although there is no proper
specification and no implementation yet, the Borneo project
\cite{Borneo} is at least in a stage of planning.  Since there are
already object-oriented languages that support value classes, e.g.\
Sather \cite{Sather1}, the basic technical questions of compiling
value classes to native code can be regarded as solved.\footnote{
C++ can emulate value class semantics by means of
pass-by-value mechanisms.}  However, it is still unclear whether and
how value classes can efficiently be added to Java by a
transformation that expresses value classes with original language
elements. In particular, it remains to be seen whether value classes
will require a change of the bytecode format.

The discussion on how to add a primitive type {\tt complex} to a
given language has a long tradition. Java is special because of its
very strict definitions of evaluation orders, in particular with
respect to the visibility of side effects in case of exceptions. A
related question of extending a language with a primitive type {\tt
complex} is whether there should be a separate primitive type for
imaginary numbers as well, as proposed by Kahan \cite{Kahan91}.
It is debated whether and how such  
a separate imaginary type should be included in the C9X proposal
\cite{C9X}. To avoid the complexity of an extra type, our work only
adds the type {\tt complex} although future extensions might have the
{\tt imaginary} type as well.

\section{Complex numbers in {\it cj}}
\label{ueberblick}

{\it Cj\,} extends the set of basic types by the type {\tt complex}.
A value of type {\tt complex} represents a pair of two double
precision floating point numbers. All the common operations for basic
types are defined for {\tt complex} in a straightforward way. The real
and imaginary part of a {\tt complex} can be accessed through the
member fields {\tt real} and {\tt imag}. Note, that the names of these
fields are not new keywords. Since the basic type {\tt complex} is a
supertype of {\tt double}, a {\tt double}-value will be implicitly
casted where a {\tt complex} is expected.  A second new keyword, {\tt
I}, is introduced to represent the imaginary unit and to express
constant expressions of type {\tt complex}, as shown in the following
code fragment.

\begin{verbatim}
          void foo(complex x, complex y) {
            complex const = 5.0 + y.real * I;
            complex sum   = const + x + y;
            ...
\end{verbatim}

\noindent In our experience, any extension of Java will only be
accepted if there is a transformation back to pure Java. But in
general better efficiency can be achieved by using optimization
techniques during bytecode generation. Our compiler {\it cj}, which is
an extension of {\it gj\,} \cite{Odersky98}, therefore supports two
different output formats, namely Java bytecode and Java source
code. In this paper, we focus on the latter and mention optimizations
only briefly.

\section{Recursive transformation rules for {\tt complex}}
\label{map}

In any current Java compiler, inner classes are transformed to earlier
Java 1.0 (without inner classes). Similarly, {\it cj\,} has another
transformation phase that resolves {\tt complex} numbers and {\tt
complex} operations. This section discusses the central ideas of this
transformation.

\subsection{Name mangling for separate compilation}

The basic part of the transformation is done by modifying the names
used by the programmer. For example, by appending {\tt \$cj\$real} to
a variable name, the name of the resulting real part of the
corresponding {\tt complex}-variable is derived. A similar technique
is used to adapt the names of methods when their signature includes
arguments of type {\tt complex}.

By making the name mangling rules also known to the bytecode loader it
is possible to compile different Java programs separately, even when
{\tt complex} is already transformed into bytecode.  Hence, if the
compiler finds a mangled method definition in a bytecode file it
internally generates an additional method symbol entry representing
the method with its original signature and type information.

\subsection{Transformation of {\tt complex} expressions}

The central part of the transformation deals with {\tt complex}
expressions.  For simplicity, we call any expression that uses {\tt
complex} values a {\tt complex} expression.  The transformation of
{\tt complex} expressions to expressions that only use {\tt double}
causes several problems.

\paragraph{Transformation locality.}  If a {\tt complex}
expression is used where only an {\it expression\,} is allowed it must
not be mapped to a sequence of statements.

\begin{verbatim}
        while (u == v && x == (y = foo(z))) {...}
\end{verbatim}

\noindent For example, for transforming the {\tt complex} condition of
this {\tt while}-loop into its real and imaginary parts it is
necessary to introduce several temporary variables whose values have
to be calculated within the body of the loop. Therefore, the loop has
to be reconstructed completely.

In general, to replace {\tt complex} expressions by three-address
statements, one needs non-local transformations that reconstruct
surrounding statements as well, although local transformation rules
that replace expressions by other expressions (not statements) were
simpler to implement in a compiler and it would be easier to reason
about their correctness.

\paragraph{Semantics.} To achieve platform independence,
Java requires a specific evaluation order for expressions (from left
to right).  Any transformation of {\tt complex} arithmetics must
implement this evaluation order using {\tt double}-arithmetic.

To preserve these semantics for {\tt complex} expressions, it is not
correct to fully evaluate the real part before evaluating the
imaginary part. Instead, the transformation has to achieve that a side
effect is only visible on the right hand side of its occurrence, but
both for the real and imaginary part. Similarly in case of an
exception, only those side effects are to become visible that occur on
the left side of the exception.  Additionally, by separating the real
part from the imaginary part, it is also unclear how to treat method
invocations ({\tt foo(z)} in the above example).  Shall {\tt foo} be
called two times? Is it even necessary to create two versions of {\tt
foo}?

\subsection{Sequence methods}

To avoid both types of problems we introduce what we call {\it
sequence methods\,} as a central idea of {\it cj}. Each {\tt complex}
expression is transformed into a sequence of expressions. These new
expressions are then combined as arguments of a sequence method. The
return value of a sequence method is ignored.  This technique enables
us to keep the nature of an expression and allows our transformation
to be local. A sequence method has an empty body; all operations
happen while evaluating the arguments of the method invocation. The
arguments are evaluated in typical Java ordering from left to
right.\footnote{Exceptions are not thrown within a sequence method but
within the invocation context.  Hence, it is unnecessary to declare
any exceptions in the signature of sequence methods.} In case of
nested expressions, the arguments of a sequence method invocation are
again invocations of sequence methods.  By using this concept we are
able to evaluate both parts of each node of a {\tt complex} expression
tree at a time. Moreover, the evaluation order (in terms of visibility
of side effects and exceptions) is guaranteed to be correct.

When {\it cj\,} is used as preprocessor and Java code is produced, the
method invocations of the sequence methods -- which are declared {\tt
final} in the surrounding class -- are not removed. However, they may
be inlined by a Just-in-time (JIT) compiler. When {\it cj\,} generates
bytecode, the compiler directly removes the method invocations -- only
the evaluations of the arguments remain. The resulting bytecode has
the same efficiency as if C/C++'s comma operator was available in
Java.

\subsection{An example of Sequence methods}

Let us first consider the right hand side of the {\tt complex}
assignment {\tt z = x + y}.  To avoid any illegal side effects we use
temporary variables to store all operands. The following code fragment
shows the (yet unoptimized) result of the transformation of the right
hand side.

\begin{verbatim}
      seq(seq(tmp1_real = x_real, tmp1_imag = x_imag),
          seq(tmp2_real = y_real, tmp2_imag = y_imag),
          tmp3_real = tmp1_real + tmp2_real, 
          tmp3_imag = tmp1_imag + tmp2_imag)
\end{verbatim}

\noindent In this example, 6 {\tt double}-variables would have to be
declared in the surrounding block (not shown in the code). When
evaluating this new expression, Java will start with the inner calls
of sequence methods (from left to right). Thus, both parts of {\tt x}
and {\tt y} are stored in temporary variables. The subsequent call of
the enclosing sequence method performs the addition (in the third and
fourth argument). A subsequent basic block optimization detects the
copy propagation and eliminates passive code.  So we only need a
minimal number of temporary variables and copy operations. In the
example, just two temporary variables and one sequence method remain.

\begin{verbatim}
      seq(tmp3_real = x_real+y_real, tmp3_imag = x_imag+y_imag)
\end{verbatim}

\noindent Now look at the assignment to {\tt z} and the two required
elementary assignments.

\begin{verbatim}
  seq(seq(tmp3_real = x_real+y_real, tmp3_imag = x_imag+y_imag),
      z_real = tmp3_real, z_imag = tmp3_imag)
\end{verbatim}

\noindent In this case the basic block optimization also reduces the
number of temporary variables and prevents the declaration of a
sequence method. Thus, the resulting Java code does not need any
temporary variables; only a single sequence method needs to be
declared in the enclosing class.\footnote{Since user defined types may
appear in the signature of sequence methods it is impossible to
predefine a collection of sequence methods in a helper class.}

\begin{verbatim}
  seq(z_real = x_real + y_real, z_imag = x_imag + y_imag)
\end{verbatim}

\noindent When we directly construct bytecode, there is no need for
the sequence method. Instead, only the arguments are evaluated.  The
resulting bytecode is identical to the one that would result from a
manual replacement of complex expressions with three-address
statements.

\subsection{Basic transformation rules in detail}
\label{easy}

In the next sections we consider an expression $E$ that consists of
subexpressions $e_1$ through $e_n$. The rewriting rule $eval[E]$
describes (on the right hand side of the $\mapsto$-symbol) the
recursive transformation into pure Java that applies $eval[e_i]$ to
each subexpression. In most cases complex expressions are mapped to
calls of sequence methods whose results are ignored. Sometimes it is
necessary to access the real or imaginary part of a {\tt complex}
expression. For this purpose there are $evalR$ and $evalI$.  Both
cause the same effect as $eval$ but are mapped to special sequence
methods ({\tt seqREAL} or {\tt seqIMAG}) that return the real or the
imaginary part of the {\tt complex} expression. If $evalR$ or $evalI$
are applied to an array of {\tt complex}-values the corresponding
sequence methods will return an array of {\tt double}-values.
Expressions that are not {\tt complex} remain unchanged when treated
by $eval$, $evalR$, or $evalI$.  The $=$-symbol refers to Java's
assignment operator.  In contrast, we use $\equiv$ to define an
identifier (left hand side of $\equiv$) that has to be expanded
textually by the expression on the right hand side.

To process the left hand side of assignments we use another rewriting
rule: $access[E]$ does not return a value but instead returns the
shortest access path to a subexpression, requiring at most one pointer
dereferencing.

From the above example, it is obvious that a lot of temporary
variables are added to the block that encloses the translated
expressions. Most of these temporary variables are removed later by
optimizations.\footnote{In case of static code or the initialization
of instance variables the remaining temporary variables are neither
static nor instance variables: they can be converted to local
variables by enclosing them with static or dynamic blocks.}  The
following transformation rules do not show the declaration of
temporary variables explicitly. However, they can easily be identified
by means of the naming convention: if $e$ is a {\tt complex}
expression, the identifiers $e_{real}$ and $e_{imag}$ denote the two
corresponding temporary variables of type {\tt double}. The use of any
other temporary variables is explained in the text. Arrays of {\tt
complex} are discussed in Section~\ref{arraytrafo}; method invocations
are described in Section~\ref{foo}. The rules for unary operations,
constant values, and literals are trivial and will be skipped. Details
can be obtained from \cite{JavaParty}.

\paragraph{Plain identifier:} The transformation rule
for $E \equiv c$ is:\\ \centerline{ \( eval[c] \mapsto
seq(E_{real} = c_{real}, E_{imag} = c_{imag})\)} Both components of
the {\tt complex} variable $c$ are stored to temporary variables that
represent the result of the expression $E$. If $c$ is used as left
hand side of an assignment, it is sufficient to use the mangled names.

\paragraph{Selection:} The transformation rule for $E
\equiv F.e$ is:\\ \centerline{ \( eval [F.e] \mapsto seq(tmp =
eval[F], E_{real} = tmp.e_{real}, E_{imag} = tmp.e_{imag})\)} $F$ is
evaluated once and stored in a temporary variable $tmp$. Then $tmp$
is used to access the two components.

If $F.e$ is used as the left hand side of an assignment, $F$ is
evaluated to a temporary variable that is used for further
transformations of the right hand side:\\ \centerline{ \(
\begin{array}{rcl} access[F.e] &
\mapsto & tmp = eval[F]\\ & \wedge & E^\downarrow_{real} \equiv
tmp.e_{real}, E^\downarrow_{imag} \equiv tmp.e_{imag} \\
\end{array} \) } 
It is important to note that the transformation rule for assignments
(see below) demands that the code on the right hand side of the
$\mapsto$-symbol is inserted at the position where $access[F.e]$ is
evaluated. Secondly, the identifiers $E^\downarrow_{real}$ and
$E^\downarrow_{imag}$ have to be replaced textually with the code
following the $\equiv$-symbol. (The $\downarrow$-notation and the
textual replacement are supposed to help understanding by clearly
separating the issues of the access path evaluation from the core
assignment. See example below.)

\paragraph{Assignment:} The transformation rule for $E
\equiv e_1 = e_2$ is:\\ \centerline{ \(
\begin{array}{rl}
eval[e_1\!=\!e_{2}]\!\mapsto\!seq( & 
access[e_1], eval[e_2], \\ &
\!E_{real}\!=\!e^\downarrow_{1real}\!=\!e_{2real}, 
E_{imag}\!=\!e^\downarrow_{1imag}\!=\!e_{2imag})\\
\end{array} \)}
First the access to $e_1$ is processed. Then the right hand side of
the assignment is evaluated. The last two steps perform the assignment
of both parts of the {\tt complex} expression. Since the assignment
itself is a Java expression it is necessary to initialize additional
temporary variables that belong to $E$. Occurrences of $e^\downarrow$
are inserted textually according to $access$.

For example, consider the following statement {\tt X.Y.z = x}. With \(
e_1 = {\tt X.Y.z}\) and \(e_2 = {\tt x} \), the transformation results
in:\\
\centerline{ \(
eval[e_1\!=\!e_{2}]\!\mapsto\!
seq(access[{\tt X.Y.z}], eval({\tt x}),\dots) \) }\\
The evaluation of \(access\) needs the transformation rules for
selections, see above.
\centerline{
\( tmp = eval[{\tt X.Y}] \) and \( E^\downarrow_{real} \equiv
tmp.z_{real}, E^\downarrow_{imag} \equiv tmp.z_{imag} \) }\\ We ignore
the fact that {\tt X.Y} is itself is a selection and that it would
require to apply the same transformation rule again. 
The assignment to {\tt tmp} is the immediate result of \( access
\) and will show up in the sequence method's first argument. Since \(
access \) has been applied on $e_1$, the
\(\downarrow \)-expressions are to be inserted textually for every
occurrence of $e_{1real}$ and $e_{1imag}$ in the subsequent arguments
of the sequence method:\\
\centerline{ \( 
eval[e_1\!=\!e_{2}]\!\mapsto\!
seq(\dots, E_{real} = \underbrace{tmp.z_{real}}_{e^\downarrow_{1real}} = e_{2real}, E_{imag} = 
\underbrace{tmp.z_{imag}}_{ e^\downarrow_{1imag}} = e_{2imag}) \) }\\ Since in the example the assignment is a
statement there is no need to actually assign to $E_{real}$ and
$E_{imag}$. Hence, after removing temporary variables and redundant
calls of sequence methods, the final result is:

\begin{verbatim}
    seq(tmp = X.Y, tmp.z_real = x_real, tmp.z_imag = x_imag)
\end{verbatim}

\paragraph{Combination of assignment and operation:} The 
transformation  rule for $E \equiv e_1 \diamond\!= e_2$, 
where $\diamond \in \{+,-,*,/\}$, is:\\
\centerline{ \( eval[e_1 \diamond\!= e_{2}] \mapsto seq(access[e1],
e^\downarrow_1 = eval[e^\downarrow_1 \diamond e_{2}]) \)} 

\noindent The address of the left hand side of the assignment is
evaluated; every occurrence of $e^\downarrow_1$ is replaced textually
with the code determined by $access$. The address is used as left
operand of the operation. Finally, the result of the operation is
written to the calculated address. This strategy is essential to avoid
repetition of side effects while evaluating $e_1$.

\paragraph{Comparison:} The transformation rule for $E
\equiv e_1 == e_2$ is:\\ \centerline{ \(
\begin{array}{rl}
eval[e_1 == e_{2}]
\mapsto seq_{value} ( & eval[e_1], eval[e_{2}], \\
 & e_{1real} == e_{2real}\
\&\& \ e_{1imag} == e_{2imag})\\
\end{array} \)} In contrast to the sequence methods
used before, this one is not returning a dummy value. Instead
$seq_{value}$ returns the value of its last argument.  The result of
the whole expression is a logical AND of the two
comparisons. Inequality tests can be expressed in the same way, we
just have to use $!\!=$ and $||$ instead of $==$ and $\&\&$. This
special kind of sequence method can also be removed while generating
bytecode.

\paragraph{Addition and subtraction:} The transformation
rule for $E \equiv e_1 \diamond e_2$, where $\diamond \in \{+,-\}$,
is:\\ \centerline{ \( 
\begin{array}{rl}
eval[e_1 \diamond e_{2}] \mapsto seq
(eval[e_1], eval[e_{2}], & E_{real} = e_{1real} \diamond e_{2real},\\
& E_{imag} = e_{1imag} \diamond e_{2imag}) \\
\end{array} \)}

\paragraph{Multiplication:} The transformation rule for 
$E \equiv e_1 * e_2$ is:\\
\centerline{ \(
\begin{array}{rcll}
 eval[e_1 * e_{2}] & \mapsto &
seq(eval[e_1], eval[e_{2}], & E_{real} = e_{1real} * e_{2real} +
e_{1imag} * e_{2imag},\\
 &&& E_{imag} = e_{1real} * e_{2imag} - e_{1imag} *
e_{2real})\\\end{array} \) }

\paragraph{Division:} The rule for division is
structurally identical to the rule for multiplication but the
expressions are considerably more complicated. {\it cj\,} offers two
versions to divide {\tt complex} expressions: a standard
implementation and a slower but numerically more stable version. The
second alternative is based on the reference implementation
\cite{JavaGrandeComplex}.  For brevity, neither of the versions is shown.

\paragraph{Type cast:} Because {\tt complex} is defined
as a supertype of {\tt double}, implicit type casts are inserted where
necessary. Furthermore, it is appropriate to remove explicit type
casts to {\tt complex} if the expression to be casted is already of
type {\tt complex}. The only remaining case ($E \equiv (complex)\ e$)
can be handled with the following rule:\\ \centerline{ \( eval[
(complex)\ e] \mapsto seq (eval[e], E_{real} = e, E_{imag} = 0) \)}

\paragraph{String concatenation:} Since string
concatenation is not considered as time-critical {\it cj\,} creates an
object of type {\tt Complex} and invokes the corresponding method {\tt
toString}. An additional benefit is that the output format can be
changed without modifying the compiler. The transformation rule
is:\\ \centerline{ \( eval[str + e] \mapsto str + (new\
Complex(evalR[e], e_{imag}).toString()) \) } $EvalR[e]$ evaluates $e$
and returns its real part. Furthermore $evalR$ declares a temporary
variable $e_{imag}$ and initializes it with the imaginary part of
$e$. This asymmetry is necessary to ensure that $e$ is evaluated
exactly once.  For brevity, we skip similar rules for $e + str$ and
the $+=$-operation.

\subsection{Transformation rules for arrays}
\label{arraytrafo}

Although it is obvious that a variable of type {\tt complex} must be
mapped to a pair of two {\tt double}-variables, there is no obvious
solution for arrays of {\tt complex}. There are two options: an array
of {\tt complex} can either be replaced by two {\tt double}-arrays or
by one {\tt double}-array of twice the size. For the latter, our
performance measurements indicated that in general it is faster to
store pairs of {\tt double}-values in adjacent index positions than to
store all real parts {\it en bloc\,} before storing all the
imaginary parts.

\begin{figure}[htb]
\centerline{\psfig{figure=nojit.prn,scale=60,clip=}}
\vspace{5mm}
\centerline{\psfig{figure=jit.prn,scale=60,clip=}}
\caption{Performance of 2-array solution compared to 1-array
solution in two different JVM/JIT-environments.}
\label{arrayfig}
\end{figure}

For various array sizes, we compared the speed of array creation,
initialization and garbage collection (called `init' in
Figure~\ref{arrayfig}) for the 1-array and the 2-array solution.  The
lines show how much faster ($<1$) or slower ($>1$) the 2-array
solution is over the 1-array solution ($=100\%$). Similar for read and
write access to the array elements. All measurements have been
repeated several times to be able to ignore clock resolution and to
achieve a small variance.

It can be noticed that there is no clear advantage of either the
1-array solution of the 2-array solution.  The average of all
measurements is within $[0.98;1,02]$ for both platforms.  We got
similar results on other platforms and with other JITs.  Read and
write access is much more stable with HotSpot, however there is some
peculiar behavior for initialization. HotSpot probably uses different
mechanisms for arrays of different sizes.

We implemented the 2-array solution, since it is neither faster nor
slower than the 1-array solution and since use of the 2-array solution
eases the implementation of {\it cj}.

\paragraph{Array creation:} 
Java
offers different language elements to create arrays or to create and
initialize arrays in one step. Let us first discuss the transformation
rule for pure array creation:\\ \centerline{ \begin{minipage}{95mm}
\(eval [new\ complex [e_1]\ldots[e_n] ] \mapsto \)\\
\(\hspace*{3mm}seq(E_{real} = new\ double
[e_1'=eval[e_1]]\ldots[e_n'=eval[e_n]],\)\\ \(\hspace*{9mm}E_{imag} =
new\ double [e_1']\ldots[e_n'])\)
\end{minipage}
} 
When calculating $E_{real}$, additional temporary variables $e'_i$
are used to allow the reuse of size expressions in the
imaginary part. 

\paragraph{Array creation with initialization:} 
Array initialization is done according to the following rule:\\
\centerline{
\begin{minipage}{95mm}
 \(eval [new\ complex\ []\ldots[] \{e_1,\ldots, e_n \}] \mapsto
\)\\ \(\hspace*{3mm}seq(E_{real} = new\ double[]\ldots[]
\{evalR[e_1],\ldots,evalR[e_n]\},\)\\ \(\hspace*{9mm}E_{imag}=new\
double[]\ldots[] \{e_{1imag},\ldots, e_{n\,imag}\})\)
\end{minipage}
} {\it EvalR\,} is able to handle inner array initialization by applying the
same rule recursively to array initializations with a smaller number
of dimensions.

\paragraph{Array access:} The transformation rule for $E
\equiv F[e_1]\ldots[e_n]$ is:\\ \centerline{ 
\(
\begin{array}{rl}
 eval [F [e_1]\ldots[e_n]]\!\mapsto\!  seq( & eval[F],\\
& E_{real}\!=\!F_{real}[e'_1\!=\!eval[e_1]]\ldots[e'_n\!=\!eval[e_n]
], \\
& E_{imag} = F_{imag} [e_1']\ldots[e_n']) 
\end{array} \) }
Again, temporary variables $e'_i$ are used to allow the reuse of index
expressions in the imaginary part.

\paragraph{Array access used as left hand side of an
assignment:} Such expressions may be affected by side effects because
the evaluation of index expressions could modify the array itself.
For example, in {\tt F[foo()]}$\diamond${\tt =}\dots, {\tt foo()}
could alter some elements of {\tt F}. Hence, the address evaluation
for {\tt F} which is needed repeatedly for the $\diamond${\tt
=}-operation must be separated from the evaluation of the index
expression which must be evaluated exactly once.  To achieve this it
is in general necessary to store a reference to the array in a
temporary variable.

For one-dimensional arrays, the transformation rule is:\\
\centerline{ \(
\begin{array}{rcl}
access(F[e]) & \mapsto & tmp = eval[F] \\
& \wedge  & E^\downarrow_{real} \equiv tmp_{real}[e'=eval[e]], 
            E^\downarrow_{imag} \equiv tmp_{imag}[e'] \\
\end{array}
\)}
As before, the $\downarrow$-notation emphasizes that the given
expressions are to be textually inserted on the right hand side of the
assignment. Hence, in the example, the resulting sequence method
would execute {\tt foo()} exactly once.

For $n$-dimensional arrays ($n>1$), it is sufficient to keep a temporary
reference to the (n-1)-dimensional sub-array $F[e_1]...[e_{n-1}]$.  The
transformation rule for the general case is:\\
\centerline{ \(
\begin{array}{rcl}
access[F [e_1]\ldots[e_n]] & \mapsto & tmp =
eval[F[e_1]\ldots[e_{n-1}]]\\ & \wedge & E^\downarrow_{real} \equiv
tmp_{real}[e_n'=eval[e_n]], E^\downarrow_{imag} \equiv
tmp_{imag}[e_n'] \\\end{array} \)} 
\noindent Again we are using a new temporary variable $e_n'$ to make
sure that the index expression is evaluated exactly once. 


\subsection{Transformation rules for method calls}
\label{foo}

We discuss {\tt complex} parameters and {\tt complex} return values
separately. Moreover, constructors must be treated differently.

\paragraph{Complex return value:} There are no means in
the JVM instruction set to return two values from a method. An obvious
work-around would be to create and return an object (or an array of
two {\tt doubles}) every time the method is called. In most cases,
this object is only necessary to pass the result out of the method and
can be disposed right afterwards.  In contrast, {\it cj\,} creates a
separate array of two {\tt doubles} for {\it each textual method call}. This
array is not defined in the enclosing block but at the beginning of
the method that encloses the call.  This strategy minimizes the number
of temporary objects that have to be created, e.g.\ for a call inside
a loop body. Instead of calling the original method $\mathit{foo}$ we
are calling a method $\widehat{\mathit{foo}}$ with a modified
signature: we pass a reference to this temporary array as an
additional argument. This temporary array is created once per textual call of
the enclosing method and may be reused several times. So the
transformation rule for $E \equiv foo()$ is (similar for methods with
arguments):\\ \centerline{ \( eval [foo()] \mapsto
seq(\widehat{\mathit{foo}}(tmp), E_{real} = tmp[0], E_{imag} =
tmp[1])\)} Two details are important to ensure the correctness of this
transformation for recursive calls and in multithreaded situations:
First, the temporary array is local to the enclosing method and
second, every textual occurrence of a call of $\mathit{foo}$ causes
the creation of a different temporary variable.

The return type of $\widehat{\mathit{foo}}$ is not {\tt void}. Instead
it returns a dummy value ({\tt null}) so that $\widehat{\mathit{foo}}$
still can be used
inside expressions.\footnote{Before returning, the elements of the
newly added array argument are initialized.}

\paragraph{Complex argument:} We use the obvious approach
by again modifying the signature of the method. Instead of passing one
argument of type {\tt complex} we hand over two {\tt double}-values.
It is important that not only the argument list of the method but also
its name is changed. This is necessary to avoid collisions with
existing methods that have the same argument types as the newly
created one.  The transformation rule can be formalized as (similar
for methods expecting several arguments of type {\tt complex}):\\
\centerline{ \( eval [bar(e)] \mapsto
\widehat{bar}(evalR[e],e_{imag})\)}

\paragraph{Constructor method:} 
Calls of constructor
methods can be treated in the same way -- except for the fact that it
is not possible to modify the name of a constructor.\footnote{To avoid
collisions that may be caused by altering the argument list, {\it
cj\,} adds a dummy parameter of a helper type. This is not shown in
the example.} Since the first statement in the body of a constructor
needs to be a call of another constructor the techniques described
above would cause the creation of invalid programs if one of its
parameters is of type {\tt complex}. The solution is demonstrated by
means of the following example.


\begin{verbatim}
  public Foo(complex x, complex z) {
    super((x+x)+z);
  }
\end{verbatim}

\noindent In this example the transformation of {\tt (x+x)+z} would
insert statements to declare temporary variables before the call of
{\tt super}. As pointed out, this is not legal in Java. To allow the
use of {\tt complex} in constructor calls an additional constructor is
created. This new constructor expects the same argument list as the
first one plus additional arguments, one for each of the necessary
temporary variables.

\begin{verbatim}
  private Foo(double x_real, double x_imag, //arguments of the 
              double z_real, double z_imag, //first constructor
              double tmp1_real, double tmp1_imag,  //temp.vars.
              double tmp2_real, double tmp2_imag) { 
    super(seqREAL(seq(tmp1_real = x_real+x_real, //generated
                      tmp1_imag = x_imag+x_imag),//when 
                  tmp2_real = tmp1_real+z_real,  //translating
                  tmp2_imag = tmp1_imag+z_imag), //super((x+x)+z) 
          tmp2_imag);
  }
\end{verbatim}

\noindent The call of {\tt super} has also been modified to accept two
{\tt double}-values instead one complex expression.

As a last step, the method call itself is transformed. Instead of
calling {\tt super} the newly created constructor is called (by using
{\tt this}). All parameters of the surrounding constructor plus an
arbitrary value for each temporary variable are passed as arguments.

\begin{verbatim}
  public Foo(double x_real, double x_imag, 
             double z_real, double z_imag) {
    this(x_real, x_imag, z_real, z_imag, 0, 0, 0, 0);
  }
\end{verbatim}

\noindent The semantic analysis of {\it cj\,} is able to detect
pathological situations where this strategy fails; {\it cj\,} issues
suitable error messages.  For example, an assignment within an
argument of a constructor call (in our above example: {\tt super(x =
0.0+x)}) cannot be handled.

\section{Benchmarks}
\label{benchmark}

\begin{figure}
\centerline{\psfig{figure=diagramme.eps,scale=46,clip=}}
\caption{Results of the benchmark programs}
\label{benchfig}
\end{figure}

\subsection{Setup}

On a Pentium 100 with 64 MB of RAM and 512 KB of cache we have
installed two operating systems: Linux 2.0.36 (Suse 6.0) and Windows
NT Version 4 (service pack 4).  We have studied several different Java
virtual machines for our tests: a pre-release of SUN's JDK 1.2 for
Linux, SUN's JDK 1.2.1 for Windows, a JDK from IBM, the JVM that is
included in Microsoft's Internet Explorer 5, and the beta release of
SUN's new JIT compiler HotSpot.

Our benchmarks fall into two groups: the group of kernel benchmarks
measures array access, basic arithmetics on {\tt complex}, and method
invocations with {\tt complex} return values. The other group measures
small applications: {\tt complex} matrix multiplication, {\tt complex}
FFT, and Microstrip calculation. (The Microstrip benchmark
\cite{Moreira98} computes the value of the potential field
$\Phi(x,y)$ in a two-dimensional microstrip structure
\cite{Edwards92}.)  There are at least two versions of each program --
one uses our basic type {\tt complex} and the other uses a class to
represent complex numbers.

\subsection{Results}

On average over all benchmarks, the programs using the basic type {\tt
complex} outperform the class-based versions {\it by a factor of 2 up
to 21}, depending on the JVM used.  We achieve the best factor with
SUN's JDK 1.2 for Windows, which is the slowest JVM in our study.  The
smaller improvement factors are achieved with better JVMs (HotSpot and
Internet Explorer) that incorporate certain optimization techniques,
e.g., removal of redundant boundary checks, fast creation and handling
of objects, and aggressive inlining of method bodies.

\subsection{Results in detail}

Figure~\ref{benchfig} gives an overview over all benchmarks, labeled (a) to (f).
In each of these six sub-figures there are five groups of bars, each
group represents a different JVM. The most important item within a
group is the black bar. This bar shows the relative execution time of
the class-based version. The factor by which this version is slower
than the basic type version (grey bar) is printed on top of the black
bar.  Some groups have more than two bars: here we did an additional
transformation by hand, substituting each {\tt complex} by two
variables of type {\tt double}. Those manually optimized programs
(white bar) are just slightly faster than code generated by {\it cj}.

In sub-figures (a) to (c) the improvement is smaller than in the other
figures. It is also apparent that better implementations of the JVM
(Internet Explorer and HotSpot) are quite good in eliminating the
overhead of object creation within the class-based solutions. But {\it
cj\,} still performs better by 10\% to 40\%.

Benchmarks (a) and (c) focus on array access and method invocation. In
contrast, programs (b) and (d-f) are predominantly calculating
arithmetic expressions, where (d) and (e) are also showing some amount
of array accesses. For arithmetics the techniques applied by {\it
cj\,} (inlining of all method invocations and reducing the number of
temporary variables) perform noticeably better than the class-based
solution.  Even on the better JVMs {\it cj\,} is 3 times faster.  On
slow JVMs {\it cj\,} achieves a factor of 8 or more. The main reason
is that {\it cj\,} does a better inlining and can avoid temporary
objects almost completely.

\section{Conclusion}

Complex numbers can be integrated seamlessly and efficiently into
Java. Because of Java's strict evaluation order it is by far not
enough to simply double the operations for their real and imaginary
parts. Sequence methods enable a formalization of the necessary
program transformations in a local context.  Our technique for dealing
with complex return values is efficient because it avoids the creation
of many temporary objects.  In comparison with their class-based
counterparts, the benchmark programs that use the new primitive type
perform better by a factor of 2 up to 21, on average, depending on the
JVM used.

\section*{Acknowledgements}

The Java Grande Forum and Siamak Hassanzadeh from Sun Microsystems
supported us in understanding the necessity of complex numbers in Java
for scientific computing. Thanks to Martin Odersky for providing {\it
gj}.  Bernhard Haumacher and Lutz Prechelt gave valuable advice for
improving the presentation.

%\bibliographystyle{plain}
%\bibliography{../../Literatur/literat}

\begin{thebibliography}{10}

\bibitem{Odersky98}
Gilard Bracha, Martin Odersky, David Stoutamire, and Philip Wadler.
\newblock Making the future safe for the past: Adding genericity to the {J}ava
  programming language.
\newblock In {\em Proc. of OOPSLA'98, 13th Annual Conf. on Object-Oriented
  Programming Systems, Languages, and Applications}, October 1998.
\newblock http://www.cis.unisa.edu.au/$\sim$pizza/gj/.

\bibitem{C9X}
C9x proposal.
\newblock ftp://ftp.dmk.com/DMK/sc22wg14/c9x/complex/ and
  http://anubis.dkuug.dk/jtc1/sc22/wg14/.

\bibitem{Borneo}
Joseph~D. Darcy and William Kahan.
\newblock {B}orneo language.
\newblock http://www.cs.berkeley.edu/$\sim$darcy/Borneo.

\bibitem{Edwards92}
Terence~C. Edwards.
\newblock {\em Foundations for Microstrip Circuit Designs}.
\newblock John Wiley \& Sons, 1992.

\bibitem{GoslingFP}
James Gosling.
\newblock The evolution of numerical computing in {J}ava.
\newblock http://java.sun.com/people/jag/FP.html.

\bibitem{Ninja99}
IBM.
\newblock Numerical intensive {J}ava.
\newblock http://www.alphaWorks.ibm.com/tech/ninja/.

\bibitem{GrandeURL}
{J}ava {G}rande {F}orum.
\newblock http://www.javagrande.org.

\bibitem{JavaParty}
{J}ava{P}arty.
\newblock http://wwwipd.ira.uka.de/JavaParty/.

\bibitem{Kahan91}
William Kahan and J.~W. Thomas.
\newblock Augmenting a programming language with complex arithmetics.
\newblock Technical Report No. 91/667, University of California at Berkeley,
  Department of Computer Science, December 1991.

\bibitem{Moreira98}
Jos{\'e} Moreira and Sam~P. Midkiff.
\newblock Fortran 90 in {CSE}: A case study.
\newblock {\em IEEE Computational Science \& Engineering}, 5(2):39--49,
  April--June 1998.

\bibitem{Sather1}
Stephen~M. Omohundro and David Stoutamire.
\newblock The {S}ather 1.1 specification.
\newblock Technical Report TR-96-012, International Computer Science Institute,
  Berkeley, 1996.

\bibitem{Steele98}
Guy Steele.
\newblock Growing a language.
\newblock In {\em Proc. of OOPSLA'98, 13th Annual Conf. on Object-Oriented
  Programming Systems, Languages, and Applications}, October 1998.
\newblock key note.

\bibitem{Phlipp98k}
George~K. Thiruvathukal, Fabian Breg, Ronald Boisvert, Joseph Darcy,
  Geoffrey~C. Fox, Dennis Gannon, Siamak Hassanzadeh, Jose Moreira, Michael
  Philippsen, Roldan Pozo, and Marc~Snir (editors).
\newblock Java {G}rande {F}orum {R}eport: Making {J}ava work for high-end
  computing.
\newblock In {\em Supercomputing'98: International Conference on High
  Performance Computing and Communications}, Orlando, Florida, November 7--13,
  1998.
\newblock panel handout.

\bibitem{JavaGrandeComplex}
{Visual Numerics}.
\newblock Java grande complex reference.
\newblock http://www.vni.com/corner/garage/grande/index.html, 1999.

\bibitem{Moreira99}
Peng Wu, Sam Midkiff, Jos{\'e} Moreira, and Manish Gupta.
\newblock Efficient support for complex numbers in {J}ava.
\newblock In {\em ACM 1999 Java Grande Conference}, pages 109--118, San
  Francisco, 1999.

\end{thebibliography}

\end{document}

