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