A principled approach to nondeferred reference-counting garbage collection

ABSTRACT

Nondeferred reference-counting (RC) garbage collection is among the oldest memory-management methods. Despite offering unique advantages, little attention has been paid on how to correctly implement it for modern programming languages. This paper revisits this collection method and describes how to implement it for a modern object-oriented language in an optimizing compiler.

The main contribution is a general algorithm that realizes one form of nondeferred RC collection for an object-oriented language having features such as exceptions, interior pointers, and object pinning. The algorithm abstracts the pertinent characteristics of instructions using concepts from data-flow analysis, such as def/use information, so that instructions are handled in a uniform manner, instead of in an ad hoc or special-case way. The abstracted information is used to systematically compute what increments and decrements to do, even in the presence of subtle conditions such as exceptional control flow. These techniques enabled us to compile a large suite of programs to use nondeferred RC collection. The paper also discusses the modifications that were necessary in the compiler for supporting the inserted RC operations, and reports measurements from a reference implementation.

References

1. Ole Agesen, David Detlefs, and J. Eliot Moss. Garbage Collection and Local Variable Type-Precision and Liveness in Java Virtual Machines. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 269--279, June 1998.
2. Bowen Alpern, C.R. Attanasio, John J. Barton, Michael G. Burke, Perry Cheng, Jong-Deok Choi, Anthony Cocchi, Stephen J. Fink, David Grove, Michael Hind, Susan Flynn-Hummel, Derek Lieber, Vassily Litvinov, Mark F. Mergen, Ton Ngo, James R. Russell, Vivek Sarkar, Mauricio J. Serrano, Janice C. Shepherd, Stephen E. Smith, VC. Sreedhar, Harini Srinivasan, and John Whaley. The Jalapeño Virtual Machine. IBM Systems Journal, 39(1):211--238, 2000.
3. Matt Austern. Draft Technical Report on C++ Library Extensions. ISO/IEC DTR 19768, The C++ Standards Committee, June 2005.
4. David F. Bacon, Perry Cheng, and V.T. Rajan. A Unified Theory of Garbage Collection. In Proceedings of the 2004~ACM SIGPLAN Conference on Object--Oriented Programming, Systems, Languages, and Applications, pages 50--68, October 2004.
5. Jeffrey M. Barth. Shifting Garbage Collection Overhead to Compile Time. Communications of the ACM, 20(7):513--518, July 1977.
6. Hans-Juergen Boehm. Simple GC-Safe Compilation. In Addendum to OOPSLA'91 Proceedings, October 1991.
7. Boost C++ Libraries. At http://www.boost.org.
8. Don Box and Chris Sells. Essential.NET: The Common Language Runtime. Addison-Wesley Publishing Company, Inc., USA, 2003.
9. Jong-Deok Choi, David Grove, Michael Hind, and Vivek Sarkar. Efficient and Precise Modeling of Exceptions for the Analysis of Java Programs. In Proceedings of the ACM SIGPLAN/SIGSOFT Workshop on Program Analysis for Software Tools and Engineering, pages 21--31, September 1999.
10. George E. Collins. A Method for Overlapping and Erasure of Lists. Communications of the ACM, 3(12):655--657, December 1960.
11. Alain Deutsch. On Determining Lifetime and Aliasing of Dynamically Allocated Data in Higher-Order Functional Specifications. In Proceedings of the ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 157--168, January 1990.
12. L. Peter Deutsch and Daniel G. Bobrow. An Efficient, Incremental Automatic Garbage Collector. Communications of the ACM, 19(9):522--526, September 1976.
13. Amer Diwan, Eliot Moss, and Richard Hudson. Compiler Support for Garbage Collection in a Statically Typed Language. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 273--282, June 1992.
14. H. Gelernter, J.R. Hansen, and C.L. Gerberich. A FORTRAN-Compiled List-Processing Language. Journal of the ACM, 7(2):87--101, April 1960.
15. Martin Hirzel, Amer Diwan, and Johannes Henkel. On the Usefulness of Type and Liveness Accuracy for Garbage Collection and Leak Detection. ACM Transactions on Programming Languages and Systems, 24(6):593--624, November 2002.
16. Paul Hudak. A Semantic Model of Reference Counting and its Abstraction (Detailed Summary). In Proceedings of the ACM SIGPLAN Conference on LISP and Functional Programming, pages 351--363, April 1986.
17. Pramod G. Joisha. Compiler Optimizations for Nondeferred Reference-Counting Garbage Collection. In Proceedings of the International Symposium on Memory Management, pages 150--161. ACM Press, June 2006.
18. Pramod G. Joisha. A Principled Approach to Nondeferred Reference--Counting Garbage Collection. Technical Report MSR-TR-2007-104, Microsoft Research, August 2007.
19. Pramod G. Joisha. Overlooking Roots: A Framework for Making Nondeferred Reference-Counting Garbage Collection Fast. In Proceedings of the International Symposium on Memory Management, pages 141--158. ACM Press, October 2007.
20. Richard Jones and Rafael Lins. Garbage Collection: Algorithms for Automatic Dynamic Memory Management. John Wiley & Sons, Inc., USA, 1996.
21. Tim Lindholm and Frank Yellin. The Java Virtual Machine Specification, Second Edition. The Java Series. Addison-Wesley Publishing Company, Inc., USA, 1999.
22. Steven S. Muchnick. Advanced Compiler Design and Implementation. Morgan Kaufmann Publishers, Inc., USA, 1997.
23. Young Gil Park and Benjamin Goldberg. Reference Escape Analysis: Optimizing Reference Counting Based on the Lifetime of References. In Proceedings of the ACM SIGPLAN Symposium on Partial Evaluation and Semantics-based Program Manipulation, pages 178--189, June 1991.
24. Chris Sells and Christopher Tavares. Adding Reference Counting to the Shared Source Common Language Infrastructure. At http://www.sellsbrothers.com/writing.
25. James M. Stichnoth, Guei-Yuan Lueh, and Michał Cierniak. Support for Garbage Collection at Every Instruction in a Java Compiler. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 118--127, May 1996.
26. David R. Tarditi, Greg Morrisett, Perry Cheng, Christopher Stone, Robert Harper, and Peter Lee. TIL: A Type-Directed Optimizing Compiler for ML. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 181--192, May 1996.

Index Terms

• Software and its engineering

  • Software notations and tools

    • Compilers

      • Source code generation

  • Software organization and properties

    • Contextual software domains

      • Operating systems

        • Memory management

          • Garbage collection