Comparative Performance of Memory Reclamation Strategies for Lock-free and Concurrently-readable Data Structures

M.Sc. Supervisor: Angela Demke Brown

Abstract

Despite their advantages, lock-free algorithms are often not adopted in practice, partly due to the perception that they perform poorly relative to lock-based alternatives in common situations when there is little contention for objects or the CPUs.

We show that memory reclamation can be a dominant performance cost for lock-free algorithms; therefore, choosing the most efficient memory reclamation method is essential to having lock-free algorithms perform well. We compare the costs of three memory reclamation strategies: quiescent-state-based reclamation, epoch-based reclamation, and safe memory reclamation (hazard pointers). Our experiments show that changing the workload or execution environment can change which of these schemes is the most efficient. We therefore demonstrate that there is, to date, no panacea for memory reclamation for lock-free algorithms.

Using a common reclamation scheme, we fairly compare lock-free and concurrently-readable hash tables. Our evaluation shows that programmers can choose memory reclamation schemes mostly independently of the target algorithm.  
 

Comparative Performance of Memory Reclamation Strategies for Lock-free and Concurrently-readable Data Structures
Thomas E. Hart. Masters Thesis, Department of Computer Science, University of Toronto, 2005. [PDF]

Making Lockless Synchronization Fast: Performance Implications of Memory Reclamation
Thomas E. Hart, Paul E. McKenney, and Angela Demke Brown. In Proceedings of the 2006 International Parallel and Distributed Processing Symposium (IPDPS 2006), Rhodes Island, Greece, April 2006. [PDF] [Slides]
Awarded Best Paper; Acceptance rate: 24%

Performance of memory reclamation for lockless synchronization
Thomas E. Hart, Paul E. McKenney, Angela Demke Brown and Jonathan Walpole. Journal of Parallel and Distributed Computing, In Press, Accepted Manuscript. [DOI]