Getting to the Root of Concurrent Binary Search Tree Performance

Authors: 

Maya Arbel-Raviv, Technion; Trevor Brown, IST Austria; Adam Morrison, Tel Aviv University

Abstract: 

Many systems rely on optimistic concurrent search trees for multi-core scalability. In principle, optimistic trees have a simple performance story: searches are read-only and so run in parallel, with writes to shared memory occurring only when modifying the data structure. However, this paper shows that in practice, obtaining the full performance benefits of optimistic search trees is not so simple.

We focus on optimistic binary search trees (BSTs) and perform a detailed performance analysis of 10 state-of-the-art BSTs on large scale x86-64 hardware, using both microbenchmarks and an in-memory database system. We find and explain significant unexpected performance differences between BSTs with similar tree structure and search implementations, which we trace to subtle performance-degrading interactions of BSTs with systems software and hardware subsystems. We further derive a prescriptive approach to avoid this performance degradation, as well as algorithmic insights on optimistic BST design. Our work underlines the gap between the theory and practice of multi-core performance, and calls for further research to help bridge this gap.

Open Access Media

USENIX is committed to Open Access to the research presented at our events. Papers and proceedings are freely available to everyone once the event begins. Any video, audio, and/or slides that are posted after the event are also free and open to everyone. Support USENIX and our commitment to Open Access.

Presentation Audio

BibTeX
@inproceedings {215945,
author = {Maya Arbel-Raviv and Trevor Brown and Adam Morrison},
title = {Getting to the Root of Concurrent Binary Search Tree Performance},
booktitle = {2018 {USENIX} Annual Technical Conference ({USENIX} {ATC} 18)},
year = {2018},
isbn = {978-1-931971-44-7},
address = {Boston, MA},
pages = {295--306},
url = {https://www.usenix.org/conference/atc18/presentation/arbel-raviv},
publisher = {{USENIX} Association},
}