No Hot Spot Non-blocking Skip List
Authors:
- Tyler CrainTCTyler Crain
- Vincent GramoliVGVincent Gramoli
- Michel RaynalMRMichel Raynal
- 1 July 2013
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 10636927,p. 196-205
Abstract
This paper presents a new non-blocking skip list algorithm. The algorithm alleviates contention by localizing synchronization at the least contended part of the structure without altering consistency of the implemented abstraction. The key idea lies in decoupling a modification to the structure into two stages: an eager abstract modification that returns quickly and whose update affects only the bottom of the structure, and a lazy selective adaptation updating potentially the entire structure but executed continuously in the background. On SPECjbb as well as on micro-benchmarks, we compared the performance of our new non-blocking skip list against the performance of the JDK non-blocking skip list. The results indicate that our implementation can me more than twice as fast as the JDK skip list.Keywords
This publication has 11 references indexed in Scilit:
- A speculation-friendly binary search tree2012
- A Simple Optimistic Skiplist Algorithm2007
- Transactional collection classes2007
- Lock-free linked lists and skip lists2004
- Scalable and lock-free concurrent dictionaries2004
- High performance dynamic lock-free hash tables and list-based sets2002
- Linearizability: a correctness condition for concurrent objectsACM Transactions on Programming Languages and Systems, 1990
- Skip lists: a probabilistic alternative to balanced treesCommunications of the ACM, 1990
- Concurrency control in database structures with relaxed balance1987
- On-the-fly garbage collectionCommunications of the ACM, 1978