Hello cafe,
In the context of the monad-par project we're just getting to the point of
trying to replace our work stealing Deque's with something more efficient
(in Haskell).
Based a quick perusal of Hackage there does not seem to be a lot of work in
this area. Of course, for Haskell the importance of this topic may be
diminished relative to pure data structures, but for doing systems-level
work like monad par good concurrent data structures are also very important.
We are about to embark on some work to fix this problem for monad-par
Deques, but if there are others working in this vicinity it would be nice to
team up.
We are going to try both pure Haskell approaches using the new casMutVar#
primop as well as wrapping foreign data structures such as those provided by
TBB. There are a whole bunch of issues with the latter -- see Appendix A
and help me out if you know how to do this.
My first goal is to get a parameterizable deque interface, implementation,
and benchmarks that makes it possible to express variations of queues
including:
- Double, single, and 1.5-ended (e.g. both ends can be RW or only R or W)
- Threadsafe or single-threaded on both ends
- Bounded or unbounded
If you require that at least the left-end support Write and the right
end support Read (excluding, for example stacks), that leaves a
configuration space of 32 options. Some of these 32 options have much
better algorithms than others, but a general algorithm (such as Michael
Scott queues) could satisfy all of them while leaving room to improve.
The TBB guys have considered making their concurrent_queus configurable to
this extent but haven't gotten around to it.
Thanks,
-Ryan
Appendix A: Using foreign data structures with Haskell
It's easy to call foreign code in Haskell, but how to use a foreign data
structure to store polymorphic Haskell values?
For example we would want a TBB concurrent_queue to store words representing
pointers into the Haskell heap. We would need, for example:
- (1) to pin arbitrary objects by making StablePtrs
- (2) to communicate those to a foreign enqueue operation
- (3) to unpin objects when the pointer is removed from a foreign
structure (or use a reference count to determine when to unpin/free the
StablePtr)
I don't have any experience here and would appreciate hearing from anyone
who does. Is this a non-starter? Will the overheads introduced by all the
StablePtr ops destroy any gains from using an efficient data structure?
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
