More Web Proxy on the site http://driver.im/

article

Relativistic red-black trees

Authors:

Philip W. Howard,

Jonathan WalpoleAuthors Info & Claims

Concurrency and Computation: Practice & Experience, Volume 26, Issue 16

Pages 2684 - 2712

https://doi.org/10.1002/cpe.3157

Published: 01 November 2014 Publication History

Abstract

This paper presents algorithms for concurrently reading and modifying a red-black tree RBTree. The algorithms allow wait-free, linearly scalable lookups in the presence of concurrent inserts and deletes. They have deterministic response times for a given tree size and uncontended read performance that is at least 60% faster than other known approaches. The techniques used to derive these algorithms arise from a concurrent programming methodology called relativistic programming. Relativistic programming introduces write-side delay primitives that allow the writer to pay most of the cost of synchronization between readers and writers. Only minimal synchronization overhead is placed on readers. Relativistic programming avoids unnecessarily strict ordering of read and write operations while still providing the capability to enforce linearizability. This paper shows how relativistic programming can be used to build a concurrent RBTree with synchronization-free readers and both lock-based and transactional memory-based writers. Copyright © 2013 John Wiley & Sons, Ltd.

References

[1]

Landley R. Red-black trees rbtree in Linux. kernel.org documentation; January 2007. {Online}. Available from: "http://www.kernel.org/doc/Documentation/rbtree.txt" {Accessed on 26 September 2013}.

[2]

Java platform standard ed. 6. {Online}. Available from: "http://download.oracle.com/javase/6/docs/api/java/util/TreeMap.html" {Accessed on 26 September 2013}.

[3]

Fernandes SM, Cachopo J. Lock-free and scalable multi-version software transactional memory. In Proceedings of the 16th ACM Symposium on Principles and Practice of Parallel Programming, <bookSeriesTitle>PPoPP '11</bookSeriesTitle>. ACM: New York, NY, USA, 2011; pp.179-188. Available from: http://doi.acm.org/10.1145/1941553.1941579 {Accessed on 26 September 2013}.

[4]

Dragojević A, Guerraoui R, Kapalka M. Stretching transactional memory. In Proceedings of the 2009 ACM SIGPLAN Conference on Programming Language Design and Implementation, <bookSeriesTitle>PLDI '09</bookSeriesTitle>. ACM: New York, NY, USA, 2009; pp.155-165. Available from: http://doi.acm.org/10.1145/1542476.1542494 {Accessed on 26 September 2013}.

[5]

Dragojevic A, Felber P, Gramoli V, Guerraoui R. Why STM can be more than a research toy. Communications of the ACM 2011; Volume 54 Issue 4: pp.70-77.

[6]

Bronson NG, Casper J, Chafi H, Olukotun K. A practical concurrent binary search tree. In Ppopp '10: Proceedings of the 15th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. ACM: New York, NY, USA, 2010; pp.257-268.

[7]

Guibas LJ, Sedgewick R. A dichromatic framework for balanced trees. In SFCS '78: Proceedings of the 19th Annual Symposium on Foundations of Computer Science. IEEE Computer Society: Washington, DC, USA, 1978; pp.8-21.

[8]

Hanke S. The performance of concurrent red-black tree algorithms. Technical Report, Albert-Ludwigs University at Freiburg, 1998.

[9]

Pugh W. Concurrent maintenance of skip lists. Technical Report, University of Maryland at College Park, College Park, MD, USA, 1990. Available from: "http://drum.lib.umd.edu/bitstream/1903/542/2/CS-TR-2222.pdf" {Accessed on 26 September 2013}.

Digital Library

[10]

Pugh W. Skip lists: a probabilistic alternative to balanced trees. Communications in ACM June 1990; Volume 33: pp.668-676. Available from: http://doi.acm.org/10.1145/78973.78977 {Accessed on 26 September 2013}.

[11]

Binder W, Mosincat A, Spycher S, Constantinescu I, Faltings B. Multiversion concurrency control for the generalized search tree. Concurrency and Computation: Practice and Experience 2009; Volume 21 Issue 12: pp.1547-1571.

[12]

Triplett J, McKenney PE, Walpole J. Scalable concurrent hash tables via relativistic programming. SIGOPS Operating Systems Review August 2010; Volume 44: pp.102-109. Available from: http://doi.acm.org/10.1145/1842733.1842750 {Accessed on 26 September 2013}.

[13]

Triplett J, McKenney PE, Walpole J. Resizable, scalable, concurrent hash tables. In Proceedings of the 2011 USENIX Conference on USENIX Annual Technical Conference, <bookSeriesTitle>USENIXATC'11</bookSeriesTitle>. USENIX Association, Berkeley, CA, USA, 2011; pp.11.

[14]

McKenney PE. Kernel korner: using RCU in the Linux 2.5 kernel. Linux Journal 2003; Volume 2003 Issue 114: pp.11.

[15]

Herlihy MP, Wing JM. Linearizability: a correctness condition for concurrent objects. ACM Transactions on Programming Language Systems 1990; Volume 12 Issue 3: pp.463-492.

[16]

Vafeiadis V, Herlihy M, Hoare T, Shapiro M. Proving correctness of highly-concurrent linearisable objects. In Proceedings of the Eleventh ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, <bookSeriesTitle>PPoPP '06</bookSeriesTitle>, ACM: New York, NY, USA, 2006; pp.129-136. Available from: http://doi.acm.org/10.1145/1122971.1122992 {Accessed on 26 September 2013}.

[17]

Herlihy M. A methodology for implementing highly concurrent data objects. ACM Transactions on Programming Languages and Systems November 1993; Volume 15: pp.745-770. Available from: http://doi.acm.org/10.1145/161468.161469 {Accessed on 26 September 2013}.

[18]

Herlihy M, Shavit N, Waarts O. Linearizable counting networks. Distributed Computing February 1996; Volume 9: pp.193-203. Available from: "http://portal.acm.org/citation.cfm?id=1063369.1063372" {Accessed on 26 September 2013}.

[19]

Howard PW, Walpole J. A relativistic enhancement to software transactional memory. In HotPar'11: Proceedings of the 3rd USENIX Workshop on Hot Topics in Parallelism, <bookSeriesTitle>HotPar'11</bookSeriesTitle>. USENIX Association: Berkeley, CA, USA, 2011; pp.15.

[20]

Howard PW. Extending relativistic programming to multiple writers. Ph.D. Thesis, Portland State University University. Available from: "http://pdxscholar.library.pdx.edu/open_access_etds/114/" {Accessed on 26 September 2013}.

[21]

Attiya H, Guerraoui R, Hendler D, Kuznetsov P, Michael MM, Vechev M. Laws of order: expensive synchronization in concurrent algorithms cannot be eliminated. In Proceedings of the 38th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, <bookSeriesTitle>POPL '11</bookSeriesTitle>. ACM: New York, NY, USA, 2011; pp.487-498. Available from: http://doi.acm.org/10.1145/1926385.1926442 {Accessed on 26 September 2013}.

[22]

McKenney PE. Exploiting deferred destruction: an analysis of read-copy-update techniques in operating system kernels, Ph.D. Thesis, OGI School of Science and Engineering at Oregon Health and Sciences University, 2004. Available from: "http://www.rdrop.com/users/paulmck/RCU/RCUdissertation.2004.07.14e1.pdf" {Accessed on 26 September 2013}.

[23]

Desnoyers M, McKenney PE, Stern AS, Dagenais MR, Walpole J. User-level implementations of read-copy update. IEEE Transactions on Parallel and Distributed Systems 2012; Volume 23 Issue 2: pp.375-382. Available from: "http://dl.acm.org/citation.cfm?id=2122267.2122521" {Accessed on 26 September 2013}.

[24]

Desnoyers M. Low-impact operating system tracing. Ph.D. Thesis, École Polytechnique de Montréal, December 2009. {Online}. Available from: "http://www.lttng.org/pub/thesis/desnoyers-dissertation-2009-12.pdf" {Accessed on 26 September 2013}.

[25]

Hart TE, McKenney PE, Brown AD, Walpole J. Performance of memory reclamation for lockless synchronization. Journal of Parallel and Distributed Computing December 2007; Volume 67: pp.1270-1285. Available from: "http://portal.acm.org/citation.cfm?id=1316099.1316427" {Accessed on 26 September 2013}.

[26]

Bayer R. Symmetric binary b-trees: data structure and maintenance algorithms. Acta Informatica 1972; Volume 1: pp.290-306. Available from: http://dx.doi.org/10.1007/BF00289509 {Accessed on 26 September 2013}.

[27]

Plauger PJ. A better red-black tree. C/C++ Users Joural July 1999; Volume 17: pp.10-19. Available from: "http://dl.acm.org/citation.cfm?id=330304.330305".

[28]

Schneier B. Red-black trees. Dr. Dobb's Journal 1992; Volume 17 Issue 4: pp.42-46.

[29]

Mellor-Crummey JM, Scott ML. Scalable reader-writer synchronization for shared-memory multiprocessors. In PPoPP '91: Proceedings of the Third ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. ACM: New York, NY, USA, 1991; pp.106-113. Available from: "http://doi.acm.org/10.1145/109625.109637" {Accessed on 26 September 2013}.

Cited By

Ghiasi-Shirazi KGhandi TTaghizadeh ARahimi-Baigi A(2024)Revisiting 2–3 red–black trees with a pedagogically sound yet efficient deletion algorithm: parity-seekingActa Informatica10.1007/s00236-023-00452-661:3(199-229)Online publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1007/s00236-023-00452-6
Lázaro JBidarte UMuguira LCuadrado CJiménez J(2021)Fast and efficient address search in System-on-a-Programmable-Chip using binary treesComputers and Electrical Engineering10.1016/j.compeleceng.2021.10740396:PBOnline publication date: 1-Dec-2021
https://dl.acm.org/doi/10.1016/j.compeleceng.2021.107403
Park SMcKenney PDufour LYeom HBilas AMagoutis KMarkatos EKostic DSeltzer M(2020)An HTM-based update-side synchronization for RCU on NUMA systemsProceedings of the Fifteenth European Conference on Computer Systems10.1145/3342195.3387527(1-15)Online publication date: 15-Apr-2020
https://dl.acm.org/doi/10.1145/3342195.3387527
Show More Cited By

Recommendations

WFR-TM

Transactional Memory (TM) is a promising concurrent programming paradigm which employs transactions to achieve synchronization in accessing common data known as transactional variables. A transaction may either commit, making its updates to ...
Rank-Balanced Trees

Since the invention of AVL trees in 1962, many kinds of binary search trees have been proposed. Notable are red-black trees, in which bottom-up rebalancing after an insertion or deletion takes O(1) amortized time and O(1) rotations worst-case. But the ...
Non-blocking timeout in scalable queue-based spin locks
PODC '02: Proceedings of the twenty-first annual symposium on Principles of distributed computing

Queue-based spin locks allow programs with busy-wait synchronization to scale to very large multiprocessors, without fear of starvation or performance-destroying contention. Timeout-capable spin locks allow a thread to abandon its attempt to acquire a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Concurrency and Computation: Practice & Experience

Concurrency and Computation: Practice & Experience Volume 26, Issue 16

November 2014

96 pages

ISSN:1532-0626

EISSN:1532-0634

Issue’s Table of Contents

Publisher

John Wiley and Sons Ltd.

United Kingdom

Publication History

Published: 01 November 2014

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 20 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ghiasi-Shirazi KGhandi TTaghizadeh ARahimi-Baigi A(2024)Revisiting 2–3 red–black trees with a pedagogically sound yet efficient deletion algorithm: parity-seekingActa Informatica10.1007/s00236-023-00452-661:3(199-229)Online publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1007/s00236-023-00452-6
Lázaro JBidarte UMuguira LCuadrado CJiménez J(2021)Fast and efficient address search in System-on-a-Programmable-Chip using binary treesComputers and Electrical Engineering10.1016/j.compeleceng.2021.10740396:PBOnline publication date: 1-Dec-2021
https://dl.acm.org/doi/10.1016/j.compeleceng.2021.107403
Park SMcKenney PDufour LYeom HBilas AMagoutis KMarkatos EKostic DSeltzer M(2020)An HTM-based update-side synchronization for RCU on NUMA systemsProceedings of the Fifteenth European Conference on Computer Systems10.1145/3342195.3387527(1-15)Online publication date: 15-Apr-2020
https://dl.acm.org/doi/10.1145/3342195.3387527
Prasad AGopinath KOliveira RFelber PHu Y(2018)A frugal approach to reduce RCU grace period overheadProceedings of the Thirteenth EuroSys Conference10.1145/3190508.3190522(1-15)Online publication date: 23-Apr-2018
https://dl.acm.org/doi/10.1145/3190508.3190522
Erkan ABarr JClear TIzu Cdel Alamo CMohammed HNadimpalli MSheard JKorhonen A(2018)Developing a Holistic Understanding of Systems and Algorithms through Research PapersProceedings of the 2017 ITiCSE Conference on Working Group Reports10.1145/3174781.3174786(86-104)Online publication date: 30-Jan-2018
https://dl.acm.org/doi/10.1145/3174781.3174786
Roghanchi SEriksson JBasu N(2017)ffwdProceedings of the 26th Symposium on Operating Systems Principles10.1145/3132747.3132771(342-358)Online publication date: 14-Oct-2017
https://dl.acm.org/doi/10.1145/3132747.3132771

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents