ShardedQueueShardedQueue is needed for some schedulers and NonBlockingMutex as a highly specialized for their use case concurrent queue
ShardedQueue is a light-weight concurrent queue, which uses spin locking and fights lock contention with sharding
Notice that while it may seem that FIFO order is guaranteed, it is not, because there can be a situation, when multiple producers triggered long resize of very large shards, all but last, then passed enough time for resize to finish, then 1 producer triggers long resize of last shard, and all other threads start to consume or produce, and eventually start spinning on last shard, without guarantee which will acquire spin lock first, so we can't even guarantee that ShardedQueue::pop_front_or_spin will acquire lock before ShardedQueue::push_back on first attempt
Notice that this queue doesn't track length, since length's increment/decrement logic may change depending on use case, as well as logic when it goes from 1 to 0 or reverse(in some cases, like NonBlockingMutex, we don't even add action to queue when count reaches 1, but run it immediately in same thread), or even negative(to optimize some hot paths, like in some schedulers, since it is cheaper to restore count to correct state than to enforce that it can not go negative in some schedulers)
```rust use sharded_queue::ShardedQueue; use std::cell::UnsafeCell; use std::fmt::{Debug, Display, Formatter}; use std::marker::PhantomData; use std::ops::{Deref, DerefMut}; use std::sync::atomic::{AtomicUsize, Ordering};
pub struct NonBlockingMutex<'capturedvariables, State: ?Sized> {
taskcount: AtomicUsize,
taskqueue: ShardedQueue
impl<'capturedvariables, State> NonBlockingMutex<'capturedvariables, State> {
#[inline]
pub fn new(maxconcurrentthreadcount: usize, state: State) -> Self {
Self {
taskcount: Default::default(),
taskqueue: ShardedQueue::new(maxconcurrentthreadcount),
unsafestate: UnsafeCell::new(state),
}
}
/// Please don't forget that order of execution is not guaranteed. Atomicity of operations is guaranteed,
/// but order can be random
#[inline]
pub fn runiffirstorscheduleonfirst(
&self,
runwithstate: impl FnOnce(MutexGuardfetch_sub] != 1
/// => some thread entered first if block in method
/// => [ShardedQueue::pushback] is guaranteed to be called
/// => [ShardedQueue::popfrontorspin] will not deadlock while spins until it gets item
///
/// Notice that we run action first, and only then decrement count
/// with releasing(pushing) memory changes, even if it looks otherwise
while self.taskcount.fetchsub(1, Ordering::Release) != 1 {
self.taskqueue.popfrontorspin()(unsafe { MutexGuard::new(self) });
}
}
}
}
/// [Send], [Sync], and [MutexGuard] logic was taken from [std::sync::Mutex]
/// and [std::sync::MutexGuard]
///
/// these are the only places where T: Send matters; all other
/// functionality works fine on a single thread.
unsafe impl<'capturedvariables, State: Send> Send
for NonBlockingMutex<'capturedvariables, State>
{
}
unsafe impl<'capturedvariables, State: Send> Sync
for NonBlockingMutex<'capturedvariables, State>
{
}
/// Code was mostly taken from [std::sync::MutexGuard], it is expected to protect [State] /// from moving out of synchronized loop pub struct MutexGuard< 'capturedvariables, 'nonblockingmutexref, State: ?Sized + 'nonblockingmutex_ref,