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.pd... 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@haskell.org [mailto:haskell-cafe-bounces@haskell.org] On Behalf Of Heinrich Apfelmus Sent: 29 March 2012 13:30 To: haskell-cafe@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@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe