<div dir="ltr">Hi Edward,<div><br></div><div>Thanks very much for this reply, it answers a lot of questions I'd had.  I'd hoped that ordering would be preserved through C--, but c'est la vie.  Optimizing compilers are ever the bane of concurrent algorithms!</div>
<div><br></div><div>stg/SMP.h does define a loadLoadBarrier, which is exposed in Ryan Newton's atomic-primops package.  From the docs, I think that's a general read barrier, and should do what I want.  Assuming it works properly, of course.  If I'm lucky it might even be optimized out.</div>
<div><br></div><div>Thanks,</div><div>John</div></div><div class="gmail_extra"><br><br><div class="gmail_quote">On Mon, Dec 30, 2013 at 6:04 AM, Edward Z. Yang <span dir="ltr"><<a href="mailto:ezyang@mit.edu" target="_blank">ezyang@mit.edu</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Hello John,<br>
<br>
Here are some prior discussions (which I will attempt to summarize<br>
below):<br>
<br>
    <a href="http://www.haskell.org/pipermail/haskell-cafe/2011-May/091878.html" target="_blank">http://www.haskell.org/pipermail/haskell-cafe/2011-May/091878.html</a><br>
    <a href="http://www.haskell.org/pipermail/haskell-prime/2006-April/001237.html" target="_blank">http://www.haskell.org/pipermail/haskell-prime/2006-April/001237.html</a><br>
    <a href="http://www.haskell.org/pipermail/haskell-prime/2006-March/001079.html" target="_blank">http://www.haskell.org/pipermail/haskell-prime/2006-March/001079.html</a><br>
<br>
The guarantees that Haskell and GHC give in this area are hand-wavy at<br>
best; at the moment, I don't think Haskell or GHC have a formal memory<br>
model—this seems to be an open research problem. (Unfortunately, AFAICT<br>
all the researchers working on relaxed memory models have their hands<br>
full with things like C++ :-)<br>
<br>
If you want to go ahead and build something that /just/ works for a<br>
/specific version/ of GHC, you will need to answer this question<br>
separately for every phase of the compiler.  For Core and STG, monads<br>
will preserve ordering, so there is no trouble.  However, for C--, we<br>
will almost certainly apply optimizations which reorder reads (look at<br>
CmmSink.hs).  To properly support your algorithm, you will have to add<br>
some new read barrier mach-ops, and teach the optimizer to respect them.<br>
(This could be fiendishly subtle; it might be better to give C-- a<br>
memory model first.)  These mach-ops would then translate into<br>
appropriate arch-specific assembly or LLVM instructions, preserving<br>
the guarantees further.<br>
<br>
This is not related to your original question, but the situation is a<br>
bit better with regards to reordering stores: we have a WriteBarrier<br>
MachOp, which in principle, prevents store reordering.  In practice, we<br>
don't seem to actually have any C-- optimizations that reorder stores.<br>
So, at least you can assume these will work OK!<br>
<br>
Hope this helps (and is not too inaccurate),<br>
Edward<br>
<br>
Excerpts from John Lato's message of 2013-12-20 09:36:11 +0800:<br>
<div class="HOEnZb"><div class="h5">> Hello,<br>
><br>
> I'm working on a lock-free algorithm that's meant to be used in a<br>
> concurrent setting, and I've run into a possible issue.<br>
><br>
> The crux of the matter is that a particular function needs to perform the<br>
> following:<br>
><br>
> > x <- MVector.read vec ix<br>
> > position <- readIORef posRef<br>
><br>
> and the algorithm is only safe if these two reads are not reordered (both<br>
> the vector and IORef are written to by other threads).<br>
><br>
> My concern is, according to standard Haskell semantics this should be safe,<br>
> as IO sequencing should guarantee that the reads happen in-order.  Of<br>
> course this also relies upon the architecture's memory model, but x86 also<br>
> guarantees that reads happen in order.  However doubts remain; I do not<br>
> have confidence that the code generator will handle this properly.  In<br>
> particular, LLVM may freely re-order loads of NotAtomic and Unordered<br>
> values.<br>
><br>
> The one hope I have is that ghc will preserve IO semantics through the<br>
> entire pipeline.  This seems like it would be necessary for proper handling<br>
> of exceptions, for example.  So, can anyone tell me if my worries are<br>
> unfounded, or if there's any way to ensure the behavior I want?  I could<br>
> change the readIORef to an atomicModifyIORef, which should issue an mfence,<br>
> but that seems a bit heavy-handed as just a read fence would be sufficient<br>
> (although even that seems more than necessary).<br>
><br>
> Thanks,<br>
> John L.<br>
</div></div></blockquote></div><br></div>