Split-ordered lists
- 1 May 2006
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 53 (3), 379-405
- https://doi.org/10.1145/1147954.1147958
Abstract
We present the first lock-free implementation of an extensible hash table running on current architectures. Our algorithm provides concurrent insert, delete, and find operations with an expected O (1) cost. It consists of very simple code, easily implementable using only load, store, and compare-and-swap operations. The new mathematical structure at the core of our algorithm is recursive split-ordering , a way of ordering elements in a linked list so that they can be repeatedly “split” using a single compare-and-swap operation. Metaphorically speaking, our algorithm differs from prior known algorithms in that extensibility is derived by “moving the buckets among the items” rather than “the items among the buckets.” Though lock-free algorithms are expected to work best in multiprogrammed environments, empirical tests we conducted on a large shared memory multiprocessor show that even in non-multiprogrammed environments, the new algorithm performs as well as the most efficient known lock-based resizable hash-table algorithm, and in high load cases it significantly outperforms it.Keywords
This publication has 15 references indexed in Scilit:
- Nonblocking k-compare-single-swapPublished by Association for Computing Machinery (ACM) ,2003
- High performance dynamic lock-free hash tables and list-based setsPublished by Association for Computing Machinery (ACM) ,2002
- Two-handed emulationPublished by Association for Computing Machinery (ACM) ,2002
- Safe memory reclamation for dynamic lock-free objects using atomic reads and writesPublished by Association for Computing Machinery (ACM) ,2002
- An algorithm for the asynchronous Write-All problem based on process collisionDistributed Computing, 2001
- Nonblocking Algorithms and Preemption-Safe Locking on Multiprogrammed Shared Memory MultiprocessorsJournal of Parallel and Distributed Computing, 1998
- Scalable reader-writer synchronization for shared-memory multiprocessorsPublished by Association for Computing Machinery (ACM) ,1991
- Linearizability: a correctness condition for concurrent objectsACM Transactions on Programming Languages and Systems, 1990
- Concurrency in linear hashingACM Transactions on Database Systems, 1987
- Extendible hashing for concurrent operations and distributed dataPublished by Association for Computing Machinery (ACM) ,1983