I only recently realized that the classic two-stack queue makes a great MPSC concurrent queue, where the “push” stack is lock-free, and the “pop” stack is sequential.
How does that work? Or, what’s the benefit of using two stacks?
I presume the “push” stack uses CAS or similar in order to keep the multiple producers from stepping on each other’s toes. You don’t need CAS for the “pop” stack, but the consumer will still periodically have to transfer elements from one stack to another, and that will still require some synchronization.
I guess what I’m asking is, if both enqueue and dequeue have to use atomics, why would you build two stacks instead of, say, a double-ended linked list?
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.
I only recently realized that the classic two-stack queue makes a great MPSC concurrent queue, where the “push” stack is lock-free, and the “pop” stack is sequential.
score 1 · canonical
How does that work? Or, what’s the benefit of using two stacks?
I presume the “push” stack uses CAS or similar in order to keep the multiple producers from stepping on each other’s toes. You don’t need CAS for the “pop” stack, but the consumer will still periodically have to transfer elements from one stack to another, and that will still require some synchronization.
I guess what I’m asking is, if both enqueue and dequeue have to use atomics, why would you build two stacks instead of, say, a double-ended linked list?
score 1 · canonical
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