[Haskell-cafe] Who is working on high performance threadsafe mutable data structures in Haskell?

[Ryan Newton]

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?
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20111027/95c0cc73/attachment.htm>