article

Ulterior reference counting: fast garbage collection without a long wait

Authors:

Stephen M. Blackburn,

Kathryn S. McKinleyAuthors Info & Claims

ACM SIGPLAN Notices, Volume 38, Issue 11

Pages 344 - 358

https://doi.org/10.1145/949343.949336

Published: 26 October 2003 Publication History

Abstract

General purpose garbage collectors have yet to combine short pause times with high throughput. For example, generational collectors can achieve high throughput. They have modest average pause times, but occasionally collect the whole heap and consequently incur long pauses. At the other extreme, concurrent collectors, including reference counting, attain short pause times but with significant performance penalties. This paper introduces a new hybrid collector that combines copying generational collection for the young objects and reference counting the old objects to achieve both goals. It restricts copying and reference counting to the object demographics for which they perform well. Key to our algorithm is a generalization of deferred reference counting we call Ulterior Reference Counting. Ulterior reference counting safely ignores mutations to select heap objects. We compare a generational reference counting hybrid with pure reference counting, pure mark-sweep, and hybrid generational mark-sweep collectors. This new collector combines excellent throughput, matching a high performance generational mark-sweep hybrid, with low maximum pause times.

References

[1]

B. Alpern, C. R. Attanasio, A. Cocchi, D. Lieber, S. Smith, T. Ngo, J. J. Barton, S. F. Hummel, J. C. Sheperd, and M. Mergen. Implementing Jalapeño in Java. In Proceedings of the 1999 ACM SIGPLAN Conference on Object-Oriented Programming Systems, Languages & Applications, OOPSLA '99, Denver, Colorado, November 1-5, 1999, volume 34(10) of ACM SIGPLAN Notices, pages 314--324. ACM Press, Oct. 1999.

Digital Library

[2]

B. Alpern, D. Attanasio, J. J. Barton, M. G. Burke, P. Cheng, J.-D. Choi, A. Cocchi, S. J. Fink, D. Grove, M. Hind, S. F. Hummel, D. Lieber, V. Litvinov, M. Mergen, T. Ngo, J. R. Russell, V. Sarkar, M. J. Serrano, J. Shepherd, S. Smith, V. C. Sreedhar, H. Srinivasan, and J. Whaley. The Jalapeño virtual machine. IBM System Journal, 39(1):211--238, February 2000.

Digital Library

[3]

A. W. Appel. Simple generational garbage collection and fast allocation. Software Practice and Experience, 19(2):171--183, 1989.

Digital Library

[4]

M. Arnold, S. J. Fink, D. Grove, M. Hind, and P. Sweeney. Adaptive optimization in the Jalapeño JVM. In OOPSLA'00 ACM Conference on Object-Oriented Systems, Languages and Applications, Minneapolis, MN, USA, October 15-19, 2000, volume 35(10) of ACM SIGPLAN Notices, pages 47--65. ACM Press, October 2000.

Digital Library

[5]

C. R. Attanasio, D. F. Bacon, A. Cocchi, and S. Smith. A comparative evaluation of parallel garbage collectors. In Languages and Compilers for Parallel Computing, 14th International Workshop, LCPC 2001, Cumberland Falls, KY, USA, August 1-3, 2001, Lecture Notes in Computer Science. Springer-Verlag, 2001.

Digital Library

[6]

H. Azatchi and E. Petrank. Integrating generations with advanced reference counting garbage collectors. In International Conference on Compiler Construction, Warsaw, Poland, Apr. 2003. To Appear.

Digital Library

[7]

D. F. Bacon, C. R. Attanasio, H. B. Lee, V. T. Rajan, and S. Smith. Java without the coffee breaks: A nonintrusive multiprocessor garbage collector. In Proceedings of the ACM SIGPLAN'01 Conference on Programming Languages Design and Implementation (PLDI), Snowbird, Utah, May, 2001, volume 36(5), June 2001.

Digital Library

[8]

D. F. Bacon, P. Cheng, and V. T. Rajan. A realtime garbage collector with low overhead and consistent utilization. In POPL 2003: The 30th SIGPLAN-SIGACT Symposium on Principles of Programming Languages, New Orleans, Louisisana, January 15-17, 2003, volume 38(1) of ACM SIGPLAN Notices. ACM Press, Jan. 2003.

Digital Library

[9]

D. F. Bacon and V. T. Rajan. Concurrent cycle collection in reference counted systems. In J. L. Knudsen, editor, Proceedings of 15th European Conference on Object-Oriented Programming, ECOOP 2001, Budapest, Hungary, June 18-22, volume 2072 of Lecture Notes in Computer Science, pages 207--235. Springer-Verlag, 2001.

Digital Library

[10]

E. D. Berger, B. G. Zorn, and K. S. McKinley. Building high-performance custom and general-purpose memory allocators. In Proceedings of SIGPLAN 2001 Conference on Programming Languages Design and Implementati on, pages 114--124, Salt Lake City, UT, June 2001.

Digital Library

[11]

S. M. Blackburn, P. Cheng, and K. S. McKinley. A garbage collection bakeoff in a Java memory management toolkit (JMTk). Technical Report TR-CS-03-02, ANU, Mar. 2003.

[12]

S. M. Blackburn, R. E. Jones, K. S. McKinley, and J. E. B. Moss. Beltway: Getting around garbage collection gridlock. In Proceedings of SIGPLAN 2002 Conference on Programming Languages Design and Implementation, PLDI'02, Berlin, June, 2002, volume 37(5) of ACM SIGPLAN Notices. ACM Press, June 2002.

Digital Library

[13]

S. M. Blackburn and K. S. McKinley. Fast garbage collection without a long wait. Technical Report TR-CS-02-06, Dept. of Computer Science, Austrailian National University, Nov. 2002.

[14]

S. M. Blackburn and K. S. McKinley. In or out? Putting write barriers in their place. In Proceedings of the Third International Symposium on Memory Management, ISMM '02, Berlin, Germany, volume 37 of ACM SIGPLAN Notices. ACM Press, June 2002.

Digital Library

[15]

H.-J. Boehm, A. J. Demers, and S. Shenker. Mostly parallel garbage collection. SIGPLAN Notices, 26(6):157--164, 1991.

Digital Library

[16]

C. J. Cheney. A non-recursive list compacting algorithm. Communications of the ACM, 13(11):677--8, Nov. 1970.

Digital Library

[17]

P. Cheng and G. Belloch. A parallel, real-time garbage collector. In Proceedings of the ACM SIGPLAN'01 Conference on Programming Languages Design and Implementation (PLDI), Snowbird, Utah, May, 2001, volume 36(5) of ACM SIGPLAN Notices, pages 125--136. ACM Press, June 2001.

Digital Library

[18]

G. E. Collins. A method for overlapping and erasure of lists. Communications of the ACM, 3(12):655--657, Dec. 1960.

Digital Library

[19]

L. P. Deutsch and D. G. Bobrow. An efficient incremental automatic garbage collector. Communications of the ACM, 19(9):522--526, September 1976.

Digital Library

[20]

R. L. Hudson and J. E. B. Moss. Incremental garbage collection for mature objects. In Y. Bekkers and J. Cohen, editors, Proceedings of the First International Workshop on Memory Management, IWMM'92, St. Malo, France, Sep, 1992, volume 637 of Lecture Notes in Computer Science. Springer-Verlag, 1992.

Digital Library

[21]

R. E. Jones and R. D. Lins. Garbage Collection: Algorithms for Automatic Dynamic Memory Management. Wiley, July 1996.

Digital Library

[22]

D. Lea. A memory allocator. http://gee.cs.oswego.edu/dl/html/malloc.html, 1997.

[23]

Y. Levanoni and E. Petrank. An on-the-fly reference counting garbage collector for Java. In ACM Conference Proceedings on Object--Oriented Programming Systems, Languages, and Applications, pages 367--380, Tampa, FL, Oct. 2001.

Digital Library

[24]

H. Lieberman and C. E. Hewitt. A real time garbage collector based on the lifetimes of objects. Communications of the ACM, 26(6):419--429, 1983.

Digital Library

[25]

E. Petrank. Private communication, July 2003.

[26]

T. Printezis and D. Detlefs. A generational mostly-concurrent garbage collector. In Proceedings of the International Symposium On Memory Management (ISMM), Minneapolis. ACM Press, Oct. 2000.

Digital Library

[27]

Standard Performance Evaluation Corporation. SPECjvm98 Documentation, release 1.03 edition, March 1999.

[28]

Standard Performance Evaluation Corporation. SPECjbb2000 (Java Business Benchmark) Documentation, release 1.01 edition, 2001.

[29]

D. Stefanović. Properties of Age-Based Automatic Memory Reclamation Algorithms. PhD thesis, University of Massachusetts, 1999.

Digital Library

[30]

D. M. Ungar. Generation scavenging: A non-disruptive high performance storage reclamation algorithm. ACM SIGPLAN Notices, 19(5):157--167, April 1984.

Digital Library

[31]

P. R. Wilson, M. S. Johnstone, M. Neely, and D. Boles. Dynamic storage allocation: A survey and critical review. In H. Baker, editor, Proceedings of International Workshop on Memory Management, IWMM'95, Kinross, Scotland, volume 986 of Lecture Notes in Computer Science. Springer-Verlag, Sept. 1995.

Digital Library

Cited By

Tabassum FIslam MUr Rahman MMajumder J(2023)A Comprehensive Study on Different Optimizations of Pure Reference Counting Garbage Collectors2023 International Conference on Computational Intelligence, Networks and Security (ICCINS)10.1109/ICCINS58907.2023.10450100(1-6)Online publication date: 22-Dec-2023
https://doi.org/10.1109/ICCINS58907.2023.10450100
Carpen-Amarie MDice DThomas GFelber P(2016)Transactional Pointers: Experiences with HTM-Based Reference Counting in C++Networked Systems10.1007/978-3-319-46140-3_8(102-116)Online publication date: 15-Sep-2016
https://doi.org/10.1007/978-3-319-46140-3_8
Cohen NPetrank EHosking ABond M(2015)Data structure aware garbage collectorProceedings of the 2015 International Symposium on Memory Management10.1145/2754169.2754176(28-40)Online publication date: 14-Jun-2015
https://dl.acm.org/doi/10.1145/2754169.2754176
Show More Cited By

Index Terms

Ulterior reference counting: fast garbage collection without a long wait
1. Software and its engineering
  1. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Memory management
        Garbage collection

Recommendations

Ulterior reference counting: fast garbage collection without a long wait
OOPSLA '03: Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications

General purpose garbage collectors have yet to combine short pause times with high throughput. For example, generational collectors can achieve high throughput. They have modest average pause times, but occasionally collect the whole heap and ...
Flexible reference-counting-based hardware acceleration for garbage collection

Languages featuring automatic memory management (garbage collection) are increasingly used to write all kinds of applications because they provide clear software engineering and security advantages. Unfortunately, garbage collection imposes a toll on ...
Myths and realities: the performance impact of garbage collection

This paper explores and quantifies garbage collection behavior for three whole heap collectors and generational counterparts: copying semi-space, mark-sweep, and reference counting, the canonical algorithms from which essentially all other collection ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices

ACM SIGPLAN Notices Volume 38, Issue 11

Special Issue: Proceedings of the OOPSLA '03 conference

November 2003

417 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/949343

Issue’s Table of Contents

OOPSLA '03: Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications
October 2003
430 pages
ISBN:1581137125
DOI:10.1145/949305
Conference Chair:
Ron Crocker
Motorola, Inc.
,
Program Chair:
Guy L. Steele
Sun Microsystems Laboratories

Copyright © 2003 ACM.

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 26 October 2003

Published in SIGPLAN Volume 38, Issue 11

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

73
Total Citations
View Citations
1,028
Total Downloads

Downloads (Last 12 months)17
Downloads (Last 6 weeks)0

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Tabassum FIslam MUr Rahman MMajumder J(2023)A Comprehensive Study on Different Optimizations of Pure Reference Counting Garbage Collectors2023 International Conference on Computational Intelligence, Networks and Security (ICCINS)10.1109/ICCINS58907.2023.10450100(1-6)Online publication date: 22-Dec-2023
https://doi.org/10.1109/ICCINS58907.2023.10450100
Carpen-Amarie MDice DThomas GFelber P(2016)Transactional Pointers: Experiences with HTM-Based Reference Counting in C++Networked Systems10.1007/978-3-319-46140-3_8(102-116)Online publication date: 15-Sep-2016
https://doi.org/10.1007/978-3-319-46140-3_8
Cohen NPetrank EHosking ABond M(2015)Data structure aware garbage collectorProceedings of the 2015 International Symposium on Memory Management10.1145/2754169.2754176(28-40)Online publication date: 14-Jun-2015
https://dl.acm.org/doi/10.1145/2754169.2754176
Dombrowski MNasartschuk KKent KDueck G(2015)A survey on object cache locality in automated memory management systems2015 IEEE 28th Canadian Conference on Electrical and Computer Engineering (CCECE)10.1109/CCECE.2015.7129301(349-354)Online publication date: May-2015
https://doi.org/10.1109/CCECE.2015.7129301
Kliot GPetrank ESteensgaard B(2009)A lock-free, concurrent, and incremental stack scanning mechanism for garbage collectorsACM SIGOPS Operating Systems Review10.1145/1618525.161852743:3(3-13)Online publication date: 31-Jul-2009
https://dl.acm.org/doi/10.1145/1618525.1618527
Kliot GPetrank ESteensgaard BHosking ABacon DKrieger O(2009)A lock-free, concurrent, and incremental stack scanning for garbage collectorsProceedings of the 2009 ACM SIGPLAN/SIGOPS international conference on Virtual execution environments10.1145/1508293.1508296(11-20)Online publication date: 11-Mar-2009
https://dl.acm.org/doi/10.1145/1508293.1508296
Xian FSrisa-an WJiang H(2008)Garbage collectionScience of Computer Programming10.1016/j.scico.2007.07.00870:2-3(89-110)Online publication date: 1-Feb-2008
https://dl.acm.org/doi/10.1016/j.scico.2007.07.008
Levanoni YPetrank E(2006)An on-the-fly reference-counting garbage collector for javaACM Transactions on Programming Languages and Systems10.1145/1111596.111159728:1(1-69)Online publication date: 1-Jan-2006
https://dl.acm.org/doi/10.1145/1111596.1111597
Azatchi HPetrank E(2006)Integrating generations with advanced reference counting garbage collectorsConcurrency and Computation: Practice and Experience10.1002/cpe.100518:9(959-995)Online publication date: 12-Jan-2006
https://doi.org/10.1002/cpe.1005
Alpern BAugart SBlackburn SButrico MCocchi ACheng PDolby JFink SGrove DHind MMcKinley KMergen MMoss JNgo TSarkar V(2005)The Jikes research virtual machine projectIBM Systems Journal10.1147/sj.442.039944:2(399-417)Online publication date: 21-Jan-2005
https://dl.acm.org/doi/10.1147/sj.442.0399
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents