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@haskell.org
http://www.haskell.org/mailman/listinfo/libraries