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

Dynamic lock-free data structures require a memory reclamation scheme with a similar progress. Until today, lock-free schemes are applied to data structures on a case-by-case basis, often with algorithm modifications to the data structure.

In this paper we introduce two new lock-free reclamation schemes, one manual and the other automatic with user annotated types. The manual reclamation scheme, named pass-the-pointer (PTP), has lock-free progress and a bound on the number of unreclaimed objects that is linear with the number of threads.

The automatic lock-free memory reclamation scheme, which we named OrcGC, uses PTP and object reference counting to automatically detect when to protect and when to de-allocate an object. OrcGC has a linear bound on memory usage and can be used with any allocator. We propose a new methodology that utilizes OrcGC to provide lock-free memory reclamation to a data structure.

We conducted a performance evaluation on two machines, an Intel and an AMD, applying PTP and OrcGC to several lock-free data structures, providing lock-free memory reclamation where before there was none. On the Intel machine we saw no significant performance impact, while on AMD we observed a worst-case performance drop below 50%.

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