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

[Florian Hartwig]

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