wCQ: A FastWait-Free Queue with Bounded Memory Usage

Ruslan Nikolaev, Binoy Ravindran

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationSPAA 2022 - Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures
PublisherAssociation for Computing Machinery
Pages307-319
Number of pages13
ISBN (Electronic)9781450391467
DOIs
StatePublished - Jul 11 2022
Event34th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2022 - Philadelphia, United States
Duration: Jul 11 2022Jul 14 2022

Publication series

NameAnnual ACM Symposium on Parallelism in Algorithms and Architectures

Conference

Conference34th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2022
Country/TerritoryUnited States
CityPhiladelphia
Period7/11/227/14/22

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture

Fingerprint

Dive into the research topics of 'wCQ: A FastWait-Free Queue with Bounded Memory Usage'. Together they form a unique fingerprint.

Cite this