I'm visiting the forum quite often and I've seen few posts about lock(wait)-free queues. Can someone enumerate best existing solutions for lock(wait)-free queues in multiple scenarios (single producer single consumer, multiple producers single consumer, etc)? Few forum members are active in this field, like Dmitriy Vyukov for example. The topic is surprisingly wide.
From my side, I can share the following:
FastForward for Efficient Pipeline Parallelism
It contains code for single producer, single consumer wait free queue which, from authors' POV, should be most efficient in its use scenario.
PS. Is the term "wait-free" correct and well adapted?
Yup, I'm here :)
Well, it's difficult to enumerate all them because there are hundreds of them.
There are:
1.1. single-producer
1.2. multi-producer
2.1. single-consumer
2.2. multi-consumer
3.1. array based
3.2. node based
3.3. hybrid
4.1. intrusive
4.2. non-intrusive
5.1. bounded
5.2. unbounded
6.1. blocks consumers when queue is empty
6.2. returns 'false' when queue is empty
7.1. blocks producer when queue is full
7.2. returns 'false' when queue is full
7.3. overwrites old items when queue is full
8.1. requires GC
8.2. does not require GC
9.1. supports priorities
9.2. does not support priorities
10.1. provides causal-FIFO
10.2. provides per-producer FIFO
10.3. provides best-effort FIFO
10.4. provides LIFO
10.5. no order guarantees
11.1. wait-free for producers
11.2. lock-free producers
11.3. blocking producers
12.1. wait-free consumers
12.2. lock-free consumers
12.3. blocking consumers
13.1. queue usually contains very few or zero elements
13.2. queue usually contains substantial amount of elements
Basically, if you choose 1 item from each category you can create specialized queue for the exact requirement set.
Some combinations of requirements are not sensible. And for some sets one will probably create the same queue implementation. But anyway here is more than 100'000 permutations!..