Brief Announcement: Memory-Friendly Lock-Free Bounded Queues
Multi-Producer Multi-Consumer queue is one of the fundamental concurrent data structures used in software systems. As previous work suggests, efficient concurrent queues are very hard to design. There are two orthogonal ways on how to improve the performance of a concurrent queue: 1) reduce the number of compare-and-swap operations, i.e. replacing compare-and-swap with more scalable fetch-and-add; and 2) make a queue more memory-friendly, i.e., reduce the total number of allocations. The standard way to make a queue more memory-friendly is to implement it using arrays. The bounded queues are inherently memory-friendly since they are represented as an array of elements even on a theoretical level. However, most of them still have issues with memory allocations - typically, they either use descriptors or store some additional meta-information with each element. The arising question is whether it is possible to design a lock-free bounded queue that uses only $O(1)$ additional memory. We present such a memory-friendly lock-free bounded queue algorithm which requires two fundamental assumptions: all the inserting elements to be distinct and needs an unlimited supply of versioned null values, which can be achieved by stealing one bit from addresses.