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

research-article

FEAST: A Lightweight Lock-free Concurrent Binary Search Tree

Authors:

Aravind Natarajan,

Arunmoezhi Ramachandran,

Neeraj MittalAuthors Info & Claims

ACM Transactions on Parallel Computing (TOPC), Volume 7, Issue 2

Article No.: 10, Pages 1 - 64

https://doi.org/10.1145/3391438

Published: 18 May 2020 Publication History

Abstract

We present a lock-free algorithm for concurrent manipulation of a binary search tree (BST) in an asynchronous shared memory system that supports search, insert, and delete operations. In addition to read and write instructions, our algorithm uses (single-word) compare-and-swap (CAS) and bit-test-and-set (BTS) read-modify-write (RMW) instructions, both of which are commonly supported by many modern processors including Intel 64 and AMD64. In contrast to most of the existing concurrent algorithms for a binary search tree, our algorithm is edge-based rather than node-based. When compared to other concurrent algorithms for a binary search tree, modify (insert and delete) operations in our algorithm (a) work on a smaller section of the tree, (b) execute fewer RMW instructions, or (c) use fewer dynamically allocated objects. In our experiments, our lock-free algorithm significantly outperformed all other algorithms for a concurrent binary search tree especially when the contention was high.

We also describe modifications to our basic lock-free algorithm so that the amortized complexity of any operation in the modified algorithm can be bounded by the sum of the tree height and the point contention to within a constant factor while preserving the other desirable features of our algorithm.

References

[1]

Advanced Micro Devices 2017. AMD64 Architecture Programmerś Manual Volume 3: General Purpose and System Instructions. Advanced Micro Devices. Retrieved from https://support.amd.com/TechDocs/24594.pdf.

[2]

Dan Alistarh, W. M. Leiserson, A. Matveev, and N. Shavit. 2015. ThreadScan: Automatic and scalable memory reclamation. In Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA’15). ACM, New York, NY, 123--132.

[3]

M. Arbel and H. Attiya. 2014. Concurrent updates with RCU: Search tree as an example. In Proceedings of the 33rd ACM Symposium on Principles of Distributed Computing (PODC’14). ACM, New York, NY, 196--205.

[4]

M. Arbel and H. Attiya. 2015. Predicate RCU: An RCU for scalable concurrent updates. In Proceedings of the 20th ACM Symposium on Principles and Practice of Parallel Programming (PPoPP’15). ACM, New York, NY, 21--30.

[5]

M. A. Bender, J. T. Fineman, S. Gilbert, and B. C. Kuszmaul. 2005. Concurrent cache-oblivious B-trees. In Proceedings of the 17th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA’05). ACM, New York, NY, 228--237.

[6]

A. Braginsky and E. Petrank. 2012. A lock-free B+tree. In Proceedings of the 24th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA’12). ACM, New York, NY, 58--67.

[7]

T. Brown, F. Ellen, and E. Ruppert. 2014. A general technique for non-blocking trees. In Proceedings of the 19th ACM Symposium on Principles and Practice of Parallel Programming (PPoPP’14). ACM, New York, NY, 329--342.

[8]

T. Brown and J. Helga. 2011. Non-blocking k-ary search trees. In Proceedings of the International Conference on Principles of Distributed Systems (OPODIS’11). Springer-Verlag, Berlin, Germany, 207--221.

[9]

T. A. Brown. 2015. Reclaiming memory for lock-free data structures: There has to be a better way. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC’15). ACM, New York, NY, 261--270.

Digital Library

[10]

B. Chatterjee, N. N. Dang, and P. Tsigas. 2014. Efficient lock-free binary search trees. In Proceedings of the 33rd ACM Symposium on Principles of Distributed Computing (PODC’14). ACM, New York, NY, 321--331.

[11]

P. Chuong, F. Ellen, and V. Ramachandran. 2010. A universal construction for wait-free transaction friendly data structures. In Proceedings of the 22nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA’10). ACM, New York, NY, 335--344.

[12]

T. H. Cormen, C. E. Leiserson, and R. L. Rivest. 1991. Introduction to Algorithms. The MIT Press, Cambridge, Massachusetts.

[13]

T. David, R. Guerraoui, and V. Trigonakis. 2015. Asynchronized concurrency: The secret to scaling concurrent search data structures. In Proceedings of the 20th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS’15). ACM, New York, NY, 631--644.

[14]

D. Drachsler, M. Vechev, and E. Yahav. 2014. Practical concurrent binary search trees via logical ordering. In Proceedings of the 19th ACM Symposium on Principles and Practice of Parallel Programming (PPoPP’14). ACM, New York, NY, 343--356.

[15]

D. Drachsler-Cohen, M. T. Vechev, and E. Yahav. 2018. Practical concurrent traversals in search trees. In Proceedings of the 23rd ACM Symposium on Principles and Practice of Parallel Programming (PPoPP’18). 207--218.

[16]

F. Ellen, P. Fatourou, J. Helga, and E. Ruppert. 2014. The amortized complexity of non-blocking binary search trees. In Proceedings of the 33rd ACM Symposium on Principles of Distributed Computing (PODC’14). ACM, New York, NY, 332--340.

[17]

F. Ellen, P. Fatourou, E. Ruppert, and F. van Breugel. 2010. Non-blocking binary search trees. In Proceedings of the 29th ACM Symposium on Principles of Distributed Computing (PODC’10). ACM, New York, NY, 131--140.

Digital Library

[18]

P. Fatourou and N. D. Kallimanis. 2011. A highly-efficient wait-free universal construction. In Proceedings of the 23rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA’11). ACM, New York, NY, 325--334.

[19]

M. Fomitchev and E. Ruppert. 2004. Lock-free linked lists and skiplists. In Proceedings of the 23rd ACM Symposium on Principles of Distributed Computing (PODC’04). ACM, New York, NY, 50--59.

[20]

K. Fraser and T. L. Harris. 2007. Concurrent programming without locks. ACM Trans. Comput. Syst. 25, 2, Article 5 (May 2007), 59 pages.

Digital Library

[21]

V. Gramoli. 2015. More than you ever wanted to know about synchronization: Synchrobench, measuring the impact of the synchronization on concurrent algorithms. In Proceedings of the 20th ACM Symposium on Principles and Practice of Parallel Programming (PPoPP’15). ACM, New York, NY, 1--10.

Digital Library

[22]

T. Harris. 2001. A pragmatic implementation of non-blocking linked-lists. In Proceedings of the Symposium on Distributed Computing (DISC’01). Springer-Verlag, Berlin, Germany, 300--314.

[23]

M. Herlihy. 1991. Wait-free synchronization. ACM Trans. Program. Lang. Syst. 13, 1 (Jan. 1991), 124--149.

Digital Library

[24]

M. Herlihy. 1993. A methodology for implementing highly concurrent objects. ACM Trans. Program. Lang. Syst. 15, 5 (1993), 745--770.

Digital Library

[25]

M. Herlihy, V. Luchangco, and M. Moir. 2003. Obstruction-free synchronization: Double-ended queues as an example. In Proceedings of the 23rd IEEE International Conference on Distributed Computing Systems (ICDCS’03). IEEE Computer Society, Washington, DC, 522--529.

[26]

M. Herlihy and N. Shavit. 2012. The Art of Multiprocessor Programming, Revised Reprint. Morgan Kaufmann, Burlington, Massachusetts.

[27]

M. Herlihy and J. M. Wing. 1990. Linearizability: A correctness condition for concurrent objects. ACM Trans. Program. Lang. Syst. 12, 3 (July 1990), 463--492.

Digital Library

[28]

S. V. Howley and J. Jones. 2012. A non-blocking internal binary search tree. In Proceedings of the 24th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA’12). ACM, New York, NY, 161--171.

[29]

Intel 2017. Intel 64 and IA-32 Architectures Software Developer’s Manual, Volume 2A: Instruction Set Reference, A-M. Intel. Retrieved from https://software.intel.com/sites/default/files/managed/39/c5/325462-sdm-vol-1-2abcd-3abcd.pdf.

[30]

M. M. Michael. 2002. High performance dynamic lock-free hash tables and list-based sets. In Proceedings of the 14th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA’02). ACM, New York, NY, 73--82.

Digital Library

[31]

A. Natarajan and N. Mittal. 2013. Brief announcement: A concurrent lock-free red-black tree. In Proceedings of the 27th Symposium on Distributed Computing (DISC’13). Springer-Verlag, Berlin, Germany, 565--566.

[32]

A. Natarajan and N. Mittal. 2014. Fast concurrent lock-free binary search trees. In Proceedings of the 19th ACM Symposium on Principles and Practice of Parallel Programming (PPoPP’14). ACM, New York, NY, 317--328.

[33]

A Natarajan, L. H. Savoie, and N. Mittal. 2013. Concurrent wait-free red-black trees. In Proceedings of the 15th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS’13). Springer-Verlag, Berlin, Germany, 45--60.

[34]

A. Prokopec. 2018. Cache-tries: Concurrent lock-free hash tries with constant-time operations. In Proceedings of the 23rd ACM Symposium on Principles and Practice of Parallel Programming (PPoPP’18). 137--151.

Digital Library

[35]

A. Prokopec, N. G. Bronson, P. Bagwell, and M. Odersky. 2012. Concurrent tries with efficient non-blocking snapshots. In Proceedings of the 17th ACM Symposium on Principles and Practice of Parallel Programming (PPoPP’12). ACM, New York, NY, 151--160.

[36]

A. Ramachandran and N. Mittal. 2015a. A fast lock-free internal binary search tree. In Proceedings of the 16th International Conference on Distributed Computing and Networking (ICDCN’15). ACM, New York, NY, Article 37, 10 pages.

[37]

A. Ramachandran and N. Mittal. 2015b. CASTLE: Fast concurrent internal binary search tree using edge-based locking. In Proceedings of the 20th ACM Symposium on Principles and Practice of Parallel Programming (PPoPP’15). ACM, New York, NY, 281--282.

[38]

J. Reinders. 2007. Intel Threading Building Blocks: Outfitting C++ for Multi-Core Processor Parallelism. O’Reilly Media, Inc., Sebastopol, CA.

[39]

N. Shafiei. 2013. Non-blocking patricia tries with replace operations. In Proceedings of the 33rd IEEE International Conference on Distributed Computing Systems (ICDCS’13). IEEE Computer Society, Washington, DC, 216--225.

Digital Library

[40]

Stampede2 2019. Stampede2 User Guide. Retrieved from https://portal.tacc.utexas.edu/user-guides/stampede2.

[41]

H. Sundell and P. Tsigas. 2004. Scalable and lock-free concurrent dictionaries. In Proceedings of the 19th ACM Symposium on Applied Computing (SAC’04). ACM, New York, NY, 1438--1445.

Cited By

Bhardwaj GChatterjee BSharma APeri SNayak S(2024)Kanva: A Lock-free Learned Search Data StructureProceedings of the 53rd International Conference on Parallel Processing10.1145/3673038.3673082(252-261)Online publication date: 12-Aug-2024
https://dl.acm.org/doi/10.1145/3673038.3673082
Fatourou PKosmas EPalpanas TPaterakis G(2023)FreSh: A Lock-Free Data Series Index2023 42nd International Symposium on Reliable Distributed Systems (SRDS)10.1109/SRDS60354.2023.00029(209-220)Online publication date: 25-Sep-2023
https://doi.org/10.1109/SRDS60354.2023.00029
Attiya HBen-Baruch OFatourou PHendler DKosmas ELee JAgrawal KSpear M(2022)Detectable recovery of lock-free data structuresProceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming10.1145/3503221.3508444(262-277)Online publication date: 2-Apr-2022
https://dl.acm.org/doi/10.1145/3503221.3508444
Show More Cited By

Index Terms

FEAST: A Lightweight Lock-free Concurrent Binary Search Tree
1. Computing methodologies
  1. Concurrent computing methodologies
    1. Concurrent algorithms
2. Theory of computation
  1. Design and analysis of algorithms
    1. Concurrent algorithms

Recommendations

Fast concurrent lock-free binary search trees
PPoPP '14

We present a new lock-free algorithm for concurrent manipulation of a binary search tree in an asynchronous shared memory system that supports search, insert and delete operations. In addition to read and write instructions, our algorithm uses (single-...
Fast concurrent lock-free binary search trees
PPoPP '14: Proceedings of the 19th ACM SIGPLAN symposium on Principles and practice of parallel programming

We present a new lock-free algorithm for concurrent manipulation of a binary search tree in an asynchronous shared memory system that supports search, insert and delete operations. In addition to read and write instructions, our algorithm uses (single-...
A Fast Lock-Free Internal Binary Search Tree
ICDCN '15: Proceedings of the 16th International Conference on Distributed Computing and Networking

We present a new lock-free algorithm for concurrent manipulation of a binary search tree in an asynchronous shared memory system that supports search, insert and delete operations. It combines ideas from two recently proposed lock-free algorithms: one ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Parallel Computing

ACM Transactions on Parallel Computing Volume 7, Issue 2

June 2020

182 pages

ISSN:2329-4949

EISSN:2329-4957

DOI:10.1145/3400890

Editor:
David A. Bader
New Jersey Institute of Technology, USA

Issue’s Table of Contents

Copyright © 2020 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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 18 May 2020

Online AM: 07 May 2020

Accepted: 01 December 2019

Revised: 01 November 2019

Received: 01 August 2017

Published in TOPC Volume 7, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

National Science Foundation

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
420
Total Downloads

Downloads (Last 12 months)46
Downloads (Last 6 weeks)19

Reflects downloads up to 24 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Bhardwaj GChatterjee BSharma APeri SNayak S(2024)Kanva: A Lock-free Learned Search Data StructureProceedings of the 53rd International Conference on Parallel Processing10.1145/3673038.3673082(252-261)Online publication date: 12-Aug-2024
https://dl.acm.org/doi/10.1145/3673038.3673082
Fatourou PKosmas EPalpanas TPaterakis G(2023)FreSh: A Lock-Free Data Series Index2023 42nd International Symposium on Reliable Distributed Systems (SRDS)10.1109/SRDS60354.2023.00029(209-220)Online publication date: 25-Sep-2023
https://doi.org/10.1109/SRDS60354.2023.00029
Attiya HBen-Baruch OFatourou PHendler DKosmas ELee JAgrawal KSpear M(2022)Detectable recovery of lock-free data structuresProceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming10.1145/3503221.3508444(262-277)Online publication date: 2-Apr-2022
https://dl.acm.org/doi/10.1145/3503221.3508444
Rukundo ATsigas P(2021)TSLQueue: An Efficient Lock-Free Design for Priority QueuesEuro-Par 2021: Parallel Processing10.1007/978-3-030-85665-6_24(385-401)Online publication date: 1-Sep-2021
https://dl.acm.org/doi/10.1007/978-3-030-85665-6_24

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 Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

Media

Figures

Other

Tables

View Issue’s Table of Contents