Getting to the root of concurrent binary search tree performance

M. Arbel-Raviv, T.A. Brown, A. Morrison, in:, Proceedings of the 2018 USENIX Annual Technical Conference, USENIX ATC 2018, USENIX Association, 2020, pp. 295–306.

Conference Paper | Published | English

Scopus indexed
Author
Arbel-Raviv, Maya; Brown, Trevor AIST Austria; Morrison, Adam
Department
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.
Publishing Year
Date Published
2020-01-01
Proceedings Title
Proceedings of the 2018 USENIX Annual Technical Conference, USENIX ATC 2018
Page
295-306
Conference
USENIX: Annual Technical Conference
Conference Location
Boston, MA, United States
Conference Date
2018-07-11 – 2018-07-13
IST-REx-ID

Cite this

Arbel-Raviv M, Brown TA, Morrison A. Getting to the root of concurrent binary search tree performance. In: Proceedings of the 2018 USENIX Annual Technical Conference, USENIX ATC 2018. USENIX Association; 2020:295-306.
Arbel-Raviv, M., Brown, T. A., & Morrison, A. (2020). Getting to the root of concurrent binary search tree performance. In Proceedings of the 2018 USENIX Annual Technical Conference, USENIX ATC 2018 (pp. 295–306). Boston, MA, United States: USENIX Association.
Arbel-Raviv, Maya, Trevor A Brown, and Adam Morrison. “Getting to the Root of Concurrent Binary Search Tree Performance.” In Proceedings of the 2018 USENIX Annual Technical Conference, USENIX ATC 2018, 295–306. USENIX Association, 2020.
M. Arbel-Raviv, T. A. Brown, and A. Morrison, “Getting to the root of concurrent binary search tree performance,” in Proceedings of the 2018 USENIX Annual Technical Conference, USENIX ATC 2018, Boston, MA, United States, 2020, pp. 295–306.
Arbel-Raviv M, Brown TA, Morrison A. 2020. Getting to the root of concurrent binary search tree performance. Proceedings of the 2018 USENIX Annual Technical Conference, USENIX ATC 2018. USENIX: Annual Technical Conference 295–306.
Arbel-Raviv, Maya, et al. “Getting to the Root of Concurrent Binary Search Tree Performance.” Proceedings of the 2018 USENIX Annual Technical Conference, USENIX ATC 2018, USENIX Association, 2020, pp. 295–306.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar
ISBN Search