Concurrent collections

Ryan Newton rrnewton at
Fri Apr 20 15:50:20 CEST 2012

We've got a few GSOCs proposed (one or two of which will be funded) that
are implementing concurrent data structures.  The following one is highly
rated and targets concurrent hash tables:

Loren isn't decided on which algorithm to implement yet.  The concurrent
tries look interesting, but I don't understand their trade-offs yet
compared to the other algorithms mentioned in the above proposal.


P.S. Several of these algorithms require a casArray# primop as well as
casMutVar#.  I've got a patch out for this, but it needs more testing and
then to be incorporated in HEAD so that the GSOC students can use it.

On Fri, Apr 20, 2012 at 9:25 AM, Milan Straka <fox at> wrote:

> Hi Simon,
> > I went to Aleksandar Prokopec's talk about Concurrent Tries at the Scala
> day earlier this week.  I thought it was pretty cool. Here's the paper.
> >
> >
> >
> >
> Nice :)
> > Maybe we should have a Haskell version?  Maybe we already do?
> I think we do not have any nontrivial concurrent structures
> (we have MVar and FIFO + Semaphore built on top of it).
> Most of work seem to be done on persistent structures. On that front,
> Johan's unordered-containers package implements the hash tries,
> which are roughly the described CTries without concurrent updates.
> I am not sure it would be worth implementing a structure in Haskell
> that is inherently concurrent. For me it was always enough to wrap
> a persistent structure in an MVar, so updates are performed sequentially
> and accesses can be made in parallel.
> Such a structure would probably have to be strict and in an ST monad,
> to get a usable and deterministic behaviour.
> Any thoughts?
> Cheers,
> Milan
> _______________________________________________
> Libraries mailing list
> Libraries at
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <>

More information about the Libraries mailing list