Groups > comp.programming.threads > #594

Re: usage of vyukov's mpsc queue

Path	csiph.com!x330-a1.tempe.blueboxinc.net!newsfeed.hal-mli.net!feeder3.hal-mli.net!news.shlink.de!news.iphh.net!iphh.net!news.osn.de!diablo2.news.osn.de!195.114.241.69.MISMATCH!feeder.news-service.com!eternal-september.org!feeder.eternal-september.org!.POSTED!not-for-mail
From	Alexander Terekhov <terekhov@web.de>
Newsgroups	comp.programming.threads
Subject	Re: usage of vyukov's mpsc queue
Date	Wed, 21 Sep 2011 19:33:42 +0200
Organization	A noiseless patient Spider
Lines	37
Message-ID	<4E7A1FF6.3671780C@web.de> (permalink)
References	<3b312755-24d8-4505-8cfe-1644c458c4d5@j1g2000yqn.googlegroups.com> <239216de-c8d6-49bb-b5bd-e9437665431c@l7g2000vbz.googlegroups.com>
Reply-To	terekhov@web.de
Mime-Version	1.0
Content-Type	text/plain; charset=us-ascii
Content-Transfer-Encoding	7bit
Injection-Info	mx04.eternal-september.org; posting-host="MCbSEzW5qwGLFMNXJh39IQ"; logging-data="21868"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+jGaYj4cflflGsOXbkKeSG05ZsS90Rz2s="
X-Mailer	Mozilla 4.77 [en] (Windows NT 5.0; U)
X-Accept-Language	en
Cancel-Lock	sha1:C+TjcgwkEJBc10PSPmMSdQNZEtM=
Xref	x330-a1.tempe.blueboxinc.net comp.programming.threads:594

Show key headers only | View raw

Dmitriy Vyukov wrote:
> 
> Since you are doing signaling (SetEvent) after each push, I think you
> don't need anything special for it to work.
> However of course you need correct memory fences in the queue
> algorithm itself, that is I think as follows:
> 
> void mpscq_push(mpscq_t* self, mpscq_node_t* n)
> {
>     n->next = 0;
>     mpscq_node_t* prev = XCHG(&self->head, n); // ACQUIRE_RELEASE

"// ACQUIRE" (without _RELEASE) is sufficient here.

But XCHG(...) can be totally relaxed with respect to memory barriers if
implemented as load-reserve/store-conditional or CAS loop (making
subsequent stores control-dependent).

X86 aside, try to unfold XCHG() using load-reserve/store-conditional or
CAS loop.

>     prev->next = n; // RELEASE

Yes.

> }
> 
> mpscq_node_t* mpscq_pop(mpscq_t* self)
> {
>     mpscq_node_t* tail = self->tail;
>     mpscq_node_t* next = tail->next; // ACQUIRE

Yes.

regards,
alexander.

Thread

usage of vyukov's mpsc queue Ephi Sinowitz <esinowitz.public@gmail.com> - 2011-09-20 06:55 -0700
  Re: usage of vyukov's mpsc queue Joshua Maurice <joshuamaurice@gmail.com> - 2011-09-20 17:19 -0700
    Re: usage of vyukov's mpsc queue Ephi Sinowitz <esinowitz.public@gmail.com> - 2011-09-20 18:35 -0700
      Re: usage of vyukov's mpsc queue Ephraim Sinowitz <ephisinowitz@yahoo.com> - 2011-09-21 06:42 -0400
  Re: usage of vyukov's mpsc queue Joshua Maurice <joshuamaurice@gmail.com> - 2011-09-21 00:26 -0700
  Re: usage of vyukov's mpsc queue Alexander Terekhov <terekhov@web.de> - 2011-09-21 12:19 +0200
    Re: usage of vyukov's mpsc queue Alexander Terekhov <terekhov@web.de> - 2011-09-21 12:34 +0200
    Re: usage of vyukov's mpsc queue Ephi Sinowitz <ephisinowitz@yahoo.com> - 2011-09-21 06:58 -0400
      Re: usage of vyukov's mpsc queue Alexander Terekhov <terekhov@web.de> - 2011-09-21 14:02 +0200
        Re: usage of vyukov's mpsc queue Ephi Sinowitz <esinowitz.public@gmail.com> - 2011-09-21 06:08 -0700
          Re: usage of vyukov's mpsc queue Alexander Terekhov <terekhov@web.de> - 2011-09-21 15:18 +0200
            Re: usage of vyukov's mpsc queue Ephi Sinowitz <esinowitz.public@gmail.com> - 2011-09-21 06:56 -0700
              Re: usage of vyukov's mpsc queue Alexander Terekhov <terekhov@web.de> - 2011-09-21 17:06 +0200
                Re: usage of vyukov's mpsc queue Ephi Sinowitz <esinowitz.public@gmail.com> - 2011-09-21 09:16 -0700
                Re: usage of vyukov's mpsc queue Alexander Terekhov <terekhov@web.de> - 2011-09-21 18:20 +0200
  Re: usage of vyukov's mpsc queue Dmitriy Vyukov <dvyukov@gmail.com> - 2011-09-21 09:58 -0700
    Re: usage of vyukov's mpsc queue Alexander Terekhov <terekhov@web.de> - 2011-09-21 19:33 +0200
      Re: usage of vyukov's mpsc queue dvyukov@google.com - 2011-10-02 04:13 -0700
        Re: usage of vyukov's mpsc queue Alexander Terekhov <terekhov@web.de> - 2011-10-04 12:15 +0200
    Re: usage of vyukov's mpsc queue Ephi Sinowitz <esinowitz.public@gmail.com> - 2011-09-21 11:04 -0700
      Re: usage of vyukov's mpsc queue Ephi Sinowitz <esinowitz.public@gmail.com> - 2011-09-21 11:17 -0700
      Re: usage of vyukov's mpsc queue "Chris M. Thomasson" <cristom@charter.net> - 2011-09-24 22:44 -0700

csiph-web