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.
- 1 Appel, A. W. Simple generational garbage collection and fast allocation. Software Practice and Experience 19, 2 (1989), 171- 183. Google ScholarDigital Library
- 2 Baker, H. G. List processing in real-time on a serial computer. Commun. ACM 21, 4 (1978), 280-94. Also AI Laboratory Working Paper 139, 1977. Google ScholarDigital Library
- 3 Baker, H. G. 'infant Mortality' and generational garbage collection. SIGPLAN Notices 28, 4 (1993), 55-57. Google ScholarDigital Library
- 4 Barendregt, H.P. The Lambda Calculus: Its Syntax and Semantics. Elsevier (North-Holland), Amsterdam, 1984. Second edition.Google Scholar
- 5 Barrett, D. A., and Zorn, B. Garbage collection using a dynamic threatening boundary. In Proceedings of SIGPLAN'95 Conference on Programming Languages Design and Implementation (La Jolla, CA, June 1995), vol. 30 of SIGPLAN Notices, ACM Press, pp. 301-314. Google ScholarDigital Library
- 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.Google Scholar
- 7 Bekkers, Y., and Cohen, J., Eds. International Workshop on Memory Management (St. Malo, France, Sept. 1992), no. 637 in Lecture Notes in Computer Science, Springer-Verlag. Google ScholarDigital Library
- 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.Google Scholar
- 9 Cheney, C. J. A nonrecursive list compacting algorithm. Commun. ACM 13, 11 (Nov. 1970), 677--678. Google ScholarDigital Library
- 10 Cheng, P., Harper, R., and Lee, P. Generational stack collection and profile-driven pretenuring. In Proceedings of SIGPLAN'98 Conference on Programming Languages Design and Implementation (Montreal, Qurbec, Canada, June 1998), vol. 33 of SIG- PLAN Notices, ACM Press, pp. 162-173. Google ScholarDigital Library
- 11 Clinger, W. D., and Hansen, L. T. Generational garbage collection and the radioactive decay model. SIGPLAN Notices 32, 5 (May 1997), 97-108. Proceedings of the ACM SIGPLAN '97 Conference on Programming Language Design and Implementation. Google ScholarDigital Library
- 12 Goldberg, A., and Robson, D. Smalltalk-80: The Language and its Implementation. Addison-Wesley, 1983. Google ScholarDigital Library
- 13 Hayes, B. Key Objects in Garbage Collection. PhD thesis, Stanford University, Stanford, California, Mar. 1993. Google ScholarDigital Library
- 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.Google Scholar
- 15 Hosking, A. L., Moss, J. E. B., and Stefanovir, D. A comparative performance evaluation of write barrier implementations. In Proceedings of the Conference on Object-Oriented Programming Systems, Languages, and Applications (Vancouver, Canada, Oct. 1992), SIGPLAN Notices 27, 10 (Oct. 1992), pp. 92-109. Google ScholarDigital Library
- 16 Hudson, R. L., and Moss, J. E.B. Incremental collection of mature objects. In Bekkers and Cohen {7}, pp. 388--403. Google Scholar
- 17 Jones, R., and Lins, R. Garbage Collection: Algorithms for Automatic Dynamic Memory Management. John Wiley, Chichester, 1996. Google ScholarDigital Library
- 18 Lang, B., and Dupont, F. Incremental incrementally compacting garbage collection. In SIGPLAN'87 Symposium on Interpreters and Interpretive Techniques (Inst. Rech. Informat. Automat. Lab., France, 1987), vol. 22(7) of SIGPLAN Notices, ACM Press, pp. 253-263. Google ScholarDigital Library
- 19 Lieberman, H., and Hewitt, C. A real-time garbage collector based on the lifetimes of objects. Commun. ACM 26, 6 (June 1983), 419-429. Google ScholarDigital Library
- 20 Moon, D. Garbage collection in a large Lisp system. In Proceedings of the A CM Symposium on Lisp and Functional Programming (Austin, TX, Aug. 1984), pp. 235-246. Google ScholarDigital Library
- 21 Nystrom, N. Bytecode-level analysis and optimization of Java class files. Master's thesis, Purdue University, West Lafayette, IN, May 1998.Google Scholar
- 22 Odersky, M., and Wadler, P. Pizza into Java: translating theory into practice. In POPL '97. Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming (New York, 1997), ACM Press, pp. 146-159. Google ScholarDigital Library
- 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.Google Scholar
- 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.Google Scholar
- 25 Stefanovir, D. Properties of Age-Based Automatic Memory Reclamation Algorithms. PhD thesis, University of Massachusetts, Amherst, MA, Feb. 1999. Google ScholarDigital Library
- 26 Stefanovi6, D., and Moss, J. E. B. Characterisation of object behaviour in Standard ML of New Jersey. In 1994 ACM Conference on Lisp and Functional Programming (Orlando, Florida, June 1994), ACM Press. Google ScholarDigital Library
- 27 Ungar, D. Generation scavenging: A non-disruptive high performance storage reclamation algorithm. In Proceedings of the ACM SIGSOFT/SIGPLAN Software Engineering Symposium on Practical Software Development Environments (Pittsburgh, Pennsylvania, Apr. 1984), SIGPLAN Notices 19, 5 (May 1984), pp. 157-167. Google ScholarDigital Library
- 28 Ungar, D. M. The Design and Evaluation of a High Performance Smalltalk System. ACM distinguished dissertation 1986. MIT Press, 1986. Google ScholarDigital Library
- 29 Ungar, D. M., and Jackson, E Tenuring policies for generationbased storage reclamation. SIGPLAN Notices 23, 11 (1988), 1-17. Google ScholarDigital Library
- 30 Ungar, D. M., and Jackson, F. An adaptive tenuring policy for generation scavengers. ACM Transactions on Programming Languages and Systems 14, 1 (1992), 1-27. Google ScholarDigital Library
- 31 Wilson, P. R. A simple bucket-brigade advancement mechanism for generation-based garbage collection. SIGPLAN Notices 24, 5 (May 1989), 38--46. Google ScholarDigital Library
- 32 Wilson, P. R. Uniprocessor garbage collection techniques. In Bekkers and Cohen {7}, pp. 1-42. Google Scholar
- 33 Wilson, P. R., and Moher, T. G. A "card-marking" scheme for controlling intergenerational references in generation-based garbage collection on stock hardware. SIGPLAN Notices 24, 5 (May 1989), 87-92. Google ScholarDigital Library
- 34 Wilson, P. R., and Moher, T.G. Design of the opportunistic garbage collector. In Proceedings of the Conference on Object- Oriented Programming Systems, Languages, and Applications (New Orleans, Louisiana, Oct. 1989), SIGPLAN Notices 24, 10 (Oct. 1989), pp. 23-35. Google ScholarDigital Library
- 35 Zorn, B. Barrier methods for garbage collection. Tech. Rep. CU-CS-494-90, University of Colorado at Boulder, Nov. 1990.Google Scholar
- 36 Zorn, B. G. Comparative Performance Evaluation of Garbage Collection Algorithms. PhD thesis, University of California at Berkeley, Dec. 1989. Available as Technical Report UCB/CSD 89/544. Google ScholarDigital Library
Index Terms
- Age-based garbage collection
Recommendations
Age-based garbage collection
OOPSLA '99: Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applicationsModern 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, ...
Exploiting the efficiency of generational algorithms for hardware-supported real-time garbage collection
SAC '07: Proceedings of the 2007 ACM symposium on Applied computingGenerational garbage collectors are more efficient than their non-generational counterparts. Unfortunately, however, generational algorithms require both write barriers and write barrier handlers and therefore degrade worst-case performance.
In this ...
Flexible reference-counting-based hardware acceleration for garbage collection
Languages featuring automatic memory management (garbage collection) are increasingly used to write all kinds of applications because they provide clear software engineering and security advantages. Unfortunately, garbage collection imposes a toll on ...
Comments