Re: [Algorithms] lock-free stack with hazard list performance

[Stephan R. <ke...@so...>]

On Tue, 2009-04-21 at 18:53 -0700, Nicholas "Indy" Ray wrote:
> So, excuse if I'm missing a lot, I haven't created any lock-free data
> structures in about 2 years, But I suspect something like the
> following might work, It has a bit longer contention, and will have to
> spin more often, but I suspect there are also better ways to achieve
> the same thing.
> 
> do
> {
>   node = head;
>   if(!node) continue;
> }
> while(cas(head, node, 0));
> 
> head = node->next;
> 
> retData = node->Data;
> 
> delete node;

Nope, it definitely works, however...

1. It's not lock-free, your cas on the head to set it to 0 forms a
lock. :)

2. It prevents other threads from peeking at the top of the stack
without potentially locking which in my case is not only lock-free but
also wait-free. Though honestly not sure how much of an issue that is as
I'm not really sure how useful it really is to peek at a stack/queue
being accessed by multiple threads. No guarantee that a following
pop/dequeue will return the peeked item.

3. One advantage that locking algorithms do have over lock-free is that
with the right kind of spinlock, thread starvation can be avoided by
guaranteeing that threads will obtain their lock in the order they
requested it. The above lock makes no such guarantees however.


> 
> This also will also require at least one dummy node, but I don't
> suppose that would be a huge problem.
> 
> Anyways, when I get access to my main computer tonight or tomorrow, I
> will check to see how my current queue manages memory, which I think
> is more optimal.

That would be awesome, I'd be most interested in seeing that.

Stephan