A comparative study of concurrent queueing algorithms and their performance

Abstract

Queues are among the most ubiquitous data structures in the field of Computing Science. With the advent of multiprocessor programming, concurrent queues are at the core of many concurrent and distributed algorithms. We were able to identify few studies surveying and replicating concurrent queuing algorithms from their seminal works. This work is an experimental study, with the aim of comparing the performance of multiple concurrent queues with one another, under different levels of contention, whilst replicating the results of other researchers. The production of a benchmarking framework for concurrent queues also forms part of this study’s contributions. We successfully replicate results to support the claims that non-blocking queues are superior to blocking ones under high contention, and remain competitive under low contention. We also expose a number of unreported, yet significant biases in a number of classical works. A limiting factor of this study is that each algorithm is benchmarked on consumer-grade hardware, fortunately, the benchmarking framework is developed to run on multiple machines, making this limitation transient in scope.