> Disclaimer: An earlier version of this post claimed the structure is wait-free, this is incorrect. Being wait-free requires that failure or suspension of any thread can’t cause failure or suspension of another thread. This queue in fact does not fulfill that requirement. The main section which discusses the wait bounds of queue operations has been amended to reflect this, but other parts of this article have not been. As such there may parts of the text which refer to this as a wait-free queue, which it is not. I chose to keep those sections to avoid rewriting chunks of this post after it was already posted. Thanks for the correction Reddit user matthieum!
Perhaps I missed it but there didn't appear to be discussion of false sharing between the N individual data slots. It might be beneficial to pad each slot to a cache line width (or at least less slots per line), and/or using some kind of bijective hashing on the slot lookup so that sequential tickets don't access adjacent slots.
If you align and pad each slot there won't be any false sharing and the stream prefetcher can kick in if there's only one producer or consumer.
If you use bijective hashing you reduce false sharing without aligning and padding. This can save memory at the expense of the stream prefetcher never kicking in.
unsafe impl<T, const N: usize> Sync for WFQueue<T, N> {}
unsafe impl<T, const N: usize> Send for WFQueue<T, N> {}
These impls are unsound, because neither constrains `T` to be `Sync`/`Send`. As-written this would let you declare a `WFQueue<Rc<T>, N>` and pass non-atomic-refcount pointers between threads.
16 comments
[ 3.5 ms ] story [ 115 ms ] threadClassy disclaimer! matthieum's (long) reddit comment is also an informative read: https://www.reddit.com/r/rust/comments/1up0uhg/girls_just_wa...
If you align and pad each slot there won't be any false sharing and the stream prefetcher can kick in if there's only one producer or consumer.
If you use bijective hashing you reduce false sharing without aligning and padding. This can save memory at the expense of the stream prefetcher never kicking in.
The fix is straightforward:
I.e., WFQueue is only Sync if T is Sync, and likewise for Send.Actually, later on, the code makes a similar mistake, but only for one impl.
Sounds like fun.