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

Gregory Collins greg at gregorycollins.net
Tue Mar 20 10:40:04 CET 2012

On Tue, Mar 20, 2012 at 2:53 AM, Florian Hartwig <
florian.j.hartwig at gmail.com> wrote:

> On 19 March 2012 11:46, Ryan Newton <rrnewton at gmail.com> wrote:
> > As Adam Foltzer mentioned in the trac ticket a really good structure
> would
> > be the concurrent bags from this paper:
> >
> >
> http://www.cse.chalmers.se/~tsigas/papers/Lock%20Free%20Bag%20SPAA11.pdf

Looks like they rely on thread-local storage, which would have to be worked
around in Haskell somehow.

> I've just read the paper and they look both useful and interesting to
> implement. Adam mentioned that GHC would need to be extended first,
> and I can't really judge how much work that would be. Can anyone chime
> in on how feasible that is?

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

and equivalents for Word32. Word64, Int16, Int32, Int64.

Gregory Collins <greg at gregorycollins.net>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20120320/17aca4f3/attachment.htm>

More information about the Haskell-Cafe mailing list