Garbage collection for strongly-typed languages using run-time type reconstruction

ABSTRACT

Garbage collectors perform two functions: live-object detection and dead-object reclamation. In this paper, we present a new technique for live-object detection based on run-time type reconstruction for a strongly typed, polymorphic language. This scheme uses compile-time type information together with the run-time tree of activation frames to determine the exact type of every object participating in the computation. These reconstructed types are then used to identify and traverse the live heap objects during garbage collection.We describe an implementation of our scheme for the Id parallel programming language compiled for the *T multiprocessor architecture. We present simulation studies that compare the performance of type-reconstructing garbage collection with conservative garbage collection and compiler-directed storage reclamation.

REFERENCES

• 1: Shail Aditya , Alejandro Caro, Compiler-directed type reconstruction for polymorphic languages, Proceedings of the conference on Functional programming languages and computer architecture, p.74-82, June 09-11, 1993, Copenhagen, Denmark [doi>10.1145/165180.165192]
• 2: Andrew W. Appel. Runtime tags aren't necessary. Lisp and Symbolic Computation, 2(2):153-163, June 1989.
• 3: Andrew W. Appel, A runtime system, Lisp and Symbolic Computation, v.3 n.4, p.343-380, Nov. 1990 [doi>10.1007/BF01807697]
• 4: Zena M. Ariola, A syntactic approach to program transformations, Proceedings of the 1991 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.116-129, June 17-19, 1991, New Haven, Connecticut, United States
• 5: Hans-Juergen Boehm , Mark Weiser, Garbage collection in an uncooperative environment, Software—Practice & Experience, v.18 n.9, p.807-820, September 1988 [doi>10.1002/spe.4380180902]
• 6: Benjamin Goldberg, Tag-free garbage collection for strongly typed programming languages, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.165-176, June 24-28, 1991, Toronto, Ontario, Canada
• 7: Benjamin Goldberg , Michael Gloger, Polymorphic type reconstruction for garbage collection without tags, Proceedings of the 1992 ACM conference on LISP and functional programming, p.53-65, June 22-24, 1992, San Francisco, California, United States
• 8: S. A. Gupta, AN INCREMENTAL TYPE INFERENCE SYSTEM FOR THE PROGRAMMING LANGUAGE ID, Massachusetts Institute of Technology, Cambridge, MA, 1990
• 9: James Hicks, Experiences with compiler-directed storage reclamation, Proceedings of the conference on Functional programming languages and computer architecture, p.95-105, June 09-11, 1993, Copenhagen, Denmark [doi>10.1145/165180.165194]
• 10: Harry G. Mairson, Deciding ML typability is complete for deterministic exponential time, Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.382-401, December 1989, San Francisco, California, United States [doi>10.1145/96709.96748]
• 11: Rishiyur S. Nikhil. Id 90.1 reference manual. CSG Memo 284-2, MIT Laboratory for Computer Science, Cambridge, MA 02139, September 1990.
• 12: G. M. Papadopoulos , G. A. Boughton , R. Greiner , M. J. Beckerle, T: integrated building blocks for parallel computing, Proceedings of the 1993 ACM/IEEE conference on Supercomputing, p.624-635, December 1993, Portland, Oregon, United States [doi>10.1145/169627.169811]
• 13: Simon L. PeytonJones. Implementing lazy functional languages on stock hardware: the Spineless Tagless G-machine. Journal of Functional Programming, 2(2):127-202, April 1992.
• 14: K. R. Traub, A COMPILER FOR THE MIT TAGGED-TOKEN DATAFLOW ARCHITECTURE, Massachusetts Institute of Technology, Cambridge, MA, 1986
• 15: Paul R. Wilson, Uniprocessor Garbage Collection Techniques, Proceedings of the International Workshop on Memory Management, p.1-42, September 17-19, 1992

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Data types and structures
      D.3.4 Processors
          Subjects: Compilers

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.3 Studies of Program Constructs
          Subjects: Type structure

General Terms:
Algorithms, Languages, Performance