abstract

Public Access

Hyaline: Fast and Transparent Lock-Free Memory Reclamation

Authors:

Ruslan Nikolaev,

Binoy RavindranAuthors Info & Claims

PODC '19: Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing

Pages 419 - 421

https://doi.org/10.1145/3293611.3331575

Published: 16 July 2019 Publication History

PDF eReader

Abstract

We present a new lock-free safe memory reclamation algorithm, Hyaline, which is fast, scalable, and transparent to the underlying data structures. Hyaline easily handles virtually unbounded number of threads that can be created and deleted dynamically, while retaining O(1) reclamation cost. We also extend Hyaline to avoid situations where stalled threads prevent others from reclaiming newly allocated objects, a common problem with epoch-based reclamation. Our evaluation reveals that Hyaline's throughput is high -- it steadily outperformed other reclamation schemes by >10% in one test and yielded even higher gains in oversubscribed scenarios.

References

[1]

Oana Balmau, Rachid Guerraoui, Maurice Herlihy, and Igor Zablotchi. 2016. Fast and Robust Memory Reclamation for Concurrent Data Structures. In The 28th ACM Symp. on Parallelism in Algorithms and Architectures (SPAA '16). 349--359.

Digital Library

Google Scholar

[2]

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). 261--270.

Digital Library

Google Scholar

[3]

Austin T. Clements, M. Frans Kaashoek, and Nickolai Zeldovich. 2012. Scalable Address Spaces Using RCU Balanced Trees. In The 17th Inter. Confer. on Architectural Support for Programming Languages and OS (ASPLOS XVII). 199--210.

Digital Library

Google Scholar

[4]

Keir Fraser. 2004. Practical Lock-freedom (Ph.D. dissert.) University of Cambridge.

Google Scholar

[5]

Thomas E. Hart, Paul E. McKenney, Angela Demke Brown, and Jonathan Walpole. 2007. Performance of memory reclamation for lockless synchronization. J. Parallel and Distrib. Comput., Vol. 67, 12 (2007), 1270 -- 1285.

Digital Library

Google Scholar

[6]

Maged M. Michael. 2004. Hazard pointers: safe memory reclamation for lock-free objects . IEEE Trans. on Parallel and Distributed Systems, Vol. 15, 6 (June 2004), 491--504.

Digital Library

Google Scholar

[7]

Ruslan Nikolaev and Binoy Ravindran. 2019. Hyaline: Fast and Transparent Lock-Free Memory Reclamation (full paper, arXiv) . http://arxiv.org/abs/1905.07903 .

Google Scholar

[8]

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). 367--369.

Digital Library

Google Scholar

[9]

John D. Valois. 1995. Lock-free Linked Lists Using Compare-and-swap. In The 14th ACM Symposium on Principles of Distributed Computing (PODC '95). 214--222.

Digital Library

Google Scholar

[10]

Haosen Wen, Joseph Izraelevitz, Wentao Cai, H. Alan Beadle, and Michael L. Scott. 2018. Interval-based Memory Reclamation. In Proceedings of the 23rd ACM Symposium on Principles and Practice of Parallel Programming (PPoPP '18). 1--13.

Digital Library

Google Scholar

Cited By

View all

Nikolaev RRavindran B(2024)A Family of Fast and Memory Efficient Lock- and Wait-Free ReclamationProceedings of the ACM on Programming Languages10.1145/36588518:PLDI(2174-2198)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3658851
Kim DBrown TSingh ALee IChabbi MSteuwer M(2024)Are Your Epochs Too Epic? Batch Free Can Be HarmfulProceedings of the 29th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming10.1145/3627535.3638491(30-41)Online publication date: 2-Mar-2024
https://dl.acm.org/doi/10.1145/3627535.3638491
Singh ABrown TMashtizadeh A(2024)Simple, Fast and Widely Applicable Concurrent Memory Reclamation via NeutralizationIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2023.333567135:2(203-220)Online publication date: Feb-2024
https://doi.org/10.1109/TPDS.2023.3335671
Show More Cited By

Index Terms

Hyaline: Fast and Transparent Lock-Free Memory Reclamation
1. Theory of computation
  1. Design and analysis of algorithms
    1. Concurrent algorithms

Recommendations

Snapshot-free, transparent, and robust memory reclamation for lock-free data structures
PLDI 2021: Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation

We present a family of safe memory reclamation schemes, Hyaline, which are fast, scalable, and transparent to the underlying lock-free data structures. Hyaline is based on reference counting -- considered impractical for memory reclamation in the past ...
Automatic memory reclamation for lock-free data structures
OOPSLA '15

Lock-free data-structures are widely employed in practice, yet designing lock-free memory reclamation for them is notoriously difficult. In particular, all known lock-free reclamation schemes are ``manual'' in the sense that the developer has to ...
Automatic memory reclamation for lock-free data structures
OOPSLA 2015: Proceedings of the 2015 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications

Lock-free data-structures are widely employed in practice, yet designing lock-free memory reclamation for them is notoriously difficult. In particular, all known lock-free reclamation schemes are ``manual'' in the sense that the developer has to ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

PODC '19: Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing

July 2019

563 pages

ISBN:9781450362177

DOI:10.1145/3293611

General Chair:
Peter Robinson
City University of Hong Kong
,
Program Chair:
Faith Ellen
University of Toronto, Canada

Permission to make digital or hard copies of part or all 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 third-party components of this work must be honored. For all other uses, contact the Owner/Author.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 16 July 2019

Check for updates

Author Tags

Qualifiers

Abstract

Funding Sources

Air Force Office of Scientific Research

Conference

PODC '19

Sponsor:

PODC '19: ACM Symposium on Principles of Distributed Computing

July 29 - August 2, 2019

Toronto ON, Canada

Acceptance Rates

PODC '19 Paper Acceptance Rate 48 of 173 submissions, 28%;

Overall Acceptance Rate 740 of 2,477 submissions, 30%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

14
Total Citations
View Citations
439
Total Downloads

Downloads (Last 12 months)104
Downloads (Last 6 weeks)26

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Nikolaev RRavindran B(2024)A Family of Fast and Memory Efficient Lock- and Wait-Free ReclamationProceedings of the ACM on Programming Languages10.1145/36588518:PLDI(2174-2198)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3658851
Kim DBrown TSingh ALee IChabbi MSteuwer M(2024)Are Your Epochs Too Epic? Batch Free Can Be HarmfulProceedings of the 29th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming10.1145/3627535.3638491(30-41)Online publication date: 2-Mar-2024
https://dl.acm.org/doi/10.1145/3627535.3638491
Singh ABrown TMashtizadeh A(2024)Simple, Fast and Widely Applicable Concurrent Memory Reclamation via NeutralizationIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2023.333567135:2(203-220)Online publication date: Feb-2024
https://doi.org/10.1109/TPDS.2023.3335671
Singh ABrown TSpear M(2023)Efficient Hardware Primitives for Immediate Memory Reclamation in Optimistic Data Structures2023 IEEE International Parallel and Distributed Processing Symposium (IPDPS)10.1109/IPDPS54959.2023.00021(112-122)Online publication date: May-2023
https://doi.org/10.1109/IPDPS54959.2023.00021
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
Nikolaev RNadeem HStone CRavindran BFalsafi BFerdman MLu SWenisch T(2022)Adelie: continuous address space layout re-randomization for Linux driversProceedings of the 27th ACM International Conference on Architectural Support for Programming Languages and Operating Systems10.1145/3503222.3507779(483-498)Online publication date: 28-Feb-2022
https://dl.acm.org/doi/10.1145/3503222.3507779
Nikolaev RRavindran BAgrawal KLee I(2022)wCQProceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3490148.3538572(307-319)Online publication date: 11-Jul-2022
https://dl.acm.org/doi/10.1145/3490148.3538572
Giersch ONolte J(2022)Fast and Portable Concurrent FIFO Queues With Deterministic Memory ReclamationIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2021.309790133:3(604-616)Online publication date: 1-Mar-2022
https://doi.org/10.1109/TPDS.2021.3097901
Nikolaev RRavindran BFreund SYahav E(2021)Snapshot-free, transparent, and robust memory reclamation for lock-free data structuresProceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation10.1145/3453483.3454090(987-1002)Online publication date: 19-Jun-2021
https://dl.acm.org/doi/10.1145/3453483.3454090
Singh ABrown TMashtizadeh ALee JPetrank E(2021)NBRProceedings of the 26th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming10.1145/3437801.3441625(175-190)Online publication date: 17-Feb-2021
https://dl.acm.org/doi/10.1145/3437801.3441625
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

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

Cited By

Index Terms

Recommendations

Snapshot-free, transparent, and robust memory reclamation for lock-free data structures

Automatic memory reclamation for lock-free data structures

Automatic memory reclamation for lock-free data structures