[Algorithms] lock-free stack with hazard list performance

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

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