<div>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:</div><div><br></div><div>
<a href="https://google-melange.appspot.com/gsoc/proposal/review/google/gsoc2012/lorehead/1" target="_blank">https://google-melange.appspot.com/gsoc/proposal/review/google/gsoc2012/lorehead/1</a></div><div><br></div>
<div>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.</div>
<div><br></div><div> -Ryan</div><br><div class="gmail_quote">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. </div>
<div class="gmail_quote"><br></div><div class="gmail_quote"><br></div><div class="gmail_quote">On Fri, Apr 20, 2012 at 9:25 AM, Milan Straka <span dir="ltr"><<a href="mailto:fox@ucw.cz" target="_blank">fox@ucw.cz</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Hi Simon,<br>
<div><br>
> 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.<br>
><br>
> <a href="http://infoscience.epfl.ch/record/166908/files/ctries-techreport.pdf" target="_blank">http://infoscience.epfl.ch/record/166908/files/ctries-techreport.pdf</a><br>
><br>
> <a href="http://lampwww.epfl.ch/~prokopec/ctries-snapshot.pdf" target="_blank">http://lampwww.epfl.ch/~prokopec/ctries-snapshot.pdf</a><br>
<br>
</div>Nice :)<br>
<div><br>
> Maybe we should have a Haskell version? Maybe we already do?<br>
<br>
</div>I think we do not have any nontrivial concurrent structures<br>
(we have MVar and FIFO + Semaphore built on top of it).<br>
<br>
Most of work seem to be done on persistent structures. On that front,<br>
Johan's unordered-containers package implements the hash tries,<br>
which are roughly the described CTries without concurrent updates.<br>
<br>
I am not sure it would be worth implementing a structure in Haskell<br>
that is inherently concurrent. For me it was always enough to wrap<br>
a persistent structure in an MVar, so updates are performed sequentially<br>
and accesses can be made in parallel.<br>
<br>
Such a structure would probably have to be strict and in an ST monad,<br>
to get a usable and deterministic behaviour.<br>
<br>
Any thoughts?<br>
<br>
Cheers,<br>
Milan<br>
<br>
_______________________________________________<br>
Libraries mailing list<br>
<a href="mailto:Libraries@haskell.org" target="_blank">Libraries@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/libraries" target="_blank">http://www.haskell.org/mailman/listinfo/libraries</a><br>
</blockquote></div><br>