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

[Ryan Newton]

> 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-0.2.0.0/GHC-Prim.html).
> 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):


https://github.com/ghc/ghc/commit/521b792553bacbdb0eec138b150ab0626ea6f36b

https://github.com/ghc/ghc/commit/606f6e1cfcb2e79abaadcc5ed643817d2a4585d8

The latter is a bugfix to the former.

Florian, your proposal looks good to me (
http://www.google-melange.com/gsoc/proposal/review/google/gsoc2012/florianhartwig/1).
 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:


https://github.com/rrnewton/ghc/commit/18ed460be111b47a759486677960093d71eef386

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#).

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