A unified theory of garbage collection

ABSTRACT

Tracing and reference counting are uniformly viewed as being fundamentally different approaches to garbage collection that possess very distinct performance properties. We have implemented high-performance collectors of both types, and in the process observed that the more we optimized them, the more similarly they behaved - that they seem to share some deep structure.

We present a formulation of the two algorithms that shows that they are in fact duals of each other. Intuitively, the difference is that tracing operates on live objects, or "matter", while reference counting operates on dead objects, or "anti-matter". For every operation performed by the tracing collector, there is a precisely corresponding anti-operation performed by the reference counting collector.

Using this framework, we show that all high-performance collectors (for example, deferred reference counting and generational collection) are in fact hybrids of tracing and reference counting. We develop a uniform cost-model for the collectors to quantify the trade-offs that result from choosing different hybridizations of tracing and reference counting. This allows the correct scheme to be selected based on system performance requirements and the expected properties of the target application.

REFERENCES

• 1: A. W. Appel, Simple generational garbage collection and fast allocation, Software—Practice & Experience, v.19 n.2, p.171-183, February 1989 [doi>10.1002/spe.4380190206]
• 2: 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
• 3: David F. Bacon , Clement R. Attanasio , Han B. Lee , V. T. Rajan , Stephen Smith, Java without the coffee breaks: a nonintrusive multiprocessor garbage collector, ACM SIGPLAN Notices, v.36 n.5, p.92-103, May 2001
• 4: David F. Bacon , Perry Cheng , V. T. Rajan, Controlling fragmentation and space consumption in the metronome, a real-time garbage collector for Java, ACM SIGPLAN Notices, v.38 n.7, July 2003
• 5: David F. Bacon , Perry Cheng , V. T. Rajan, A real-time garbage collector with low overhead and consistent utilization, ACM SIGPLAN Notices, v.38 n.1, p.285-298, January 2003
• 6: David F. Bacon , V. T. Rajan, Concurrent Cycle Collection in Reference Counted Systems, Proceedings of the 15th European Conference on Object-Oriented Programming, p.207-235, June 18-22, 2001
• 7: 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]
• 8: Henry G. Baker, The treadmill: real-time garbage collection without motion sickness, ACM SIGPLAN Notices, v.27 n.3, p.66-70, March 1992 [doi>10.1145/130854.130862]
• 9: Jeffrey M. Barth, Shifting garbage collection overhead to compile time, Communications of the ACM, v.20 n.7, p.513-518, July 1977 [doi>10.1145/359636.359713]
• 10: BISHOP,P.B.Computer Systems with a Very Large Address Space and Garbage Collection. PhD thesis, Laboratory for Computer Science, Massachussets Institute of Technology, May 1977. MIT/LCS/TR-178.
• 11: Stephen M Blackburn , Richard Jones , Kathryn S. McKinley , J Eliot B Moss, Beltway: getting around garbage collection gridlock, ACM SIGPLAN Notices, v.37 n.5, May 2002
• 12: Stephen M. Blackburn , Kathryn S. McKinley, Ulterior reference counting: fast garbage collection without a long wait, ACM SIGPLAN Notices, v.38 n.11, November 2003
• 13: Rodney A. Brooks, Trading data space for reduced time and code space in real-time garbage collection on stock hardware, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.256-262, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802042]
• 14: A. M. Cheadle , A. J. Field , S. Marlow , S. L. Peyton Jones , R. L. While, Non-stop Haskell, ACM SIGPLAN Notices, v.35 n.9, p.257-267, Sept. 2000
• 15: C. J. Cheney, A nonrecursive list compacting algorithm, Communications of the ACM, v.13 n.11, p.677-678, Nov 1970 [doi>10.1145/362790.362798]
• 16: Perry Cheng , Guy E. Blelloch, A parallel, real-time garbage collector, ACM SIGPLAN Notices, v.36 n.5, p.125-136, May 2001
• 17: CHRISTOPHER, T. W. Reference count garbage collection. Software - Practice and Experience 14, 6 (June 1984), 503--507.
• 18: George E. Collins, A method for overlapping and erasure of lists, Communications of the ACM, v.3 n.12, p.655-657, Dec. 1960 [doi>10.1145/367487.367501]
• 19: DETREVILLE, J. Experience with concurrent garbage collectors for Modula-2+. Tech. Rep. 64, DEC Systems Research Center, Aug. 1990.
• 20: L. Peter Deutsch , Daniel G. Bobrow, An efficient, incremental, automatic garbage collector, Communications of the ACM, v.19 n.9, p.522-526, Sept. 1976 [doi>10.1145/360336.360345]
• 21: Edsger W. Dijkstra , Leslie Lamport , A. J. Martin , Carel S. Scholten , E. F. M. Steffens, On-the-fly garbage collection: an exercise in cooperation, Language Hierarchies and Interfaces, International Summer School, p.43-56, July 23-August 02, 1975
• 22: Damien Doligez , Xavier Leroy, A concurrent, generational garbage collector for a multithreaded implementation of ML, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.113-123, March 1993, Charleston, South Carolina, United States [doi>10.1145/158511.158611]
• 23: HENRIKSSON,R.Scheduling Garbage Collection in Embedded Systems. PhD thesis, Lund Institute of Technology, July 1998.
• 24: Martin Hirzel , Amer Diwan , Matthew Hertz, Connectivity-based garbage collection, ACM SIGPLAN Notices, v.38 n.11, November 2003
• 25: Richard L. Hudson , J. Eliot B. Moss, Incremental Collection of Mature Objects, Proceedings of the International Workshop on Memory Management, p.388-403, September 17-19, 1992
• 26: Mark Stuart Johnstone , Paul R. Wilson, Non-compacting memory allocation and real-time garbage collection, 1997
• 27: KUNG,H.T.,AND SONG, S. W. An efficient parallel garbage collection system and its correctness proof. In IEEE Symposium on Foundations of Computer Science (1977), pp. 120--131.
• 28: LAMPORT, L. Garbage collection with multiple processes: an exercise in parallelism. In Proc. of the 1976 International Conference on Parallel Processing (1976), pp. 50--54.
• 29: Bernard Lang , Christian Queinnec , José Piquer, Garbage collecting the world, Proceedings of the 19th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.39-50, January 19-22, 1992, Albuquerque, New Mexico, United States [doi>10.1145/143165.143176]
• 30: Martin Larose , Marc Feeley, A compacting incremental collector and its performance in a production quality compiler, ACM SIGPLAN Notices, v.34 n.3, p.1-9, March 1999
• 31: Yossi Levanoni , Erez Petrank, An on-the-fly reference counting garbage collector for Java, Proceedings of the 16th ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, p.367-380, October 14-18, 2001, Tampa Bay, FL, USA
• 32: A. D. Martínez , R. Wachenchauzer , R. D. Lins, Cyclic reference counting with local mark-scan, Information Processing Letters, v.34 n.1, p.31-35, February 1990 [doi>10.1016/0020-0190(90)90226-N]
• 33: John McCarthy, Recursive functions of symbolic expressions and their computation by machine, Part I, Communications of the ACM, v.3 n.4, p.184-195, April 1960 [doi>10.1145/367177.367199]
• 34: Scott Nettles , James O'Toole, Real-time replication garbage collection, ACM SIGPLAN Notices, v.28 n.6, p.217-226, June 1993
• 35: Mendel Rosenblum , John K. Ousterhout, The design and implementation of a log-structured file system, Proceedings of the thirteenth ACM symposium on Operating systems principles, p.1-15, October 13-16, 1991, Pacific Grove, California, United States
• 36: H. Schorr , W. M. Waite, An efficient machine-independent procedure for garbage collection in various list structures, Communications of the ACM, v.10 n.8, p.501-506, Aug. 1967 [doi>10.1145/363534.363554]
• 37: Jacob Seligmann , Steffen Grarup, Incremental Mature Garbage Collection Using the Train Algorithm, Proceedings of the 9th European Conference on Object-Oriented Programming, p.235-252, August 07-11, 1995
• 38: Yefim Shuf , Manish Gupta , Rajesh Bordawekar , Jaswinder Pal Singh, Exploiting prolific types for memory management and optimizations, ACM SIGPLAN Notices, v.37 n.1, p.295-306, Jan. 2002
• 39: Guy L. Steele, Jr., Multiprocessing compactifying garbage collection, Communications of the ACM, v.18 n.9, p.495-508, Sept. 1975 [doi>10.1145/361002.361005]
• 40: Darko Stefanović , Kathryn S. McKinley , J. Eliot B. Moss, Age-based garbage collection, ACM SIGPLAN Notices, v.34 n.10, p.370-381, Oct. 1999
• 41: David Ungar, Generation Scavenging: A non-disruptive high performance storage reclamation algorithm, ACM SIGPLAN Notices, v.19 n.5, p.157-167, May 1984
• 42: J. Weizenbaum, Symmetric list processor, Communications of the ACM, v.6 n.9, p.524-536, Sept. 1963 [doi>10.1145/367593.367617]
• 43: Joseph Weizenbaum, Recovery of reentrant list structures in SLIP, Communications of the ACM, v.12 n.7, p.370-372, July 1969 [doi>10.1145/363156.363159]
• 44: T. Yuasa, Real-time garbage collection on general-purpose machines, Journal of Systems and Software, v.11 n.3, p.181-198, Mar. 1990 [doi>10.1016/0164-1212(90)90084-Y]
• 45: Karen Zee , Martin Rinard, Write barrier removal by static analysis, ACM SIGPLAN Notices, v.37 n.11, November 2002
• 46: ZORN, B. Barrier methods for garbage collection. Tech. Rep. CU-CS-494-90, University of Colorado at Boulder, 1990.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Dynamic storage management

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Memory management (garbage collection)
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Garbage collection

General Terms:
Algorithms, Languages, Performance

Keywords:
graph algorithms, mark-and-sweep, reference counting, tracing