BlockFIFO & MultiFIFO: Scalable Relaxed Queues

Stefan Koch, Peter Sanders, Marvin Williams · 2025

Read BlockFIFO & MultiFIFO: Scalable Relaxed Queues by Stefan Koch, Peter Sanders, Marvin Williams (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-22764.txt.

Introduction

Stefan Koch, Peter Sanders, and Marvin Williams present two faster queue designs for programs where many threads share one line. Strict first-in-first-out queues bottleneck because every thread contends at the head and tail. Allowing a little reordering, as relaxed queues do, unlocks far more throughput.

BlockFIFO grows out of ring buffers, while MultiFIFO adapts the MultiQueue idea, giving two orthogonal designs. Extensive micro-benchmarks plus a breadth-first search over large graphs tested both. Each beat the best existing relaxed and strict queues on throughput and scaling. The authors argue relaxed semantics, carefully bounded, are the practical future for concurrent queues in parallel software.

Catalog record

CREATORStefan Koch, Peter Sanders, Marvin Williams
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE56 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-22764

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

BlockFIFO & MultiFIFO: Scalable Relaxed Queues Stefan Koch, Peter Sanders, Marvin Williams Abstract FIFO queues are a fundamental data structure used in a wide range of applications. Concurrent FIFO queues allow multiple execution threads to access the queue simultaneously. Maintaining strict FIFO semantics in concurrent queues leads to low throughput due to high contention at the head and tail of the queue. By relaxing the FIFO semantics to allow some reordering of elements, it becomes possible to achieve much higher scalability. This work presents two orthogonal designs for relaxed concurrent FIFO queues, one derived from the MultiQueue and the other based on ring buffers. We evaluate both designs extensively on various micro-benchmarks and a breadth-first search application on large graphs. Both designs outperform state-of-the-art relaxed and strict FIFO queues, achieving higher throughput and better scalability. Karlsruhe Institute of [email protected] Karlsruhe Institut of Technology, [email protected]://orcid.org/0000-0003-3330-9349 Karlsruhe Institut of Technology, [email protected]://orcid.org/0000-0002-1990-0899 {CCSXML} ¡ccs2012¿ ¡concept¿ ¡concept_id¿10010147.10011777¡/concept_id¿ ¡concept_desc¿Computing methodologies Concurrent computing methodologies¡/concept_desc¿ ¡concept_significance¿500¡/concept_significance¿ ¡/concept¿ ¡/ccs2012¿ ccs Computing methodologies Concurrent computing methodologies keywords concurrent data structure, FIFO queues, relaxed semantics † † runningauthor: S. Koch and P. Sanders and M. Williams † † copyright: S. Koch and P. Sanders and M. Williams 1 Introduction FIFO (First-in first-out) queues are data structures that support the insertion of elements ( push ) and the deletion of the least recently inserted element ( pop ). They are at the core of a wide range of applications, including breadth-first search, processing pipelines, message queues, and network routers. Sequential implementations using circular arrays are fast and cache-efficient, offering high throughput with constant-time operations. As most performance-critical computations today use parallel hardware, concurrent queues have become increasingly important. Indeed, in many applications, a concurrent queue serves as the central coordination mechanism among threads. For example, multiple threads may concurrently produce and consume data items from the queue, or, in a breadth-first traversal of a graph, the queue may hold the nodes yet to be explored. Ideally, using p threads, one would like the throughput to be close to p times the throughput of a sequential queue. Unfortunately, high contention on the head and tail pointers of the queue is unavoidable [ 5 , 2 ] , and even sophisticated implementations of concurrent queues with strict semantics (e.g., [ 17 , 18 , 20 ] ) suffer from poor scalability. The throughput remains constant or might even deteriorate with increasing numbers of threads. Thus, such designs are not suitable for situations that require a high throughput with many threads. In order to achieve higher scalability, the idea of relaxing the semantics of queues and similar data structures in order to benefit from reduced contention has become an increasingly relevant topic of study [ 1 , 15 , 12 , 24 , 26 ] . We say that a popped element has rank error r when it was pushed later than r other elements. We introduce two concurrent relaxed FIFO queues with particularly good scalability: The MultiFIFO (see section 4 ) is an adaptation of the MultiQueue [ 19 , 27 , 26 ] , a state-of-the-art relaxed priority queue that uses \BigO(p) sequential FIFO queues internally. Pushed elements go to a random queue, along with their insertion time stamp. Pops remove the least recent element from two randomly chosen queues. The MultiFIFO has expected constant time per operation and inherits a rank error linear in p from the MultiQueue. By making threads reuse the same internal queues for a fixed number of consecutive operations, performance can be further increased at the cost of higher rank errors. The BlockFIFO (see section 5 ) is based on a ring buffer of small FIFO blocks, where threads operate on different blocks to reduce contention. It exhibits even higher throughput than the MultiFIFO in its most relaxed configurations. Summary of Contributions • Introduction of two highly scalable relaxed concurrent FIFOs—MultiFIFO and BlockFIFO. • Extensive experiments ( section 6 ) on different architectures and benchmarks indicating an order-of-magnitude improved throughput of the new FIFO queues compared to the previous state of the art. 2 Preliminaries The first-in first-out (FIFO) queue is a data structure that manages a dynamic sequence of elements, supporting the following two operations: push Insert an element at the end ( tail ) of the sequence. pop Remove and return the element at the front ( head ) of the sequence. If a FIFO is empty, the pop operation fails and returns the special element \bot , which cannot be inserted. Bounded FIFO queues have a fixed capacity of elements, and pushing into to a full bounded FIFO conventionally fails 1 1 1 Other semantics, such as overwriting the oldest element or allocating more space, are possible. . A common bounded FIFO queue is the ring buffer (or circular buffer ), which conceptually arranges the slots for elements in a circular manner. Ring buffers are typically implemented as contiguous fixed-size arrays with head and tail pointers indicating the next slot to pop from and push into, respectively. These pointers are incremented by the corresponding operations and wrap around to the beginning when they reach the end of the array. Concurrent FIFO queues allow concurrent push and pop operations by multiple threads. Linearizability [ 13 ] is a popular consistency criterion for specifying the semantics of concurrent data structures with respect to their sequential counterparts. Essentially, a concurrent data structure is linearizable if each operation appears to execute instantly at a single point in time (its linearization point ) between its invocation and response. Linearizability is generally highly desirable: with non-overlapping operations, the data structure behaves like a sequential one, and concurrent executions offer strong and intuitive guarantees. Unfortunately, linearizable FIFO queue implementations suffer from high contention and exhibit limited scalability [ 2 ] . To alleviate this issue, the semantics of FIFO queues can be relaxed , allowing the pop operation to remove elements out-of-order, or even fail to remove elements that are still in the queue. For many applications, it is useful for failed pops to be linearizable, meaning that popping may only fail if the queue was empty at some point during the operation. A natural quality metric for the degree of relaxation is the rank error : For an element e that was returned by a pop operation, the rank error of the pop operation is the number of elements in the queue that were inserted before e . An algorithm is lock-free if at least one thread is guaranteed to make progress towards completing an operation within a bounded number of steps, regardless of the actions of other threads. The ABA problem arises when a thread reads the same value A from a shared memory location twice, incorrectly assuming the value has not changed between the reads, even though it was changed to B and then back to A by other threads. We denote p as the (maximum) number of threads participating in an algorithm concurrently. An event occurs with high probability (with respect to p ) if the probability is at least 1-p^{-a} for some constant a\geq 1 . 3 Related Work The FIFO queue is a conceptually simple data structure that appears in most introductory algorithm textbooks (e.g.,

Read the complete text