Fast and scalable, lock-free k-FIFO queues

Abstract. We introduce fast and scalable algorithms that implement bounded-and unbounded-size lock-free k-FIFO queues on parallel, shared memory hard-ware. Logically, a k-FIFO queue can be understood as queue where elements may be dequeued out-of-order up to k−1, or as pool where the oldest element is de-queued within at most k dequeue operations. The presented algorithms enable up to k enqueue and k dequeue operations to be performed in parallel. Unlike previ-ous designs, however, the algorithms also implement linearizable emptiness (and full) checks without impairing scalability. We show experimentally that there ex-ist optimal and robust k that result in best access performance and scalability. We then demonstrate that our algorithms outperform and outscale all state-of-the-art concurrent pool and queue algorithms that we considered in all micro-and most macrobenchmarks. Moreover, we demonstrate a prototypical controller which identifies optimal k automatically at runtime achieving better performance than with any statically configured k.