The MultiQueue: A Simple and Fast Relaxed Concurrent Priority Queue

Priority queues are used in a wide range of applications, including prioritized online scheduling, discrete event simulation, and greedy algorithms. In parallel settings, classical priority queues often become a severe bottleneck, resulting in low throughput. Consequently, there has been significant interest in concurrent priority queues with relaxed semantics. In this article, we present the MultiQueue , a highly scalable and flexible relaxed priority queue. Its design is based on leveraging multiple internal priority queues using the seemingly paradoxical technique of “wait-free locking”. The practical performance of the MultiQueue is further enhanced by element buffering, batched operations on the internal queues, and cache-optimized access patterns. We evaluate the quality-throughput tradeoff of the MultiQueue against state-of-the-art competitors. The quality is measured using two complementary metrics: rank error (the distance of a deleted element to the best element), and delay (the number of elements with lower priority deleted before a given element). Extensive experiments on both micro-benchmarks and benchmarks based on real-world applications (shortest-path and branch-and-bound) show that the MultiQueue consistently outperforms its competitors. Additionally, its design allows users to easily tune the balance between throughput and quality to meet specific application requirements, and we believe that “wait-free locking” may be of broader interest for converting sequential data structures into high-performance, relaxed concurrent ones.