comp.programming.threads

Kaz Kylheku

4/2/2015 5:22:00 PM

On 2015-04-02, Dmitry Knyaginin <knyaginin@gmail.com> wrote:
> Please check out my algorithm unbounded SPSC (wait free?) queue.
> This implementation is wait free?
> I tested this code on os x, windows, ubuntu.
> Everywhere works!
> ThreadSanitizer detect data race.
>
> C++ code
> http://pastebin.co...

Complete junk, I'm afraid.

Your code assumes that you can just magically stick a node into the shared
data structure without worrying about what another thread is doing.

You've written an ordinary doubly-linked list and simply *called*
it "wait-free".

What if two processors execute "last->v = v" at the same time?

What if two processors execute "last->next = tmp" at around the same time?

What if two processors execute "last = tmp" at the same time?

What if you have this scenario:

Processor A Processor B

last->next = tmp
last->next = tmp
last = tmp
last = tmp


How about this one:



Processor A Processor B

last->next = tmp
last->next = tmp
last = tmp
last = tmp


It is baffling as to how you can neglect such questions in code that
is supposed to be concurrent programming.