Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.programming.threads > #2951
| 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 <kaz@kylheku.com> |
| 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> (permalink) |
| 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 |
Show key headers only | View raw
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.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.
Back to comp.programming.threads | Previous | Next — Previous in thread | Find similar | Unroll thread
Please check out my algorithm unbounded SPSC (wait free?) queue Dmitry Knyaginin <knyaginin@gmail.com> - 2015-04-01 22:36 -0700 Re: Please check out my algorithm unbounded SPSC (wait free?) queue Kaz Kylheku <kaz@kylheku.com> - 2015-04-02 17:22 +0000
csiph-web