On 19 March 2012 11:46, Ryan Newton
As Adam Foltzer mentioned in the trac ticket a really good structure would be the concurrent bags from this paper:
http://www.cse.chalmers.se/~tsigas/papers/Lock%20Free%20Bag%20SPAA11.pdf
We separately did a C implementation of those and they performed really well in our bake-off of producer consumer data structures (vs. TBB queues, and many other implementations).
I've just read the paper and they look both useful and interesting to implement. Adam mentioned that GHC would need to be extended first, and I can't really judge how much work that would be. Can anyone chime in on how feasible that is?
I'm less familiar with the literature on concurrent hash tables. TBB's have been a little bit underwhelming in performance. But it's definitely an important structure. Ditto for priority queues.
The data structures I mentioned were just my initial ideas, I'm open to any other suggestions. In my (limited) experience with parallel programming, queues and priority queues tend to come up quite a bit, but I'd be happy to get input from anyone with more experience regarding what would be useful/important.