You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
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.
The text was updated successfully, but these errors were encountered:
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:
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.
The text was updated successfully, but these errors were encountered: