Department of Information Technology

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.

Publications

A detailed description of CA trees with support for single-element operations (insert, delete, and update) with pseudo-code, correctness properties, and scalability comparison to related concurrent data structures appears in this paper.

  • 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. (This technical report complements the paper with a more detailed correctness proof.)

The following publication gives a detailed description of CA tree algorithms for range queries, range updates, bulk insert and delete as well as a comparison to related data structures.

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.

The publication below describes how CA trees can be used to improve the scalability of the Erlang Term Storage.

Benchmarks and Code

Range Queries and Range Updates

Source code for our CA tree implementations with range query and range update support as well as benchmarks can be found downloaded here.

We have run benchmarks for range queries and range updates on two machines. The first machine called Bulldozer has four AMD Opteron 6276 (2.3 GHz, 16 cores, 16M L2/16M L3 Cache), giving a total of 64 cores and 128GB or RAM, running Linux 3.10-amd64 and Oracle Hotspot JVM 1.8.0_31 (started with parameters -Xmx4g, -Xms4g, -server and -d64). The second machine called Sandy has four Intel(R) Xeon(R) E5-4650 CPUs (2.70GHz each with eight cores and hyperthreading) and the same operating system and JVM as bulldozer. On Sandy we pinned threads to NUMA nodes so the first 16 threads run on one chip, from 17 to 32 threads on two chips and so on. Performance graphs showing throughput in ops/microsecond on the y-axis and thread counts on the x-axis can be found below. A figure title of the form w:A% r:B% q:C%-R1 u:D%-R2 represents a scenario with (A/2)% insert, (A/2)% remove, B% get operations, C% range queries of maximum range size R1, and D% range updates with maximum range size R2.

Machine\Key range 500000 1000000 2000000
Bulldozer Download Download Download
Sandy Download Download Download

Basic Set Operations

A Java benchmark for the CA tree as well as CA tree implementations can be downloaded here. See the README.md file in the archive for more details. Our Java AVL-tree based CA tree implementation with basic set operations has also been included in the Synchrobench benchmark suite.

This PDF document contains graphs for the benchmark described in the technical report mentioned above. It is recommended to view the graphs with a PDF reader that support zooming in and out to study the different scenarios.

Hardware Lock Elision (HLE) Benchmark

A benchmark for the HLE extension of the CA tree as well as CA tree implementations written in C can be downloaded here. See the README.md file in the archive for more details.

This PDF document contains graphs from a benchmark run on an Intel(R) Xeon(R) CPU E3-1230 v3 (3.30GHz), 4 cores with hyperthreading (8 logical cores), and 16GB of RAM running Ubuntu 13.10.

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.

Updated  2017-08-16 21:40:45 by Kjell Winblad.