Safe memory reclamation techniques that utilize per read reservations, such as hazard pointers and hazard eras, often cause significant overhead in traversals of linked concurrent data structures. This is primarily due to the need to announce a reservation, and fence to make it globally visible (and enforce appropriate ordering), before each read. In real world read-intensive workloads, this overhead is amplified because, even if relatively little memory reclamation actually occurs, the full overhead of reserving records before use is still incurred while traversing data structures.

In this paper, we propose a novel memory reclamation technique by combining POSIX signals and delayed reclamation, introducing a publish-on-ping approach. This method eliminates the need to make reservations globally visible before use. Instead, threads privately track which records they are accessing, and share this information on demand with threads that intend to reclaim memory. The approach can serve as a drop-in replacement for hazard pointers and hazard eras. Furthermore, the capability to retain reservations during traversals in data structure operations and publish them on demand facilitates the construction of a variant of hazard pointers (EpochPOP). This variant uses epochs to approach the performance of epoch-based reclamation in the common case where threads are not frequently delayed (while retaining the robustness of hazard pointers).

Our publish-on-ping implementations based on hazard pointers and hazard eras, when applied to various data structures, exhibit significant performance improvements. The improvements across various workloads and data structures range from 1.2X to 4X over the original HP, up to 20% compared to a heavily optimized HP implementation similar to the one in the Folly open-source library, and up to 3X faster than hazard eras. EpochPOP delivers performance similar to epoch-based reclamation while providing stronger guarantees.

Mon 3 Mar

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

14:00 - 15:20
Session 3: Concurrent Data Structures and Synchronization I (Session Chair: Yuanhao Wei)Main Conference at Acacia D
14:00
20m
Talk
Reciprocating Locks
Main Conference
Dave Dice Oracle Labs, Alex Kogan Oracle Labs, USA
14:20
20m
Talk
Aggregating Funnels for Faster Fetch&Add and Queues
Main Conference
Younghun Roh MIT, Yuanhao Wei University of British Columbia, Eric Ruppert York University, Panagiota Fatourou FORTH ICS and University of Crete, Greece, Siddhartha Jayanti Google Research, Julian Shun MIT
14:40
20m
Talk
Fairer and More Scalable Reader-Writer Locks by Optimizing Queue Management
Main Conference
Takashi Hoshino Cybozu Labs, Inc., Kenjiro Taura The University of Tokyo
15:00
20m
Talk
Publish on Ping: A Better Way to Publish Reservations in Memory Reclamation for Concurrent Data StructuresDistinguished Paper Award
Main Conference
Ajay Singh FORTH ICS and University of Waterloo, Trevor Brown University of Toronto