\section{Conclusions}
\label{conclusions}

In this paper, we have described a scheme for garbage collection of Id
programs using run-time type reconstruction (TRGC).  We described the
compiler and run-time mechanisms required to reconstruct the exact
types of all run-time objects. We also described an interpreted and a
compiled marking schema for traversing and marking live run-time
objects using the reconstructed type information.  We have implemented
the interpreted marking schema on a simulator for the *T architecture
and compared its performance with conservative garbage collection
(CGC) and compiler-directed storage reclamation (CDSR) on several
benchmarks.

Our results show that in general, TRGC does more work in marking the
live objects than CGC, unless it can avoid scanning large, scalar,
array-like objects using type information. The type reconstruction
overhead increases with the amount of polymorphism and higher-order
functions (closures) used in the program, although the cost of
reconstruction is small compared to the cost of marking live objects
with type interpretation. The cost of interpreted marking itself
should get reduced considerably using the compiled marking schema
instead of type interpretation.

TRGC has the additional advantage that other storage reclamation
schemes may be used, such as compaction or copying.  These may not be
used with CGC because they require the update of live pointers, and
CGC cannot guarantee that what it uses as a pointer is not really a
scalar value. On the other hand, TRGC requires initialization of
polymorphic and pointer data with valid values and cannot cope with
stale data as CGC can.

CDSR consistently does better than either of the garbage collection
schemes in terms of time spent in the run-time system. This is as
expected, although sometimes it is not able to collect all the garbage
and therefore requires more memory than strictly necessary. CDSR also
takes much longer to compile, sometimes increasing compile-time by a
factor of 10.

On the whole, type reconstruction and type-reconstruction-based
garbage collection seem to be a promising area of research with a lot
of scope for compiler optimization and run-time performance
improvement. This initial study has shown that type reconstruction
based garbage collection is certainly feasible and can be competitive
with other storage management strategies under the right mix of
applications.

\subsection{Future Work}

There are several dimensions in which further investigation would be
useful. We already plan to implement the compiled marking schema and
compare its performance with our current interpreted marking schema.
We expect to see a substantial improvement in performance using
specialized marking functions. We also plan to investigate mixed
storage management schemes that combine garbage collection with
explicit storage reclamation within the same run-time environment.

Although our system has been designed and implemented for a
multi-processor architecture, we have currently made a study for only
a single processor. We would like to see how TRGC scales under a
multi-processor environment and quantify the inter-processor
communication overhead for type reconstruction.

It would be very interesting to compare the performance of TRGC with
an explicitly tagged object identification scheme implemented within
the same framework. It would be interesting to know if TRGC offers any
concrete advantages over that technique.

Finally, it would be useful to implement a compacting garbage
collector based on type reconstruction with a very simple allocation
scheme (bumping a pointer) and compare its heap management overhead
with that of the CGC and CDSR that require a more sophisticated
storage management scheme (free lists).

\section{Acknowledgments}

The authors would like to thank Prof. Arvind, Mike Ernst, David Moon
and the anonymous referees for their insightful comments and
suggestions.

The research described in this paper was funded in part by the
Advanced Research Projects Agency of the Department of Defense under
Office of Naval Research contract N00014-89-J-1988.
