Concurrent collections

[Johan Tibell]

On Friday, April 20, 2012, Milan Straka 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.
> >
> > http://infoscience.epfl.ch/record/166908/files/ctries-techreport.pdf
> >
> > http://lampwww.epfl.ch/~prokopec/ctries-snapshot.pdf
>
> 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.


The data structure described in the paper above is based on the same data
structure I use, so it shouldn't be too hard to build a concurrent version.


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


I think it is worth implementing. We use the MVar strategy in the IO
manager, but it scales poorly.


>
> 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 haskell.org <javascript:;>
> http://www.haskell.org/mailman/listinfo/libraries
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/libraries/attachments/20120420/d5cfe4a0/attachment.htm>