We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
A Fast Contention-Friendly Binary Search Tree.
- Authors
Crain, Tyler; Gramoli, Vincent; Raynal, Michel
- Abstract
This paper presents a fast concurrent binary search tree algorithm. To achieve high performance under contention, the algorithm divides update operations within an eager abstract access that returns rapidly for efficiency reason and a lazy structural adaptation that may be postponed to diminish contention. To achieve high performance under read-only workloads, it features a rebalancing mechanism and guarantees that read-only operations searching for an element execute lock-free. We evaluate the contention-friendly binary search tree using Synchrobench, a benchmark suite to compare synchronization techniques. More specifically, we compare its performance against five state-of-the-art binary search trees that use locks, transactions or compare-and-swap for synchronization on Intel Xeon, AMD Opteron and Oracle SPARC. Our results show that our tree is more efficient than other trees and double the throughput of existing lock-based trees under high contention.
- Subjects
DATA structures; READ-only memory; SYNCHRONIZATION; CONTENTION resolution protocols (Computer network protocols); ARRAY processors
- Publication
Parallel Processing Letters, 2016, Vol 26, Issue 3, p-1
- ISSN
0129-6264
- Publication type
Article
- DOI
10.1142/S0129626416500158