Generational garbage collection and the radioactive decay model

ABSTRACT

If a fixed exponentially decreasing probability distribution function is used to model every object's lifetime, then the age of an object gives no information about its future life expectancy. This radioactive decay model implies there can be no rational basis for deciding which live objects should be promoted to another generation. Yet there remains a rational basis for deciding how many objects to promote, when to collect garbage, and which generations to collect.Analysis of the model leads to a new kind of generational garbage collector whose effectiveness does not depend upon heuristics that predict which objects will live longer than others.This result provides insight into the computational advantages of generational garbage collection, with implications for the management of objects whose life expectancies are difficult to predict.

References

1. 1.Milton Abramowitz and Irene A. Stegun. Handbook of Mathematical Punctions. National Bureau of Standards Applied Mathematics Series, 55, June 1964.
2. 2.Andrew W. Appel. Simple generational garbage collection and fast allocation. Software Practice and Experience 19(2), February 1989, pages 171-183.
3. 3.Henry G. Baker. List processing in real time on a serial computer. CACM 21(4), April 1978, pages 280-294.
4. 4.Henry G. Baker. The Boyer benchmark at warp speed. A CM Lisp Pointers 5(3), July-September 1992, pages 13-14.
5. 5.Henry G. Baker. infant mortality and generational garbage collection. SIGPLAN Notices 28(4), April 1993, pages 55-57.
6. 6.Henry G. Baker. The Boyer benchmark meets linear logic. ACM Lisp Pointers 6(4), October-December 1993, pages 3- 10.
7. 7.Henry G. Baker. Personal communication via electronic mail, 6 November 1995, quoting a personal communication via fax from Bob Boyer dated 3 December 1993.
8. 8.David A. Barrett and Benjamin G. Zorn. Using lifetime predictors to improve memory allocation performance. In ACM SIGPLAN Conference on Programming Language Design and Implementation, 1993, pages 187-196.
9. 9.Patrick J. Caudill and Allen Wirfs-Brock. A third-generation Smalltalk-80 implementation. In Conference on Object Oriented Programming Systems, Languages, and Applications (OOPSLA '86), October 1986, pages 119-130.
10. 10.C. J. Cheney. A nonrecursive list compacting algorithm. CACM 13(11), November 1970, pages 677-678.
11. 11.Douglas W. Clark and C. Cordell Green. An empirical study of list structure in LISP. CACM 20(2), February 1977, pages 78-87.
12. 12.Douglas W. Clark. Measurements of dynamic list structure use in Lisp. IEEE 7hansactions on Software Engineering, 5(1), January 1979, 51-59.
13. 13.William Clinger. Further measurements relevant to this paper will be made available through the World-Wide Web. See http://ewe, ccs .neu. edu/home/will/Qg/index, h~ml.
14. 14.William Clinger and Lain Thomas Hansen. Lambda, the ultimate label; or a simple optimizing compiler for Scheme. In A CM Conference on Lisp and kSznctional Prog~mming, June 1994, pages 128-139.
15. 15.Alan Demers, Mark Weiser, Barry Hayes, Daniel Bobrow, and Scott Shenker. Combining generational and conservarive garbage collection: framework and implementations. In A CM Symposium on Principles of Programming Languages, January 1990, pages 261-269.
16. 16.Marc Feeley, Marcel Turcotte, and Guy Lapalme. Using Multilisp for solving constraint satisfaction problems: an application to nucleic acid 3D structure determination. In Journal of Lisp and Symbolic Computation 7(2/3), 1994, pages 231- 246.
17. 17.Robert R. Fenichel and Jerome C. Yocheison. A LISP garbage-collector for virtual-memory computer systems. CACM 12(11), November 1969, pages 611-612.
18. 18.Richard P. Gabriel. Performance and Evaluation of Lisp Programs. MIT Press, 1985.
19. 19.Marcelo J. R. Gonqalves and Andrew Appel. Cache performance of fast-allocating programs. In A CM SIGPLAN- $IGARCH-WG~.8 Conference on Functional Programming Languages and Computer Architecture (FPCA), June 1995, pages 293-305.
20. 20.Leslie Greengard. The Rapid Evaluation of Potential Fields in Particle Systems. ACM Press, 1987.
21. 21.Lars Thomas Hansen. The Impact of Programming Style on the Performance of Scheme Programs. M.S. thesis, University of Oregon, 1992.
22. 22.David R. Hanson. Storage management for an implementation of SNOBOL4. In Software: Practice and Ea~per/ence 7(2), March 1977, pages 179-192.
23. 23.Pieter H. Hartel, Marc Feeley, et al. Benchmarking implementations of functional languages with "Pseudoknot", a float-intensive benchmark. In Journal of Fanctional Programming 6(4), July 1996, pages 621-655.
24. 24.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.
25. 25.Fritz HengIein. Global tagging optimization by type inference. In Proceedings of the A CM Symposium on Lisp and Functional Programming, 1992, pages 205-215.
26. 26.Antony L. Hosking, J. Eliot B. Moss, and Darko Stefanovid. A comparative performance evaluation of write barrier implementations. In Conference on Object Oriented Programming Systems, Languages, and Applications (OOPSLA '9~), October 1992, pages 92-109.
27. 27.IEEE Standard for the Scheme Programming Language. IEEE Std 1178-1990.
28. 28.Suresh Jagannathan and Andrew Wright. Effective flow analysis for avoiding run-time checks. In Proceedings of the $nd International Static Analysis Symposium, Springer-Verlag LNCS 983, September 1995, pages 207-224.
29. 29.Henry Lieberman and Carl Hewitt. A real-time garbage collector based on the lifetimes of objects. CACM 26(6), June 1983, pages 419-429.
30. 30.Marvin Minsky. A LISP garbage collector algorithm using serial secondary storage. MIT AI Memo 58, 1963.
31. 31.David Moon. Garbage collection in a large Lisp system. In A CM Conference on Lisp and k'hnctional Prvgramming, 1984, pages 235-246.
32. 32.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.
33. 33.Darko Stefanovi~ and J. Eliot B. Moss. Characterisation of object behaviour in Standard ML of New Jersey. In A CM Conference on Lisp and Functional Programming, 1994, pages 43-54.
34. 34.George B. Thomas, Jr. Calculus and Analytic Geometry. Addison-Wesley, 1968.
35. 35.David M. Ungar. Generation scavenging: a non-disruptive high-performance storage reclamation algorithm, in A CM SIGSOFT/SIGPLAN Software Engineering Symposium on Practical Software Development Environments, A CM SIG- PLAN Notices 19(5), May 1987, pages 157-167.
36. 36.David Ungar and Frank Jackson. An adaptive tenuring policy for generation scavengers. A CM 7~ansactions on Programming Languages and Systems, 14(1), January 1992, pages 1-27.
37. 37.Paul R. Wilson, Michael S. Lam, and Thomas G. Moher. Caching considerations for generational garbage collection. In A CM Conference on Lisp and Fanctional Programming, June 1992, pages 32-42.
38. 38.Paul R. Wilson, Mark S. Johnstone, Michael Neely, and David Boles. Dynamic storage allocation: a survey and critical review. In Proceedings of the 1995 International Workshop on Memory Management, September 1995, SpringeroVerlag LNCS. Available via anonymous ftp from cs. utexas, edu, in pub/garbage.
39. 39.Paul R. Wilson. Uniprocessor garbage collection techniques. A CM Computing Surveys, to appear. Available via anonymous ftp from cs.utexas, edu, in pub/gsxbage.
40. 40.Feng Zhao. An O(N) algorithm for three-dimensional n-body simulations. Master's thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, 1987.
41. 41.Benjamin Zorn. The measured cost of conservative garbage collection. Software Practice and E~perience 23(7), 1993, pages 733-756.
42. 42.Benjamin Zorn. Garbage collection using a dynamic threatening boundary. In A CM $IGPLAN Conference on Programming Language Design and Implementation, June 1995, pages 301-314.

Index Terms

• Software and its engineering

  • Software organization and properties

    • Contextual software domains

      • Operating systems

        • Memory management

          • Allocation / deallocation strategies

• Theory of computation

  • Models of computation

    • Probabilistic computation