research-article

Reference object processing in on-the-fly garbage collection

Authors:

Tomoharu Ugawa,

Richard E. Jones,

Carl G. RitsonAuthors Info & Claims

ISMM '14: Proceedings of the 2014 international symposium on Memory management

Pages 59 - 69

https://doi.org/10.1145/2602988.2602991

Published: 12 June 2014 Publication History

Abstract

Most proposals for on-the-fly garbage collection ignore the question of Java's weak and other reference types. However, we show that reference types are heavily used in DaCapo benchmarks. Of the few collectors that do address this issue, most block mutators, either globally or individually, while processing reference types. We introduce a new framework for processing reference types on-the-fly in Jikes RVM. Our framework supports both insertion and deletion write barriers. We have model checked our algorithm and incorporated it in our new implementation of the Sapphire on-the-fly collector. Using a deletion barrier, we process references while mutators are running in less than three times the time that previous approaches take while mutators are halted; our overall execution times are no worse, and often better.

References

[1]

J. Auerbach, D. F. Bacon, B. Blainey, P. Cheng, M. Dawson, M. Fulton, D. Grove, D. Hart, and M. Stoodley. Design and implementation of a comprehensive real-time Java virtual machine. In 7th ACM & IEEE International Conference on Embedded Software, pages 249--258, Salzburg, Austria, Sept. 2007. ACM Press.

Digital Library

[2]

J. Auerbach, D. F. Bacon, P. Cheng, D. Grove, B. Biron, C. Gracie, B. McCloskey, A. Micic, and R. Sciampacone. Tax-and-spend: Democratic scheduling for real-time garbage collection. In 8th ACM International Conference on Embedded Software, pages 245--254, Atlanta, GA, 2008. ACM Press.

Digital Library

[3]

H. Azatchi, Y. Levanoni, H. Paz, and E. Petrank. An on-the-fly mark and sweep garbage collector based on sliding views. In ACMSIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications, ACMSIGPLANNotices 38(11), pages 269--281, Anaheim, CA, Nov. 2003. ACM Press.

Digital Library

[4]

D. F. Bacon, P. Cheng, and V. Rajan. A real-time garbage collector with low overhead and consistent utilization. In 30th Annual ACM Symposium on Principles of Programming Languages, ACM SIGPLAN Notices 38(1), pages 285--298, New Orleans, LA, Jan. 2003. ACM Press.

Digital Library

[5]

S. M. Blackburn, R. Garner, C. Hoffman, A. M. Khan, K. S. McKinley, R. Bentzur, A. Diwan, D. Feinberg, D. Frampton, S. Z. Guyer, M. Hirzel, A. Hosking, M. Jump, H. Lee, J. E. B. Moss, A. Phansalkar, D. Stefanović, T. VanDrunen, D. von Dincklage, and B. Wiedermann. The DaCapo benchmarks: Java benchmarking development and analysis. In ACM SIGPLAN Conference on Object- Oriented Programming, Systems, Languages, and Applications, ACM SIGPLAN Notices 41(10), pages 169--190, Portland, OR, Oct. 2006. ACM Press.

Digital Library

[6]

C. Click, G. Tene, and M. Wolf. The Pauseless GC algorithm. In M. Hind and J. Vitek, editors, 1st ACM SIGPLAN/SIGOPS International Conference on Virtual Execution Environments, pages 46--56, Chicago, IL, June 2005. ACM Press.

Digital Library

[7]

D. Doligez and G. Gonthier. Portable, unobtrusive garbage collection for multiprocessor systems. In 21st Annual ACM Symposium on Principles of Programming Languages, pages 70--83, Portland, OR, Jan. 1994. ACM Press.

Digital Library

[8]

T. Domani, E. K. Kolodner, E. Lewis, E. E. Salant, K. Barabash, I. Lahan, E. Petrank, I. Yanover, and Y. Levanoni. Implementing an onthe- fly garbage collector for Java. In C. Chambers and A. L. Hosking, editors, 2nd International Symposium on Memory Management, ACM SIGPLAN Notices 36(1), pages 155--166, Minneapolis, MN, Oct. 2000. ACM Press.

Digital Library

[9]

A. Georges, L. Eeckhout, and D. Buytaert. Java performance evaluation through rigorous replay compilation. In ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications, ACM SIGPLAN Notices 43(10), pages 367--384, Nashville, TN, Oct. 2008. ACM Press.

Digital Library

[10]

R. Henriksson. Scheduling Garbage Collection in Embedded Systems. PhD thesis, Lund Institute of Technology, July 1998.

[11]

G. J. Holzmann. The SPIN Model Checker: Primer and Reference Manual. Addison-Wesley, 2004.

Digital Library

[12]

R. L. Hudson and J. E. B.Moss. Sapphire: Copying garbage collection without stopping the world. Concurrency and Computation: Practice and Experience, 15(3--5):223--261, 2003.

[13]

B. Iyengar, G. Tene, M. Wolf, and E. Gehringer. The Collie: a waitfree compacting collector. In McKinley and Vechev, editors, 11th International Symposium on Memory Management, pages 85--96, China, June 2012. ACM Press.

Digital Library

[14]

R. Jones, A. Hosking, and E. Moss. The Garbage CollectionHandbook: The Art of Automatic Memory Management. CRCApplied Algorithms and Data Structures. Chapman & Hall, Aug. 2012.

Digital Library

[15]

T. Kalibera. Replicating real-time garbage collector for Java. In 7th International Workshop on Java Technologies for Real-time and Embedded Systems (JTRES), pages 100--109, Madrid, Spain, Sept. 2009. ACM Press.

Digital Library

[16]

B. McCloskey, D. F. Bacon, P. Cheng, and D. Grove. Staccato: A parallel and concurrent real-time compacting garbage collector for multiprocessors. IBM Research Report RC24505, IBM Research, 2008.

[17]

Oracle Corp. Java Platform, Standard Edition 7: API Specification,2013.

[18]

P. P. Pirinen. Barrier techniques for incremental tracing. In S. L. Peyton Jones and R. Jones, editors, 1st International Symposium on Memory Management, ACMSIGPLAN Notices 34(3), pages 20--25, Vancouver, Canada, Oct. 1998. ACM Press.

Digital Library

[19]

F. Pizlo, D. Frampton, E. Petrank, and B. Steensgard. Stopless: A real-time garbage collector for multiprocessors. In G. Morrisett and M. Sagiv, editors, 6th International Symposium on Memory Management, pages 159--172, Montréal, Canada, Oct. 2007. ACM Press.

Digital Library

[20]

F. Pizlo, A. L. Hosking, and J. Vitek. Hierarchical real-time garbage collection. In ACM SIGPLAN/SIGBED Conference on Languages, Compilers, and Tools for Embedded Systems, ACMSIGPLANNotices 42(7), pages 123--133, San Diego, CA, June 2007. ACM Press.

Digital Library

[21]

F. Pizlo, E. Petrank, and B. Steensgaard. A study of concurrent real-time garbage collectors. In R. Gupta and S. P. Amarasinghe, editors, ACM SIGPLAN Conference on Programming Language Design and Implementation, ACM SIGPLAN Notices 43(6), pages 33--44, Tucson, AZ, June 2008. ACM Press.

Digital Library

[22]

F. Pizlo, L. Ziarek, P. Maj, A. L. Hosking, E. Blanton, and J. Vitek. Schism: Fragmentation-tolerant real-time garbage collection. In ACM SIGPLAN Conference on Programming Language Design and Implementation, ACM SIGPLAN Notices 45(6), pages 146--159, Toronto, Canada, June 2010. ACM Press.

Digital Library

[23]

M. Schoeberl and W. Puffitsch. Non-blocking object copy for realtime garbage collection. In 6th International Workshop on Java Technologies for Real-time and Embedded Systems (JTRES), pages 77--84, Santa Clara, CA, Sept. 2008. ACM Press.

Digital Library

[24]

G. Tene, B. Iyengar, and M. Wolf. C4: The continuously concurrent compacting collector. In H. Boehm and D. Bacon, editors, 10th International Symposium on Memory Management, pages 79--88, San Jose, CA, June 2011. ACM Press.

Digital Library

[25]

X. Yang, S. M. Blackburn, D. Frampton, and A. L. Hosking. Barriers reconsidered, friendlier still! In McKinley and Vechev, editors, 11th International Symposium on Memory Management, pages 37--48, China, June 2012. ACM Press.

Digital Library

Cited By

Yamazaki TNakamaru TShioya RUgawa TChiba S(2023)Collecting Cyclic Garbage across Foreign Function Interfaces: Who Takes the Last Piece of Cake?Proceedings of the ACM on Programming Languages10.1145/35912447:PLDI(591-614)Online publication date: 6-Jun-2023
https://dl.acm.org/doi/10.1145/3591244
Yang AWrigstad T(2022)Deep Dive into ZGC: A Modern Garbage Collector in OpenJDKACM Transactions on Programming Languages and Systems10.1145/353853244:4(1-34)Online publication date: 21-Sep-2022
https://dl.acm.org/doi/10.1145/3538532
Lee DWon YPark YLee SHung CCerny TShin DBechini A(2020)Two-tier garbage collection for persistent objectProceedings of the 35th Annual ACM Symposium on Applied Computing10.1145/3341105.3373986(1246-1255)Online publication date: 30-Mar-2020
https://dl.acm.org/doi/10.1145/3341105.3373986
Show More Cited By

Index Terms

Reference object processing in on-the-fly garbage collection
1. Software and its engineering
  1. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Memory management
        Garbage collection

Recommendations

Reference object processing in on-the-fly garbage collection
ISMM '14

Most proposals for on-the-fly garbage collection ignore the question of Java's weak and other reference types. However, we show that reference types are heavily used in DaCapo benchmarks. Of the few collectors that do address this issue, most block ...
Adaptive scanning reduces sweep time for the Lisp2 mark-compact garbage collector
ISMM '13: Proceedings of the 2013 international symposium on memory management

Mark-compact garbage collection helps long-running programs avoid fragmentation. The Lisp2 mark-compact collector is a classic but still widely-used compaction algorithm. It sequentially scans the entire heap to compact all live objects at one end of ...
Controlling garbage collection and heap growth to reduce the execution time of Java applications

In systems that support garbage collection, a tension exists between collecting garbage too frequently and not collecting it frequently enough. Garbage collection that occurs too frequently may introduce unnecessary overheads at the risk of not ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ISMM '14: Proceedings of the 2014 international symposium on Memory management

June 2014

136 pages

ISBN:9781450329217

DOI:10.1145/2602988

General Chair:
David Grove
IBM Research, USA
,
Program Chair:
Samuel Z. Guyer
Tufts University, USA

ACM SIGPLAN Notices Volume 49, Issue 11
ISMM '14
November 2014
121 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/2775049
Editor:
Andy Gill
University of Kansas, Lawrence, KS
Issue’s Table of Contents

Copyright © 2014 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 the author(s) 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

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 June 2014

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Conference

ISMM '14

Sponsor:

SIGPLAN

ISMM '14: International Symposium on Memory Management

June 12, 2014

Edinburgh, United Kingdom

Acceptance Rates

ISMM '14 Paper Acceptance Rate 11 of 22 submissions, 50%;

Overall Acceptance Rate 72 of 156 submissions, 46%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
292
Total Downloads

Downloads (Last 12 months)8
Downloads (Last 6 weeks)1

Reflects downloads up to 22 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Yamazaki TNakamaru TShioya RUgawa TChiba S(2023)Collecting Cyclic Garbage across Foreign Function Interfaces: Who Takes the Last Piece of Cake?Proceedings of the ACM on Programming Languages10.1145/35912447:PLDI(591-614)Online publication date: 6-Jun-2023
https://dl.acm.org/doi/10.1145/3591244
Yang AWrigstad T(2022)Deep Dive into ZGC: A Modern Garbage Collector in OpenJDKACM Transactions on Programming Languages and Systems10.1145/353853244:4(1-34)Online publication date: 21-Sep-2022
https://dl.acm.org/doi/10.1145/3538532
Lee DWon YPark YLee SHung CCerny TShin DBechini A(2020)Two-tier garbage collection for persistent objectProceedings of the 35th Annual ACM Symposium on Applied Computing10.1145/3341105.3373986(1246-1255)Online publication date: 30-Mar-2020
https://dl.acm.org/doi/10.1145/3341105.3373986
Ugawa TRitson CJones R(2018)Transactional SapphireACM Transactions on Programming Languages and Systems10.1145/322622540:4(1-56)Online publication date: 10-Dec-2018
https://dl.acm.org/doi/10.1145/3226225
Franco JClebsch SDrossopoulou SVitek JWrigstad T(2018)Correctness of a Concurrent Object Collector for Actor LanguagesProgramming Languages and Systems10.1007/978-3-319-89884-1_31(885-911)Online publication date: 14-Apr-2018
https://doi.org/10.1007/978-3-319-89884-1_31
Ugawa TAbe TMaeda T(2017)Model checking copy phases of concurrent copying garbage collection with various memory modelsProceedings of the ACM on Programming Languages10.1145/31338771:OOPSLA(1-26)Online publication date: 12-Oct-2017
https://dl.acm.org/doi/10.1145/3133877
Ugawa TRitson CJones R(2018)Transactional SapphireACM Transactions on Programming Languages and Systems10.1145/322622540:4(1-56)Online publication date: 10-Dec-2018
https://dl.acm.org/doi/10.1145/3226225
Yu HShi XFeng W(2015)LeakTracer: Tracing leaks along the way2015 IEEE 15th International Working Conference on Source Code Analysis and Manipulation (SCAM)10.1109/SCAM.2015.7335414(181-190)Online publication date: Sep-2015
https://doi.org/10.1109/SCAM.2015.7335414

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 Table of Contents