Contention Adapting Search Trees
A contention adapting binary search tree (CA tree) is a concurrent ordered set data structure that adapts its structure according to the contention level. This web site contains links to CA tree papers, implementations, benchmarks and performance graphs.
A comprehensive description of CA trees with support for the operations insert, delete, lookup and range query is given in the journal publication below. This publication contains a detailed description of the data structure including pseudo-code and proofs for the correctness properties (linearizability, deadlock freedom and livelock freedom).
- Konstantinos Sagonas and Kjell Winblad. A contention adapting approach to concurrent ordered sets. Journal of Parallel and Distributed Computing, 2018 (submitted 2016). (publisher's version, preprint)
The journal publication above is built upon the following two conference publications. The first of those papers describes CA trees with support for single-element operations (insert, delete, and lookup). This paper contains two experimental evaluations of CA tree optimizations that are not included in the journal paper above. One of these optimzations is for use cases with very high contention. The other one combines a CA tree with hardware lock elision. The second paper evaluates and describes a CA tree extension to support linearizable range operations (range queries and range updates) and bulk operations. The technical report that is referred to in these two papers has been replaced by the journal publication above.
- Konstantinos Sagonas and Kjell Winblad. Contention Adapting Search Trees. In Proceedings of the Fourteenth International Symposium on Parallel and Distributed Computing, Limassol, Cyprus, July 2015. (publisher's version, preprint, code)
- Konstantinos Sagonas and Kjell Winblad. Efficient Support for Range Queries and Range Updates Using Contention Adapting Search Trees. In Proceedings of the 28th International Workshop on Languages and Compilers for Parallel Computing, Raleigh, USA, September 2015. (publisher's version, preprint, code)
The publication below describes an optimization for CA trees that is enabled by using an immutable data structure internally. This optimization is especially beneficial for range queries when contention is high. The experimental results presented in the paper show that the optimized CA tree variant outperform many recently proposed data structures in many scenarios. The benchmark code and the code for the optimized CA tree variant is available here.
- Kjell Winblad. Faster Concurrent Range Queries with Contention Adapting Search Trees Using Immutable Data. In the proceedings of 2017 Imperial College Computing Student Workshop (ICCSW 2017), London, United Kingdom, September 2017. (publisher's version, preprint, code)
The publication below describes how CA trees can be used to improve the scalability of the Erlang Term Storage.
- Konstantinos Sagonas and Kjell Winblad. More Scalable Ordered Set for ETS Using Adaptation. In Proceedings of the Thirteenth ACM SIGPLAN Workshop on Erlang, pages 3-11, Gothenburg, Sweden, September 2014.
Benchmarks and Code
The code used to obtain the experimental results included in the CA tree papers can be found by following the links with the text "code" that can be found next to the citations above.
Java Path Finder Tests for Pseudocode
The pseudocde included in the CA tree papers have been extracted from runnable Java code that have been tested with the help of the JavaPathFinder state space explorer. The Java code and the tests can be found in this archive. Please see the readme file inside the archive for information on how to run the tests.