skip to main content
10.1145/1346256.1346275acmconferencesArticle/Chapter ViewAbstractPublication PagesveeConference Proceedingsconference-collections
research-article

A principled approach to nondeferred reference-counting garbage collection

Published: 05 March 2008 Publication History

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.

Cited By

View all

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
VEE '08: Proceedings of the fourth ACM SIGPLAN/SIGOPS international conference on Virtual execution environments
March 2008
190 pages
ISBN:9781595937964
DOI:10.1145/1346256
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 March 2008

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. instrumentation
  2. reference counting
  3. static analysis

Qualifiers

  • Research-article

Conference

VEE '08

Acceptance Rates

VEE '08 Paper Acceptance Rate 18 of 57 submissions, 32%;
Overall Acceptance Rate 80 of 235 submissions, 34%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)4
  • Downloads (Last 6 weeks)0
Reflects downloads up to 19 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2018)Biased reference countingProceedings of the 27th International Conference on Parallel Architectures and Compilation Techniques10.1145/3243176.3243195(1-12)Online publication date: 1-Nov-2018
  • (2013)ResurrectorACM SIGPLAN Notices10.1145/2544173.250951248:10(111-130)Online publication date: 29-Oct-2013
  • (2013)ResurrectorProceedings of the 2013 ACM SIGPLAN international conference on Object oriented programming systems languages & applications10.1145/2509136.2509512(111-130)Online publication date: 29-Oct-2013
  • (2012)On the benefits and pitfalls of extending a statically typed language JIT compiler for dynamic scripting languagesACM SIGPLAN Notices10.1145/2398857.238463147:10(195-212)Online publication date: 19-Oct-2012
  • (2012)On the benefits and pitfalls of extending a statically typed language JIT compiler for dynamic scripting languagesProceedings of the ACM international conference on Object oriented programming systems languages and applications10.1145/2384616.2384631(195-212)Online publication date: 19-Oct-2012
  • (2012)Lazy reference counting for the microgridProceedings of the 2012 16th Workshop on Interaction between Compilers and Computer Architectures (INTERACT)10.1109/INTERACT.2012.6339625(41-48)Online publication date: 25-Feb-2012
  • (2010)Concurrent non-deferred reference counting on the MicrogridProceedings of the 22nd international conference on Implementation and application of functional languages10.5555/2050135.2050147(185-202)Online publication date: 1-Sep-2010
  • (2010)Efficient interpretation using quickeningACM SIGPLAN Notices10.1145/1899661.186963345:12(1-14)Online publication date: 18-Oct-2010
  • (2010)Efficient interpretation using quickeningProceedings of the 6th symposium on Dynamic languages10.1145/1869631.1869633(1-14)Online publication date: 18-Oct-2010
  • (2009)Allocation wallProceedings of the 24th ACM SIGPLAN conference on Object oriented programming systems languages and applications10.1145/1640089.1640116(361-376)Online publication date: 26-Oct-2009
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media