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

[Ryan Newton]

The MichaelScott lockefree queues in that repository pass tests and should
work.  Additional stress testing and feedback would be appreciated.  There
are some other queues in the literature that might be worth implementing
but I think other data structures are higher priority.

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).  By the way, we can share the code for
this little bake-off as a performance baseline for the Haskell versions.

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.

In any case, I welcome your interest in the topic, Florian!

Cheers,
   -Ryan



On Mon, Mar 19, 2012 at 7:33 AM, Florian Hartwig <
florian.j.hartwig at gmail.com> wrote:

> On 19 March 2012 09:56, Gregory Collins <greg at gregorycollins.net> wrote:
> > A lock-free concurrent queue alone would be worth a summer project IMO.
> >
> > G
>
> Ryan Newton is already doing that
> (https://github.com/rrnewton/haskell-lockfree-queue).
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20120319/acd09f67/attachment.htm>