On 29 March 2012 at 12:01 PM, Heinrich Apfelmus <apfelmus at quantentunnel.de> wrote: > 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?
Well, terminology-wise it would probably be more accurate to say that you can implement lock-free algorithms using both (i.e. it's not really CAS and STM that are lock-free, but the algorithms implemented using them). But maybe this is a pedantic distinction. As to the difference between the two: CAS is just a machine instruction that takes an old "expected" value, a new value and an address and updates the memory pointed to by the address iff it contains the old/expected value. All this happens atomically, so you avoid the potential conflicts between threads concurrently reading from and writing to the same address. STM is much higher-level. It's an abstraction that allows the programmer to treat any sequence of reads and writes as a single atomic operation. This is, as the name says, implemented in software. 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. I hope this makes some sense. Cheers, Florian _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe