Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

xadd qs producer buffer rotation can be improved #266

Closed
franz1981 opened this issue Oct 21, 2019 · 0 comments
Closed

xadd qs producer buffer rotation can be improved #266

franz1981 opened this issue Oct 21, 2019 · 0 comments

Comments

@franz1981
Copy link
Collaborator

franz1981 commented Oct 21, 2019

Both the xadd qs are able to recycle chunks and save allocations while offering.
During a producer buffer rotation while appending a pooled
chunk there is a small window where offering threads see a NIL chunk as producerBuffer, preventing them to backward navigate the list of chunks to reach the target one. It cannot happen with a non-pooled chunk.

The appending algorithm requires that producerBuffer must always contain the buffer with the highest index or NIL (ie index := -1) in order to allow offering threads to reach their target chunk to write the element into or just wait until a valid chunk is available. The publishing of chunks happens by calling soProducerBuffer, that need to be called exclusively to preserve the ordering guarantee above: the exclusivity is ensured by casProducerChunkIndex. A stalled producer could see a pooled chunk turning its chunk index into the last one right before entering the casProducerChunkIndex, making it able to succeed. It means that
https://github.com/JCTools/JCTools/blob/master/jctools-core/src/main/java/org/jctools/queues/MpscUnboundedXaddArrayQueue.java#L317
is the last instruction that would be executed exclusively by a single thread and soProducerBuffer has to be called before it to ensure the ordering.

This issue could be solved similarly to #265 marking the rotation state (using a parity bit or -2) and making racing producers able to make progress or just "wait" before attempting to append a new chunk.
This would allow to publish producerBuffer only when is fully initialized.

Just a note: newChunk.soIndex(nextChunkIndex) need to remain an ordered store, because stalled producers need to see a stable/correct newChunk::prev ie soIndex will write release prev to them.

franz1981 added a commit to franz1981/JCTools that referenced this issue Oct 21, 2019
franz1981 added a commit to franz1981/JCTools that referenced this issue Oct 21, 2019
@nitsanw nitsanw closed this as completed in f5ddd65 Nov 5, 2019
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant