Pretty much what the title says. I'm building async code that depends on event loops that I anticipate becoming tight enough that the overhead of calling functions and repeated atomic ops becomes significant. I'd like a queue structure where I can push a T, but when I pop, I get back the equivalent of an ArrayVec<T, N> that gives me up to N items, in queue order. I do not mind if I am sometimes given pessimistically short arrays, so long as values eventually come out in the right order and come out in bulk most of the time.
Does a data structure like this exist? I'd rather not write my own unless I have to. Can I write my own, or is there some deeper issue that means I'd have to fall back to mutexes? (In which case a queue of mutex would work)
Yes, this is possible. The trick would be to maintain two values: a start and end index into a deque, each being AtomicUsizes. Using compare-and-swap (CAS) operations, you can have threads determine which one has achieved "ownership" over a segment of values based on who wins the CAS.
The main difficulty would be growing the queue, but if you allow producers to fail on full threads, or if you come up with a clever work-sharing approach, this can still be O(1) using a similar approach to Dr. Cliff Click's lock-free hashmaps. It's possible, but requires some doing.