Description
I have recently fallen into https://www.semanticscholar.org/paper/Brief-Announcement%3A-Jiffy%3A-A-Fast%2C-Memory-Wait-Free-Adas-Friedman/cd837a3f38878541c31acee3409c4481f98481d6 and I see that the algorithm they have used is the same of JCTools XADD queues (mpsc in particular).
The main difference seems that buffer appenders just use a buffer's next CAS to append new chunks instead of an int queue field.
The solution using the next buffer field works perfectly with non-generational GC environment, but on a GC environment a consumer must null out next to prevent GC nepotism to happen (ie just consumed chunk is old, referencing a newer one through next) meaning that a stale/slow appending producer can succeed to CAS(null, nextBuffer) on an already consumed (maybe reused too) buffer, appending what it expect to be the next chunk to it, but creating instead a wrongly ordered/dead-end buffers chain.
The way to support this mechanism with Java is to use a singleton tombstone buffer instead of null, preventing consumed buffers to be used to append new chunks.
There are other important effects of this change:
- the next buffer must be allocated/borrowed upfront the CAS -> we cannot use a spsc array q as buffer pool, but a mpmc one (still causing new CAS :()
- using a single CAS to batch append new buffers isn't feasible anymore
- consumer(s) cannot help anymore appenders or they risk to contend again on the mpmc pool (or allocate!)
Considered the drawbacks I don't see the Jiffy solution that good (that's why I have not implemented it in the final version, but just in my playground pr that wasn't solving GC nepotism), but maybe there are other points I am missing and it worth to be resurrected and made it right.
Just as side note: the process that use the cas on next still don't make the q to be wait-free because only when producer buffer is updated other producers can cooperate and append new buffers, otherwise they are blocked to make any progress.