research-article

Open access

wCQ: A Fast Wait-Free Queue with Bounded Memory Usage

Authors:

Ruslan Nikolaev,

Binoy RavindranAuthors Info & Claims

SPAA '22: Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures

Pages 307 - 319

https://doi.org/10.1145/3490148.3538572

Published: 11 July 2022 Publication History

Abstract

The concurrency literature presents a number of approaches for building non-blocking, FIFO, multiple-producer and multiple-consumer (MPMC) queues. However, only a fraction of them have high performance. In addition, many queue designs, such as LCRQ, trade memory usage for better performance. The recently proposed SCQ design achieves both memory efficiency as well as excellent performance. Unfortunately, both LCRQ and SCQ are only lock-free. On the other hand, existing wait-free queues are either not very performant or suffer from potentially unbounded memory usage. Strictly described, the latter queues, such as Yang & Mellor-Crummey's (YMC) queue, forfeit wait-freedom as they are blocking when memory is exhausted. We present a wait-free queue, called wCQ. wCQ is based on SCQ and uses its own variation of fast-path-slow-path methodology to attain wait-freedom and bound memory usage. Our experimental studies on x86 and PowerPC architectures validate wCQ's great performance and memory efficiency. They also show that wCQ's performance is often on par with the best known concurrent queue designs.

References

[1]

Vitaly Aksenov, Nikita Koval, and Petr Kuznetsov. 2022. Memory-Optimality for Non-Blocking Containers. https://arxiv.org/abs/2104.15003

[2]

ARM. 2022. ARM Architecture Reference Manual. http://developer.arm.com/.

[3]

Nachshon Cohen. 2018. Every Data Structure Deserves Lock-free Memory Reclamation. Proc. ACM Program. Lang. 2, OOPSLA, Article 143 (Oct. 2018), 24 pages. https://doi.org/10.1145/3276513

Digital Library

[4]

Andreia Correia, Pedro Ramalhete, and Pascal Felber. 2021. OrcGC: Automatic Lock-Free Memory Reclamation. In Proceedings of the 26th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP '21). ACM, 205--218. https://doi.org/10.1145/3437801.3441596

Digital Library

[5]

DPDK Developers. 2022. Data Plane Development Kit (DPDK). https://dpdk.org/.

[6]

Jason Evans. 2006. A scalable concurrent malloc(3) implementation for FreeBSD. In Proceedings of the BSDCan Conference, Ottawa, Canada. https://www.bsdcan. org/2006/papers/jemalloc.pdf

[7]

Panagiota Fatourou and Nikolaos D. Kallimanis. 2011. A Highly-Efficient Wait- Free Universal Construction. In Proceedings of the 23rd Annual ACM Symposium on Parallelism in Algorithms and Architectures (San Jose, California, USA) (SPAA '11). ACM, NewYork, NY, USA, 325--334. https://doi.org/10.1145/1989493.1989549

Digital Library

[8]

Panagiota Fatourou and Nikolaos D. Kallimanis. 2012. Revisiting the Combining Synchronization Technique. In Proceedings of the 17th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (New Orleans, Louisiana, USA) (PPoPP '12). ACM, New York, NY, USA, 257--266. https://doi.org/10.1145/2145816. 2145849

Digital Library

[9]

Steven Feldman and Damian Dechev. 2015. A Wait-free Multi-producer Multiconsumer Ring Buffer. ACM SIGAPP Applied Computing Review 15, 3 (Oct. 2015), 59--71. https://doi.org/10.1145/2835260.2835264

Digital Library

[10]

Eric Freudenthal and Allan Gottlieb. 1991. Process Coordination with Fetchand- increment. In Proceedings of the 4th International Conference on Architectural Support for Programming Languages and Operating Systems (Santa Clara, California, USA) (ASPLOS IV). 260--268. https://doi.org/10.1145/106972.106998

Digital Library

[11]

Oliver Giersch and Jörg Nolte. 2022. Fast and Portable Concurrent FIFO Queues With Deterministic Memory Reclamation. IEEE Trans. on Parallel and Distributed Systems 33, 3 (2022), 604--616. https://doi.org/10.1109/TPDS.2021.3097901

[12]

Danny Hendler, Nir Shavit, and Lena Yerushalmi. 2004. A Scalable Lock-free Stack Algorithm. In Proceedings of the 16th ACM Symposium on Parallelism in Algorithms and Architectures (Barcelona, Spain) (SPAA '04). ACM, New York, NY, USA, 206--215. https://doi.org/10.1145/1007912.1007944

Digital Library

[13]

Maurice P. Herlihy and Jeannette M. Wing. 1990. Linearizability: A Correctness Condition for Concurrent Objects. ACM Trans. Program. Lang. Syst. 12, 3 (jul 1990), 463--492. https://doi.org/10.1145/78969.78972

Digital Library

[14]

IBM. 2005. PowerPC Architecture Book, Version 2.02. Book I: PowerPC User Instruction Set Architecture. http://www.ibm.com/developerworks/.

[15]

Intel. 2022. Intel 64 and IA-32 Architectures Developer's Manual. http://www. intel.com/.

[16]

Giorgos Kappes and Stergios V. Anastasiadis. 2021. POSTER: A Lock-Free Relaxed Concurrent Queue for Fast Work Distribution. In Proceedings of the 26th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (Virtual Event, Republic of Korea) (PPoPP '21). ACM, New York, NY, USA, 454--456. https: //doi.org/10.1145/3437801.3441583

Digital Library

[17]

Christoph M. Kirsch, Michael Lippautz, and Hannes Payer. 2013. Fast and Scalable, Lock-Free k-FIFO Queues. In Proceedings of the 12th International Conference on Parallel Computing Technologies - Volume 7979. Springer-Verlag, Berlin, Heidelberg, 208--223. https://doi.org/10.1007/978--3--642--39958--9_18

[18]

Alex Kogan and Erez Petrank. 2011. Wait-free Queues with Multiple Enqueuers and Dequeuers. In Proceedings of the 16th ACM Symposium on Principles and Practice of Parallel Programming (San Antonio, TX, USA) (PPoPP '11). ACM, New York, NY, USA, 223--234. https://doi.org/10.1145/1941553.1941585

Digital Library

[19]

Alex Kogan and Erez Petrank. 2012. A Methodology for Creating Fast Wait-free Data Structures. In Proceedings of the 17th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (New Orleans, Louisiana, USA) (PPoPP '12). ACM, New York, NY, USA, 141--150. https://doi.org/10.1145/2145816.2145835

Digital Library

[20]

Nikita Koval and Vitaly Aksenov. 2020. POSTER: Restricted Memory-Friendly Lock-Free Bounded Queues. In Proceedings of the 25th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (San Diego, California) (PPoPP '20). ACM, NewYork, NY, USA, 433--434. https://doi.org/10.1145/3332466.3374508

Digital Library

[21]

Alexander Krizhanovsky. 2013. Lock-free Multi-producer Multi-consumer Queue on Ring Buffer. Linux J. 2013, 228, Article 4 (2013).

[22]

Leslie Lamport. 1979. How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs. IEEE Trans. Comput. 28, 9 (Sept. 1979), 690--691.

[23]

Liblfds. 2022. Lock-free Data Structure Library. https://www.liblfds.org.

[24]

Liblfds. 2022. Ringbuffer disappointment 2016-04--29. https://www.liblfds.org/ slblog/index.html.

[25]

Lockless Inc. 2022. Memory Allocator Benchmarks. https://locklessinc.com.

[26]

Maged M. Michael and Michael L. Scott. 1998. Nonblocking Algorithms and Preemption-Safe Locking on Multiprogrammed Shared Memory Multiprocessors. J. Parallel and Distrib. Comput. 51, 1 (May 1998), 1--26. https://doi.org/10.1006/ jpdc.1998.1446

Digital Library

[27]

Gal Milman, Alex Kogan, Yossi Lev, Victor Luchangco, and Erez Petrank. 2018. BQ: A Lock-Free Queue with Batching. In Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures (Vienna, Austria) (SPAA '18). ACM, New York, NY, USA, 99--109. https://doi.org/10.1145/3210377.3210388

Digital Library

[28]

MIPS. 2022. MIPS32/MIPS64 Rev. 6.06. http://www.mips.com/products/ architectures/.

[29]

Mark Moir, Daniel Nussbaum, Ori Shalev, and Nir Shavit. 2005. Using Elimination to Implement Scalable and Lock-free FIFO Queues. In Proceedings of the 17th ACM Symposium on Parallelism in Algorithms and Architectures (Las Vegas, Nevada, USA) (SPAA '05). 253--262. https://doi.org/10.1145/1073970.1074013

Digital Library

[30]

Adam Morrison and Yehuda Afek. 2013. Fast Concurrent Queues for x86 Processors. In Proceedings of the 18th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (Shenzhen, China) (PPoPP '13). ACM, New York, NY, USA, 103--112. https://doi.org/10.1145/2442516.2442527

Digital Library

[31]

Ruslan Nikolaev. 2019. A Scalable, Portable, and Memory-Efficient Lock-Free FIFO Queue. In 33rd International Symposium on Distributed Computing (DISC 2019) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 146), Jukka Suomela (Ed.). Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 28:1--28:16. https://doi.org/10.4230/LIPIcs.DISC.2019.28

[32]

Ruslan Nikolaev and Binoy Ravindran. 2019. Brief Announcement: Hyaline: Fast and Transparent Lock-Free Memory Reclamation. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (Toronto ON, Canada) (PODC '19). ACM, NewYork, NY, USA, 419--421. https://doi.org/10.1145/3293611.3331575

Digital Library

[33]

Ruslan Nikolaev and Binoy Ravindran. 2020. Universal Wait-Free Memory Reclamation. In Proceedings of the 25th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. ACM, New York, NY, USA, 130--143. https: //doi.org/10.1145/3332466.3374540

Digital Library

[34]

Ruslan Nikolaev and Binoy Ravindran. 2021. Brief Announcement: Crystalline: Fast and Memory Efficient Wait-Free Reclamation. In 35th International Symposium on Distributed Computing (DISC 2021) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 209), Seth Gilbert (Ed.). Schloss Dagstuhl -- Leibniz- Zentrum für Informatik, Dagstuhl, Germany, 60:1--60:4. https://doi.org/10.4230/ LIPIcs.DISC.2021.60

[35]

Ruslan Nikolaev and Binoy Ravindran. 2021. Snapshot-Free, Transparent, and Robust Memory Reclamation for Lock-Free Data Structures. In Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation. ACM, New York, NY, USA, 987--1002. https://doi.org/10. 1145/3453483.3454090

Digital Library

[36]

Ruslan Nikolaev and Binoy Ravindran. 2022. POSTER: wCQ: A Fast Wait-Free Queue with Bounded Memory Usage. In Proceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (Seoul, Republic of Korea) (PPoPP '22). ACM, New York, NY, USA, 461--462. https://doi.org/10.1145/ 3503221.3508440

Digital Library

[37]

Pedro Ramalhete and Andreia Correia. 2016. A Wait-Free Queue with Wait- Free Memory Reclamation (Complete Paper). https://github.com/pramalhe/ ConcurrencyFreaks/blob/master/papers/crturnqueue-2016.pdf

[38]

Pedro Ramalhete and Andreia Correia. 2017. Brief Announcement: Hazard Eras - Non-Blocking Memory Reclamation. In Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures (Washington, DC, USA) (SPAA '17). ACM, New York, NY, USA, 367--369. https://doi.org/10.1145/3087556.3087588

Digital Library

[39]

Pedro Ramalhete and Andreia Correia. 2017. POSTER: A Wait-Free Queue with Wait-Free Memory Reclamation. In Proceedings of the 22nd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (Austin, Texas, USA) (PPoPP '17). ACM, New York, NY, USA, 453--454. https://doi.org/10.1145/ 3018743.3019022

Digital Library

[40]

Susmit Sarkar, Kayvan Memarian, Scott Owens, Mark Batty, Peter Sewell, Luc Maranget, Jade Alglave, and Derek Williams. 2012. Synchronising C/C++ and POWER. In Proceedings of the 33rd ACM SIGPLAN Conference on Programming Language Design and Implementation (Beijing, China) (PLDI '12). ACM, New York, NY, USA, 311--322. https://doi.org/10.1145/2254064.2254102

Digital Library

[41]

SPDK Developers. 2022. Storage Performance Development Kit. https://spdk.io/.

[42]

Philippas Tsigas and Yi Zhang. 2001. A Simple, Fast and Scalable Non-blocking Concurrent FIFO Queue for Shared Memory Multiprocessor Systems. In Proceedings of the 13th ACM Symposium on Parallel Algorithms and Architectures (Crete Island, Greece) (SPAA '01). 134--143. https://doi.org/10.1145/378580.378611

Digital Library

[43]

Dmitry Vyukov. 2022. Bounded MPMC queue. http://www.1024cores.net/home/ lock-free-algorithms/queues/bounded-mpmc-queue.

[44]

Haosen Wen, Joseph Izraelevitz, Wentao Cai, H. Alan Beadle, and Michael L. Scott. 2018. Interval-Based Memory Reclamation. In Proceedings of the 23rd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (Vienna, Austria) (PPoPP '18). ACM, New York, NY, USA, 1--13. https://doi.org/10.1145/ 3178487.3178488

Digital Library

[45]

Chaoran Yang and John Mellor-Crummey. 2016. A Wait-free Queue As Fast As Fetch-and-add. In Proceedings of the 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (Barcelona, Spain) (PPoPP '16). ACM, New York, NY, USA, Article 16, 13 pages. https://doi.org/10.1145/2851141.2851168

Digital Library

Cited By

Nikolaev RRavindran B(2024)A Family of Fast and Memory Efficient Lock- and Wait-Free ReclamationProceedings of the ACM on Programming Languages10.1145/36588518:PLDI(2174-2198)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3658851
Naderibeni HRuppert E(2024)A wait-free queue with polylogarithmic step complexityDistributed Computing10.1007/s00446-024-00471-737:4(309-334)Online publication date: 17-Aug-2024
https://doi.org/10.1007/s00446-024-00471-7
Naderibeni HRuppert EOshman RNolin AHalldorsson MBalliu A(2023)A Wait-free Queue with Polylogarithmic Step ComplexityProceedings of the 2023 ACM Symposium on Principles of Distributed Computing10.1145/3583668.3594565(124-134)Online publication date: 19-Jun-2023
https://dl.acm.org/doi/10.1145/3583668.3594565

Index Terms

wCQ: A Fast Wait-Free Queue with Bounded Memory Usage
1. Theory of computation
  1. Design and analysis of algorithms
    1. Concurrent algorithms

Recommendations

wCQ: a fast wait-free queue with bounded memory usage
PPoPP '22: Proceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming

The concurrency literature presents a number of approaches for building non-blocking, FIFO, multiple-producer and multiple-consumer (MPMC) queues. However, existing wait-free queues are either not very scalable or suffer from potentially unbounded memory ...
A wait-free queue as fast as fetch-and-add
PPoPP '16: Proceedings of the 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming

Concurrent data structures that have fast and predictable performance are of critical importance for harnessing the power of multicore processors, which are now ubiquitous. Although wait-free objects, whose operations complete in a bounded number of ...
A scalable multi-producer multi-consumer wait-free ring buffer
SAC '15: Proceedings of the 30th Annual ACM Symposium on Applied Computing

A ring buffer or cyclical queue is a First In, First Out (FIFO) queue that stores elements on a fixed-length array. This allows for efficient O(1) operations, cache-aware optimizations, and low memory overhead. Because ring buffers are limited to only ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SPAA '22: Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures

July 2022

464 pages

ISBN:9781450391467

DOI:10.1145/3490148

General Chair:
Kunal Agrawal
Washington University in St. Louis, USA
,
Program Chair:
I-Ting Angelina Lee
Washington University in St. Louis, USA

Copyright © 2022 Owner/Author.

This work is licensed under a Creative Commons Attribution International 4.0 License.

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGARCH: ACM Special Interest Group on Computer Architecture
EATCS: European Association for Theoretical Computer Science

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 July 2022

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Conference

SPAA '22

Sponsor:

SPAA '22: 34th ACM Symposium on Parallelism in Algorithms and Architectures

July 11 - 14, 2022

PA, Philadelphia, USA

Acceptance Rates

Overall Acceptance Rate 447 of 1,461 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
983
Total Downloads

Downloads (Last 12 months)442
Downloads (Last 6 weeks)69

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Nikolaev RRavindran B(2024)A Family of Fast and Memory Efficient Lock- and Wait-Free ReclamationProceedings of the ACM on Programming Languages10.1145/36588518:PLDI(2174-2198)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3658851
Naderibeni HRuppert E(2024)A wait-free queue with polylogarithmic step complexityDistributed Computing10.1007/s00446-024-00471-737:4(309-334)Online publication date: 17-Aug-2024
https://doi.org/10.1007/s00446-024-00471-7
Naderibeni HRuppert EOshman RNolin AHalldorsson MBalliu A(2023)A Wait-free Queue with Polylogarithmic Step ComplexityProceedings of the 2023 ACM Symposium on Principles of Distributed Computing10.1145/3583668.3594565(124-134)Online publication date: 19-Jun-2023
https://dl.acm.org/doi/10.1145/3583668.3594565

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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

Media

Figures

Other

Tables

View Table of Contents