[Haskell-cafe] Google Summer of Code - Lock-free data structures

Ryan Newton rrnewton at gmail.com
Thu Mar 29 06:57:57 CEST 2012

> GHC already has a CAS primitive on MutVar#, it just needs to be extended
> to MutableArray# and MutableByteArray# (at all of the bit-widths the CAS
> instruction would support, e.g. see readWordXxArray# in
> http://www.haskell.org/ghc/docs/latest/html/libraries/ghc-prim-
> The implementation should be almost identical to casMutVar#.
> In particular I think you need:
>     casMutArray# :: MutableArray# s a -> Int# -> a -> a -> State# s -> (#
> State# s, Int#, a #)
>     casWord16MutByteArray :: MutableByteArray# s -> Int# -> Word# -> Word#
> -> State# s -> (# State# s, Int#, Word#)

FYI, I started working on adding these.  I'm hoping to have it working in
GHC HEAD for any students who need to use it.  To my knowledge the only two
patches required to implement casMutVar# were these two (plus the
preexisting cas() definition in SMP.h):



The latter is a bugfix to the former.

Florian, your proposal looks good to me (
 You touched on the major things we need to know.

I just read in your proposal that you started looking into the casMutArray#
issue as well.  How far have you gotten with that?  Do you want to work on
this together a bit?

I've got an implementation of a casArray# primop that passes a basic test,
but I'm not sure if the GC write barrier is correct:


The ByteArray versions will be more annoying, requiring more variations,
but they are also less essential, because the user can always use
ForeignPtr and bits-atomic in this case, and I believe for our concurrent
data structures we want to store arbitrary pointers (hence casArray#).

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20120329/afade6be/attachment.htm>

More information about the Haskell-Cafe mailing list