Queues based on Unsafe#getAndAdd instead of CAS spins?

[felixbarny]

Hi,

I'm learning about lock-free and wait-free algorithms and I was asking myself whether queues could be implemented based on the wait-free Unsafe#getAndAdd method as opposed to the lock-free CAS spin. The latter can still lead to queuing effects, especially under high contention and when there are more threads than processors concurrently doing the CAS spin.

Example of a CAS spin in MpmcArrayQueue:

JCTools/jctools-core/src/main/java/org/jctools/queues/MpmcArrayQueue.java

Lines 175 to 176 in 6b8feea

	while (seq > pIndex || // another producer has moved the sequence(or +)
	!casProducerIndex(pIndex, pIndex + 1)); // failed to increment

Would it be possible to restructure the algorithm to be wait-free or is that inherently impossible?

Thanks,
Felix

[franz1981]

Please take a look to https://github.com/JCTools/JCTools/blob/master/jctools-experimental/src/main/java/org/jctools/queues/MpscRelaxedArrayQueue.java

[felixbarny]

Cool, thanks for the link! Is there a paper or a presentation somewhere which explains the algorithm? Are there plans for an Mpmc variant?

[franz1981]

@felixbarny Not at short term, considering that this version is just experimental (even if quite stable now). @nitsanw maybe has something in mind, I can't say :)

Re the algorithm is commented and explained on the code and is a (now huge) variation of the Aeron publication log buffer: https://github.com/real-logic/aeron/wiki/Data-Structures.
Any differences from the orgiinal version introduced by me or @nitsanw are undocumented in any article/paper AFAIK, but the core design is quite similar to the Aeron original data structure.

[franz1981]

@felixbarny I suppose you should be interested into #230