Write a Blog >>
PPoPP 2021
Sat 27 February - Wed 3 March 2021
Tue 2 Mar 2021 10:00 - 10:15 - Session 4. Memory Management Chair(s): Naama Ben-David

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.

Conference Day
Tue 2 Mar

Displayed time zone: Eastern Time (US & Canada) change

10:00 - 11:00
Session 4. Memory ManagementMain Conference
Chair(s): Naama Ben-DavidVMware Research
10:00
15m
Talk
NBR: Neutralization Based Reclamation
Main Conference
Ajay SinghUniversity of Waterloo, Trevor BrownUniversity of Waterloo, Ali MashtizadehUniversity of Waterloo
Link to publication
10:15
15m
Talk
Efficiently Reclaiming Memory in Concurrent Search Data Structures While Bounding Wasted Memory
Main Conference
Daniel SolomonTel Aviv University, Adam MorrisonTel Aviv University
Link to publication
10:30
15m
Talk
OrcGC: Automatic Lock-Free Memory Reclamation
Main Conference
Andreia CorreiaUniversity of Neuchatel, Switzerland, Pedro RamalheteCisco Systems, Pascal FelberUniversity of Neuchâtel
Link to publication
10:45
15m
Talk
Are Dynamic Memory Managers on GPUs Slow? A Survey and Benchmarks
Main Conference
Martin WinterGraz University of Technology, Mathias PargerGraz University of Technology, Daniel MlakarGraz University of Technology, Markus SteinbergerGraz University of Technology
Link to publication