Yeah, the idea is that the “push” stack is a Treiber stack (to keep it simple), and the “pop” stack is a singly-linked list. The consumer can atomically transfer all elements from the “push” stack to the “pop” stack with a single XCHG, then it needs to reverse the “pop” stack before it can use it. So the single atomic XCHG instruction is amortized over all the pops from that stack. (The reversing overhead of course is still O(n).) If you want a lock-free MPSC queue, then this is simpler and more efficient than say a Michael-Scott queue (because the consumer has no per-pop atomic overhead).
It still won’t scale any better for multiple producers though (M-S scales to maybe 2-4 threads IME). No linearizable concurrent queue will scale well.
Yeah, the idea is that the “push” stack is a Treiber stack (to keep it simple), and the “pop” stack is a singly-linked list. The consumer can atomically transfer all elements from the “push” stack to the “pop” stack with a single XCHG, then it needs to reverse the “pop” stack before it can use it. So the single atomic XCHG instruction is amortized over all the pops from that stack. (The reversing overhead of course is still O(n).) If you want a lock-free MPSC queue, then this is simpler and more efficient than say a Michael-Scott queue (because the consumer has no per-pop atomic overhead).
It still won’t scale any better for multiple producers though (M-S scales to maybe 2-4 threads IME). No linearizable concurrent queue will scale well.
score 1 · canonical