A mark-and-sweep collector C++

ABSTRACT

Our research is concerned with compiler-independent, tag-free garbage collection for the C++ programming language. We have previously presented a copying collector based on root registration. This paper presents a mark-and-sweep garbage collector that ameliorates shortcomings of the previous collector. We describe the two collectors and discuss why the new one is an improvement over the old one. We have tested this collector and a conservative collector in a VLSI CAD application, and this paper discusses the differences. Currently this prototype of the collector imposes too much overhead on our application. We intend to solve that problem, and then use the techniques described in this paper to implement a generational Mark-and-Sweep collector for C++.

REFERENCES

• App87: Andrew W. Appel, Garbage collection can be faster than stack allocation, Information Processing Letters, v.25 n.4, p.275-279, June 17, 1987 [doi>10.1016/0020-0190(87)90175-X]
• App89: Andrew W. Appel. Runtime tags aren't necessary. In Lisp and Symbolic Computation, volume 2, pages 153-162, 1989.
• Ass91: Association for Computing Machinery. Proceedings of the SIGPLAN '91 Conference on Programming Language Design and Implementation. ACM Press, June 1991.
• Bar88: Joel F. Bartlett. Compacting garbage collection with ambiguous roots. Technical Report 88/2, Digital Equipment Corporation, Western Research Laboratory, Palo Alto, California, February 1988.
• Bar89: Joel F. Bartlett. Mostly copying garbage collection picks up generations and C++. Technical Report TN-12, DEC WRL, October 1989.
• BDS91: Hans-J. Boehm , Alan J. Demers , Scott Shenker, Mostly parallel garbage collection, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.157-164, June 24-28, 1991, Toronto, Ontario, Canada
• BW88: Hans-Juergen Boehm , Mark Weiser, Garbage collection in an uncooperative environment, Software—Practice & Experience, v.18 n.9, p.807-820, September 1988 [doi>10.1002/spe.4380180902]
• CDG+88: L. CardeIIi, J. Donahue, L. Glassmaa, M. Jordan, B. Kalsow, and G. Nelson. Moduia-3 report. Technical report, Digital Systems Research Center and Olivetti Research Center, Palo Alto, CA, 1988.
• CUL89: C. Chambers , D. Ungar , E. Lee, An efficient implementation of SELF a dynamically-typed object-oriented language based on prototypes, Conference proceedings on Object-oriented programming systems, languages and applications, p.49-70, October 02-06, 1989, New Orleans, Louisiana, United States
• Det90: David Detlefs. Concurrent garbage collection for C++. Technical Report CMU-CS- 90-119, Carnegie Mellon, 1990.
• Ede90: Daniel R Edelson, DYNAMIC STORAGE RECLAMATION IN C++ (M.S. Thesis), University of California at Santa Cruz, Santa Cruz, CA, 1990
• EP91: Daniel Edelson and Ira Pohl. A copying collector for C++. In Usenix C-~--t- Conference Proceedings {Use91}, pages 85-102.
• FY69: 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]
• Gol91: Benjamin Goldberg, Tag-free garbage collection for strongly typed programming languages, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.165-176, June 24-28, 1991, Toronto, Ontario, Canada
• GR83: Adele Goldberg , David Robson, Smalltalk-80: the language and its implementation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1983
• Ken91: Brian Kennedy. The features of the objectoriented abstract type hierarchy (OATH). In Usenix C++ Conference Proceedings
• Usegl: , pages 41-50.
• Knu73: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• Lam83: Butler W. Lampson. A description of the Cedar language: A Cedar language reference manual. Technical Report CLS-83- 15, Xerox PARC, 1983.
• Lea91: Doug Lea. A memory allocator for libg+4-, 1991. private communication.
• Mey88: Bertrand Meyer, Object-oriented software construction (2nd ed.), Prentice-Hall, Inc., Upper Saddle River, NJ, 1997
• RMC90: Vincent Russo, Peter W. Madany, and Roy H. Campbell. C++ and operating systems performance: A case study. in Usenix C++ Conference Proceedings, pages 103-114, San Francisco, CA, April 1990. Usenix Association.
• Rus91: Vincent Russo, 1991. Using the parallel Boehm/Weiser/Demers collector in an operating system: private communication.
• Ste84: Guy L. Steele, Jr., Common LISP: the language, Digital Press, Newton, MA, 1984
• Str87: Bjarne Stroustrup. The evolution of C++ 1985 to 1987. In Usenix C++ Workshop Proceedings, pages 1-22, Santa Fe, NM, November 1987. Usenix Association.
• Str91: Bjarne Stroustrup. The C++ Reference Manual. Addison-Wesley, 2~d edition, 1991.
• Use91: Usenix Association. Usenix C+-/- Conference Proceedings, Washington, DC, April 1991.
• Wik87: Åke Wikström, Functional programming using standard ML, Prentice Hall International (UK) Ltd., Hertfordshire, UK, 1987
• X3J91: ANSI Committee X3J16. Draft standard for programming language C++, May 1991.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: C++

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Allocation/deallocation strategies

General Terms:
Algorithms, Languages