[Haskell-cafe] Google Summer of Code - Lock-free data structures

[Heinrich Apfelmus]

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