Concurrent Systems Research Group

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.5x.