\section{Performance}
\label{performance}

We are interested in two aspects of the performance of the
type-reconstructed garbage collection (TRGC): how long it takes to
garbage collect, and how much garbage it reclaims.  We compared
several programs running with TRGC, conservative garbage collection
(CGC), and compiler-directed storage reclamation (CDSR).

%%%  We would consider TRGC to be useful if it enabled programs to run in less
%%% memory than CGC without incurring an excessive run-time penalty.

In preparing a uniform execution platform, we naturally had to
accommodate the requirements of each storage management scheme within
the same run-time system. This resulted in a system that was not tuned
to any particular storage management scheme. For instance, a copying
garbage collector could not be used for TRGC since CGC would not work
in that setup. Thus, the results we obtained cannot be treated as an
absolute measure of performance for any particular scheme. On the
other hand, they provide a good measure of relative performance of the
object identification mechanisms studied and also characterize systems
where more than one storage management strategy is used.

\subsection{Benchmarking Setup}

\begin{figure*}[t]
\illustrationpercent{cycles}{80}
\caption{Total Cost and Run-time System Cost for the Benchmarks.}
\label{fig:cycles}
\end{figure*}

We used four different benchmarks. \ibx{Quicksort} is the standard
recursive algorithm for sorting $N$ list elements parameterized by a
polymorphic comparison predicate. \ibx{Paraffins} generates and counts
the number of distinct paraffin isomers of up to $N$ carbon atoms.
\ibx{Gamteb} is a Monte Carlo simulation of $N$ photons impinging on a
carbon rod divided into two cells.  Finally, \ibx{Wavefront} consists
of 10 iterations of a successive over-relaxation kernel of a $N \times
N$ matrix containing floating-point data. 

For each of the programs we tested, we ran three versions: TRGC, CGC,
and CDSR.  The TRGC version is the program running with
type-reconstructing garbage collection.  The CGC version is running
with conservative garbage collection, and the CDSR is the
automatically annotated version running with no garbage collection.
Both garbage collectors use the mark and sweep algorithm, and use the
same implementation of sweeping and inter-processor synchronization.
Using a simple GC algorithm allowed us to separate the basic heap
management cost (allocation and deallocation) from the overall cost of
garbage collection. Thus, the cost of object traversal and marking of
TRGC and CGC can be truly ascribed to their respective object
identification strategies.

In all three cases, actual heap storage management and statistics
collection is performed by the same Id run-time system. Although
statistics gathering is mildly intrusive, it constitutes a tiny
fraction of total cycles executed. Online statistics processing
(resampling profiles) is not counted. 

\subsection{Benchmark Runs and Discussion}

We simulated several problem sizes for a single processor with each
program and storage management scheme. The TRGC and CGC runs were made
with sufficient storage to avoid thrashing. Each garbage collected run
also performed a final GC at the end of the run to reclaim all the
uncollected garbage.

The total instruction cycles and the cycles spent in the run-time
system and garbage collection for all the runs are shown in
\fig{cycles}.\footnote{More detailed numbers are available from the
authors. We could not present all the raw numbers here for lack of
space.} The numbers appearing on top of the curves are the number of
garbage collections performed by TRGC and CGC for that run. Both TRGC
and CGC did the same number of garbage collections in all runs.
Garbage collection was switched off for CDSR runs. These curves give
an idea of the growth of run-time system cost of the various schemes
as a function of problem size and as a fraction of the total cost.

\subsubsection{Time Analysis}

Several trends are apparent from \fig{cycles}. The CDSR scheme
consistently has the lowest run-time cost since it does not perform
any garbage collection and only incurs the basic heap and frame
management cost (allocation and deallocation). The fraction of time
spent in the run-time system varies widely depending upon the nature
of the application and the cost and the number of garbage collections
performed. For example, Paraffins allocates a lot of small-sized
data-structures keeping them live until the very end. Thus, each mark
phase has to do a lot of work. Similarly, Quicksort rapidly unfolds
into a tree of activation frames each of which holds onto a
substantial amount of storage, so the cost of marking is high there as
well. On the other hand, for Gamteb, the size of the live heap is
quite small so the garbage collected schemes incur very little
overhead.

\illfigure{breakup}{Run-time System Cost Breakup.}

Comparing the relative run-time costs of TRGC and the CGC, we find
that for Quicksort and Paraffins TRGC does much worse than CGC while
for Wavefront it performs much better.  This wide variation can be
explained by looking at the normalized run-time cost breakup shown in
\fig{breakup} for the largest sized runs. We break the run-time system
cost into basic frame and heap management cost, type reconstruction
cost, the cost of marking frames and objects, and sweeping cost.

For both Quicksort and Paraffins, TRGC spends a significant amount of
time in the type reconstruction phase.  This is due to the fact that
they both contain polymorphic functions so the type reconstruction
mechanism has to generate and propagate the exact run-time type
instantiation down from the root to each frame in the dynamic call
tree. This reconstruction cost is much less visible in Gamteb and
Wavefront that are not polymorphic and largely consist of first-order
functions.  Furthermore, the run-time types are represented as C
data-structures and are currently managed using conventional
\tbx{malloc} and \tbx{free} system calls. This cost can be
substantially reduced by using a specialized version of \tbx{malloc}.

The marking cost of TRGC is also about 1.5-2.2 times higher than that
of CGC in case of Quicksort of 10 elements and Paraffins of 13 carbon
atoms. Our current implementation interprets the type structures at
run-time in order to traverse and mark the corresponding run-time
objects. This interpretation overhead could be eliminated by using the
compiled marking schema as described in Section~\ref{compmark} where
the compiler generates a specialized marking routine for each source
type parameterized over its polymorphic variables. Furthermore, these
routines can be inlined to produce highly optimized traversal and
marking functions for each user-defined function activation frame.

In the case of Wavefront, TRGC takes much less time than CGC, and very
little more time than CDSR, where no marking at all took place (see
\fig{cycles}). For Wavefront of $40\times{}40$, the marking cost of
CGC is 25 times higher than that of TRGC. TRGC did so well because it
could determine that the arrays contained only scalar data by
inspecting their run-time type.  Therefore, it only marked the arrays
themselves and did not scan for pointers inside them, as CGC did. This
scanning cost depends on the total size of the arrays and was
responsible for the quadratic growth in run-time cost for CGC in
\fig{cycles}.  However, sweeping took the same amount of time for both
TRGC and CGC (see \fig{breakup}).

The wavefront example shows that in an ideal situation, the time to
mark the heap for TRGC is proportional to the total \ibx{number} of
live object references, rather than the total \ibx{amount} of live
storage as it is for CGC. TRGC can use the reconstructed type
information to avoid scanning elements of scalar arrays and scalar
fields within records and algebraic types.

\subsubsection{Space Analysis}

In terms of space usage, both TRGC and CGC perform identically. CGC is
able to reclaim all the garbage because of our restrictive compilation
model and support from the run-time system (see Section~\ref{cgc}).
The performance of CDSR varies with the application. For Gamteb and
Wavefront, CDSR is able to insert deallocation commands to reclaim all
the garbage automatically. Therefore, these benchmarks are able to run
under CDSR without leaking any storage. The garbage collected versions
for these benchmarks had to be given 2-10 times the storage used by
CDSR to avoid thrashing. On the other hand, for Paraffins and
Quicksort, CDSR is able to reclaim only 10-20\% of the total garbage,
therefore the TRGC and CGC versions are able to run in same or less
storage than the CDSR version without thrashing.

%\begin{figure*}
%\centering
%\begin{tabular}{|lr|rr|rrrrrrr|r|}\hline
%Mode & Input & Heapsize & Maxheap & Id & IdRTS & Mark & TREC & Sweep & Sync & Other & Total
%\\
%& N &\multicolumn{2}{c|}{(kilowords)}&\multicolumn{7}{c|}{($\times 1000$ cycles)} & ($\times 1000$)
%\\ \hline
%TRGC    & 5     & 2.25   & 1.8  & 151 & 73 & 46 & 5 & 9 & 3 & 97 & 384
% \\
%CGC     & 5     & 2.25   & 1.8  & 151 & 74 &  2 & 0 & 9 & 3 & 78 & 360
% \\
%CDSR      & 5     & 2.25   & 1.7  & 149 & 64 & 0 & 0 & 0 & 1 & 67 & 280
% \\ \hline
%TRGC    & 10    & 12.5  & 10.2 & 729 & 440 & 143 & 43 & 42 & 3 & 170 & 1571
% \\
%CGC     & 10    & 12.5  & 10.2 & 726 & 440 & 147 & 0 & 44 & 3 & 112 & 1474
% \\
%CDSR      & 10    & 12.5  & 10.9 & 721 & 378 & 0 & 0 & 0 & 1 & 122 & 1222
% \\ \hline
%TRGC    & 11    & 22.5  & 19.3 & 1081 & 679 & 232 & 91 & 71 & 3 & 272 & 2430
% \\
%CGC     & 11    & 22.5  & 19.3 & 1084 & 683 & 305 & 0 & 74 & 3 & 167 & 2316
% \\
%CDSR      & 11    & 22.5  & 17.7 & 1061 & 558 & 0 & 0 & 0 & 1 & 183 & 1802
% \\ \hline
%TRGC    & 12    & 37.5 & 33.4 & 2283 & 1163 & 573 & 470 & 193 & 3 & 428 & 4067
% \\
%CGC     & 12    & 37.5 & 33.4 & 1738 & 1112 & 590 & 0 & 126 & 3 & 223 & 3803
% \\
%CDSR      & 12    & 37.5 & 30.8 & 1767 & 915 & 0 & 0 & 0 & 1 & 234 & 2827
% \\ \hline
%\end{tabular}
%\caption{\label{fig:paraffins-performance-results}Performance Results for
% Paraffins of N Carbons}
%\end{figure*}
%The first benchmark, Paraffins, counts the number of distinct isomers
%of up to $N$ carbon atoms.
%Figure~\ref{fig:paraffins-performance-results} shows the performance
%results for Paraffins of $N$ carbons.  In each of these runs, garbage
%collection was performed 2 times, once when the heap fill-fraction
%was exceeded, and once at the end of the run.  Because of this final
%garbage collection, the TRGC and CGC runs actually reclaim more
%storage than the CDSR runs, because the compiler could not insert
%deallocation commands for all of the temporary storage.
%
%
%\begin{figure*}
%\centering
%\begin{tabular}{|lr|rr|rrrrrrr|r|}\hline
%Mode & Input & Heapsize & Maxheap & Id & IdRTS & Mark & TREC & Sweep & Sync & Other & Total
%\\
%&N&\multicolumn{2}{c|}{(kilowords)}&\multicolumn{7}{c|}{($\times 1000$ cycles)} & ($\times 1000$)
%\\ \hline
%TRGC    & 10    & 10  & 3.3 & 970 & 156 & 138 & 10 & 12 & 5 & 215 & 1506
% \\
%CGC     & 10    & 10  & 3.3 & 878 & 158 & 178 & 0 & 12 & 5 & 289 & 1543
% \\
%CDSR     & 10    & 10  & 1.7 & 899 & 166 & 0 & 0 & 0 & 0 & 248 & 1332
% \\ \hline
%TRGC    & 20    & 40  & 8.9 & 1681 & 308 & 100 & 7 & 20 & 3 & 421 & 2595
% \\
%CGC     & 20    & 40  & 8.9 & 1687 & 313 & 117 & 0 & 20 & 3 & 474 & 2615
% \\
%CDSR      & 20    & 40  & 1.8 & 1731 & 329 & 0 & 0 & 0 & 0 & 440 & 2500
% \\ \hline
%TRGC    & 30    & 60  & 12.7 & 2393 & 428 & 63 & 4 & 28 & 3 & 559 & 3542
% \\
%CGC     & 30    & 60  & 12.7 & 2388 & 432 & 90 & 0 & 28 & 3 & 560 & 3568
% \\
%CDSR      & 30    & 60  & 1.8 & 2452 & 454 & 0 & 0 & 0 & 0 & 589 & 3502
% \\ \hline
%TRGC    & 100   & 100  & 20.2 & 7424 & 1299 & 119 & 8 & 72 & 5 & 1489 & 10641
% \\
%CGC     & 100   & 100  & 20.2 & 7431 & 1204 & 49 & 0 & 120 & 5 & 1617 & 10655
% \\
%CDSR      & 100    & 100  & 1.7 & 7636 & 1387 & 0 & 0 & 0 & 0 & 1676 & 10699
% \\ \hline
%\end{tabular}
%\caption{\label{fig:gamteb-performance-results}Performance Results for
%Gamteb of N Particles}
%\end{figure*}
%The second benchmark, Gamteb, is a Monte Carlo simulation of photons
%impinging on a carbon rod divided into two cells.
%Figure~\ref{fig:gamteb-performance-results} shows the performance results
%for Gamteb of $N$ particles.  TRGC performed 5 garbage collections for size
%10, and 2 each for sizes 20 and 30.  CGC collected 3 times for sizes 10 and
%100, and 2 times for sizes 20 and 30.
%
%
%\begin{figure*}
%\centering
%\begin{tabular}{|lr|rr|rrrrrrr|r|}\hline
%Mode & Input & Heapsize & Maxheap & Id & IdRTS & Mark & TREC & Sweep & Sync & Other & Total \\
%&N&\multicolumn{2}{c|}{(kilowords)}&\multicolumn{7}{c|}{($\times 1000$ cycles)} & ($\times 1000$)
%\\ \hline
%TRGC    & 10    & 2.5  & 1.4 & 529 & 24 & 72 & 5 & 6 & 7 & 258 & 901
% \\
%CGC     & 10    & 2.5  & 1.4 & 529 & 24 & 140 & 0 & 6 & 7 & 256 & 963
% \\
%CDSR      & 10    & 1.2  & 1.1 & 533 & 21 & 0 & 0 & 0 & 1 & 193 & 748
% \\ \hline
%TRGC    & 20    & 6  & 5.3 & 2049 & 72 & 72 & 5 & 6 & 7 & 615 & 2827
% \\
%CGC     & 20    & 6  & 5.3 & 2042 & 73 & 351 & 0 & 7 & 7 & 615 & 3095
% \\
%CDSR      & 20    & 3.25  & 3.4 & 2083 & 70 & 0 & 0 & 0 & 1 & 541 & 2626
% \\ \hline
%TRGC    & 30    & 13.5 & 10.5 & 4600 & 111 & 73 & 5 & 7 & 7 & 1218 & 6020
% \\
%CGC     & 30    & 13.5 & 10.5 & 4584 & 111 & 672 & 0 & 6 & 7 & 1217 & 6597
% \\
%CDSR      & 30    & 7 & 6.5 & 4681 & 109 & 0 & 0 & 0 & 1 & 1129 & 5919
% \\ \hline
%TRGC    & 40    & 24  & 20.7 & 8192 & 174 & 73 & 5 & 7 & 7 & 2064 & 10521
% \\
%CGC     & 40    & 24  & 20.7 & 8165 & 174 & 1208 & 0 & 7 & 7 & 2074 & 11636
% \\
%CDSR      & 40    & 24  & 12.7 & 8325 & 171 & 0 & 0 & 0 & 1 & 1956 & 10454
% \\ \hline
%\end{tabular}
%\caption{\label{fig:wavefront-performance-results}Performance Results for
%Wavefront of NxN Matrix for 10 Iterations}
%\end{figure*}
%The third benchmark, Wavefront, is a successive over-relaxation program.
%Figure~\ref{fig:wavefront-performance-results} shows the performance
%results for Wavefront for 10 iterations of an $N\times N$ matrix.  Garbage
%collection was performed 4 times in each of the TRGC and CGC runs.  For
%Wavefront, we see that TRGC takes considerably less time than CGC.  We
%attribute this to the fact that TRGC does not have to mark the elements of
%the matrices created, because it can determine that they are matrices of
%{\tt float}.
%
