000184477 001__ 184477
000184477 005__ 20181203023018.0
000184477 0247_ $$2doi$$a10.1145/2370036.2145837
000184477 022__ $$a0362-1340
000184477 02470 $$2ISI$$a000309350200016
000184477 037__ $$aARTICLE
000184477 245__ $$aA Speculation-Friendly Binary Search Tree
000184477 260__ $$bAssoc Computing Machinery$$c2012$$aNew York
000184477 269__ $$a2012
000184477 300__ $$a10
000184477 336__ $$aJournal Articles
000184477 520__ $$aWe 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.5x.
000184477 6531_ $$aAlgorithms
000184477 6531_ $$aLanguages
000184477 6531_ $$aPerformance
000184477 6531_ $$aBackground Rebalancing
000184477 6531_ $$aOptimistic Concurrency
000184477 6531_ $$aTransactional Memory
000184477 700__ $$uIRISA, Inst Univ France, Paris, France$$aCrain, Tyler
000184477 700__ $$0242987$$g183046$$aGramoli, Vincent
000184477 700__ $$aRaynal, Michel$$uIRISA, Inst Univ France, Paris, France
000184477 773__ $$j47$$tAcm Sigplan Notices$$k8$$q161-170
000184477 909C0 $$xU10407$$0252114$$pDCL
000184477 909CO $$pIC$$particle$$ooai:infoscience.tind.io:184477
000184477 917Z8 $$x166927
000184477 937__ $$aEPFL-ARTICLE-184477
000184477 973__ $$rREVIEWED$$sPUBLISHED$$aEPFL
000184477 980__ $$aARTICLE