An experimental study of renewal-older-first garbage collection

Abstract

Generational collection has improved the efficiency of garbage collection in fast-allocating programs by focusing on collecting young garbage, but has done little to reduce the cost of collecting a heap containing large amounts of older data. A new generational technique, older-first collection, shows promise in its ability to manage older data.This paper reports on an implementation study that compared two older-first collectors to traditional (younger-first) generational collectors. One of the older-first collectors performed well and was often effective at reducing the first-order cost of collection relative to younger-first collectors. Older-first collectors perform especially well when objects have queue-like or random lifetimes.

References

1. Henry G. Baker. The Boyer benchmark at warp speed. ACM Lisp Pointers 5(3), July--September 1992, pages 13--14.
2. Henry G. Baker. Infant mortality and generational garbage collection. ACM SIGPLAN Notices 28(4), April 1993, pages 55--57.
3. Henry G. Baker. The Boyer benchmark meets linear logic. ACM Lisp Pointers 6(4), October--December 1993, pages 3--10.
4. Henry G. Baker. Personal communication via electronic mail, 6 November 1995, quoting a personal communication via fax from Bob Boyer dated 3 December 1993.
5. A. Bawden, R. Greenblatt, J. Holloway, T. Knight, D. A. Moon, and D. Weinreb. Lisp machine progress report. AI Memo 444, MIT AI Lab, August 1977.
6. Steve M. Blackburn, Richard Jones, K. S. McKinley, and J. Eliot B. Moss. Beltway: Getting Around Garbage Collection Gridlock. ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), June 17-19, 2002.
7. C. J. Cheney. A nonrecursive list compacting algorithm. Communications of the ACM 13(11), November 1970, pages 677--678.
8. William D Clinger and Lars Thomas Hansen. Lambda, the ultimate label, or a simple optimizing compiler for Scheme. Proceedings of the 1994 ACM Conference on Lisp and Functional Programming. ACM LISP Pointers VIII(3), July--September 1994, pages 128--139.
9. William D Clinger and Lars T Hansen. Generational Garbage Collection and the Radioactive Decay Model. Proceedings of the 1997 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), ACM SIGPLAN Notices 32(5), May 1997, pages 97--108.
10. William Clinger. Data provided via the World-Wide Web at http://www.ccs.neu.edu/home/will/GC/index.html.
11. Jacques Cohen. Garbage collection of linked data structures. ACM Computing Surveys 13(3), September 1981, pages 341--367.
12. L. Peter Deutsch and Daniel G. Bobrow. An efficient incremental automatic garbage collector. Communications of the ACM 19(7), July 1976, pages 522--526.
13. J. Earley. An efficient context-free parsing algorithm. Communications of the ACM 13(2), 1970, pages 94--102.
14. Richard P. Gabriel. Performance and Evaluation of Lisp Systems. The MIT Press, 1985.
15. Jacob Seligmann and Steffen Grarup. Incremental mature garbage collection using the train algorithm. In Proceedings of 1995 European Conference on Object-Oriented Programming, Lecture Notes in Computer Science, Springer-Verlag, August 1995.
16. Lars Thomas Hansen. The impact of programming style on the performance of Scheme programs. M.S. Thesis, University of Oregon, 1992.
17. Lars Thomas Hansen. Older-first Garbage Collection in Practice. Ph.D. Thesis, Northeastern University, November 2000. Available online---see www-clinger-gc.
18. David R. Hanson. Storage Management for an Implementation of SNOBOL4. Software---Practice and Experience 7, 1977, pages 179--192.
19. Barry Hayes. Using key object opportunism to collect old objects. In Conference on Object Oriented Programming Systems, Languages, and Applications (OOPSLA '91), October 1991, pages 33--46.
20. Michael W. Hicks, Luke Hornof, Jonathan T. Moore and Scott M. Nettles. A Study of Large Object Spaces. ISMM '98---International Symposium on Memory Management, pages 138--147. ACM Press, 1998.
21. Anthony L. Hosking, J. Eliot B. Moss, and Darko Stefanovic. A Comparative Performance Evaluation of Write Barrier Implementations. OOPSLA '92 Conference Proceedings, ACM SIGPLAN Notices 27(10), October 1992, pages 92--109.
22. Richard L. Hudson and J. Eliot B. Moss. Incremental garbage collection for mature objects. In Proceedings of International Workshop on Memory Management, (Yves Bekkers and Jacques Cohen, editors), Lecture Notes in Computer Science 637. Springer-Verlag, September 1992.
23. IEEE Standard for the Scheme Programming Language. IEEE Std 1178-1990.
24. Richard Jones and Rafael Lins. Garbage Collection: Algorithms for Automatic Dynamic Memory Management. John Wiley & Sons, 1996.
25. Richard Kelsey, William Clinger, and Jonathan Rees (editors). Revised5 Report on the Algorithmic Language Scheme. ACM SIGPLAN Notices~33(9), September 1998, pages 26--76.
26. The Larceny home page at http://www.larceny.org/+.
27. Henry Lieberman and Carl Hewitt. A Real-Time Garbage Collector Based on the Lifetimes of Objects. Communications of the ACM 26(6), 419--429, June 1983.
28. David A. Moon. Garbage Collection in a Large Lisp System. In ACM Conference on Lisp and Functional Programming, 235--246, 1984.
29. Patrick M. Sansom and Simon L. Peyton Jones. Generational garbage collection for Haskell. In Conference on Functional Programming Languages and Computer Architecture, 1993, pages 106--116.
30. Darko Stefanovic and J. Eliot B. Moss. Characterisation of object behaviour in Standard ML of New Jersey. In ACM Conference on Lisp and Functional Programming, 1994, pages 43--54.
31. Darko Stefanovic. Properties of Age-Based Automatic Memory Reclamation Algorithms. Ph.D. thesis, University of Massachusetts, Amherst, Massachusetts, February 1999.
32. Darko Stefanovic, Kathryn S. McKinley, and J. Eliot B. Moss. Age-Based Garbage Collection. OOPSLA~'99 Conference Proceedings, ACM SIGPLAN Notices 34(10), October 1999, pages 370--381.
33. Darko Stefanovic, Matthew Hertz, Steve M. Blackburn, K. S. McKinley, and J. Eliot B. Moss. Older-first Garbage Collection in Practice: Evaluation in a Java Virtual Machine. Workshop on Memory System Performance, Berlin, Germany, June 2002.
34. David Ungar. Generation Scavenging: A Non-disruptive High Performance Storage Reclamation Algorithm. In ACM SIGSOFT-SIGPLAN Practical Programming Environments Conference, Pittsburgh PA, April 1984, pages 157--167.
35. Paul R. Wilson and Thomas G. Moher. Design of the opportunistic garbage collector. OOPSLA '89 Conference Proceedings, ACM SIGPLAN Notices 24(10), October 1989, pages 23--35.
36. Paul R. Wilson. Uniprocessor garbage collection techniques. ACM Computing Surveys, to appear. Available via anonymous ftp from cs.utexas.edu, in pub/garbage.

Index Terms

• Software and its engineering

  • Software organization and properties

    • Contextual software domains

      • Operating systems

        • Memory management

          • Garbage collection