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

[Gregory Collins]

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

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

G
-- 
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>