Florian Hartwig wrote:
Hi everyone, I would like to do the GSoC project outlined in http://hackage.haskell.org/trac/summer-of-code/ticket/1608
One of Haskell's great strengths is its support for all kinds of concurrent and parallel programmming, so I think that the Haskell ecosystem would benefit from having a wider range of efficient concurrent data structures. Also, more selfishly, I remember reading the article in CACM last summer and thinking that the whole idea of updating data structures directly using atomic compare-and-swap was really cool, so I would love to have an excuse to play around with it.
Some (initial) ideas for lock-free data structures worth implementing: 1. A lock-free priority queue, e.g. using the approach based on skip-lists explained in [2] 2. Stacks, see [1] and [3] 3. Hash tables [4] but if anyone has other suggestions, I would obviously happy to hear them.
Since I don't know much about concurrency, I have a simple question: what is the difference between atomic compare-and-swap and software transactional memory? Both are lock-free? Is it possible to implement every data structure based on CAS in terms of STM? What are the drawbacks? The other way round? Best regards, Heinrich Apfelmus -- http://apfelmus.nfshost.com