---
_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: <i>Proceedings of the 2018 USENIX Annual Technical
    Conference</i>. USENIX Association; 2020:295-306.'
  apa: 'Arbel-Raviv, M., Brown, T. A., &#38; Morrison, A. (2020). Getting to the root
    of concurrent binary search tree performance. In <i>Proceedings of the 2018 USENIX
    Annual Technical Conference</i> (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 <i>Proceedings of the 2018 USENIX
    Annual Technical Conference</i>, 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 <i>Proceedings of the 2018 USENIX Annual Technical
    Conference</i>, 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.” <i>Proceedings of the 2018 USENIX Annual Technical Conference</i>,
    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'
...