research-article

NBR: neutralization based reclamation

Authors:

Ali MashtizadehAuthors Info & Claims

PPoPP '21: Proceedings of the 26th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming

Pages 175 - 190

https://doi.org/10.1145/3437801.3441625

Published: 17 February 2021 Publication History

Abstract

Safe memory reclamation (SMR) algorithms suffer from a trade-off between bounding unreclaimed memory and the speed of reclamation. Hazard pointer (HP) based algorithms bound unreclaimed memory at all times, but tend to be slower than other approaches. Epoch based reclamation (EBR) algorithms are faster, but do not bound memory reclamation. Other algorithms follow hybrid approaches, requiring special compiler or hardware support, changes to record layouts, and/or extensive code changes. Not all SMR algorithms can be used to reclaim memory for all data structures.

We propose a new neutralization based reclamation (NBR) algorithm that is often faster than the best known EBR algorithms and achieves bounded unreclaimed memory. It is non-blocking when used with a non-blocking operating system (OS) kernel, and only requires atomic read, write and CAS. NBR is straightforward to use with many different data structures, and in most cases, requires similar reasoning and programmer effort to two-phased locking. NBR is implemented using OS signals and a lightweight handshaking mechanism between participating threads to determine when it is safe to reclaim a record. Experiments on a lock-based binary search tree and a lazy linked list show that NBR significantly outperforms many state of the art reclamation algorithms. In the tree, NBR is faster than next best algorithm, DEBRA, by up to 38% and HP by up to 17%. And, in the list, NBR is 15% and 243% faster than DEBRA and HP, respectively.

References

[1]

Yehuda Afek, Haim Kaplan, Boris Korenfeld, Adam Morrison, and Robert E Tarjan. 2014. The CB tree: a practical concurrent self-adjusting search tree. Distributed computing 27, 6 (2014), 393--417.

[2]

Dan Alistarh, Patrick Eugster, Maurice Herlihy, Alexander Matveev, and Nir Shavit. 2014. Stacktrack: An automated transactional approach to concurrent memory reclamation. In Proceedings of the Ninth European Conference on Computer Systems. 1--14.

Digital Library

[3]

Dan Alistarh, William Leiserson, Alexander Matveev, and Nir Shavit. 2017. Forkscan: Conservative memory reclamation for modern operating systems. In Proceedings of the Twelfth European Conference on Computer Systems. 483--498.

Digital Library

[4]

Dan Alistarh, William Leiserson, Alexander Matveev, and Nir Shavit. 2018. Threadscan: Automatic and scalable memory reclamation. ACM Transactions on Parallel Computing (TOPC) 4, 4 (2018), 1--18.

Digital Library

[5]

Oana Balmau, Rachid Guerraoui, Maurice Herlihy, and Igor Zablotchi. 2016. Fast and robust memory reclamation for concurrent data structures. In Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures. 349--359.

Digital Library

[6]

Guy E Blelloch and Yuanhao Wei. 2020. Concurrent Reference Counting and Resource Management in Wait-free Constant Time. arXiv preprint arXiv:2002.07053 (2020).

[7]

Anastasia Braginsky, Alex Kogan, and Erez Petrank. 2013. Drop the anchor: lightweight memory management for non-blocking data structures. In Proceedings of the twenty-fifth annual ACM symposium on Parallelism in algorithms and architectures. 33--42.

Digital Library

[8]

Nathan G Bronson, Jared Casper, Hassan Chafi, and Kunle Olukotun. 2010. A practical concurrent binary search tree. ACM Sigplan Notices 45, 5 (2010), 257--268.

Digital Library

[9]

Trevor Brown. 2017. Techniques for Constructing Efficient Lock-free Data Structures. arXiv preprint arXiv:1712.05406 (2017).

[10]

Trevor Brown, Faith Ellen, and Eric Ruppert. 2014. A General Technique for Non-blocking Trees. In Proceedings of the 19th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP '14). 329--342. Full version available from http://tbrown.pro.

Digital Library

[11]

Trevor Brown, Faith Ellen, and Eric Ruppert. 2014. A general technique for non-blocking trees. In Proceedings of the 19th ACM SIGPLAN symposium on Principles and practice of parallel programming. 329--342.

Digital Library

[12]

Trevor Brown, Aleksandar Prokopec, and Dan Alistarh. 2020. Non-blocking interpolation search trees with doubly-logarithmic running time. In Proceedings of the 25th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. 276--291.

Digital Library

[13]

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

Digital Library

[14]

Nachshon Cohen. 2018. Every data structure deserves lock-free memory reclamation. Proceedings of the ACM on Programming Languages 2, OOPSLA (2018), 1--24.

Digital Library

[15]

Nachshon Cohen and Erez Petrank. 2015. Automatic memory reclamation for lock-free data structures. ACM SIGPLAN Notices 50, 10 (2015), 260--279.

Digital Library

[16]

Nachshon Cohen and Erez Petrank. 2015. Efficient memory management for lock-free data structures with optimistic access. In Proceedings of the 27th ACM symposium on Parallelism in Algorithms and Architectures. 254--263.

Digital Library

[17]

Tudor David, Rachid Guerraoui, and Vasileios Trigonakis. 2015. Asynchronized concurrency: The secret to scaling concurrent search data structures. ACM SIGARCH Computer Architecture News 43, 1 (2015), 631--644.

Digital Library

[18]

David L Detlefs, Paul A Martin, Mark Moir, and Guy L Steele Jr. 2002. Lock-free reference counting. Distributed Computing 15, 4 (2002), 255--271.

[19]

Dave Dice, Maurice Herlihy, and Alex Kogan. 2016. Fast non-intrusive memory reclamation for highly-concurrent data structures. In Proceedings of the 2016 ACM SIGPLAN International Symposium on Memory Management. 36--45.

Digital Library

[20]

Dana Drachsler, Martin Vechev, and Eran Yahav. 2014. Practical concurrent binary search trees via logical ordering. In Proceedings of the 19th ACM SIGPLAN symposium on Principles and practice of parallel programming. 343--356.

Digital Library

[21]

Aleksandar Dragojević, Maurice Herlihy, Yossi Lev, and Mark Moir. 2011. On the power of hardware transactional memory to simplify memory management. In Proceedings of the 30th annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing. 99--108.

Digital Library

[22]

Faith Ellen, Panagiota Fatourou, Joanna Helga, and Eric Ruppert. 2014. The amortized complexity of non-blocking binary search trees. In Proceedings of the 2014 ACM symposium on Principles of distributed computing. 332--340.

Digital Library

[23]

Faith Ellen, Panagiota Fatourou, Eric Ruppert, and Franck van Breugel. 2010. Non-blocking binary search trees. In Proceedings of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing. 131--140.

Digital Library

[24]

Jason Evans. 2006. A scalable concurrent malloc (3) implementation for FreeBSD. In Proc. of the bsdcan conference, ottawa, canada.

[25]

Panagiota Fatourou, Elias Papavasileiou, and Eric Ruppert. 2019. Persistent non-blocking binary search trees supporting wait-free range queries. In The 31st ACM Symposium on Parallelism in Algorithms and Architectures. 275--286.

Digital Library

[26]

Keir Fraser. 2004. Practical lock-freedom. Technical Report. University of Cambridge, Computer Laboratory.

[27]

Anders Gidenstam, Marina Papatriantafilou, Håkan Sundell, and Philippas Tsigas. 2008. Efficient and reliable lock-free memory reclamation based on reference counting. IEEE Transactions on Parallel and Distributed Systems 20, 8 (2008), 1173--1187.

Digital Library

[28]

Timothy L Harris. 2001. A pragmatic implementation of non-blocking linked-lists. In International Symposium on Distributed Computing. Springer, 300--314.

Digital Library

[29]

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. 67, 12 (2007), 1270--1285.

Digital Library

[30]

Meng He and Mengdu Li. 2017. Deletion without rebalancing in non-blocking binary search trees. In 20th International Conference on Principles of Distributed Systems (OPODIS 2016). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.

[31]

Steve Heller, Maurice Herlihy, Victor Luchangco, Mark Moir, William N Scherer, and Nir Shavit. 2005. A lazy concurrent list-based set algorithm. In International Conference On Principles Of Distributed Systems. Springer, 3--16.

[32]

Maurice Herlihy, Victor Luchangco, Paul Martin, and Mark Moir. 2005. Nonblocking memory management support for dynamic-sized data structures. ACM Transactions on Computer Systems (TOCS) 23, 2 (2005), 146--196.

Digital Library

[33]

Shane V Howley and Jeremy Jones. 2012. A non-blocking internal binary search tree. In Proceedings of the twenty-fourth annual ACM symposium on Parallelism in algorithms and architectures. 161--171.

Digital Library

[34]

Paul E McKenney and John D Slingwine. 1998. Read-copy update: Using execution history to solve concurrency problems. In Parallel and Distributed Computing and Systems, Vol. 509518.

[35]

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

Digital Library

[36]

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

Digital Library

[37]

Ruslan Nikolaev and Binoy Ravindran. 2019. Hyaline: fast and transparent lock-free memory reclamation. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing. 419--421.

Digital Library

[38]

Ruslan Nikolaev and Binoy Ravindran. 2020. Universal wait-free memory reclamation. In Proceedings of the 25th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. 130--143.

Digital Library

[39]

Aleksandar Prokopec, Nathan Grasso Bronson, Phil Bagwell, and Martin Odersky. 2012. Concurrent tries with efficient non-blocking snapshots. In Proceedings of the 17th ACM SIGPLAN symposium on Principles and Practice of Parallel Programming. 151--160.

Digital Library

[40]

Arunmoezhi Ramachandran and Neeraj Mittal. 2015. CASTLE: fast concurrent internal binary search tree using edge-based locking. ACM SIGPLAN Notices 50, 8 (2015), 281--282.

Digital Library

[41]

Arunmoezhi Ramachandran and Neeraj Mittal. 2015. A fast lock-free internal binary search tree. In Proceedings of the 2015 International Conference on Distributed Computing and Networking. 1--10.

Digital Library

[42]

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

Digital Library

[43]

Niloufar Shafiei. 2013. Non-blocking Patricia tries with replace operations. In 2013 IEEE 33rd International Conference on Distributed Computing Systems. IEEE, 216--225.

Digital Library

[44]

Ajay Singh, Trevor Brown, and Ali Mashtizadeh. 2020. NBR: Neutralization Based Reclamation. arXiv:2012.14542 [cs.DC]

[45]

Shahar Timnat and Erez Petrank. 2014. A practical wait-free simulation for lock-free data structures. ACM SIGPLAN Notices 49, 8 (2014), 357--368.

Digital Library

[46]

Haosen Wen, Joseph Izraelevitz, Wentao Cai, H Alan Beadle, and Michael L Scott. 2018. Interval-based memory reclamation. ACM SIGPLAN Notices 53, 1 (2018), 1--13.

Digital Library

Cited By

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
Kim JJung JKang JAgrawal KPetrank E(2024)Expediting Hazard Pointers with Bounded RCU Critical SectionsProceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3626183.3659941(1-13)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3626183.3659941
Show More Cited By

Index Terms

NBR: neutralization based reclamation
1. Computing methodologies
  1. Concurrent computing methodologies

Recommendations

VBR: Version Based Reclamation
SPAA '21: Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures

Safe lock-free memory reclamation is a difficult problem. Existing solutions follow three basic methods: epoch based reclamation, hazard pointers, and optimistic reclamation. Epoch-based methods are fast, but do not guarantee lock-freedom. Hazard ...
A marriage of pointer- and epoch-based reclamation
PLDI 2020: Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation

All pointer-based nonblocking concurrent data structures should deal with the problem of safe memory reclamation: before reclaiming a memory block, a thread should ensure no other threads hold a local pointer to the block that may later be dereferenced. ...
The ERA Theorem for Safe Memory Reclamation
PPoPP '23: Proceedings of the 28th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming

Safe memory reclamation (SMR) schemes for concurrent data structures offer trade-offs between three desirable properties: ease of integration, robustness, and applicability. In this paper we define SMR and these three properties, and we present the ERA ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PPoPP '21: Proceedings of the 26th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming

February 2021

507 pages

ISBN:9781450382946

DOI:10.1145/3437801

General Chair:
Jaejin Lee
Seoul National University, South Korea
,
Program Chair:
Erez Petrank
Technion, Israel

Copyright © 2021 Owner/Author.

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

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 17 February 2021

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Badges

Author Tags

Qualifiers

Research-article

Funding Sources

Natural Sciences and Engineering Research Council of Canada

Conference

PPoPP '21

Sponsor:

PPoPP '21: 26th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming

February 27, 2021

Virtual Event, Republic of Korea

Acceptance Rates

PPoPP '21 Paper Acceptance Rate 31 of 150 submissions, 21%;

Overall Acceptance Rate 230 of 1,014 submissions, 23%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

14
Total Citations
View Citations
410
Total Downloads

Downloads (Last 12 months)76
Downloads (Last 6 weeks)5

Reflects downloads up to 22 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

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
Kim JJung JKang JAgrawal KPetrank E(2024)Expediting Hazard Pointers with Bounded RCU Critical SectionsProceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3626183.3659941(1-13)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3626183.3659941
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
Jung JLee JChoi JKim JPark SKang J(2023)Modular Verification of Safe Memory Reclamation in Concurrent Separation LogicProceedings of the ACM on Programming Languages10.1145/36228277:OOPSLA2(828-856)Online publication date: 16-Oct-2023
https://dl.acm.org/doi/10.1145/3622827
Sheffi GPetrank EOshman RNolin AHalldorsson MBalliu A(2023)The ERA Theorem for Safe Memory ReclamationProceedings of the 2023 ACM Symposium on Principles of Distributed Computing10.1145/3583668.3594564(102-112)Online publication date: 19-Jun-2023
https://dl.acm.org/doi/10.1145/3583668.3594564
Wei YBlelloch GFatourou PRuppert EDehnavi MKulkarni MKrishnamoorthy S(2023)Practically and Theoretically Efficient Garbage Collection for MultiversioningProceedings of the 28th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming10.1145/3572848.3577508(66-78)Online publication date: 25-Feb-2023
https://dl.acm.org/doi/10.1145/3572848.3577508
Sheffi GPetrank EDehnavi MKulkarni MKrishnamoorthy S(2023)The ERA Theorem for Safe Memory ReclamationProceedings of the 28th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming10.1145/3572848.3577491(435-437)Online publication date: 25-Feb-2023
https://dl.acm.org/doi/10.1145/3572848.3577491
Jung JLee JKim JKang JAgrawal KShun J(2023)Applying Hazard Pointers to More Concurrent Data StructuresProceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3558481.3591102(213-226)Online publication date: 17-Jun-2023
https://dl.acm.org/doi/10.1145/3558481.3591102
Sheng YHassan ASpear M(2023)Separating Mechanism from Policy in STM2023 32nd International Conference on Parallel Architectures and Compilation Techniques (PACT)10.1109/PACT58117.2023.00031(279-296)Online publication date: 21-Oct-2023
https://doi.org/10.1109/PACT58117.2023.00031
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 Table of Contents