Boost Lock-free Queue and Stack with Batching

Abstract

Concurrent queues and stacks are important components of many software systems. They are well-known contended data structures due to intense contention on hotspots, resulting in limited performance and poor scalability. To achieve higher performance, several attempts applied the batching technique, which packs a group of standard operations into a single batch for execution, to lock-free queues and stacks built upon the linked list, but still inherited the contended compare-and-swap (CAS).

In this paper, we construct the lock-free queue and stack to support linearizable batch operations, which benefit from fetch-and-add (FAA) primitive and get rid of the inherent CAS contention. In our evaluation, our new design has a significant performance advantage over the competitors.