Skip to Main content Skip to Navigation
Reports

A Speculation-Friendly Binary Search Tree

Abstract : We introduce the first binary search tree algorithm designed for speculative executions. Prior to this work, tree structures were mainly designed for their pessimistic (non-speculative) accesses to have a bounded complexity. Researchers tried to evaluate transactional memory using such tree 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 show that our speculation-friendly tree outperforms the existing transaction-based version of the AVL and the red-black trees. Its key novelty stems from the decoupling of update operations: they are split into one transaction that modifies the abstraction state and multiple ones that restructure its tree implementation in the background. In particular, the speculation-friendly tree is shown correct, reusable and it speeds up a transaction-based travel reservation application by up to 3:5 .
Document type :
Reports
Complete list of metadata

Cited literature [32 references]  Display  Hide  Download

https://hal.inria.fr/inria-00618995
Contributor : Ist Rennes Connect in order to contact the contributor
Submitted on : Monday, March 5, 2012 - 9:10:14 AM
Last modification on : Thursday, January 20, 2022 - 4:20:05 PM
Long-term archiving on: : Wednesday, December 14, 2016 - 10:15:45 AM

File

PI-1984-v2.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00618995, version 2

Citation

Tyler Crain, Vincent Gramoli, Michel Raynal. A Speculation-Friendly Binary Search Tree. [Research Report] PI-1984, 2011, pp.21. ⟨inria-00618995v2⟩

Share

Metrics

Record views

6081

Files downloads

2640