[Haskell-cafe] Google Summer of Code - Lock-free data structures
florian.j.hartwig at gmail.com
Thu Mar 29 13:14:27 CEST 2012
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.
More information about the Haskell-Cafe