Hello cafe,
<div><br></div><div>In the context of the monad-par project we&#39;re just getting to the point of trying to replace our work stealing Deque&#39;s with something more efficient (in Haskell).</div><div><br></div><div>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.</div>

<div><br></div><div>We are about to embark on some work to fix this problem for monad-par &amp; Deques, but if there are others working in this vicinity it would be nice to team up.  </div><div>   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.</div>

<div><br></div><div><div>My first goal is to get a parameterizable deque interface, implementation, and benchmarks that makes it possible to express  variations of queues including:</div></div><div><ul><li>Double, single, and 1.5-ended (e.g. both ends can be RW or only R or W)</li>

<li>Threadsafe or single-threaded on both ends</li><li>Bounded or unbounded</li></ul></div><div>If you require that at least the &quot;left&quot;-end support Write and the &quot;right&quot; 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 &amp; Scott queues) could satisfy all of them while leaving &quot;room to improve&quot;.  The TBB guys have considered making their concurrent_queus configurable to this extent but haven&#39;t gotten around to it.</div>

<div><br></div><div>Thanks,</div><div>  -Ryan</div><div><br></div><div><br></div><div>Appendix A: Using foreign data structures with Haskell</div><div>----------------------------------------------------------------------------</div>

<div><br></div><div>It&#39;s easy to call foreign code in Haskell, but how to use a foreign data structure to store polymorphic Haskell values?</div><div><br></div><div>For example we would want a TBB concurrent_queue to store words representing pointers into the Haskell heap.  We would need, for example:</div>

<div><ul><li>(1) to pin arbitrary objects by making StablePtrs</li><li>(2) to communicate those to a foreign enqueue operation</li><li>(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)</li>

</ul><div>I don&#39;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?</div>

<div><br></div></div>