Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!weretis.net!feeder4.news.weretis.net!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: Tue, 04 Oct 2011 12:15:01 +0200
Organization: A noiseless patient Spider
Lines: 34
Message-ID: <4E8ADCA5.8BABEFF1@web.de>
References: <3b312755-24d8-4505-8cfe-1644c458c4d5@j1g2000yqn.googlegroups.com> <239216de-c8d6-49bb-b5bd-e9437665431c@l7g2000vbz.googlegroups.com> <4E7A1FF6.3671780C@web.de> <165625.663.1317554015291.JavaMail.geo-discussion-forums@yqbr29>
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="30932"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19VTZWn8ms0+j/+we3fVXV+YtMdfyvCtQ4="
X-Mailer: Mozilla 4.77 [en] (Windows NT 5.0; U)
X-Accept-Language: en
Cancel-Lock: sha1:HlGcAlk7huVK+LEsyZZfyVi1qSM=
Xref: x330-a1.tempe.blueboxinc.net comp.programming.threads:623


dvyukov@google.com wrote:
> 
> On Wednesday, September 21, 2011 9:33:42 PM UTC+4, Alexander Terekhov wrote:
> > 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).
> 
> In my model there is no such thing as "control-dependent", 
> each acquire simply must pair with release :)
> But I am curious about your model, how is n->next=0 prevented 
> from sinking below XCHG (which would be a disaster)? 
> It seems that even a compiler can easily do that.

My mistake. The XCHG's store is not control dependent on 
n->next = 0 and hence must have either release or sink-store 
(relaxed release affecting only preceding stores) label.

regards,
alexander.