Making Lockless Synchronization Fast: Performance Implications of Memory Reclamation
đź“ś Abstract
Achieving high performance for concurrent applications on modern multiprocessors remains challenging. Many programmers avoid locking to improve performance, while others replace locks with non-blocking synchronization to protect against deadlock, priority inversion, and convoying. In both cases, dynamic data structures that avoid locking, require a memory reclamation scheme that reclaims nodes once they are no longer in use. The performance of existing memory reclamation schemes has not been thoroughly evaluated. We conduct the first fair and comprehensive comparison of three recent schemes—quiescent-state-based reclamation, epoch-based reclamation, and hazard-pointer-based reclamation—using a flexible microbenchmark. Our results show that there is no globally optimal scheme. When evaluating lockless synchronization, programmers and algorithm designers should thus carefully consider the data structure, the workload, and the execution environment, each of which can dramatically affect memory reclamation performance.
✨ Summary
Summary
The paper studies memory reclamation as a major performance component of lockless and non-blocking data structures. It compares quiescent-state-based reclamation (QSBR), epoch-based reclamation (EBR), hazard-pointer-based reclamation (HPBR), and, in selected experiments, lock-free reference counting. The evaluation uses linked lists and queues on IBM POWER-based symmetric multiprocessors, varying traversal length, workload mix, thread count, preemption, and memory pressure.
The central result is that no reclamation scheme is universally optimal. QSBR generally has the lowest base cost because it avoids per-operation atomic instructions, but it can delay reclamation indefinitely when a thread is stalled or fails to reach a quiescent state. EBR is easier for application programmers because its bookkeeping is implicit, but its per-operation fencing creates substantial overhead. HPBR provides non-blocking reclamation and a provable bound on unreclaimed memory, making it more robust under preemption and memory pressure; however, its per-node fences and hazard-pointer scans make it increasingly expensive for long traversals and update-heavy workloads. Lock-free reference counting performs worst in the reported experiments because of repeated per-node atomic operations.
The paper also demonstrates that algorithm comparisons can be misleading unless the algorithms use the same reclamation mechanism. It proposes new epoch-based reclamation (NEBR), which moves epoch bookkeeping to a higher application level so that fencing costs can be amortized across multiple operations. The authors further argue that a non-blocking data structure can reasonably be paired with a blocking reclamation scheme when fault tolerance against memory exhaustion is not required, while retaining benefits such as resistance to deadlock, priority inversion, and signal-handler self-deadlock.
Influence
The conference paper was subsequently extended into the peer-reviewed journal article “Performance of memory reclamation for lockless synchronization,” published in the Journal of Parallel and Distributed Computing in December 2007, with Jonathan Walpole added as a coauthor. (sciencedirect.com) The work was also identified by the authors as an IPDPS 2006 Best Paper and has been incorporated into later technical discussions of RCU and memory-reclamation performance, including Paul McKenney’s Is Parallel Programming Hard, And, If So, What Can You Do About It? bibliography. (cs.toronto.edu) Later research on lock-free and wait-free reclamation continues to cite the work as an early comparative performance study establishing that reclamation costs depend strongly on workload, traversal size, and execution environment. (ssrg.ece.vt.edu)