A speculation‐friendly binary search tree. (31st July 2018)

• Record Type: Journal Article
• Authors: Crain, Tyler; Gramoli, Vincent; Raynal, Michel
• Is Part Of: Concurrency and computation. Volume 31:Number 4(2019)
• Page Start: n/a
• Page End: n/a
• Publication Date: 2018-07-31
• Subjects: background rebalancing -- HTM -- optimistic concurrency -- transactional memory; Parallel processing (Electronic computers) -- Periodicals; Parallel computers -- Periodicals; 004.35
• DOI: 10.1002/cpe.4883
• Languages: English
• ISSNs: 1532-0626

Abstract

Summary: We introduce the first concurrent data structure algorithm designed for speculative executions. Prior to this work, concurrent structures were mainly designed for their pessimistic (non‐speculative) accesses to have a predictable asymptotic complexity. Researchers tried to evaluate transactional memory using such structures whose prominent example is the red‐black tree library developed by Oracle Labs that is part of multiple benchmark distributions. Although well‐engineered, such structures remain badly suited for speculative accesses, whose step complexity might raise dramatically with contention. We propose a binary search tree data structure whose key novelty stems from the decoupling of update operations, ie, instead of performing an update operation in a single large transaction, it is split into one transaction that modifies the abstraction state and several other transactions that restructure the tree implementation in the background. This results in a speculation‐friendly tree ( s‐tree ) that outperforms previous HTM‐based and STM‐based trees by being transiently unbalanced during contention peaks and by rebalancing in quadratic time when contention disappears. In particular, the s‐tree is shown correct, reusable, and speeds up a transaction‐based travel reservation application by up to 3.5×.