research-article

Efficiently reclaiming memory in concurrent search data structures while bounding wasted memory

Authors:

Daniel Solomon,

Adam MorrisonAuthors Info & Claims

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

Pages 191 - 204

https://doi.org/10.1145/3437801.3441582

Published: 17 February 2021 Publication History

Abstract

Nonblocking data structures face a safe memory reclamation (SMR) problem. In these algorithms, a node removed from the data structure cannot be reclaimed (freed) immediately, as other threads may be about to access it. The goal of an SMR scheme is to minimize the number of removed nodes that cannot be reclaimed---called wasted memory---while imposing low run-time overhead. It is also desirable for an SMR scheme to be self-contained and not require specific OS features.

No existing self-contained SMR scheme can guarantee a predetermined bound on wasted memory without imposing significant run-time overhead. In this paper, we introduce margin pointers (MP), the first nonblocking, self-contained SMR scheme featuring both predetermined bounded wasted memory and low run-time overhead. MP targets search data structures, such as binary trees and skip lists, which are important SMR clients and also victims of its high overhead. MP's novelty lies in its protecting logical subsets of the data structure from being reclaimed, as opposed to previous work, which protects physical locations (explicit nodes).

References

[1]

Dan Alistarh, William Leiserson, Alex Matveev, and Nir Shavit. 2015. ThreadScan: Automatic and Scalable Memory Reclamation. In SPAA '15.

Digital Library

[2]

Dan Alistarh, William Leiserson, Alex Matveev, and Nir Shavit. 2017. Forkscan: Conservative Memory Reclamation for Modern Operating Systems. In EuroSys '17.

Digital Library

[3]

Oana Balmau, Rachid Guerraoui, Maurice Herlihy, and Igor Zablotchi. 2016. Fast and Robust Memory Reclamation for Concurrent Data Structures. In SPAA '16.

[4]

Anastasia Braginsky, Alex Kogan, and Erez Petrank. 2013. Drop the Anchor: Lightweight Memory Management for Non-blocking Data Structures. In SPAA '13.

Digital Library

[5]

Trevor Brown, Faith Ellen, and Eric Ruppert. 2014. A General Technique for Non-Blocking Trees. In PPoPP '14.

Digital Library

[6]

Trevor Alexander Brown. 2015. Reclaiming Memory for Lock-Free Data Structures: There Has to Be a Better Way. In PODC '15.

Digital Library

[7]

Nachshon Cohen. 2018. Every Data Structure Deserves Lock-free Memory Reclamation. Proceedings of the ACM on Programming Languages 2, OOPSLA, Article 143 (2018).

Digital Library

[8]

Nachshon Cohen and Erez Petrank. 2015. Automatic Memory Reclamation for Lock-free Data Structures (OOPSLA 2015).

[9]

Nachshon Cohen and Erez Petrank. 2015. Efficient Memory Management for Lock-Free Data Structures with Optimistic Access. In SPAA '15.

[10]

Tudor David, Rachid Guerraoui, and Vasileios Trigonakis. 2015. Asynchronized Concurrency: The Secret to Scaling Concurrent Search Data Structures. In ASPLOS '15.

Digital Library

[11]

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

[12]

Dave Dice, Maurice Herlihy, and Alex Kogan. 2016. Fast Non-Intrusive Memory Reclamation for Highly-Concurrent Data Structures. In ISMM '16.

[13]

Faith Ellen, Panagiota Fatourou, Eric Ruppert, and Franck van Breugel. 2010. Non-Blocking Binary Search Trees. In PODC '10.

[14]

Jason Evans. 2006. A Scalable Concurrent malloc(3) Implementation for FreeBSD.

[15]

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

[16]

Timothy L. Harris. 2001. A Pragmatic Implementation of Non-blocking Linked-Lists. In DISC '01.

Digital Library

[17]

Maurice Herlihy. 1991. Wait-free synchronization. TOPLAS 13 (January 1991), 26 pages. Issue 1.

[18]

Maurice Herlihy, Victor Luchangco, Paul Martin, and Mark Moir. 2002. Dynamic-Sized Lock-Free Data Structures. In PODC '02.

Digital Library

[19]

Shane V. Howley and Jeremy Jones. 2012. A Non-Blocking Internal Binary Search Tree. In SPAA '12.

[20]

Paul E. McKenney and John D. Slingwine. 1998. Read-copy update: Using execution history to solve concurrency problems. In PDCS '98.

[21]

Maged M. Michael. 2002. High Performance Dynamic Lock-Free Hash Tables and List-Based Sets. In SPAA '02.

[22]

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

Digital Library

[23]

Maged M. Michael, Michael Wong, Paul McKenney, Arthur O'Dwyer, and David Hollman. 2017. Hazard Pointers: Safe Resource Reclamation for Optimistic Concurrency. Technical Report P0233R3. C++ SG14 Working Group.

[24]

Aravind Natarajan and Neeraj Mittal. 2014. Fast Concurrent Lock-free Binary Search Trees. In PPoPP '14.

[25]

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. Proceedings of the ACM on Programming Languages (2017).

Digital Library

[26]

Arunmoezhi Ramachandran and Neeraj Mittal. 2015. A Fast Lock-Free Internal Binary Search Tree. In ICDCN '15.

Digital Library

[27]

Pedro Ramalhete and Andreia Correia. 2017. Brief Announcement: Hazard Eras - Non-Blocking Memory Reclamation. In SPAA '17.

Digital Library

[28]

Daniel Solomon. 2020. Efficiently Reclaiming Memory in Concurrent Search Data Structures While Bounding Wasted Memory. Master's thesis. Tel Aviv University.

[29]

Haosen Wen, Joseph Izraelevitz, Wentao Cai, H. Alan Beadle, and Michael L. Scott. 2018. Interval-based Memory Reclamation. In PPoPP '18.

Cited By

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

Index Terms

Efficiently reclaiming memory in concurrent search data structures while bounding wasted memory
1. Theory of computation
  1. Design and analysis of algorithms
    1. Parallel algorithms
      1. Shared memory algorithms

Recommendations

Reclaiming Memory for Lock-Free Data Structures: There has to be a Better Way
PODC '15: Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing

Memory reclamation for sequential or lock-based data structures is typically easy. However, memory reclamation for lock-free data structures is a significant challenge. Automatic techniques such as garbage collection are inefficient or use locks, and ...
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 ...
Fast non-intrusive memory reclamation for highly-concurrent data structures
ISMM '16

Current memory reclamation mechanisms for highly-concurrent data structures present an awkward trade-off. Techniques such as epoch-based reclamation perform well when all threads are running on dedicated processors, but the delay or failure of a single ...

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

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

Author Tags

Qualifiers

Research-article

Funding Sources

Israel Science Foundation

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

1
Total Citations
View Citations
289
Total Downloads

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

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

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

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