Correct and Efficient Bounded FIFO Queues

• Nhat Minh Lê INRIA / ÉNS
• Adrien Guatto INRIA / ÉNS
• Albert Cohen INRIA / ÉNS
• Antoniu Pop INRIA / ÉNS

Abstract

Bounded single-producer single-consumer FIFO queues are one of the simplest concurrent data-structure, and they do not require more than sequential consistency for correct operation. Still, sequential consistency is an unrealistic hypothesis on shared-memory multiprocessors, and enforcing it through memory barriers induces significant performance and energy overhead. This paper revisits the optimization and correctness proof of bounded FIFO queues in the context of weak memory consistency, building upon the recent axiomatic formalization of the C11 memory model. We validate the portability and performance of our proven implementation over 3 processor architectures with diverse hardware memory models, including ARM and PowerPC. Comparison with state-of-the-art implementations demonstrate consistent improvements for a wide range of buffer and batch sizes.

Keywords: Indexes, Instruction sets, Arrays, Radio frequency, Load modeling, Memory management, FIFO queue, lock-free algorithm, weak memory model, % data-flow programming, Kahn process network