A Wait-Free MPMCQueue

[MengRao]

Hi, I've just created a wait-free MPMC based on an idea by this project, can you help take a look: WFMPMC.

Thanks.

[rigtorp]

What are the advantages? Seems exactly the same as my queue but with an API that make it easy to block readers and writers indefinitely.

[MengRao]

There're blockinig API that're easiest to use, but also wait-free and zero-copy APIs which are not too hard to use.

[rigtorp]

You can create zero-copy API using visitor pattern:

template <typename Func,typename = enable_if<noexcept_invokable<Func>>>
void pop(Func &func){}

This would be a safe and easy to use API. You can do similar for emplace, but the same can be achieved by writing the constructors you need for the item type.

try_pop() is wait free, why is your unsafe version better?

Also you're version is not exception safe.

[MengRao]

I agree with your suggestion with zero-copy API using visitor pattern, it could make my tryEmplace/tryPop zero-copy.

But I don't think your try_push()/try_pop() is wait-free, because you're using CAS + loop to implement.

Regarding execption safety, do you mean I should add checking for is_nothrow_constructible to related function?

[rigtorp]

My try_pop is not strictly wait free, but in practice. You can make it wait free, but I think it will reduce performance, benchmark it. If you remove the retry logic the number of iterations per try_pop is bounded. One writer is guaranteed to make progress.

You're version is not even non-blocking since queue could be non-empty yet writers would block for reader to complete tryPop().

For example if destructor throws queue breaks, so you need to require nothrow destructor.

[MengRao]

For a bounded queue, writer's try attempt should fail if corresponding reader hasn't complete its pop, it makes perfect sense just as reader's try attempt on an empty queue should fail, and I don't think it's blocking because it returns false immediately and user could do something else and retry later.

Regarding exception, I admit it lacks checks for non_throw on constructor/destructor, I'm not quite a fan of exception, nor a fan of writing noexcept, yes I'm lazy and I allow the user of this queue to be lazy too. If it does throw, it sucks then.

[rigtorp]

Using your queue writer A pushes item. Reader B grabs next index, but didn't complete try_pop due to A was still writing data. Now reader B sleeps for 1 hour or exits. Writer A pushes more items until queue is full. Reader C reads all items except the one B is still reading (which it cannot read, it's already reserved for B). Writer A can now no longer make progress even though queue is not full (needs to wait for reader B). So the queue is not non-blocking. Also your queue is not FIFO.

[MengRao]

You're right, that's the reason the queue is not strict wait-free, and I've mentioned this pitfall in project's README.

Regarding not being FIFO, yes and no. FIFO is guaranteed by the index get from fetch_and_add, however it could happen that a reader with higher index completes pop operation earlier than the one with lower index, but it's not a problem in practice, because even if the two readers complete pop in order, they could handle data out of order too, and out of order is a normal phenomenon(rather than an issue) in multi-threaded environment that every user needs to deal with. Besides, from a single thread's point of view, the queue is strict FIFO as two sequential pops always return data in order.

Lastly, I've added zero-copy Try API: tryVisitPush(lambda) and tryVisitPop(lambda) thanks to your suggestion.