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

[Florian Hartwig]

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
>
> We separately did a C implementation of those and they performed really well
> in our bake-off of producer consumer data structures (vs. TBB queues, and
> many other implementations).

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?

> I'm less familiar with the literature on concurrent hash tables.  TBB's have
> been a little bit underwhelming in performance.  But it's definitely an
> important structure.   Ditto for priority queues.

The data structures I mentioned were just my initial ideas, I'm open
to any other suggestions. In my (limited) experience with parallel
programming, queues and priority queues tend to come up quite a bit,
but I'd be happy to get input from anyone with more experience
regarding what would be useful/important.