Combining generational and conservative garbage collection: framework and implementations

ABSTRACT

Two key ideas in garbage collection are generational collection and conservative pointer-finding. Generational collection and conservative pointer-finding are hard to use together, because generational collection is usually expressed in terms of copying objects, while conservative pointer-finding precludes copying. We present a new framework for defining garbage collectors. When applied to generational collection, it generalizes the notion of younger/older to a partial order. It can describe traditional generational and conservative techniques, and lends itself to combining different techniques in novel ways. We study in particular two new garbage collectors inspired by this framework. Both these collectors use conservative pointer-finding. The first one is based on a rewrite of an existing trace-and-sweep collector to use one level of generation. The second one has a single parameter, which controls how objects are partitioned into generations: the value of this parameter can be changed dynamically with no overhead. We have implemented both collectors and present measurements of their performance in practice.

REFERENCES

• Appel88: A. W. Appel , J. R. Ellis , K. Li, Real-time concurrent collection on stock multiprocessors, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.11-20, June 20-24, 1988, Atlanta, Georgia, United States
• Baker78: Henry G. Baker, Jr., List processing in real time on a serial computer, Communications of the ACM, v.21 n.4, p.280-294, April 1978 [doi>10.1145/359460.359470]
• Bartlett88: Joel F. Bartlett. Compacting Garbage Collection with Ambiguous Roots. Western Research L~boratory Research Report 88/2, Digital Equipment Corp., February 1988.
• Boehm88: 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]
• Cardelli88: Luca Cardelli, James Donahue, Lucille Glassman, Mick Jordan, Bill Kalsow and Greg Nelson. Modula-3 Report. Olivetti Research Center Technical Report ORC-1, 1988.
• Courts87: Bob Courts. Improving Locality of Reference in a Garbage-Collecting Memory Management System. lnternalTl memo, November 1987.
• Fitzgerald86: Robert Fitzgerald , Richard F. Rashid, The integration of virtual memory management and interprocess communication in Accent, ACM Transactions on Computer Systems (TOCS), v.4 n.2, p.147-177, May 1986 [doi>10.1145/214419.214422]
• Gabriel85: Richard P. Gabriel, Performance and evaluation of LISP systems, Massachusetts Institute of Technology, Cambridge, MA, 1985
• Hanson77: David R. Hanson. Storage Management for an Implementation of SNOBOL4. Software: Practice and Experience. Vol. 7, No. 2. pp. 179-192, March 1977.
• Hudak86: Paul Hudak, A semantic model of reference counting and its abstraction (detailed summary), Proceedings of the 1986 ACM conference on LISP and functional programming, p.351-363, August 1986, Cambridge, Massachusetts, United States [doi>10.1145/319838.319876]
• IBUKI87: IBUKI Common Lisp, IBLC Release 01/01. IBUKI, Mountain View, Ca, 1987.
• Lieberman83: Henry Lieberman , Carl Hewitt, A real-time garbage collector based on the lifetimes of objects, Communications of the ACM, v.26 n.6, p.419-429, June 1983 [doi>10.1145/358141.358147]
• Moon84: David A. Moon, Garbage collection in a large LISP system, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.235-246, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802040]
• Ripley78: G. David Ripley, Ralph E. Griswold, David R. Han~n. Performance of Storage Management in an implementation of S NOBOL4. IEEE Transactions on Soft,re Engineering, SE-4, No. 2, pp. 130-137, March 1978.
• Rovner85: Paul Rovner. On Adding Garbage Collection and Runtime Types to a Strongly-Typed, Statically- Checked, Concurrent Language. Xerox PARC Report CSL-84-7,1985.
• Shaw87: Robert A. Shaw. improving Garbage Collector Performance in Virtual Memory. Computer Systems Laboratory Technical Report: CSL-TR-87-323. Stanford University, March 1987.
• Sobalvarro88: Patrick G. Sobalvarro. A Lifetime-based Garbage Collector for LISP Systems on General- Purpose Computers, Bachelors Thesis. Electrical Engineering and Computer Science. Massachusetts institute of Technology. September 1988.
• Unger84: David Ungar, Generation Scavenging: A non-disruptive high performance storage reclamation algorithm, Proceedings of the first ACM SIGSOFT/SIGPLAN software engineering symposium on Practical software development environments, p.157-167, April 1984
• Weiser89: M. Weiser , A. Demers , C. Hauser, The portable common runtime approach to interoperability, Proceedings of the twelfth ACM symposium on Operating systems principles, p.114-122, November 1989
• Wilson89: P. R. Wilson, A simple bucket-brigade advancement mechanism for generation-bases garbage collection, ACM SIGPLAN Notices, v.24 n.5, p.38-46, May 1989 [doi>10.1145/66068.66070]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Allocation/deallocation strategies

General Terms:
Design, Languages, Theory