Fast and Scalable k-FIFO Queues
Christoph M. Kirsch, Michael Lippautz, Hannes Payer · 2012
We introduce fast and scalable algorithms that implement bounded- and unbounded-size, lock-free, linearizable k-FIFO queues with empty (and full) check. Logically, a k-FIFO queue can be understood as queue where each element may be dequeued out-of-order up to k − 1 or as pool where each element is dequeued within a k-bounded number of dequeue operations. We show experimentally that there exist optimal and robust k that result in best performance and scalability. We then demonstrate that our algorithms outperform and outscale many state-of-the-art concurrent queue and pool algorithms on different workloads. We finally demonstrate a prototypical controller which aims at identifying optimal k automatically at runtime for best performance.