Thursday, March 16, 2017

MultiList - A MPSC Wait-Free Queue

I was going to talk about BitNextLazyHead but didn't get the time to write a decent post about it, so instead I'm going to just post a link to one of our recent queues, named MultiList.

MultiList is based on an idea that Andreia had of having a queue with multiple linked lists instead of a singly linked list. This idea by itself is not new, but she was the first to come up with an approach that is linearizable and lock-free. In fact, this is not just lock-free, it's wait-free for enqueuing. Even more, in its simplest form, it's a wait-free Multi-Producer-Single-Consumer queue... and it doesn't need memory reclamation technique.

Yes, that's right, as crazy as it may seem, the MPSC variant does not need any kind of memory reclamation like RCU or Hazard Pointers or things like that. How awesome is that?
The paper is short and the code even shorter.
Link to the paper here: https://github.com/pramalhe/ConcurrencyFreaks/blob/master/papers/multilist-2017.pdf