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: A. W. Appel , J. R. Ellis , K. Li, Real-time concurrent collection on stock multiprocessors, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.11-20, June 20-24, 1988, Atlanta, Georgia, United States
• 2: 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]
• 3: H. D. Baecker, Garbage collection for virtual memory computer systems, Communications of the ACM, v.15 n.11, p.981-986, Nov. 1972 [doi>10.1145/355606.361886]
• 4: 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]
• 5: Jacques Cohen , Alexandru Nicolau, Comparison of Compacting Algorithms for Garbage Collection, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.4, p.532-553, Oct. 1983 [doi>10.1145/69575.357226]
• 6: Robert Courts, Improving locality of reference in a garbage-collecting memory management system, Communications of the ACM, v.31 n.9, p.1128-1138, Sept. 1988 [doi>10.1145/48529.48536]
• 7: D. Julia. M. Davies, Memory occupancy patterns in garbage collection systems, Communications of the ACM, v.27 n.8, p.819-825, Aug 1984 [doi>10.1145/358198.358226]
• 8: Alan Demmers , Mark Weiser , Barry Hayes , Hans Boehm , Daniel Bobrow , Scott Shenker, Combining generational and conservative garbage collection: framework and implementations, Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.261-269, December 1989, San Francisco, California, United States [doi>10.1145/96709.96735]
• 9: Robert R. Fenichel , Jerome C. Yochelson, A LISP garbage-collector for virtual-memory computer systems, Communications of the ACM, v.12 n.11, p.611-612, Nov. 1969 [doi>10.1145/363269.363280]
• 10: Franz incorporated. Allegro Common Lisp User Guide, Release 3.0 (beta) edition, April 1988.
• 11: 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]
• 12: John McCarthy, Recursive functions of symbolic expressions and their computation by machine, Part I, Communications of the ACM, v.3 n.4, p.184-195, April 1960 [doi>10.1145/367177.367199]
• 13: 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]
• 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: 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: Robert A. Shaw. improving garbage collector performance in virtual memory. Technical Report CSL-TR- 87-323, Stanford University, March 1987.
• 17: Robert Allen Shaw, Empirical analysis of a LISP system, Stanford University, Stanford, CA, 1988
• 18: Patrick G. Sobalvarro. A lifet~e-based garbage collector for LISP systems on general purpose computers. Bachelor's thesis, MIT, 1988.
• 19: George Taylor. Ratio of MIP$ R$000 instructions to heap references. Personal communication, October 1989.
• 20: 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
• 21: David Ungar , Frank Jackson, Tenuring policies for generation-based storage reclamation, Conference proceedings on Object-oriented programming systems, languages and applications, p.1-17, September 25-30, 1988, San Diego, California, United States
• 22: David Michael Ungar, The design and evaluation of a high performance SMALLTALK system, University of California at Berkeley, Berkeley, CA, 1986
• 23: Taiichi Yuaza and Masami Hagiya. The KCL Report. Research Institute for Mathematical Sciences, University of Kyoto.
• 24: Benjamin Goth Zorn, Comparative performance evaluation of garbage collection algorithms, 1989
• 25: Benjamin G. Zorn , Paul N. Hilfinger, SPUR Lisp: Design and Implementation, University of California at Berkeley, Berkeley, CA, 1987

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Allocation/deallocation strategies

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
  D.3 PROGRAMMING LANGUAGES

General Terms:
Design, Languages, Performance, Reliability