---
_id: '7272'
abstract:
- lang: eng
text: "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.\r\n\r\nWe
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."
article_processing_charge: No
author:
- first_name: Maya
full_name: Arbel-Raviv, Maya
last_name: Arbel-Raviv
- first_name: Trevor A
full_name: Brown, Trevor A
id: 3569F0A0-F248-11E8-B48F-1D18A9856A87
last_name: Brown
- first_name: Adam
full_name: Morrison, Adam
last_name: Morrison
citation:
ama: '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 Association; 2020:295-306.'
apa: '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 (pp. 295–306). Boston, MA, United States: USENIX
Association.'
chicago: 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, 295–306. USENIX Association, 2020.
ieee: 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, Boston, MA, United States, 2020, pp. 295–306.
ista: '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: Annual Technical Conference, 295–306.'
mla: Arbel-Raviv, Maya, et al. “Getting to the Root of Concurrent Binary Search
Tree Performance.” Proceedings of the 2018 USENIX Annual Technical Conference,
USENIX Association, 2020, pp. 295–306.
short: M. Arbel-Raviv, T.A. Brown, A. Morrison, in:, Proceedings of the 2018 USENIX
Annual Technical Conference, USENIX Association, 2020, pp. 295–306.
conference:
end_date: 2018-07-13
location: Boston, MA, United States
name: 'USENIX: Annual Technical Conference'
start_date: 2018-07-11
date_created: 2020-01-14T07:27:08Z
date_published: 2020-01-01T00:00:00Z
date_updated: 2021-01-11T15:25:48Z
day: '01'
ddc:
- '000'
department:
- _id: DaAl
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://www.usenix.org/system/files/conference/atc18/atc18-arbel-raviv.pdf
month: '01'
oa: 1
oa_version: Published Version
page: 295-306
project:
- _id: 26450934-B435-11E9-9278-68D0E5697425
name: NSERC Postdoctoral fellowship
publication: Proceedings of the 2018 USENIX Annual Technical Conference
publication_identifier:
isbn:
- '9781939133021'
publication_status: published
publisher: USENIX Association
quality_controlled: '1'
scopus_import: '1'
status: public
title: Getting to the root of concurrent binary search tree performance
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2020'
...