Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!nntp.club.cc.cmu.edu!feeder.erje.net!eu.feeder.erje.net!news.swapon.de!aioe.org!.POSTED!not-for-mail From: Kaz Kylheku Newsgroups: comp.programming.threads Subject: Re: Please check out my algorithm unbounded SPSC (wait free?) queue Date: Thu, 2 Apr 2015 17:22:21 +0000 (UTC) Organization: Aioe.org NNTP Server Lines: 48 Message-ID: <20150402095708.956@kylheku.com> References: <785a0132-5d2d-41b5-973e-f1fde6dced1b@googlegroups.com> NNTP-Posting-Host: OGJi3KNpFOhM58UHZwXj0w.user.speranza.aioe.org X-Complaints-To: abuse@aioe.org User-Agent: slrn/pre1.0.0-18 (Linux) X-Notice: Filtered by postfilter v. 0.8.2 Xref: csiph.com comp.programming.threads:2951 On 2015-04-02, Dmitry Knyaginin 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.com/fWYjhyyv 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.