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

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

On 19 March 2012 11:46, Ryan Newton 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-P...). 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