research-article

A speculation-friendly binary search tree

Authors:

Vincent Gramoli,

Michel RaynalAuthors Info & Claims

PPoPP '12: Proceedings of the 17th ACM SIGPLAN symposium on Principles and Practice of Parallel Programming

Pages 161 - 170

https://doi.org/10.1145/2145816.2145837

Published: 25 February 2012 Publication History

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

References

[1]

G. Adelson-Velskii and E. M. Landis. An algorithm for the organization of information. In Proc. of the USSR Academy of Sciences, volume 146, pages 263--266, 1962.

[2]

K. Agrawal, I.-T. A. Lee, and J. Sukha. Safe open-nested transactions through ownership. In Proc. of the 14th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming, 2009.

Digital Library

[3]

L. Ballard. Conflict avoidance: Data structures in transactional memory, May 2006. Undergraduate thesis, Brown University.

[4]

R. Bayer. Symmetric binary b-trees: Data structure and maintenance algorithms. Acta Informatica 1, 1(4):290--306, 1972.

Digital Library

[5]

L. Bougé, J. Gabarro, X. Messeguer, and N. Schabanel. Height-relaxed AVL rebalancing: A unified, fine-grained approach to concurrent dictionaries, 1998. Research Report 1998--18, ENS Lyon.

[6]

N. G. Bronson, J. Casper, H. Chafi, and K. Olukotun. A practical concurrent binary search tree. In Proc. of the 15th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming, 2010.

Digital Library

[7]

C. Cao Minh, J. Chung, C. Kozyrakis, and K. Olukotun. STAMP: Stanford transactional applications for multi-processing. In Proc. of The IEEE Int'l Symp. on Workload Characterization, 2008.

[8]

C. Cole and M. Herlihy. Snapshots and software transactional memory. Sci. Comput. Program., 58(3):310--324, 2005.

Digital Library

[9]

T. Crain, V. Gramoli, and M. Raynal. A speculation-friendly binary search tree. Technical Report PI-1984, IRISA, September 2011.

[10]

L. Dalessandro, M. Spear, and M. L. Scott. NOrec: streamlining S™ by abolishing ownership records. In Proc. of the 15th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming, 2010.

Digital Library

[11]

D. Dice, O. Shalev, and N. Shavit. Transactional locking II. In Proc. of the 20th Int'l Symp. on Distributed Computing, 2006.

Digital Library

[12]

E. W. Dijkstra, L. Lamport, A. J. Martin, C. S. Scholten, and E. F. M. Steffens. On-the-fly garbage collection: an exercise in cooperation. Commun. ACM, 21(11):966--975, 1978.

Digital Library

[13]

A. Dragojevic, P. Felber, V. Gramoli, and R. Guerraoui. Why S™ can be more than a research toy. Commun. ACM, 54(4):70--77, 2011.

Digital Library

[14]

P. Felber, C. Fetzer, and T. Riegel. Dynamic performance tuning of word-based software transactional memory. In Proc. of the 13th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming, 2008.

Digital Library

[15]

P. Felber, V. Gramoli, and R. Guerraoui. Elastic transactions. In Proc. of the 23rd Int'l Symp. on Distributed Computing, 2009.

Digital Library

[16]

V. Gramoli and R. Guerraoui. Democratizing transactional programming. In Proc. of the ACM/IFIP/USENIX 12th Int'l Middleware Conference, 2011.

Digital Library

[17]

L. J. Guibas and R. Sedgewick. A dichromatic framework for balanced trees. In Proc. of the 19th Annual Symp. on Foundations of Computer Science, 1978.

Digital Library

[18]

T. Harris, S. Marlow, S. Peyton-Jones, and M. Herlihy. Composable memory transactions. In Proc. of the 10th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming, 2005.

Digital Library

[19]

M. Herlihy and E. Koskinen. Transactional boosting: A methodology for highly-concurrent transactional objects. In Proc. of the 13th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming, 2008.

Digital Library

[20]

M. Herlihy, V. Luchangco, M. Moir, and W. N. Scherer, III. Software transactional memory for dynamic-sized data structures. In Proc. of the 22nd Annual ACM SIGACT-SIGOPS Symp. on Principles of Distributed Computing, 2003.

Digital Library

[21]

M. Herlihy and J. E. B. Moss. Transactional memory: Architectural support for lock-free data structures. In Proc. of the 20th Annual Int'l Symp. on Computer Architecture, 1993.

Digital Library

[22]

Intel Corporation. Intel transactional memory compiler and runtime application binary interface, May 2009.

[23]

J. L. W. Kessels. On-the-fly optimization of data structures. Comm. ACM, 26:895--901, 1983.

Digital Library

[24]

U. Manbar and R. E. Ladner. Concurrency control in a dynamic search structure. ACM Trans. Database Syst., 9(3):439--455, 1984.

Digital Library

[25]

C. Mohan. Commit-LSN: a novel and simple method for reducing locking and latching in transaction processing systems. In Proc. of the 16th Int'l Conference on Very Large Data Bases, 1990.

Digital Library

[26]

J. E. B. Moss. Open nested transactions: Semantics and support. In Workshop on Memory Performance Issues, 2006.

[27]

Y. Ni, V. Menon, A.-R. Abd-Tabatabai, A. L. Hosking, R. L. Hudson, J. E. B. Moss, B. Saha, and T. Shpeisman. Open nesting in software transactional memory. In Proc. of the 12th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming, 2007.

Digital Library

[28]

O. Nurmi and E. Soisalon-Soininen. Uncoupling updating and rebalancing in chromatic binary search trees. In Proc. of the 10th ACM Symp. on Principles of Database Systems, 1991.

Digital Library

[29]

O. Nurmi, E. Soisalon-Soininen, and D. Wood. Concurrency control in database structures with relaxed balance. In Proc. of the 6th ACM Symp. on Principles of Database Systems, 1987.

Digital Library

[30]

V. Pankratius and A.-R. Adl-Tabatabai. A study of transactional memory vs. locks in practice. In Proc. of the 23rd ACM Symp. on Parallelism in Algorithms and Architectures, 2011.

Digital Library

[31]

C. J. Rossbach, O. S. Hofmann, and E. Witchel. Is transactional programming actually easier? In Proc. of the 15th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming, 2010.

Digital Library

[32]

N. Shavit. Data structures in the multicore age. Commun. ACM, 54(3):76--84, 2011.

Digital Library

[33]

N. Shavit and D. Touitou. Software transactional memory. In Proc. of the 14th ACM Symp. on Principles of Distributed Computing, 1995.

Digital Library

[34]

R. M. Yoo, Y. Ni, A. Welc, B. Saha, A.-R. Adl-Tabatabai, and H.-H. S. Lee. Kicking the tires of software transactional memory: why the going gets tough. In Proc. of the 20th ACM Symp. on Parallelism in Algorithms and Architectures, 2008.

Digital Library

Cited By

Cai BYao JLi MXiao X(2023)A Scalable Adaptive Locking Mechanism for High Performance Computing2023 4th International Conference on Computer Vision, Image and Deep Learning (CVIDL)10.1109/CVIDL58838.2023.10166039(651-658)Online publication date: 12-May-2023
https://doi.org/10.1109/CVIDL58838.2023.10166039
Siakavaras DNikas KGoumas GKoziris N(2021)RCU‐HTM: A generic synchronization technique for highly efficient concurrent search treesConcurrency and Computation: Practice and Experience10.1002/cpe.617433:10Online publication date: 12-Jan-2021
https://doi.org/10.1002/cpe.6174
Jordan HSubotić PZhao DScholz B(2020)Specializing parallel data structures for DatalogConcurrency and Computation: Practice and Experience10.1002/cpe.564334:2Online publication date: 7-Jan-2020
https://doi.org/10.1002/cpe.5643
Show More Cited By

Index Terms

A speculation-friendly binary search tree
1. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language features
        Concurrent programming structures
    2. Software libraries and repositories

Recommendations

A practical concurrent binary search tree
PPoPP '10: Proceedings of the 15th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming

We propose a concurrent relaxed balance AVL tree algorithm that is fast, scales well, and tolerates contention. It is based on optimistic techniques adapted from software transactional memory, but takes advantage of specific knowledge of the the ...
A speculation-friendly binary search tree
PPOPP '12

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 ...
TxLinux: using and managing hardware transactional memory in an operating system
SOSP '07

TxLinux is a variant of Linux that is the first operating system to use hardware transactional memory (HTM) as a synchronization primitive, and the first to manage HTM in the scheduler. This paper describes and measures TxLinux and discusses two ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PPoPP '12: Proceedings of the 17th ACM SIGPLAN symposium on Principles and Practice of Parallel Programming

February 2012

352 pages

ISBN:9781450311601

DOI:10.1145/2145816

General Chair:
J. Ramanujam
Louisiana State University, USA
,
Program Chair:
P. Sadayappan
The Ohio State University, USA

ACM SIGPLAN Notices Volume 47, Issue 8
PPOPP '12
August 2012
334 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/2370036
Issue’s Table of Contents

Copyright © 2012 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 25 February 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

PPoPP '12

Sponsor:

SIGPLAN

PPoPP '12: ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming

February 25 - 29, 2012

Louisiana, New Orleans, USA

Acceptance Rates

Overall Acceptance Rate 230 of 1,014 submissions, 23%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

54
Total Citations
View Citations
662
Total Downloads

Downloads (Last 12 months)12
Downloads (Last 6 weeks)2

Reflects downloads up to 15 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Cai BYao JLi MXiao X(2023)A Scalable Adaptive Locking Mechanism for High Performance Computing2023 4th International Conference on Computer Vision, Image and Deep Learning (CVIDL)10.1109/CVIDL58838.2023.10166039(651-658)Online publication date: 12-May-2023
https://doi.org/10.1109/CVIDL58838.2023.10166039
Siakavaras DNikas KGoumas GKoziris N(2021)RCU‐HTM: A generic synchronization technique for highly efficient concurrent search treesConcurrency and Computation: Practice and Experience10.1002/cpe.617433:10Online publication date: 12-Jan-2021
https://doi.org/10.1002/cpe.6174
Jordan HSubotić PZhao DScholz B(2020)Specializing parallel data structures for DatalogConcurrency and Computation: Practice and Experience10.1002/cpe.564334:2Online publication date: 7-Jan-2020
https://doi.org/10.1002/cpe.5643
Dice DKogan ADan TDahlia M(2019)BRAVOProceedings of the 2019 USENIX Conference on Usenix Annual Technical Conference10.5555/3358807.3358835(315-328)Online publication date: 10-Jul-2019
https://dl.acm.org/doi/10.5555/3358807.3358835
Jordan HSubotić PZhao DScholz B(2019)BrieProceedings of the 10th International Workshop on Programming Models and Applications for Multicores and Manycores10.1145/3303084.3309490(31-40)Online publication date: 17-Feb-2019
https://dl.acm.org/doi/10.1145/3303084.3309490
Jordan HSubotić PZhao DScholz BHollingsworth JKeidar I(2019)A specialized B-tree for concurrent datalog evaluationProceedings of the 24th Symposium on Principles and Practice of Parallel Programming10.1145/3293883.3295719(327-339)Online publication date: 16-Feb-2019
https://dl.acm.org/doi/10.1145/3293883.3295719
Ha PAnshus OUmar I(2019)Efficient Concurrent Search Trees Using Portable Fine-Grained LocalityIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2019.289296830:7(1580-1595)Online publication date: 13-Jun-2019
https://dl.acm.org/doi/10.1109/TPDS.2019.2892968
Crain TGramoli VRaynal M(2018)A speculation‐friendly binary search treeConcurrency and Computation: Practice and Experience10.1002/cpe.488331:4Online publication date: 31-Jul-2018
https://doi.org/10.1002/cpe.4883
Hassan APalmieri RPeluso SRavindran B(2017)Optimistic Transactional BoostingIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2017.272583728:12(3600-3614)Online publication date: 9-Nov-2017
https://dl.acm.org/doi/10.1109/TPDS.2017.2725837
Siakavaras DNikas KGoumas GKoziris N(2017)RCU-HTM: Combining RCU with HTM to Implement Highly Efficient Concurrent Binary Search Trees2017 26th International Conference on Parallel Architectures and Compilation Techniques (PACT)10.1109/PACT.2017.17(1-13)Online publication date: Sep-2017
https://doi.org/10.1109/PACT.2017.17
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten