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

[Nicholas \Indy\ R. <ar...@gm...>]

I'm not familiar with Hazard lists, but from reading the pseudo code,
it seems that you get additional functionality at the cost or
performance, Unless I am missing something (which is likely, googling
"hazard lists" doesn't seem to be very helpful.) It seems that it'd
would be slower by principal. and only losing about 25% performance
over a spin lock doesn't seem to bad.

Nicholas "Indy" Ray

On Tue, Apr 21, 2009 at 1:52 PM, Stephan Rose <ke...@so...> wrote:
> Currently working on lock-free stack and queue implementations with hazard lists.
>
> >From a technical standpoint, they are working nicely, currently doing my testing with the stack as it's just the simpler one implementation-wise so less room for bugs to sneak in.
>
> However, performance wise, things aren't so happy.
>
> Ran a few tests:
>
> Common to all tests:
> Values pushed/popped: 2^24 per push thread
> Thread count, 2 pushing 2 popping
> Processor: Quad core so each thread is running on its own core
>
> Stack with spinlock: ~33 seconds
>
> Stack with hazard-pointer, properly deleting memory: ~45 seconds
>
> Stack with hazard-pointer, leaking memory by just simply marking the pointer as no longer referenced: ~17 seconds
>
> The 3rd test does indicate a significant gain over the spinlock, nearly cutting the time in half.
>
> However, something about scanning the other threads for pointers that are being referenced is just taking performance and is completely dragging it down. In pseudo count this looks roughly something like this:
>
> In pseudocode below:
>
> if deleteCount < threshold return; // Tried various values here, values up to around 128 seem to slightly improve performance, while larger values like 1024 totally annihilate performance.
>
> foreach node
>  if node->status = Delete
>    if !scan(node->pointer) // scan returns false if no other threads hold a ref
>      delete the node and mark node as free
>    endif
>  endif
> endforeach
>
> then the scan function:
>
> foreach thread
>  if thread != thisthread and thread->isrunning
>    if thread->hasreference(pointer)
>      return true;
>    endif
>  endif
> endforeach
>
> The hasrefeference function then has to cycle through every single entry of it's threads hazard list and see if it has an active reference to that pointer.
>
> It works. Slowly. But 1 loop that for each iteration calls another loop which for each iteration calls another loop (try to say that 10 times really fast...) is bound to be like trying to tow a garbage truck with a honda civic, especially as the number of items in the lists goes up.
>
> Currently this these lists are all singly linked lists, I could try using something like a hashtable and seeing if I do better than that. But all the information I've found online about hazard pointers I think also use just singly linked lists so I'm not quite sure where my issue is.
>
> Any ideas?
>
> Thanks,
>
> 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
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>