skip to main content
10.1145/1133956.1133976acmconferencesArticle/Chapter ViewAbstractPublication PagesismmConference Proceedingsconference-collections
Article

Compiler optimizations for nondeferred reference: counting garbage collection

Published: 10 June 2006 Publication History

Abstract

Reference counting is a well-known technique for automatic memory management, offering unique advantages over other forms of garbage collection. However, on account of the high costs associated with the maintenance of up-to-date tallies of references from the stack, deferred variants are typically used in modern implementations. This partially sacrifices some of the benefits of non-deferred reference-counting (RC) garbage collection, like the immediate reclamation of garbage and short collector pause times.This paper presents a series of optimizations that target the stack and substantially enhance the throughput of nondeferred RC collection. A key enabler is a new static analysis and optimization called RC subsumption that significantly reduces the overhead of maintaining the stack contribution to reference counts. We report execution time improvements on a benchmark suite of ten C# programs, and show how RC subsumption, aided with other optimizations, improves the performance of nondeferred RC collection by as much as a factor of 10, making possible running times that are within 32% of that with an advanced traversal-based collector on seven programs, and 19% of that with a deferred RC collector on eight programs. This is in the context of a baseline RC implementation that is typically at least a factor of 6 slower than the tracing collector and a factor of 5 slower than the deferred RC collector.

References

[1]
Association for Computing Machinery. Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation, June 2000.
[2]
David F. Bacon, Clement R. Attanasio, Han B. Lee, V. T. Rajan, and Stephen Smith. Java without the Coffee Breaks: A Nonintrusive Multiprocessor Garbage Collector. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 92--103. Association for Computing Machinery, June 2001.
[3]
David F. Bacon and V. T. Rajan. Concurrent Cycle Collection in Reference Counted Systems. In Proceedings of the 15th European Conference on Object-Oriented Programming, volume 2072 of Lecture Notes in Computer Science, pages 207--235. Springer-Verlag, June 2001.
[4]
Henry G. Baker. Minimizing Reference Count Updating with Deferred and Anchored Pointers for Functional Data Structures. ACM SIGPLAN Notices, 29(9):38--43, September 1994.
[5]
Jeffrey M. Barth. Shifting Garbage Collection Overhead to Compile Time. Communications of the ACM, 20(7):513--518, July 1977.
[6]
Stephen M. Blackburn and Kathryn S. McKinley. Ulterior Reference Counting: Fast Garbage Collection without a Long Wait. In Proceedings of the 18th ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications, pages 344--358, October 2003.
[7]
Don Box and Chris Sells. Essential .NET: The Common Language Runtime. Addison-Wesley Publishing Company, Inc., Redwood City, CA 94065, USA, 2003.
[8]
George E. Collins. A Method for Overlapping and Erasure of Lists. Communications of the ACM, 3(12):655--657, December 1960.
[9]
Keith D. Cooper and L. Taylor Simpson. Live Range Splitting in a Graph Coloring Register Allocator. In Proceedings of the 7th International Conference on Compiler Construction, volume 1383 of Lecture Notes in Computer Science, pages 174--187. Springer-Verlag, March 1998.
[10]
Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest. Introduction to Algorithms. The MIT Electrical Engineering and Computer Science Series. The MIT Press, Cambridge, MA 02142, USA, 1995.
[11]
John DeTreville. Experience with Concurrent Garbage Collectors for Modula-2+. Technical Report SRC-RR-64, Digital Systems Research Center, November 1990.
[12]
Alain Deutsch. On Determining Lifetime and Aliasing of Dynamically Allocated Data in Higher-Order Functional Specifications. In Proceedings of the 17th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 157--168. Association for Computing Machinery, January 1990.
[13]
L. Peter Deutsch and Daniel G. Bobrow. An Efficient, Incremental Automatic Garbage Collector. Communications of the ACM, 19(9):522--526, September 1976.
[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]
Sanjay Ghemawat, Keith H. Randall, and Daniel J. Scales. Field Analysis: Getting Useful and Low-Cost Interprocedural Information. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation {1}, pages 334--344.
[16]
Paul Hudak. A Semantic Model of Reference Counting and its Abstraction (Detailed Summary). In Proceedings of the ACM Conference on LISP and Functional Programming, pages 351--363. Association for Computing Machinery, April 1986.
[17]
Richard Jones and Rafael Lins. Garbage Collection: Algorithms for Automatic Dynamic Memory Management. John Wiley & Sons, Inc., New York City, NY 10158, USA, 1996.
[18]
Yossi Levanoni and Erez Petrank. An On-the-fly Reference Counting Garbage Collector for Java. In Proceedings of the 16th ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications, pages 367--380, October 2001.
[19]
Rafael D. Lins. Cyclic Reference Counting with Lazy Mark-Scan. Information Processing Letters, 44(4):215--220, December 1992.
[20]
Steven S. Muchnick. Advanced Compiler Design and Implementation. Morgan Kaufmann Publishers, Inc., San Francisco, CA 94104, USA, 1997.
[21]
V. Krishna Nandivada and David Detlefs. Compile-Time Concurrent Marking Write Barrier Removal. In Proceedings of the 5th International Symposium on Code Generation and Optimization, pages 37--48. IEEE Computer Society Press, March 2005.
[22]
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. Association for Computing Machinery, June 1991.
[23]
Harel Paz, Erez Petrank, David F. Bacon, Elliot K. Kolodner, and V. T.Rajan. An Efficient On-the-Fly Cycle Collection. In Proceedings of the 14th International Conference on Compiler Construction, volume 3443 of Lecture Notes in Computer Science, pages 156--171. Springer-Verlag, April 2005.
[24]
Benjamin C. Pierce. Types and Programming Languages. The MIT Press, Cambridge, MA 02142, USA, 2002.
[25]
Dale E. Rogerson. Inside COM. Microsoft Press, Redmond, WA98052, USA, 1997.
[26]
Paul Rovner. 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, July 1985.
[27]
Erik Ruf. Effective Synchronization Removal for Java. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation {1}, pages 208--218.
[28]
Wolfram Schulte. Deriving Residual Reference Count Garbage Collectors. In Proceedings of the 6th International Symposium on Programming Language Implementation and Logic Programming, pages 102--116, September 1994.
[29]
Wolfram Schulte and Wolfgang Grieskamp. Generating Efficient Portable Code for a Strict Applicative Language. In Proceedings of the PHOENIX Seminar and Workshop on Declarative Programming, pages 239--252, November 1991.
[30]
Chris Sells and Christopher Tavares. Adding Reference Counting to the Shared Source Common Language Infrastructure. At http://www.sellsbrothers.com/writing.
[31]
Martin T. Vechev and David F. Bacon. Write Barrier Elision for Concurrent Garbage Collectors. In Proceedings of the 4th International Symposium on Memory Management, pages 13--24. Association for Computing Machinery, October 2004.
[32]
Joseph Weizenbaum. Symmetric List Processor. Communications of the ACM, 6(9):524--536, September 1963.

Cited By

View all

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
ISMM '06: Proceedings of the 5th international symposium on Memory management
June 2006
202 pages
ISBN:1595932216
DOI:10.1145/1133956
  • General Chair:
  • Erez Petrank,
  • Program Chair:
  • Eliot Moss
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: 10 June 2006

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. reference counting
  2. static analyses

Qualifiers

  • Article

Conference

ISMM06
Sponsor:

Acceptance Rates

Overall Acceptance Rate 72 of 156 submissions, 46%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

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

Other Metrics

Citations

Cited By

View all
  • (2024)Being Lazy When It CountsFunctional and Logic Programming10.1007/978-981-97-2300-3_11(188-216)Online publication date: 15-May-2024
  • (2022)Quantifying the interpretation overhead of PythonScience of Computer Programming10.1016/j.scico.2021.102759215:COnline publication date: 1-Mar-2022
  • (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
  • (2017)Dynamic atomicity: optimizing swift memory managementACM SIGPLAN Notices10.1145/3170472.313384352:11(15-26)Online publication date: 24-Oct-2017
  • (2017)Dynamic atomicity: optimizing swift memory managementProceedings of the 13th ACM SIGPLAN International Symposium on on Dynamic Languages10.1145/3133841.3133843(15-26)Online publication date: 24-Oct-2017
  • (2014)Compiler techniques for massively scalable implicit task parallelismProceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis10.1109/SC.2014.30(299-310)Online publication date: 16-Nov-2014
  • (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)Adding dynamically-typed language support to a statically-typed language compilerACM SIGPLAN Notices10.1145/2365864.215104747:7(169-180)Online publication date: 3-Mar-2012
  • (2012)Adding dynamically-typed language support to a statically-typed language compilerProceedings of the 8th ACM SIGPLAN/SIGOPS conference on Virtual Execution Environments10.1145/2151024.2151047(169-180)Online publication date: 3-Mar-2012
  • 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