Age-based garbage collection

ABSTRACT

Modern generational garbage collectors look for garbage among the young objects, because they have high mortality; however, these objects include the very youngest objects, which clearly are still live. We introduce new garbage collection algorithms, called age-based, some of which postpone consideration of the youngest objects. Collecting less than the whole heap requires write barrier mechanisms to track pointers into the collected region. We describe here a new, efficient write barrier implementation that works for age-based and traditional generational collectors. To compare several collectors, their configurations, and program behavior, we use an accurate simulator that models all heap objects and the pointers among them, but does not model cache or other memory effects. For object-oriented languages, our results demonstrate that an older-first collector, which collects older objects before the youngest ones, copies on average much less data than generational collectors. Our results also show that an older-first collector does track more pointers, but the combined cost of copying and pointer tracking still favors an older-first over a generational collector in many cases. More importantly, we reopen for consideration the question where in the heap and with which policies copying collectors will achieve their best performance.

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: 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]
• 3: Henry G. Baker, Infant mortality and generational garbage collection, ACM SIGPLAN Notices, v.28 n.4, p.55-57, April 1993 [doi>10.1145/152739.152747]
• 4: Barendregt, H.P. The Lambda Calculus: Its Syntax and Semantics. Elsevier (North-Holland), Amsterdam, 1984. Second edition.
• 5: David A. Barrett , Benjamin G. Zorn, Garbage collection using a dynamic threatening boundary, ACM SIGPLAN Notices, v.30 n.6, p.301-314, June 1995
• 6: Bekkers, Y., Canet, B., Ridoux, O., and Ungaro, L. MALI: A memory with a real-time garbage collector for implementing logic programming languages, in 3rd Symposium on Logic Programming (1986), IEEE Press, pp. 258-264.
• 7: Proceedings of the International Workshop on Memory Management, September 1992
• 8: Bishop, P.B. Computer Systems with a Very Large Address Space and Garbage Collection. PhD thesis, Massachusetts Institute of Technology, Cambridge, MA, May 1977.
• 9: 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]
• 10: Perry Cheng , Robert Harper , Peter Lee, Generational stack collection and profile-driven pretenuring, ACM SIGPLAN Notices, v.33 n.5, p.162-173, May 1998
• 11: William D. Clinger , Lars T. Hansen, Generational garbage collection and the radioactive decay model, ACM SIGPLAN Notices, v.32 n.5, p.97-108, May 1997
• 12: Adele Goldberg , David Robson, Smalltalk-80: the language and its implementation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1983
• 13: Barry Hayes, Key objects in garbage collection, Stanford University, Stanford, CA, 1993
• 14: Hosking, A. L., and Hudson, R. L. Remembered sets can also play cards. In OOPSI_A/ECOOP '93 Workshop on Garbage Collection in Object-Oriented Systems (Oct. 1993), E. Moss, P. R. Wilson, and B. Zorn, Eds.
• 15: Antony L. Hosking , J. Eliot B. Moss , Darko Stefanovic, A comparative performance evaluation of write barrier implementation, ACM SIGPLAN Notices, v.27 n.10, p.92-109, Oct. 1992
• 16: 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
• 17: Richard Jones , Rafael Lins, Garbage collection: algorithms for automatic dynamic memory management, John Wiley & Sons, Inc., New York, NY, 1996
• 18: B. Lang , F. Dupont, Incremental incrementally compacting garbage collection, Papers of the Symposium on Interpreters and interpretive techniques, p.253-263, June 24-26, 1987, St. Paul, Minnesota, United States
• 19: 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]
• 20: 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]
• 21: Nystrom, N. Bytecode-level analysis and optimization of Java class files. Master's thesis, Purdue University, West Lafayette, IN, May 1998.
• 22: Martin Odersky , Philip Wadler, Pizza into Java: translating theory into practice, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.146-159, January 15-17, 1997, Paris, France [doi>10.1145/263699.263715]
• 23: Proebsting, T. A., Townsend, G., Bridges, P., Hartman, J. H., Newsham, T., and Watterson, S.A. Toba: Java for applications, a way ahead of time (WAT) compiler. (at http://www.cs.arizona.edu/sumatra/toba/), 1998.
• 24: Sobalvarro, P. G. A lifetime-based garbage collector for LISP systems on general-purpose computers, 1988. B.S. Thesis, Dept. of EECS, Massachusetts Institute of Technology, Cambridge.
• 25: Darko Stefanovic , J. Eliot Moss, Properties of age-based automatic memory reclamation algorithms, 1999
• 26: Darko Stefanovic , J. Eliot B. Moss, Characterization of object behaviour in Standard ML of New Jersey, Proceedings of the 1994 ACM conference on LISP and functional programming, p.43-54, June 27-29, 1994, Orlando, Florida, United States
• 27: 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
• 28: David Michael Ungar, The design and evaluation of a high performance Smalltalk system, MIT Press, Cambridge, MA, 1987
• 29: David Ungar , Frank Jackson, Tenuring policies for generation-based storage reclamation, ACM SIGPLAN Notices, v.23 n.11, p.1-17, Nov. 1988
• 30: David Ungar , Frank Jackson, An adaptive tenuring policy for generation scavengers, ACM Transactions on Programming Languages and Systems (TOPLAS), v.14 n.1, p.1-27, Jan. 1992 [doi>10.1145/111186.116734]
• 31: 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]
• 32: Paul R. Wilson, Uniprocessor Garbage Collection Techniques, Proceedings of the International Workshop on Memory Management, p.1-42, September 17-19, 1992
• 33: P. R. Wilson , T. G. Moher, A “card-marking” scheme for controlling intergenerational references in generation-based garbage collection on stock hardware, ACM SIGPLAN Notices, v.24 n.5, p.87-92, May 1989 [doi>10.1145/66068.66077]
• 34: P. R. Wilson , T. G. Moher, Design of the opportunistic garbage collector, ACM SIGPLAN Notices, v.24 n.10, p.23-35, Oct. 1989
• 35: Zorn, B. Barrier methods for garbage collection. Tech. Rep. CU-CS-494-90, University of Colorado at Boulder, Nov. 1990.
• 36: Benjamin G. Zorn, Comparative Performance Evaluation of, University of California at Berkeley, Berkeley, CA, 1989

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Garbage collection

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Object-oriented languages

  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.2 Installation Management
          Subjects: Benchmarks

General Terms:
Algorithms, Design, Languages, Measurement, Performance, Standardization, Theory

Keywords:
garbage collection, generational and copy collection, object behavior, write barrier