A practical concurrent binary search tree
- 9 January 2010
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGPLAN Notices
- Vol. 45 (5), 257-268
- https://doi.org/10.1145/1837853.1693488
Abstract
We propose a concurrent relaxed balance AVL tree algorithm that is fast, scales well, and tolerates contention. It is based on optimistic techniques adapted from software transactional memory, but takes advantage of specific knowledge of the the algorithm to reduce overheads and avoid unnecessary retries. We extend our algorithm with a fast linearizable clone operation, which can be used for consistent iteration of the tree. Experimental evidence shows that our algorithm outperforms a highly tuned concurrent skip list for many access patterns, with an average of 39% higher single-threaded throughput and 32% higher multi-threaded throughput over a range of contention levels and operation mixes.Keywords
This publication has 11 references indexed in Scilit:
- On the Performance of Contention Managers for Complex Transactional Memory BenchmarksPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2009
- McRT-STMPublished by Association for Computing Machinery (ACM) ,2006
- Fast and lock-free concurrent priority queues for multi-thread systemsJournal of Parallel and Distributed Computing, 2005
- Performance analysis of BSTs in system softwareACM SIGMETRICS Performance Evaluation Review, 2004
- Software transactional memory for dynamic-sized data structuresPublished by Association for Computing Machinery (ACM) ,2003
- 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
- Skip lists: a probabilistic alternative to balanced treesCommunications of the ACM, 1990
- Concurrency control in database structures with relaxed balancePublished by Association for Computing Machinery (ACM) ,1987
- Symmetric binary B-Trees: Data structure and maintenance algorithmsActa Informatica, 1972