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]
|