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

[Tim Harris (RESEARCH)]

Hi,

Somewhat related to this...

Next month we have a paper coming up at EuroSys about a middle-ground between using STM and programming directly with CAS:

http://research.microsoft.com/en-us/um/people/tharris/papers/2012-eurosys.pdf

This was done in the context of shared memory data structures in C/C++, rather than Haskell. 

It might be interesting to see how the results carry over to Haskell, e.g. adding short forms of specialized transactions that interact correctly with normal STM-Haskell transactions.

In the paper we have some examples of using short specialized transactions for the fast paths in data structures, while keeping the full STM available as a fall-back for expressing the cases that cannot be implemented using short transactions.

 --Tim




-----Original Message-----
From: haskell-cafe-bounces at haskell.org [mailto:haskell-cafe-bounces at haskell.org] On Behalf Of Heinrich Apfelmus
Sent: 29 March 2012 13:30
To: haskell-cafe at haskell.org
Subject: Re: [Haskell-cafe] Google Summer of Code - Lock-free data structures

Florian Hartwig wrote:
> Heinrich Apfelmus wrote:
> 
> So while the two are related, CAS is a machine primitive that works 
> for a single operation and on a single word while STM is a software 
> abstraction that isolates sequences of operations on multiple memory 
> locations from each other.
> 
>> Is it possible to implement every data structure based on CAS in 
>> terms of STM? What are the drawbacks? The other way round?
> 
> I think so. Atomically reading and writing a single memory location 
> (which CAS does) is just a very simple transaction. But using a CAS 
> instruction should be more efficient, since STM has to maintain a 
> transaction log and commit transactions, which creates some overhead.

Ah, I see. In that case, it may be worthwhile to implement the CAS instruction in terms of STM as well and measure the performance difference this makes for the final data structure. After all, STM is a lot more compositional than CAS, so I'd like to know whether the loss of expressiveness is worth the gain in performance.


Best regards,
Heinrich Apfelmus

--
http://apfelmus.nfshost.com


_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe at haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe