Subj : Re: RCU+SMR
To   : comp.programming.threads
From : Joe Seigh
Date : Fri Jul 01 2005 09:43 am

Joe Seigh wrote:
> 
> Way back, I came up with a scheme where you make the queue a lock-free
> LIFO stack using compare and swap.  The single reader just grabbed the
> entire queue using compare and swap, reversed order making it FIFO
> and worked off of that util it was empty and then repeated the whole
> process by grabbing the shared LIFO stack again.
> 
Actually, the original was just a doubly linked list with the reader
filling in the back links as needed.  You don't even need to ever
dequeue from the queue anchor if you just leave that last element
on the queue as a place holder.  There's some cache hit to the reader
doing the reverse linking but probably less overall than some complicated
lock-free fifo queue algorithms.   If you had spare hardware threads,
you could have one doing the reverse linking in parallel with the
reader thread and improve latency for the reader thread.

Haven't done that kind of stuff in a while.  Usually, I'm doing single
writer, multiple reader lock-free queues for multi-casting.

-- 
Joe Seigh

When you get lemons, you make lemonade.
When you get hardware, you make software.

.