Concurrent collections
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 Maybe we should have a Haskell version? Maybe we already do? Simon
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
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
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:
https://google-melange.appspot.com/gsoc/proposal/review/google/gsoc2012/lore...
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.
-Ryan
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
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
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@haskell.org http://www.haskell.org/mailman/listinfo/libraries
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
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 javascript:; http://www.haskell.org/mailman/listinfo/libraries
On 20/04/2012 16:06, Johan Tibell wrote:
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.
Are you referring to the priority queue here? My vague recollection was that once we avoided the generational GC issue and fixed the blackhole implementation, there weren't any remaining problems. I'd really like to see some applications that are suffering here, and analyse whether it really is contention for the shared data structure, and if so, whether there's anything else we can do. Ryan, do you have anything? Cheers, Simon
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 javascript:; http://www.haskell.org/mailman/listinfo/libraries
_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries
I'd really like to see some applications that are suffering here, and analyse whether it really is contention for the shared data structure, and if so, whether there's anything else we can do. Ryan, do you have anything?
Only the monad-par (and new meta-par) schedulers. There, we've certainly had problems with contention on IORefs *AND* with extra GC pressure resulting from functional updates rather than in-place updates (which some of these mutable concurrent structures alleviate). However, it would be nice to know with more clarity what exactly is keeping us from having scheduler overhead more competitive with sparks, because I can't confidently say that it is only the above issues. One contention problem we have is that we keep adding brand new pieces of functionality (like the CPU/GPU scheduling) and inevitably in the interest of fast prototyping we initially use something basic for concurrently accessed data that performs poorly. Ultimately, I think the fundamental problem applications that have a single point of contention (MVar/IORef) between all or most threads. Even the best possible implementation of a single IORef or a single MVar, (for example using CAS for update than atomicModifyIORef), will still be a bottleneck on larger SMP systems. From our perspective, what we really want is the ability to drop in logically *singular* shared data structures (like the concurrent bag), which are actually using TLS behind the scenes to access mostly disjoint memory addresses. That's the place where we get a big design win in terms of keeping the client code simple but also getting scalability. (Those concurrent bags in particular perform really well and are basically a complete work-stealing implementation in a box.) Looking forward -- we've got a real medical imaging app that we've started working on; I'll let you know if there are any particular examples of data structure contention there. But for now the monad-par/meta-par schedulers are the only example I've got. Cheers, -Ryan 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 javascript:; http://www.haskell.org/**mailman/listinfo/librarieshttp://www.haskell.org/mailman/listinfo/libraries
______________________________**_________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/**mailman/listinfo/librarieshttp://www.haskell.org/mailman/listinfo/libraries
participants (5)
-
Johan Tibell -
Milan Straka -
Ryan Newton -
Simon Marlow -
Simon Peyton-Jones