Comparing mark-and sweep and stop-and-copy garbage collection

ABSTRACT

Stop-and-copy garbage collection has been preferred to mark-and-sweep collection in the last decade because its collection time is proportional to the size of reachable data and not to the memory size. This paper compares the CPU overhead and the memory requirements of the two collection algorithms extended with generations, and finds that mark-and-sweep collection requires at most a small amount of additional CPU overhead (3-6%) but, requires an average of 20% (and up to 40%) less memory to achieve the same page fault rate. The comparison is based on results obtained using trace-driven simulation with large Common Lisp programs.

References

1. 1.Andrew Appel, John Ellis, and Kai Li. Real-time concurrent collection on stock multiprocessors. In SIC. PLAN'88 Conference on Programming Language Design and Implementation, pages 11-20, Atlanta, CA, June 1988. $IGPLAN, ACM Press.
2. 2.Andrew W. Appel. Simple generational garbage collection and fast allocation. Software--Practice and Expe. rience, 19(2):171-183, February 1989.
3. 3.H. D. Baecker. Garbage collection for virtual mereory computer systems. Communications of the A CM, 15(11):981-986, November 1972.
4. 4.C. $. Cheney. A nonrecursive list compacting algorithm. Communications of the A CM, 13(11):677-678, Novembet 1970.
5. 5.Jacques Cohen and Alexandru Nicolau. Comparison of compacting algorithms for garbage collection. A CM Transactions on Programming Languages and Systems, 5(4):512-553, October 1983.
6. 6.Robert Courts. Improving locality of reference in a garbage-collecting memory management system. Cornmunications of the A CM, 31(9):1128-1138, September 1988.
7. 7.D. Julian M. Davies. Memory occupancy patterns in garbage collection systems. Communication~ of the ACM, 27(8):819-825, August 1984.
8. 8.Alan Demers, Mark Weiser, Barry Hayes, Hans Boehm, Daniel Bobrow, and Scott $henker. Combining generational and conservative garbage collection: Framework and implementations. In Conference Record of the Seventeenth AGM Symposium on Principles of Programming Lanyuages, pages 261-269, January 1990.
9. 9.Robert R. Fenichel and Jerome C. Yochelson. A Lisp garbage-collector for virtual memory computer systems. Communications of the ACM, 12(11):611-612, November 1969.
10. 10.Franz incorporated. Allegro Common Lisp User Guide, Release 3.0 (beta) edition, April 1988.
11. 11.Henry Lieberman and Carl Hewitt. A real-time garbage collector based on the lifetimes of objects. Comrnunications of the ACM, 26(6):419-429, June 1983.
12. 12.John McCarthy. Recursive functions of symbolic expressions and their computations by machinet part I. Communications of the A CM, 3(4):184-195, April 1960.
13. 13.David A. Moon. Garbage collection in a large Lisp system. In Conference Record of the 1984 A CM Symposium on LISP and Functional Programming, pages 235-246~ Austin, Texas, August 1984.
14. 14.I. A. Newman and M. C. Woodward. Alternative approaches to multiprocessor garbage collection. In Proceedings of the 1982 International Conference on Parallel Processing, pages 205-210, Ohio State University, Columbus, OH, August 1982. IEEE.
15. 15.C.-J. Peng and G. S. Sold. Cache memory design considerations to support languages with dynamic heap allocation. Technical Report 860, Computer Sciences Dept., Univ. of Wisconsin--Madison, July 1989.
16. 16.Robert A. Shaw. improving garbage collector performance in virtual memory. Technical Report CSL-TR- 87-323, Stanford University, March 1987.
17. 17.Robert A. Shaw. Empirical Analysis of a Lisp System. PhD thesis, Stanford University, Stanford, CA, February 1988. Also appears as Computer Systems Laboratory tech report CSL-TR-88-351.
18. 18.Patrick G. Sobalvarro. A lifet~e-based garbage collector for LISP systems on general purpose computers. Bachelor's thesis, MIT, 1988.
19. 19.George Taylor. Ratio of MIP$ R$000 instructions to heap references. Personal communication, October 1989.
20. 20.David Ungar. Generation scavenging: A non-disruptive high performance storage reclamation algorithm. In SIGSOFT/SIGPLA N Practical Programming Environrnentz Conference, pages 157-167, April 1984.
21. 21.David Ungar and Frank Jackson. Tenuring policies for generation-based storage reclamation. In OOPSLA '88 Conference Proceedingz, pages 1-17. ACM, September 1988.
22. 22.Duvid M. Ungar. The Design and Evaluation of A High Performance Srnalltalk System. PhD thesis, University of Callforn/a at Berkeley, Berkeley, CA, March 1986. Also appears as tech ~eport UCB/CSD 86/287.
23. 23.Taiichi Yuaza and Masami Hagiya. The KCL Report. Research Institute for Mathematical Sciences, University of Kyoto.
24. 24.Benjamin Zorn. Comparatiue Performance Evaluatior~ of Garbage Collection Algorithrn~. PhD thesis, University of CaLifornia at Berkeley, Berkeley, CA, November 1989. Also appears as tech report UCB/CSD 89/544.
25. 25.Benjamin Zorn, Paul Hilfinger, Kinson Ho, and James Larus. SPUR Lisp: Design and implementation. Technical Report UCB/CSD 87/373, Computer Science Division (EECS), University of California, Berkeley, Octobcr 1987.

Index Terms

• Software and its engineering

  • Software creation and management

    • Software development techniques

  • Software notations and tools

    • Compilers

  • Software organization and properties

    • Contextual software domains

      • Operating systems

        • Memory management

          • Allocation / deallocation strategies