GoKawiilGirls Just Wanna Have Fast MPMC Queues with bounded waiting
Disclaimer: An earlier version of this post claimed the structure is wait-free, this is incorrect. Being wait-free requires that failure or suspension of any thread can’t cause failure or suspension of another thread. This queue in fact does not fulfill that requirement. The main section which discusses the wait bounds of queue operations has been amended to reflect this, but other parts of this article have not been. As such there may parts of the text which refer to this as a wait-free queue, which it is not. I chose to keep those sections to avoid rewriting chunks of this post after it was already posted. Thanks for the correction Reddit user matthieum!
After my last post I started working on writing a data structure to facilitate sharing a buffer mutably between multiple threads. One tangent lead to another and that lead to me getting really into lock-free data structures so I decided I wanted to make a wait-free queue. This thing seems decently fast to me and I’m proud of it so I figured its worth writing about it. I also wanted to write something short and sweet after the novella that was my last post.
To be clear, I am not claiming this data structure is ground-breaking in any way. This is me testing my intuition of lock-free/wait-free programming. To that end, I’ve kept cross-referencing of other works to a minimum, only going so far as to benchmark some other queue implementations* on my machine without peeking at their internals. I’m hoping to get some feedback from people who know more about this stuff than me, so if that’s you, please feel to give your thoughts!
* When ever I mention benchmarks for “other queues” I’m referencing benchmarks I got through max0x7ba’s excellent atomic_queue repository. It has a set of scripts and make files that made it very easy to get a solid collection of benchmarks for various popular queue implementations.
Design
Theory
The queue works based off a ticket lock wait system. Imagine that there are two ticket dispensers, one for producers and one for consumers, as well as a set of N boxes next to each other that are labeled from 0 to N-1. Above each box is a display keeping track of whose turn it is, it shows a reservation number and a letter to indicate whether it is the consumer or producer’s turn. Each ticket will have two numbers printed on it, one is the box number, the other is the reservation number.
The flow for either consumer or producer is simple: take a ticket from the appropriate dispenser, find the box with the number shown on the ticket and wait for the reservation number on the ticket to display above the box. Once the reservation number is displayed, one can perform the action permitted by their ticket, either taking (consuming), or placing (producing) an item.
It’s worth noting that the reservation system here would ensure that for any one box the following holds true:
... continue reading