Nathan G. Bronson
Hassan Chafi
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.
- G. Adel'son--Vel'skiǐ and E. M. Landis. An algorithm for the organization of information. In Proceedings of the USSR Academy of Sciences, volume 145, pages 263--266, 1962. In Russian, English translation by Myron J. Ricci in Soviet Doklady, 3:1259--1263, 1962.Google Scholar
- M. Ansari, C. Kotselidis, M. Lujan, C. Kirkham, and I. Watson. On the performance of contention managers for complex transactional memory benchmarks. In ISPDC '09: Proceedings of the 8th International Symposium on Parallel and Distributed Computing, pages 83--90, 2009. Google ScholarDigital Library
- L. Ballard. Conflict avoidance: Data structures in transactional memory. Brown University Undergraduate Thesis, 2006.Google Scholar
- R. Bayer. Symmetric binary B-Trees: Data structure and maintenance algorithms. Acta Inf., 1:290--306, 1972.Google ScholarDigital Library
- R. Bayer and M. Schkolnick. Concurrency of operations on B-Trees. In Readings in Database Systems (2nd ed.), pages 216--226, San Francisco, CA, USA, 1994. Morgan Kaufmann Publishers Inc. Google ScholarDigital Library
- L. Bouge, J. Gabarro, X. Messeguer, and N. Schabanel. Height-relaxed AVL rebalancing: A unified, fine-grained approach to concurrent dictionaries. ResearchReport RR1998-18, LIP, ENS Lyon, March 1998.Google Scholar
- N. Bronson. CCSTM. http://github.com/nbronson/ccstm.Google Scholar
- P. Felber, V. Gramoli, and R. Guerraoui. Elastic transactions. In DISC '09: Proceedings of the 23rd International Symposium on Distributed Computing, pages 93--107, 2009. Google ScholarDigital Library
- K. Fraser. Practical Lock Freedom. PhD thesis, University of Cambridge, 2003.Google Scholar
- L. J. Guibas and R. Sedgewick. A dichromatic framework for balanced trees. In 19th Annual Symposium on Foundations of Computer Science, pages 8--21, Oct. 1978. Google ScholarDigital Library
- M. Herlihy, Y. Lev, V. Luchangco, and N. Shavit. A provably correct scalable concurrent skip list. In OPODIS '06: Proceedings of the 10th International Conference On Principles Of Distributed Systems, 2006.Google Scholar
- M. Herlihy, V. Luchangco, M. Moir, and W. N. Scherer, III. Software transactional memory for dynamic-sized data structures. In PODC '03: Proceedings of the twenty-second annual symposium on Principles of distributed computing, pages 92--101, New York, NY, USA, 2003. ACM. Google ScholarDigital Library
- M. P. Herlihy and J. M. Wing. Linearizability: A correctness condition for concurrent objects. ACM Transactions on Programming Languages and Systems, 12(3):463--492, 1990. Google ScholarDigital Library
- K. S. Larsen. AVL trees with relaxed balance. In IPPT '94: Proceedings of the 8th International Symposium on Parallel Processing, pages 888--893, Washington, DC, USA, 1994. IEEE Computer Society. Google ScholarDigital Library
- J. M. Mellor-Crummey and M. L. Scott. Scalable reader-writer synchronization for shared--memory multiprocessors. In PPOPP '91: Proceedings of the Third ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pages 106--113, New York, NY, USA, 1991. ACM. Google ScholarDigital Library
- O. Nurmi, E. Soisalon-Soininen, and D. Wood. Concurrency control in database structures with relaxed balance. In PODS '87: Proceedings of the Sixth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pages 170--176, New York, NY, USA, 1987. ACM. Google ScholarDigital Library
- B. Pfaff. Performance analysis of BSTs in system software. SIGMETRICS Performance Evaluation Review, 32(1):410--411, 2004. Google ScholarDigital Library
- W. Pugh. Concurrent maintenance of skip lists. Technical Report CS-TR-2222.1, 1989.Google ScholarDigital Library
- W. Pugh. Skip lists: A probabilistic alternative to balanced trees. ACM Transactions on Database Systems, 33(6):668--676, 1990. Google ScholarDigital Library
- B. Saha, A.-R. Adl-Tabatabai, R. L. Hudson, C. Cao Minh, and B. Hertzberg. McRT--STM: A high performance software trans- actional memory system for a multi-core runtime. In PPoPP '06: Proceedings of the eleventh ACM SIGPLAN symposium on Principles and practice of parallel programming, pages 187--197, New York, NY, USA, March 2006. ACM Press. Google ScholarDigital Library
- H. Sundell and P. Tsigas. Fast and lock-free concurrent priority queues for multi-thread systems. Journal of Parallel Distributed Computing, 65(5):609--627, 2005. Google ScholarDigital Library
Index Terms
- A practical concurrent binary search tree
Recommendations
A speculation-friendly binary search tree
PPOPP '12We introduce the first binary search tree algorithm designed for speculative executions. Prior to this work, tree structures were mainly designed for their pessimistic (non-speculative) accesses to have a bounded complexity. Researchers tried to ...
A practical concurrent binary search tree
PPoPP '10: Proceedings of the 15th ACM SIGPLAN Symposium on Principles and Practice of Parallel ProgrammingWe 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 ...
TxLinux: using and managing hardware transactional memory in an operating system
SOSP '07TxLinux is a variant of Linux that is the first operating system to use hardware transactional memory (HTM) as a synchronization primitive, and the first to manage HTM in the scheduler. This paper describes and measures TxLinux and discusses two ...
Comments