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 MarDisplayed 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 20mTalk | Scaling Up Transactions with Slower Clocks Main Conference Link to publication DOI | ||
10:20 20mTalk | 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 20mTalk | 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 |