> 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!
Classy disclaimer! matthieum's (long) reddit comment is also an informative read: https://www.reddit.com/r/rust/comments/1up0uhg/girls_just_wa...
Surprised nobody here nor on the reddit thread caught this one: https://github.com/nahla-nee/wfqueue/blob/main/src/lib.rs#L3...
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.
The fix is straightforward:
unsafe impl<T: Sync, const N: usize> Sync for WFQueue<T, N> {}
unsafe impl<T: Send, const N: usize> Send for WFQueue<T, N> {}
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.
unsafe impl<'a, T, const N: usize> Send for DrivableWFEnqueue<'a, T, N> where T: Send {}
unsafe impl<'a, T, const N: usize> Send for DrivableWFDequeue<'a, T, N> {}
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.
>fast MPMC queues with bounded waiting
Sounds like fun.