PPoPP 2024
Sat 2 - Wed 6 March 2024 Edinburgh, United Kingdom
Mon 4 Mar 2024 10:40 - 11:00 at Moorfoot - Synchronization and Concurrency Control 1 Chair(s): Michael Scott

Epoch based memory reclamation (EBR) is one of the most popular techniques for reclaiming memory in lock-free and optimistic locking data structures, due to its ease of use and good performance in practice. However, EBR is known to be sensitive to thread delays, which can result in performance degradation. Moreover, the exact mechanism for this performance degradation is not well understood. This paper illustrates this performance degradation in a popular data structure benchmark, and does a deep dive to uncover its root cause—a subtle interaction between EBR and state-of-the-art memory allocators. In essence, modern allocators attempt to reduce the overhead of freeing by maintaining bounded thread caches of objects for local reuse, actually freeing them (a very high latency operation) only when thread caches become too large. EBR immediately bypasses these mechanisms whenever a particularly large batch of objects is freed, substantially increasing overheads and latencies. Beyond EBR, many memory reclamation algorithms, and data structures, that reclaim objects in large batches suffer similar deleterious interactions with popular allocators. We propose a simple algorithmic fix for such algorithms to amortize the freeing of large object batches over time, and apply this technique to ten existing memory reclamation algorithms, observing performance improvements for nine out of ten, and over 50% improvement for six out of ten in experiments on a high performance lock-free ABtree. We also present an extremely simple token passing variant of EBR and show that, with our fix, it performs 1.5-2.6× faster than the fastest known memory reclamation algorithm, and 1.2-1.5× faster than not reclaiming at all, on a 192 thread four socket Intel system.

Mon 4 Mar

Displayed time zone: London change

10:00 - 11:00
Synchronization and Concurrency Control 1Main Conference at Moorfoot
Chair(s): Michael Scott University of Rochester
10:00
20m
Talk
Scaling Up Transactions with Slower Clocks
Main Conference
Pedro Ramalhete Cisco Systems, Andreia Correia University of Neuchâtel
Link to publication DOI
10:20
20m
Talk
Locks as a Resource: Fairly Scheduling Lock Occupation with CFL
Main Conference
Jonggyu Park University of Washington, Young Ik Eom Dept. of Electrical and Computer Engineering / College of Computing and Informatics, Sungkyunkwan University
Link to publication DOI
10:40
20m
Talk
Are Your Epochs Too Epic? Batch Free Can Be Harmful
Main Conference
Daewoo Kim University of Waterloo, Trevor Brown University of Waterloo, Ajay Singh University of Waterloo
Link to publication DOI