Space efficient conservative garbage collection

ABSTRACT

We call a garbage collector conservative if it has only partial information about the location of pointers, and is thus forced to treat arbitrary bit patterns as though they might be pointers, in at least some cases. We show that some very inexpensive, but previously unused techniques can have dramatic impact on the effectiveness of conservative garbage collectors in reclaiming memory. Our most significant observation is that static data that appears to point to the heap should not result in misidentified references to the heap. The garbage collector has enough information to allocate around such references. We also observe that programming style has a significant impact on the amount of spuriously retained storage, typically even if the collector is not terribly conservative. Some fairly common C and C++ programming style significantly decrease the effectiveness of any garbage collector. These observations suffice to explain some of the different assessments of conservative collection that have appeared in the literature.

REFERENCES

• 1: Standard X3.159-1989, American National $tan. dard for Information Systems - Programming Language - C, American National Standards Institute, Inc.
• 2: R. Atkinson , A. Demers , C. Hauser , C. Jacobi , P. Kessler , M. Weiser, Experiences creating a portable cedar, ACM SIGPLAN Notices, v.24 n.7, p.322-329, July 1989
• 3: Bartlett, Joel F. "Compacting garbage collection with ambiguous roots", Lisp Pointers 1, 6 (April- June 1988), pp. 3-12.
• 4: Bartlett, Joel F., Scheme -> C a Portable Schemeto-C Compiler, WRL Research Report 89/1, Digital Equipment Corporation Western Research Laboratory, January 1989.
• 5: Bartlett, Joel F., Mostly Copying Garbage Collection Picks Up Generations and C++, Technical Report TN-12, Digital Equipment Corporation Western Research Laboratory, October 1989.
• 6: Yves Bekkers , Olivier Ridoux , Lucien Ungaro, Dynamic Memory Management for Sequential Logic Programming Languages, Proceedings of the International Workshop on Memory Management, p.82-102, September 17-19, 1992
• 7: Boehm, Hans-J., and David Chase, "A Proposal for Garbage-Collector-Safe C Compilation", The Journal of C Language Translation d, 2 (December 1992), pp. 126-141.
• 8: Hans-J. Boehm , Alan J. Demers , Scott Shenker, Mostly parallel garbage collection, ACM SIGPLAN Notices, v.26 n.6, p.157-164, June 1991
• 9: 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]
• 10: Emmanuel Chailloux, A Conservative Garbage Collector with Ambiguous Roots for Static Typechecking Languages, Proceedings of the International Workshop on Memory Management, p.218-229, September 17-19, 1992
• 11: Cridlig, Regis, "An Optimizing ML to C Compiler'', A CM SIGPLAN Workshop on ML and its Applications, San Francisco, June 1992, David MacQueen, chair.
• 12: 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]
• 13: Detlefs, David L., "Concurrent Garbage Collection for C++", in Advanced Programming Language implementation, Peter Lee, ed., MIT Press, 1991.
• 14: Daniel R. Edelson, A mark-and-sweep collector C++, Proceedings of the 19th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.51-58, January 19-22, 1992, Albuquerque, New Mexico, United States [doi>10.1145/143165.143178]
• 15: Benjamin Goldberg , Michael Gloger, Polymorphic type reconstruction for garbage collection without tags, Proceedings of the 1992 ACM conference on LISP and functional programming, p.53-65, June 22-24, 1992, San Francisco, California, United States
• 16: Hastings, Reed, and Bob Joyce, "Fast Detection of Memory Leaks and Access Errors", Proceedings of the Winter '92 USENIX conference, pp. 125-136.
• 17: Omohundro, Stephen M., The Sather Language, ICSI, Berkeley, 1991.
• 18: John R. Rose , Hans Muller, Integrating the Scheme and C languages, Proceedings of the 1992 ACM conference on LISP and functional programming, p.247-259, June 22-24, 1992, San Francisco, California, United States
• 19: Rovner, Paul, "On Adding Garbage Collection and Runtime Types to a Strongly-Typed Statically Checked, Concurrent Language", Technical Report CSL-84-7, Xerox Palo Alto Research Center, Palo Alto, CA, July 1985.
• 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: Bill Schelter , Michael Ballantyne, Free AI development system: Kyoto Common LISP, AI Expert, v.3 n.3, p.75-77, March 1987
• 22: M. Weiser , A. Demers , C. Hauser, The portable common runtime approach to interoperability, Proceedings of the twelfth ACM symposium on Operating systems principles, p.114-122, November 1989
• 23: E. P. Wentworth, Pitfalls of conservation garbage collection, Software—Practice & Experience, v.20 n.7, p.719-727, July 1990 [doi>10.1002/spe.4380200707]
• 24: Paul R. Wilson, Uniprocessor Garbage Collection Techniques, Proceedings of the International Workshop on Memory Management, p.1-42, September 17-19, 1992
• 25: Zorn, Benjamin, "The Measured Cost of Conservative Garbage Collection", University of Colorado at Boulder, Department of Computer Science Technical Report CU-CS-573-92.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

Additional Classification:
  C. Computer Systems Organization
  C.0 GENERAL

      Nouns: SPARC

  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: Cedar; C

General Terms:
Languages, Performance