% -*- Mode: LaTeX -*-

\section{Introduction}

Dynamic memory management is an integral component of modern
programming languages such as C++, Common Lisp, SML, and Haskell that
support the notion of a globally shared heap of objects. It is
possible to manage the heap memory explicitly by means of explicit
allocation and deallocation calls, but usually it is more convenient
to use a separate garbage collector that reclaims storage once it is
no longer in use.  In such cases, the overall performance of the user
program depends heavily on the choice of garbage collection technique
and its run-time performance.

Abstractly, a garbage collector performs two functions: it
distinguishes live objects from those that are garbage ({\em
live-object detection}), and it reclaims the storage allocated to
objects that are garbage ({\em dead-object reclamation}). For
live-object detection, the garbage collector must be able to
distinguish scalar objects from heap objects and determine their sizes
({\em object identification}).

Conventional techniques for object identification
\cite{Appel90,Boehm88a} operate with a very simple memory model and
make little or no use of language and compiler-specific information.
In this paper, we present a new technique for object identification
based on run-time ``type reconstruction'' for polymorphic languages
\cite{Aditya93}. Our scheme bridges the gap between the compiler and
the garbage collector by using compiler-generated, polymorphic type
information and the dynamic call tree of activation frames to compute
the exact run-time types of all objects.  These exact type are then
used by the garbage collector to identify and traverse the live
objects residing on the heap.  We describe our implementation and
compare its performance with other storage management schemes,
including a conservative garbage collector that does not use any type
information \cite{Boehm88a} and a compiler-directed storage
reclamation scheme that explicitly deallocates objects based on static
life-time analysis \cite{Hicks93}.

%A variety of different garbage collection techniques have been
%presented in the literature (see \cite{Wilson92} for a recent survey).
%All these techniques rely upon some way of identifying the heap
%objects that are live or currently in use. Conceptually, this requires
%the ability to identify a root set of objects, the ability to
%distinguish aggregate objects from scalar ones, and to determine the
%size of the aggregate objects. But, the actual means of achieving the
%above goal varies from system to system. In this paper, we concentrate
%on this very aspect of garbage collection. We will study three
%different mechanism for identifying and traversing the heap objects at
%run-time: maintaining universal type-tags on every object, a
%conservative pointer-guessing scheme, and a compiler-directed scheme
%based on ``run-time type reconstruction'' that computes and uses the
%exact run-time type of all reachable objects. This last scheme is the
%main contribution of this paper.

\subsection{Motivation}

%In this section, we attempt to motivate the reader that an object
%identification scheme based on full run-time type reconstruction is
%interesting and worth comparing against more conventional schemes used
%in other garbage collectors.

A common technique for object identification is to tag every
object: a few bits (usually one or two) in every word are used as a
\ibx{tag} to distinguish scalar objects from pointers to heap objects.
Also, heap objects have headers that identify their type and size.
Keeping tag bits in every word reduces the range of representable
scalars and pointers in conventional architectures, and the user
application also pays the additional cost of tag maintenance.
In some systems such as SML \cite{Appel90}, scalar values (usually
floating point numbers) are \ibx{boxed} in a heap data-structure to
preserve their full range.  This incurs the additional cost of
allocating the box and accessing it indirectly.

If the semantics of a language necessitates a tagged or boxed
representation for objects, or if special hardware support for tags is
available, then run-time type reconstruction is probably not the right
choice.  For example, in the implementation of lazy languages such as
Haskell \cite{PeytonJones92}, all objects need to be boxed into
\ibx{closures} unless they are known to contribute towards the final
result.  These closures can easily identify themselves \via their code
pointers.  Similarly, in a dynamically-typed language like Lisp, type
reconstruction essentially reduces to continuous type maintenance
because there are no static type restrictions on run-time objects.
Again, this would be no cheaper than maintaining tags on every object.

The primary motivation for a type-reconstruction-based object
identification scheme is to take advantage of the enormous
compile-time type information available in a statically-typed language
in optimizing its run-time performance. In particular, it is
possible in such a system to use a tagless and unboxed representation
for scalar objects and eliminate type headers for heap objects because
all that type information can be reconstructed when necessary.  This
not only saves space and unnecessary heap allocations but also saves
time spent in tag maintenance.  Although the cost of type
reconstruction may be significant, it needs to be paid only when the
garbage collection is requested. Therefore, such a scheme may work
very well for scientific applications where numerical performance is
of prime concern and garbage collection is expected to happen
infrequently and is used in conjunction with explicit storage
management. Keeping tagless data also permits easy interoperability
with conventional C and Fortran libraries that do not support tags.

Full run-time type reconstruction also offers some unique advantages
that are not present in other untagged schemes for object
identification.  Having the exact run-time types of objects allows the
garbage collector to examine and traverse objects selectively. For
example, the collector need not search for heap pointers inside a
large array of floating point numbers.  Similarly, the scalar fields
of a record may be safely skipped. For scientific applications
manipulating large numeric arrays, this may constitute a substantial
saving in identifying the set of all live objects.

It is also quite easy in this scheme to generate specialized traversal
and marking functions for user-defined objects and function activation
frames that understand their type and control structure.  These
functions selectively traverse the fields that point to heap objects
as determined by their types, and mark those objects as live.  Since
these functions are specialized to the type of a particular object,
they may be more efficient than interpreting the run-time
reconstructed types of the objects.

Finally, the overall framework for type-reconstruction-based object
traversal and marking easily extends to other applications such as
displaying objects within a debugger, object-oriented I/O \etc.  This
framework serves as a general paradigm for cooperation between the
compiler and the run-time system. We have already used this mechanism
successfully within the Id debugger for the Monsoon machine for
displaying arbitrary Id objects \cite{Aditya93}.

%However, for the class of statically-typed languages that follow
%applicative-order of evaluation,\footnote{By applicative-order
%evaluation, we mean languages that evaluate function arguments before
%or in parallel with the invocation of the function.} type
%reconstruction enables substantial representational savings without
%sacrificing any run-time information.  But more importantly, full
%run-time type reconstruction offers some unique advantages that are
%not present in other schemes for object identification. Having the
%exact run-time types of objects allows the garbage collector to
%examine and traverse objects selectively. For example, the collector
%need not search for heap pointers inside a large array of floating
%point numbers.  Similarly, the scalar fields of a record may be safely
%skipped. For scientific applications manipulating large numeric
%arrays, this may constitute a substantial saving in identifying the
%set of all live objects.

%In this paper, we will describe our compiler-directed object
%identification scheme in detail and compare its compile-time and
%run-time performance with the conservative and tagged identification
%mechanisms also implemented within the same garbage collection system.
%We will also compare the overall performance of these implicit garbage
%collection schemes with an explicit compiler-directed storage
%management scheme \cite{Hicks93} developed under the same environment.

\subsection{Related Work}

Conservative and tagged mechanisms have been used extensively in
various garbage collection systems (see \cite{Wilson92} for a recent
survey), but object identification based on type reconstruction for
strongly-typed, polymorphic languages is a relatively new idea. The
basic concept for type reconstruction was suggested by Appel
\cite{Appel89} and expanded by Goldberg and Gloger
\cite{Goldberg91,Goldberg92}. These schemes were sometimes unable to
compute the exact run-time type of objects embedded inside polymorphic
functions.  Traversal and marking of such live objects without
complete type information remained a problem. On the other hand, our
object identification scheme is based on a complete run-time type
reconstruction mechanism which ensures that the exact types of all
objects are reconstructed even if those objects are created or
embedded within polymorphic functions \cite{Aditya93}.

Our work also relates to compiler-directed storage reclamation shown
by Hicks \cite{Hicks93} since that scheme also manages dynamic storage
in the context of a strongly-typed, polymorphic language without any
run-time type-tags. In that scheme, the compiler performs life-time
analysis of objects and automatically inserts explicit deallocation
calls at appropriate places in the program. The compile-time cost of
this analysis can be substantial since it uses abstract interpretation
over the whole program, although its run-time cost is minimal.  Also,
sometimes this scheme is unable to reclaim shared or cyclic
data-structures.  Thus, in general, this technique has to be used in
conjunction with a regular garbage collector that picks up the
remaining undetected garbage.

\subsection{System Setup}

In order to make a reasonable performance comparison of the
type-reconstruction-based garbage collection with the conservative and
explicit deallocation schemes, we have implemented them for the same
source language, compiler, and the target architecture.  Our source
language is Id, which is a polymorphic, strongly-typed, implicitly
parallel programming language \cite{Id90.1}.  We are compiling Id for
the *T multiprocessor architecture \cite{*T} and executing it on an
emulator for that machine.

We have chosen a very simple mark-and-sweep garbage collection
algorithm so that the cost of object identification can be clearly
identified during the mark phase. The wall clock performance of the
garbage collection algorithm is not our major concern, we are
primarily interested in the relative cost of type reconstruction and
marking \vs the cost of conservative marking.  Explicit deallocation
scheme serves as a calibration point representing the essential cost
of managing the storage.

\subsection{Outline}

The outline of the rest of the paper is as follows.
Section~\ref{framework} describes the language compilation framework
and our run-time model.  Section~\ref{trec} describes our
compiler-directed garbage collection scheme based on run-time type
reconstruction. In Section~\ref{implementation}, we briefly describe
the *T multi-threaded architecture and our implementation of the
various storage management schemes on it.  Section~\ref{performance}
discusses our benchmarks and presents the performance results.
Finally, Section~\ref{conclusions} presents the conclusions.
