\section{Benchmarking the System}
\label{sec:benchmarks}

It would be impractical to use Java as a new intermediate language if
its performance was not comparable to that of the existing system.  In
this section we compare the performance of the generated Java code
running on different Java virtual machines to that of the original
\vcode\ running on a native \vcode\ interpreter.  Specifically, we test:

\begin{itemize}
\item \emph{JDK:} A Java interpreter.  Java interpreters are available
  for most current platforms.
\item \emph{JIT:} A just-in-time (JIT) Java compiler.  JIT compilers use
  run-time code generation to reduce interpretive overhead in iterative
  constructs such as loops; however, they are more difficult to
  implement (for example, at the time of writing, no web browser for a
  Unix platform has a JIT Java compiler).
\item \emph{Native:} The native \vcode\ interpreter, written in C and
  linked against a serial version of the \cvl\ library.  The code has
  been tuned for asymptotic performance on large vectors, with
  hand-unrolled loops and a memory-management mechanism designed
  specifically for \vcode.
\end{itemize}

We use three standard \nesl\ benchmarks: 

\begin{itemize}
\item \emph{Least-squares line-fitting}: Finds the best fit to a
  sequence of points using the least-squares method.  It is simple
  straight-line code with no conditionals or loops, and hence can be
  used to measure interpretive overhead~\cite{javanesl-tr96}.
\item \emph{Selection (generalized median-finding)}: Finds the element
  in a vector that would be at a specified position if the vector were
  sorted.  It picks the middle element of the vector as a pivot to split
  it into two parts, and recursively finds the required element in the 
  appropriate part.
\item \emph{Sparse matrix-vector multiplication}: Multiplies a sparse
  matrix stored in compressed row format by a dense vector.  It uses a
  nested data-parallel algorithm.
\end{itemize}

We give the source code and test data for the benchmarks in
Appendix~\ref{sec:benchmarkcode}.  All three benchmarks have asymptotic
running times that are linear in the size of the problem.  Timings for
the benchmarks have previously been reported in~\cite{nesl-jpdc94,
  Hardwick94}.

\subsection{Methodology}

To minimize performance effects due to machine architecture, we used
two different machines for benchmarking: a Sun SPARCstation~5/85 running
Solaris~2.5, and a DX4-120 PC running Windows~95.  Compilation was done
using \nesl\ 3.1, gcc v2.7.0, and JDK 1.1.1, with full optimization.  We
used Sun's latest reference JDK 1.1.1 as the Java interpreter on both
platforms (although the code generated by our system is
backwards-compatible with JDK 1.0.2).  In addition, on the PC we used
Microsoft's JIT compiler from Internet Explorer v3.02, and on the Sparc
we used Sun's JIT compiler for JDK 1.0.2.  

All benchmarks were performed on idle machines to minimize outside
effects.  This is particularly important for the Java benchmarks,
because Java provides only a time-of-day clock rather than a per-process
timer.  The poor resolution of the standard PC clock also created
problems.  To obtain accurate timings of the benchmarks at small problem
sizes, we timed multiple iterations of each benchmark, adjusting
iteration counts so that each total run took at least one second.
We ran the Java virtual machines with their default heap sizes, which
resulted in some garbage collection taking place for all but the
smallest of runs.  To reduce these nondeterministic memory effects, we
forced a garbage collection before the beginning of a benchmark.
Each of the benchmarks
was run five times at problem sizes ranging from $2^1$ to $2^{17}$
(131072).  Table~\ref{tab:results-table} contains results for selected
problem sizes, while Figure~\ref{fig:linefit} shows performance graphs.
We'll analyze the results for the line-fit benchmark in depth
(concentrating on the PC platform), and then briefly discuss the results
for the selection and sparse matrix-vector multiplication benchmarks.

\begin{table}[htb]
  \singlespacing
  \begin{center}
    \begin{tabular}{|r|rrrrrr|} \hline
        \multicolumn{1}{|c|}{Problem} & \multicolumn{3}{c|}{DX4-120 PC} & 
        \multicolumn{3}{c|}{SPARCstation 5/85} \\
        \multicolumn{1}{|c|}{size} & 
        \multicolumn{1}{c} {JDK} &
        \multicolumn{1}{c} {JIT} & 
        \multicolumn{1}{c|} {Native} &
        \multicolumn{1}{c} {JDK} &
        \multicolumn{1}{c} {JIT} & 
        \multicolumn{1}{c|} {Native} \\
        \hline & \multicolumn{6}{c|}{Line-fit} \\
        16    &  3.9  &  2.0 & 0.73 &  3.3 &  3.2 & 0.62 \\
        128   &  8.7  &  3.7 &  1.3 &  6.5 &  3.9 & 0.85 \\
        1024  &   46  &   14 &  6.6 &   35 &   10 &  5.4 \\
        8192  &  346  &   99 &   50 &  265 &   65 &   40 \\
        65536 & 2780  &  780 &  464 & 2132 &  480 &  312 \\
        \hline & \multicolumn{6}{c|}{Selection} \\
        16    &  6.5  &  4.1 &  1.3 &  4.8 &  5.2 &  1.3 \\
        128   &   12  &  7.0 &  2.1 &  9.4 &  8.3 &  2.0 \\
        1024  &   36  &   16 &  4.7 &   30 &   17 &  4.3 \\
        8192  &  182  &   55 &   19 &  156 &   51 &   21 \\
        65536 & 1308  &  286 &  127 & 1145 &  297 &  155 \\
        \hline & \multicolumn{6}{c|}{Sparse matrix-vector multiplication} \\
        16    &  1.0  & 0.60 & 0.17 &  0.7 & 0.73 & 0.14 \\
        128   &  2.1  &  1.0 & 0.28 &  1.6 & 0.92 & 0.20 \\
        1024  &   10  &  4.0 &  1.4 &  8.2 &  2.5 & 0.95 \\
        8192  &   73  &   24 &   12 &   60 &   16 &  8.2 \\
        65536 &  604  &  187 &  112 &  479 &  120 &   68 \\
      \hline
    \end{tabular}
  \end{center}
  \onehalfspacing
  \caption{Average running times in milliseconds for three \nesl\ benchmarks
    using different intermediate language implementations on a DX4-120 PC
    and a SPARCstation 5/85.} 
  \label{tab:results-table}
\end{table}

\begin{figure}[p]
  \centerline{Line fitting benchmark}
  \vspace{0.1in}
  \centerline{\psfig{figure=pc-linefit-mono.ps,width=3.3in}
    \psfig{figure=sparc-linefit-mono.ps,width=3.3in}}
  \vspace{0.1in}
  \centerline{Selection benchmark}
  \vspace{0.1in}
  \centerline{\psfig{figure=pc-select-mono.ps,width=3.3in}
    \psfig{figure=sparc-select-mono.ps,width=3.3in}}
  \vspace{0.1in}
  \centerline{Sparse matrix-vector multiplication benchmark}
  \vspace{0.1in}
  \centerline{\psfig{figure=pc-sparsemat-mono.ps,width=3.3in}
    \psfig{figure=sparc-sparsemat-mono.ps,width=3.3in}}
  \onehalfspacing
  \caption{
    Performance of different intermediate language implementations for
    three \nesl\ benchmarks using a DX4-120 PC (left) and a SPARCstation
    5/85 (right).  Note that the $x$ axis has a log scale.}
  \label{fig:linefit}
\end{figure}


\subsection{Line-fit Benchmark}

On the line-fit benchmark, 
the native \vcode\ interpreter is fastest, as we would expect, and its
relative advantage is greatest at small vector sizes.  Absolute
performance falls off after approximately 16,000 elements, when the
problem no longer fits into the PC's 256~KB L2 cache.

The JIT compiler achieves about half the performance of the \vcode\ 
interpreter for problems bigger than approximately 1,000 elements.  The
line-fit benchmark is dominated by looping over arrays; we suspect that
some of the performance loss is to due to the requirement that a Java VM
must initialize every element of an array before use, and must perform
bounds checks on every array access.  There are techniques for
guaranteeing valid indices without requiring these extra conditionals,
such as performing loop-bounds analysis or exploiting virtual memory
mechanisms for protection purposes; to our knowledge, however, these
optimizations are not performed by any current JIT compiler.

% Cite Asymetrix Supercede?

Finally, the JDK interpreter achieves about one-sixth the performance of
the native \vcode\ interpreter, since it has the additional overhead of
interpreting every bytecode instruction in the loops of the code.
This is too slow for computationally-intensive simulations; JIT
compilers are required for good performance.

We can also use the results of the line-fit benchmark to calculate the
fixed overhead and asymptotic time per element of each implementation.
This is possible because the benchmark executes a fixed number of
\vcode\ operations---and hence should has a fixed \vcode\ interpretive
overhead---for all problem sizes.  The resulting figures for the
constant overhead and the time per element are shown in
Table~\ref{tab:overhead}.

\begin{table}[htb]
  \begin{center}
    \begin{tabular}{|l|r|r|r|r|} \hline
        & \multicolumn{2}{c|}{120~MHz 486 PC} 
        & \multicolumn{2}{c|}{SPARCstation 5/85} \\
      \multicolumn{1}{|c|}{Implementation}
        & \multicolumn{1}{c|}{Overhead}
        & \multicolumn{1}{c|}{Per-elt.}
        & \multicolumn{1}{c|}{Overhead}
        & \multicolumn{1}{c|}{Per-elt.} \\ \hline
      JDK       & 3220  & 42    & 2420  & 32 \\
      JIT       & 1870  & 12    & 3060  & 7.3 \\
      Native    & 460   & 6.8   &  410  & 4.7 \\ \hline
    \end{tabular}
  \end{center}
  \onehalfspacing
  \caption{Constant overhead and asymptotic time per element (in
    microseconds) for the \nesl\ line-fit benchmark using different
    intermediate language implementations on a PC and a SPARCstation.}
  \label{tab:overhead}
\end{table}

The shapes of the performance curves on the SPARCstation are generally
similar to those on the PC, although the cache effect for the \vcode\ 
interpreter is much more pronounced and happens at around 500 elements,
due to the SPARCstation's much smaller cache.  This general similarity of
the results for the two platforms is true for all three benchmarks,
suggesting that there are no architecture-dependent effects skewing the
results.  The two platforms are also comparable in terms of absolute
speed.

%%%%%%%%%%%%%%%%%%

\subsection{Selection Benchmark}

The ordering of results for the selection benchmark is the same as for
the line-fit benchmark: the \vcode\ interpreter is fastest, followed by
the JIT compiler and finally the JDK.  However, the shapes of the curves
are different, reflecting the fact that the selection benchmark spends
less time in straight-line code than line-fit, and places more emphasis
on recursion and dynamic memory use.  

%%%%%%%%%%%%%%%%%%

\subsection{Sparse Matrix-Vector Multiplication Benchmark}

The ordering of results for the sparse-matrix vector multiplication
benchmark is the same as for the previous two benchmarks.  Even though
this is a nested data-parallel algorithm that uses segmented \vcode\ 
operations, the shapes of the graphs and the performance ratios are
similar to those for the non-nested line-fit benchmark, which uses
mostly unsegmented operations.  

%%%%%%%%%%%%%%%%%%

\subsection{Memory Usage}

The space efficiency of an intermediate language is often as
important as its time efficiency.  The Java \texttt{VcodeEmulation}
class and the existing \cvl\ implementation use essentially the same data
types, and so their memory usage per vector is similar.  For example, a
Java integer array of length $n$ occupies $4n + 16$ bytes in the Sun
JDK, compared to $4n$ bytes in a typical C implementation.  However, the
dynamic memory usage of the \vcode\ and Java interpreters differ.  The
\vcode\ interpreter is optimized for the case of a few big objects
(vectors), whereas Java's general-purpose memory allocation mechanism is
optimized for many small objects.  In particular, the \vcode\ interpreter
uses reference counting to determine when a vector is no longer used,
and hence can reclaim its space immediately.  The interpreter has to
halt and compress vector memory only when it can no longer find a free
fragment large enough to satisfy a request.  By comparison, current Java
virtual machines typically perform garbage collection only when the
system is idle, when there is no longer enough free memory, or on
demand.

As an example, the \vcode\ interpreter requires just over 1.75~MB of
heap to run the line-fit benchmark on input vectors of length $2^{16}$
(65536) without performing memory compaction.  A double-precision
floating-point vector of this length requires 0.5~MB of memory, so the
\vcode\ interpreter is storing at most three of these vectors at any one
time.  The JDK Java interpreter using the original
\texttt{VcodeEmulation} class requires 8.5~MB of heap to run the same
benchmark without triggering a garbage collection, because it does not
immediately reclaim the space used by the temporary vectors that the
benchmark generates.  We therefore extended \texttt{VcodeEmulation} to
reuse the last vector popped from the top of the stack whenever possible
(i.e., whenever the vector is of the right length and type to be used
for a result).  This modification reduces the minimum Java heap size
required to run the benchmark without garbage collection to 3.5~MB, and
all benchmark results are for this modified version of
\texttt{VcodeEmulation}.  A full reference-counting algorithm similar to
that employed by the \vcode\ interpreter would probably reduce the memory
usage still further.  This would effectively be implementing a second
level of garbage collection specialized for our particular language,
which has rather unusual memory usage characteristics.



