research-article

Open access

Concurrent Immediate Reference Counting

Authors:

Jeonghyeon Kim,

Matthew J. Parkinson,

Jeehoon KangAuthors Info & Claims

Proceedings of the ACM on Programming Languages, Volume 8, Issue PLDI

Article No.: 153, Pages 151 - 174

https://doi.org/10.1145/3656383

Published: 20 June 2024 Publication History

Abstract

Memory management for optimistic concurrency in unmanaged programming languages is challenging. Safe memory reclamation (SMR) algorithms help address this, but they are difficult to use correctly. Automatic reference counting provides a simpler interface, but it has been less efficient than SMR algorithms. Recently, there has been a push to apply the optimizations used in garbage collectors for managed languages to elide reference count updates from local references. Notably, Fast Reference Counter, OrcGC, and Concurrent Deferred Reference Counting use SMR algorithms to protect local references by deferring decrements or reclamation. While they show a significant performance improvement, their use of deferral may result in growing memory usage due to slow reclamation of linked structures, and suboptimal performance in update-heavy workloads.

We present Concurrent Immediate Reference Counting (CIRC), a new combination of SMR algorithms with reference counting. CIRC employs deferral like other modern methods, but it avoids their problems with novel algorithms for (1) immediately reclaiming linked structures recursively by tracking the reachability of each object, and (2) applying decrements immediately and deferring only the reclamation. Our experiments show that CIRC’s memory usage does not grow over time and is only slightly higher than the underlying SMR. Moreover, CIRC further narrows the performance gap between the underlying SMR, positioning it as a promising solution to safe automatic memory management for highly concurrent data structures in unmanaged languages.

References

[1]

Daniel Anderson, Guy E. Blelloch, and Yuanhao Wei. 2021. Concurrent Deferred Reference Counting with Constant-Time Overhead. In Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation (PLDI 2021). Association for Computing Machinery, New York, NY, USA. 526–541. isbn:9781450383912 https://doi.org/10.1145/3453483.3454060

Digital Library

[2]

Daniel Anderson, Guy E. Blelloch, and Yuanhao Wei. 2022. Turning Manual Concurrent Memory Reclamation into Automatic Reference Counting. In Proceedings of the 43rd ACM SIGPLAN International Conference on Programming Language Design and Implementation (PLDI 2022). Association for Computing Machinery, New York, NY, USA. 61–75. isbn:9781450392655 https://doi.org/10.1145/3519939.3523730

Digital Library

[3]

David F. Bacon, Clement R. Attanasio, Han B. Lee, V. T. Rajan, and Stephen Smith. 2001. Java without the Coffee Breaks: A Nonintrusive Multiprocessor Garbage Collector. In Proceedings of the ACM SIGPLAN 2001 Conference on Programming Language Design and Implementation (PLDI ’01). Association for Computing Machinery, New York, NY, USA. 92–103. isbn:1581134142 https://doi.org/10.1145/378795.378819

Digital Library

[4]

Hans-Juergen Boehm and Mark Weiser. 1988. Garbage Collection in an Uncooperative Environment. 18, 9 (1988), 807–820. https://doi.org/10.1002/spe.4380180902

Digital Library

[5]

Trevor Alexander Brown. 2015. Reclaiming Memory for Lock-Free Data Structures: There Has to Be a Better Way. In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing (PODC ’15). Association for Computing Machinery, New York, NY, USA. 261–270. isbn:9781450336178 https://doi.org/10.1145/2767386.2767436

Digital Library

[6]

Nachshon Cohen and Erez Petrank. 2015. Automatic Memory Reclamation for Lock-Free Data Structures. In Proceedings of the 2015 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA 2015). Association for Computing Machinery, New York, NY, USA. 260–279. isbn:9781450336895 https://doi.org/10.1145/2814270.2814298

Digital Library

[7]

Andreia Correia, Pedro Ramalhete, and Pascal Felber. 2021. OrcGC: Automatic Lock-Free Memory Reclamation. In Proceedings of the 26th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP ’21). Association for Computing Machinery, New York, NY, USA. 205–218. isbn:9781450382946 https://doi.org/10.1145/3437801.3441596

Digital Library

[8]

Crossbeam Developers. 2023. Crossbeam. https://github.com/crossbeam-rs/crossbeam

[9]

L. Peter Deutsch and Daniel G. Bobrow. 1976. An Efficient, Incremental, Automatic Garbage Collector. Commun. ACM, 19, 9 (1976), sep, 522–526. issn:0001-0782 https://doi.org/10.1145/360336.360345

Digital Library

[10]

Dave Dice, Hui Huang, and Mingyao Yang. 2001. Asymmetric Dekker Synchronization. http://web.archive.org/web/20080220051535/http://blogs.sun.com/dave/resource/Asymmetric-Dekker-Synchronization.txt

[11]

Jason Evans. 2006. A scalable concurrent malloc (3) implementation for FreeBSD.

[12]

Keir Fraser. 2004. Practical lock-freedom. Ph. D. Dissertation. University of Cambridge, Computer Laboratory.

[13]

David Goldblatt. 2022. P1202R5: Asymmetric Fences. https://wg21.link/p1202r5

[14]

Maurice Herlihy, Victor Luchangco, Paul Martin, and Mark Moir. 2005. Nonblocking Memory Management Support for Dynamic-Sized Data Structures. ACM Trans. Comput. Syst., 23, 2 (2005), may, 146–196. issn:0734-2071 https://doi.org/10.1145/1062247.1062249

Digital Library

[15]

Jaehwang Jung, Jeonghyeon Kim, Matthew J. Parkinson, and Jeehoon Kang. 2024. Concurrent Immediate Reference Counting (artifact and appendix). https://doi.org/10.5281/zenodo.10806736 Project webpage:

[16]

Yossi Levanoni and Erez Petrank. 2001. 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 (OOPSLA ’01). Association for Computing Machinery, New York, NY, USA. 367–380. isbn:1581133359 https://doi.org/10.1145/504282.504309

Digital Library

[17]

P. E. McKenney and J. D. Slingwine. 1998. Read-copy update: Using execution history to solve concurrency problems. In PDCS ’98.

[18]

Meta. 2023. Folly: Facebook Open-source Library. https://github.com/facebook/folly

[19]

Maged M. Michael. 2002. High Performance Dynamic Lock-Free Hash Tables and List-Based Sets. In Proceedings of the Fourteenth Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA ’02). Association for Computing Machinery, New York, NY, USA. 73–82. isbn:1581135297 https://doi.org/10.1145/564870.564881

Digital Library

[20]

Maged M. Michael. 2002. Safe Memory Reclamation for Dynamic Lock-Free Objects Using Atomic Reads and Writes. In Proceedings of the Twenty-First Annual Symposium on Principles of Distributed Computing (PODC ’02). Association for Computing Machinery, New York, NY, USA. 21–30. isbn:1581134851 https://doi.org/10.1145/571825.571829

Digital Library

[21]

Maged M. Michael. 2004. Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects. IEEE Trans. Parallel Distrib. Syst., 15, 6 (2004), June, 491–504. issn:1045-9219 https://doi.org/10.1109/TPDS.2004.8

Digital Library

[22]

Maged M. Michael. 2020. Brief Announcement: Hazard Pointer Protection of Structures with Immutable Links. In Proceedings of the 39th Symposium on Principles of Distributed Computing (PODC ’20). Association for Computing Machinery, New York, NY, USA. 230–232. isbn:9781450375825 https://doi.org/10.1145/3382734.3405738

Digital Library

[23]

Maged M. Michael and Michael L. Scott. 1996. Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms. In Proceedings of the Fifteenth Annual ACM Symposium on Principles of Distributed Computing (PODC ’96). Association for Computing Machinery, New York, NY, USA. 267–275. isbn:0897918002 https://doi.org/10.1145/248052.248106

Digital Library

[24]

Aravind Natarajan and Neeraj Mittal. 2014. Fast Concurrent Lock-Free Binary Search Trees. In Proceedings of the 19th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP ’14). Association for Computing Machinery, New York, NY, USA. 317–328. isbn:9781450326568 https://doi.org/10.1145/2555243.2555256

Digital Library

[25]

Ruslan Nikolaev and Binoy Ravindran. 2021. Snapshot-Free, Transparent, and Robust Memory Reclamation for Lock-Free Data Structures. In Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation (PLDI 2021). Association for Computing Machinery, New York, NY, USA. 987–1002. isbn:9781450383912 https://doi.org/10.1145/3453483.3454090

Digital Library

[26]

Matthew Parkinson, Dimitrios Vytiniotis, Kapil Vaswani, Manuel Costa, Pantazis Deligiannis, Dylan McDermott, Aaron Blankstein, and Jonathan Balkind. 2017. Project Snowflake: Non-Blocking Safe Manual Memory Management in .NET. Proc. ACM Program. Lang., 1, OOPSLA (2017), Article 95, oct, 25 pages. https://doi.org/10.1145/3141879

Digital Library

[27]

Matthew J. Parkinson, Sylvan Clebsch, and Ben Simner. 2023. Wait-Free Weak Reference Counting. In Proceedings of the 2023 ACM SIGPLAN International Symposium on Memory Management (ISMM 2023). Association for Computing Machinery, New York, NY, USA. 85–96. isbn:9798400701795 https://doi.org/10.1145/3591195.3595271

Digital Library

[28]

Pedro Ramalhete and Andreia Correia. 2017. Brief Announcement: Hazard Eras - Non-Blocking Memory Reclamation. In Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA ’17). Association for Computing Machinery, New York, NY, USA. 367–369. isbn:9781450345934 https://doi.org/10.1145/3087556.3087588

Digital Library

[29]

Pedro Ramalhete and Andreia Correia. 2017. DoubleLink - A Low-Overhead Lock-Free Queue. https://concurrencyfreaks.blogspot.com/2017/01/doublelink-low-overhead-lock-free-queue.html

[30]

Rifat Shahriyar, Stephen M. Blackburn, and Kathryn S. McKinley. 2014. Fast conservative garbage collection. In Proceedings of the 2014 ACM International Conference on Object Oriented Programming Systems Languages & Applications (OOPSLA ’14). Association for Computing Machinery, New York, NY, USA. 121–139. isbn:9781450325851 https://doi.org/10.1145/2660193.2660198

Digital Library

[31]

Nir N Shavit, Yosef Lev, and Maurice P Herlihy. 2011. Concurrent lock-free skiplist with wait-free contains operator. https://patentcenter.uspto.gov/applications/12191008 US Patent 7,937,378

[32]

Charles Tripp, David Hyde, and Benjamin Grossman-Ponemon. 2018. FRC: A High-Performance Concurrent Parallel Deferred Reference Counter for C++. In Proceedings of the 2018 ACM SIGPLAN International Symposium on Memory Management (ISMM 2018). Association for Computing Machinery, New York, NY, USA. 14–28. isbn:9781450358019 https://doi.org/10.1145/3210563.3210569

Digital Library

[33]

Haosen Wen, Joseph Izraelevitz, Wentao Cai, H. Alan Beadle, and Michael L. Scott. 2018. Interval-Based Memory Reclamation. In Proceedings of the 23rd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP ’18). Association for Computing Machinery, New York, NY, USA. 1–13. isbn:9781450349826 https://doi.org/10.1145/3178487.3178488

Digital Library

[34]

Anthony Williams. 2019. C++ Concurrency in Action,2E (2 ed.). Manning Publications, New York, NY.

[35]

Albert Mingkun Yang and Tobias Wrigstad. 2017. Type-Assisted Automatic Garbage Collection for Lock-Free Data Structures. In Proceedings of the 2017 ACM SIGPLAN International Symposium on Memory Management (ISMM 2017). Association for Computing Machinery, New York, NY, USA. 14–24. isbn:9781450350440 https://doi.org/10.1145/3092255.3092274

Digital Library

[36]

Wenyu Zhao, Stephen M. Blackburn, and Kathryn S. McKinley. 2022. Low-Latency, High-Throughput Garbage Collection. In Proceedings of the 43rd ACM SIGPLAN International Conference on Programming Language Design and Implementation (PLDI 2022). Association for Computing Machinery, New York, NY, USA. 76–91. isbn:9781450392655 https://doi.org/10.1145/3519939.3523440

Digital Library

Cited By

Jung JKim JParkinson MKang JDhulipala LSun Y(2024)Concurrent Immediate Reference Counting (Abstract)Proceedings of the 2024 ACM Workshop on Highlights of Parallel Computing10.1145/3670684.3673408(3-4)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3670684.3673408
de Wolff IAnderson DKeller GSeletskiy A(2024)A Fast Wait-Free Solution to Read-Reclaim Races in Reference CountingEuro-Par 2024: Parallel Processing10.1007/978-3-031-69583-4_8(103-118)Online publication date: 26-Aug-2024
https://doi.org/10.1007/978-3-031-69583-4_8

Index Terms

Concurrent Immediate Reference Counting
1. Computing methodologies
  1. Concurrent computing methodologies
    1. Concurrent algorithms
2. Software and its engineering
  1. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Memory management
        Garbage collection

Recommendations

Concurrent Immediate Reference Counting (Abstract)
HOPC'24: Proceedings of the 2024 ACM Workshop on Highlights of Parallel Computing

We present Concurrent Immediate Reference Counting (CIRC), a new automatic concurrent reference counting method for unmanaged languages. CIRC utilizes deferral for high-performance local references, and yet it can immediately reclaim big linked ...
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 ...
Ulterior reference counting: fast garbage collection without a long wait
Special Issue: Proceedings of the OOPSLA '03 conference

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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Proceedings of the ACM on Programming Languages

Proceedings of the ACM on Programming Languages Volume 8, Issue PLDI

June 2024

2198 pages

EISSN:2475-1421

DOI:10.1145/3554317

Editor:
Michael Hicks
Amazon, USA

Issue’s Table of Contents

Copyright © 2024 Owner/Author.

This work is licensed under a Creative Commons Attribution International 4.0 License.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 20 June 2024

Published in PACMPL Volume 8, Issue PLDI

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Badges

Author Tags

Qualifiers

Research-article

Funding Sources

Samsung Research Funding & Incubation Center of Samsung Electronics

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
1,090
Total Downloads

Downloads (Last 12 months)1,090
Downloads (Last 6 weeks)58

Reflects downloads up to 15 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Jung JKim JParkinson MKang JDhulipala LSun Y(2024)Concurrent Immediate Reference Counting (Abstract)Proceedings of the 2024 ACM Workshop on Highlights of Parallel Computing10.1145/3670684.3673408(3-4)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3670684.3673408
de Wolff IAnderson DKeller GSeletskiy A(2024)A Fast Wait-Free Solution to Read-Reclaim Races in Reference CountingEuro-Par 2024: Parallel Processing10.1007/978-3-031-69583-4_8(103-118)Online publication date: 26-Aug-2024
https://doi.org/10.1007/978-3-031-69583-4_8

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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 Article

Figures

Tables

Media

View Issue’s Table of Contents