More Web Proxy on the site http://driver.im/

research-article

FRC: a high-performance concurrent parallel deferred reference counter for C++

Authors:

Benjamin Grossman-PonemonAuthors Info & Claims

ISMM 2018: Proceedings of the 2018 ACM SIGPLAN International Symposium on Memory Management

Pages 14 - 28

https://doi.org/10.1145/3210563.3210569

Published: 18 June 2018 Publication History

Abstract

We present FRC, a high-performance concurrent parallel reference counter for unmanaged languages. It is well known that high-performance garbage collectors help developers write memory-safe, highly concurrent systems and data structures. While C++, C, and other unmanaged languages are used in high-performance applications, adding concurrent memory management to these languages has proven to be difficult. Unmanaged languages like C++ use pointers instead of references, and have uncooperative mutators which do not pause easily at a safe point. Thus, scanning mutator stack root references is challenging.

FRC only defers decrements and does not require mutator threads to pause during collection. By deferring only decrements, FRC avoids much of the synchronization overhead of a fully-deferred implementation. Root references are scanned without interrupting the mutator by publishing these references to a thread-local array. FRC's performance can exceed that of the C++ standard library's shared pointer by orders of magnitude. FRC's thread-safety guarantees and low synchronization overhead enable significant throughput gains for concurrently-readable shared data structures.

We describe the components of FRC, including our static tree router data structure: a novel barrier which improves the scalability of parallel collection workers. FRC's performance is evaluated on several concurrent data structures. We release FRC and our tests as open-source code and expect FRC will be useful for many concurrent C++ software systems.

References

[1]

Nikolas Askitis. 2012. Cache-conscious String Data Structures, Sorting and Algorithms: theory and practice. http://web.archive.org/web/20120206015921/http://www.naskitis.com/

[2]

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). ACM, New York, NY, USA, 92-103.

Digital Library

[3]

Stephen M. Blackburn and Kathryn S. McKinley. 2003. Ulterior Reference Counting: Fast Garbage Collection Without a Long Wait. In Proceedings of the 18th Annual ACM SIGPLAN Conference on Object-oriented Programing, Systems, Languages, and Applications (OOPSLA '03). ACM, New York, NY, USA, 344-358.

Digital Library

[4]

Stephen M. Blackburn and Kathryn S. McKinley. 2008. Immix: A Mark-Region Garbage Collector with Space Efficiency, Fast Collection, and Mutator Performance. In ACM Conference on Programming Language Design and Implementation (PLDI '08). ACM, 22-32.

Digital Library

[5]

Hans-J. Boehm. 2002. Bounding Space Usage of Conservative Garbage Collectors. In Proceedings of the 29th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL '02). ACM, New York, NY, USA, 93-100.

Digital Library

[6]

Hans-Juergen Boehm. 2004. The Space Cost of Lazy Reference Counting. In Proceedings of the 31st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL '04). ACM, New York, NY, USA, 210-219.

Digital Library

[7]

Hans-Juergen Boehm and Mark Weiser. 1988. Garbage Collection in an Uncooperative Environment. Softw. Pract. Exper. 18, 9 (Sept. 1988), 807-820.

Digital Library

[8]

George E. Collins. 1960. A Method for Overlapping and Erasure of Lists. Commun. ACM 3, 12 (Dec. 1960), 655-657.

Digital Library

[9]

David Detlefs, Christine Flood, Steve Heller, and Tony Printezis. 2004. Garbage-first Garbage Collection. In Proceedings of the 4th International Symposium on Memory Management (ISMM '04). ACM, New York, NY, USA, 37-48.

Digital Library

[10]

L. Peter Deutsch and Daniel G. Bobrow. 1976. An Efficient, Incremental, Automatic Garbage Collector. Commun. ACM 19, 9 (Sept. 1976), 522-526.

Digital Library

[11]

Daniel Frampton. 2010. Garbage Collection and the Case for High-level Low-level Programming. Ph.D. Dissertation. Australian National University.

[12]

Ivan Jibaja, Stephen M. Blackburn, Mohammad R. Haghighat, and Kathryn S. McKinley. 2011. Deferred Gratification: Engineering for High Performance Garbage Collection from the Get Go. In Proceedings of the 2011 ACM SIGPLAN Workshop on Memory Systems Performance and Correctness (MSPC '11). ACM, New York, NY, USA, 58-65.

Digital Library

[13]

Ryan Johnson, Ippokratis Pandis, Nikos Hardavellas, Anastasia Ailamaki, and Babak Falsafi. 2009. Shore-MT: A Scalable Storage Manager for the Multicore Era. In Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology (EDBT '09). ACM, New York, NY, USA, 24-35.

Digital Library

[14]

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). ACM, New York, NY, USA, 367-380.

Digital Library

[15]

John McCarthy. 1960. Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I. Commun. ACM 3, 4 (April 1960), 184-195.

Digital Library

[16]

Maged M. Michael. 2004. Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects. IEEE Trans. Parallel Distrib. Syst. 15, 6 (June 2004), 491-504.

Digital Library

[17]

Jon Rafkind, Adam Wick, John Regehr, and Matthew Flatt. 2009. Precise Garbage Collection for C. In Proceedings of the 2009 International Symposium on Memory Management (ISMM '09). ACM, New York, NY, USA, 39-48.

Digital Library

[18]

Rifat Shahriyar, Stephen M. Blackburn, and Daniel Frampton. 2012. Down for the Count? Getting Reference Counting Back in the Ring. In Proceedings of the 2012 International Symposium on Memory Management (ISMM '12). ACM, New York, NY, USA, 73-84.

Digital Library

[19]

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). ACM, New York, NY, USA, 121- 139.

Digital Library

[20]

Rifat Shahriyar, Stephen Michael Blackburn, Xi Yang, and Kathryn S. McKinley. 2013. Taking off the Gloves with Reference Counting Immix. In Proceedings of the 2013 ACM SIGPLAN International Conference on Object Oriented Programming Systems Languages & Applications (OOPSLA '13). ACM, New York, NY, USA, 93-110.

Digital Library

[21]

Paul R. Wilson. 1992. Uniprocessor Garbage Collection Techniques. In Proceedings of the International Workshop on Memory Management (IWMM '92). Springer-Verlag, London, UK, UK, 1-42. http://dl.acm.org/citation.cfm?id=645648.664824

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
Jung JKim JParkinson MKang J(2024)Concurrent Immediate Reference CountingProceedings of the ACM on Programming Languages10.1145/36563838:PLDI(151-174)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656383
BLINKOV YSHCHETININ E(2023)USING DYNAMIC MEMORY REALLOCATION IN GINVПрограммирование10.31857/S0132347423020061(21-26)Online publication date: 1-Jul-2023
https://doi.org/10.31857/S0132347423020061
Show More Cited By

Index Terms

FRC: a high-performance concurrent parallel deferred reference counter for C++
1. Software and its engineering
  1. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Memory management
        Garbage collection

Recommendations

Low-latency, high-throughput garbage collection
PLDI 2022: Proceedings of the 43rd ACM SIGPLAN International Conference on Programming Language Design and Implementation

To achieve short pauses, state-of-the-art concurrent copying collectors such as C4, Shenandoah, and ZGC use substantially more CPU cycles and memory than simpler collectors. They suffer from design limitations: i) concurrent copying with inherently ...
FRC: a high-performance concurrent parallel deferred reference counter for C++
ISMM '18

We present FRC, a high-performance concurrent parallel reference counter for unmanaged languages. It is well known that high-performance garbage collectors help developers write memory-safe, highly concurrent systems and data structures. While C++, C, ...
An efficient on-the-fly cycle collection

A reference-counting garbage collector cannot reclaim unreachable cyclic structures of objects. Therefore, reference-counting collectors either use a backup tracing collector infrequently, or employ a cycle collector to reclaim cyclic structures. We ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ISMM 2018: Proceedings of the 2018 ACM SIGPLAN International Symposium on Memory Management

June 2018

119 pages

ISBN:9781450358019

DOI:10.1145/3210563

General Chair:
Hannes Payer
Google, Germany
,
Program Chair:
Jennifer B. Sartor
Vrije Universiteit Brussel, Belgium

ACM SIGPLAN Notices Volume 53, Issue 5
ISMM '18
May 2018
119 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/3299706
Editor:
Matthew Fluet
Rodchester Institude of Technology
Issue’s Table of Contents

Copyright © 2018 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: 18 June 2018

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ISMM '18

Sponsor:

SIGPLAN

ISMM '18: The International Symposium on Memory Management 2018

June 18, 2018

PA, Philadelphia, USA

Acceptance Rates

Overall Acceptance Rate 72 of 156 submissions, 46%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
565
Total Downloads

Downloads (Last 12 months)72
Downloads (Last 6 weeks)7

Reflects downloads up to 14 Dec 2024

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
Jung JKim JParkinson MKang J(2024)Concurrent Immediate Reference CountingProceedings of the ACM on Programming Languages10.1145/36563838:PLDI(151-174)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656383
BLINKOV YSHCHETININ E(2023)USING DYNAMIC MEMORY REALLOCATION IN GINVПрограммирование10.31857/S0132347423020061(21-26)Online publication date: 1-Jul-2023
https://doi.org/10.31857/S0132347423020061
Anderson DBlelloch GWei YDhulipala LSun Y(2023)Smarter Atomic Smart Pointers: Safe and Efficient Concurrent Memory Management (Abstract)Proceedings of the 2023 ACM Workshop on Highlights of Parallel Computing10.1145/3597635.3598027(9-10)Online publication date: 18-Jul-2023
https://dl.acm.org/doi/10.1145/3597635.3598027
Blinkov YShchetinin E(2023)Using Dynamic Memory Reallocation in GInvProgramming and Computer Software10.1134/S036176882302005649:4(355-359)Online publication date: 28-Jul-2023
https://doi.org/10.1134/S0361768823020056
Wang K(2023)Communication Combination Technology and Routing Protocol Algorithm Design Based on Artificial Neural Networks2023 International Conference on Power, Electrical Engineering, Electronics and Control (PEEEC)10.1109/PEEEC60561.2023.00124(608-613)Online publication date: 25-Sep-2023
https://doi.org/10.1109/PEEEC60561.2023.00124
Yang XLiu MMao KWu W(2023)Research on Switching Structure of High-Performance Higher-Order Router Based on Grey Clustering Algorithm2023 International Conference on Networking, Informatics and Computing (ICNETIC)10.1109/ICNETIC59568.2023.00082(365-369)Online publication date: May-2023
https://doi.org/10.1109/ICNETIC59568.2023.00082
Anderson DBlelloch GWei YJhala RDillig I(2022)Turning manual concurrent memory reclamation into automatic reference countingProceedings of the 43rd ACM SIGPLAN International Conference on Programming Language Design and Implementation10.1145/3519939.3523730(61-75)Online publication date: 9-Jun-2022
https://dl.acm.org/doi/10.1145/3519939.3523730

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