% $Id: exp.tex,v 1.13 1997/07/30 19:20:11 cierniak Exp $

\section{EXPERIMENTS}
\label{sec:exp}


For our array-based benchmarks, the JIT version of Briki performs the
same optimizations as its off-line predecessor.  Furthermore for our
data sets the time to perform the optimizations just-in-time is
several orders of magnitude shorter than the time to run the
benchmark, even though we chose small (by scientific computing
standards) problem sizes---none of our benchmarks took more than 15s
to complete.  Since the overhead for JIT optimizations is so small,
the speedups are identical (within three significant digits) with the
results published elsewhere~\cite{Cierniak-offline-CPE-1997} and range
from 10\% to 20\%.

The speedups of Java benchmarks are not as good as the results of
applying the same optimizations to Fortran versions of the same
programs (those were as high as 50\%).  This can be explained by the
lack of standard optimizations in the pre-release version of Kaffe
used in our experiments.  The quality of code generated by Kaffe will,
undoubtfully, improve over time.  The current version produces very
poor code for array references.  For example the i386 instruction
sequence for a simple reference to a 2-D array: {\tt a[i][j]} contains
30 instructions including two branches (for bounds checking) and ten
memory references (for accesses to array handles and register spills
and reloads).  A high-performance Fortran compiler would translate an
array reference like that (if {\tt i} and {\tt j} are loop variables)
to one or two instructions with just one memory reference---the load
of the array element.  Our optimizations reduce the cost of this one
load, by increasing the cache hit ratio for this instruction.  In the
code generated by Kaffe this gain is dampened by the cost of the extra
nine memory references and 20 other instructions which are not
improved by our optimizations.



To provide a better context for the discussion in
Section~\ref{sec:impl}, we present here times spent in various steps
of our optimizer.  We ran those experiments on a Linux computer with a
200~MHz Pentium Pro processor.  Some of the times measured by us were
too short for the granularity of standard Unix timing routines.  To
obtain accurate results, we have used cycle counters defined by the
Pentium architecture.  The resolution of those counters was more than
sufficient for our needs.

Figure~\ref{fig:exp:break:down} shows the break-down of the array
transformation time for the cholesky benchmark.  The time represented
in the figure corresponds to less than half of the total JIT time (if
we include the time of the Kaffe front- and back-ends).  The absolute
time for the array transformation optimization is 8.4ms.
\begin{figure}[hbt]
  \centerline{\psfig{figure=break-down.eps,height=3.2in}}
  \caption{Break-down of the optimization time for cholesky}
  \label{fig:exp:break:down}
\end{figure}



\begin{figure}[hbt]
  \centerline{\psfig{figure=cholesky.eps,height=1.6in}
    \hspace{0.3in}
    \psfig{figure=mxm.eps,height=1.6in}}
  \caption{Briki vs.\ kaffe}
  \label{fig:exp:briki}
\end{figure}
Figure~\ref{fig:exp:briki} shows the overhead for performing array
transformations for Java versions of cholesky and mxm kernels from the
SPEC CPU92 Benchmarks~\cite{SPEC-CPU92-1996}. Note that we have
increased data sizes so that the execution times are meaningful.  For
scientific computing standards the problem sizes are still very small:
on a 200~MHz Pentium Pro the execution times are 4s for mxm and 12s for
cholesky.  However, the array sizes are large enough to benefit from
better locality.

Even for those very small problem sizes, the relative time spent on
our optimizations is completely negligible---three orders of magnitude
shorter than the time spent on useful computation.  Note that the time
spent in Kaffe {\em doing the translation\/} is comparable to the time
spent in Briki.  The time attributed to Kaffe in
Figure~\ref{fig:exp:briki} is larger because we categorize the
start-up time and the time to load all class files as ``Kaffe
overhead.''

