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?