Re: lock-free stack with hazard list performance

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



------------------------------------------------------------------------------
Stay on top of everything new and different, both inside and 
around Java (TM) technology - register by April 22, and save
$200 on the JavaOne (SM) conference, June 2-5, 2009, San Francisco.
300 plus technical and hands-on sessions. Register today. 
Use priority code J9JMT32. http://p.sf.net/sfu/p
_______________________________________________
GDAlgorithms-list mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list