[Haskell-cafe] Google Summer of Code - Lock-free data structures
ekirpichov at gmail.com
Thu Mar 29 10:39:31 CEST 2012
Though of course you can implement CAS in terms of STM, CAS is much
more low-level and will probably be many times (though not
On Thu, Mar 29, 2012 at 12:01 PM, Heinrich Apfelmus
<apfelmus at quantentunnel.de> wrote:
> Florian Hartwig wrote:
>> Hi everyone,
>> I would like to do the GSoC project outlined in
>> One of Haskell's great strengths is its support for all kinds of
>> 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
>> 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. Stacks, see  and 
>> 3. Hash tables 
>> 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
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
Principal Engineer, Mirantis Inc. http://www.mirantis.com/
More information about the Haskell-Cafe