[Haskell-cafe] Software Transactional Memory and LWN
marcin.kosiba at gmail.com
Fri Jun 12 07:12:53 EDT 2009
On Thursday 11 June 2009, Ketil Malde wrote:
> Browsing LWN, I ran across this comment:
> The author makes a bunch of unsubstantiated claims about STM, namely
> that all implementations use locking under the hood, and that STM can
> live- and deadlock. I've seen a lot of similar sentiments in other
> places as well (comp.arch springs to mind).
> Now, I'm no expert on STM, but I was pretty sure these are incorrect,
> and I certainly had the impression that Haskell's STM guarantees some
> progress - which it couldn't in a deadlock situation.
> Am I wrong?
While I'm no STM expert either, I'd like to remind an often overlooked
detail: locks and STM are two different abstractions. While locks provide
semantics for running critical sections (informally, parts of code which only
one thread can execute) STM provides semantics for atomic actions
(informally, actions the intermediate state of which can't be observed by
Now, while an STM implementation can use locks under the hood, it doesn't
change the fact that the programmer isn't exposed to using those. Saying STM
is bad because it uses locks under the hood is the same as saying that a
garbage-collected environment is bad because it uses malloc and free under
As far as the STM-is-better-because-it-doesn't-use-locks theory is concerned,
the idea here is that STM doesn't associate a lock with every atomic section.
This means that (in an optimistic implementation) any number of threads (and
potentially CPU cores) can execute the atomic action in parallel, and if
there are few rollbacks, this can lead to better performance than using a
single lock. And you can't forget about composability -- code written
using locks is less modular than code written using STM.
While either optimistic or pessimistic STM can livelock, this can be
solved by some sort of exponential backoff algorithm (which does not
guarantee progress, just makes a livelock less likely).
As far as deadlock is concerned -- if we allow for retry, then as it has
already been mentioned, there is a possibility for deadlock. But with STM,
you can do deadlock detection by means of cycle detection in wait-for graphs
(in much the same way as it is done in DBMS).
While now STM usually performs worse than locks, it is an active area of
research (even Intel released an experimental STM-supporing C++ compiler).
It is also true, that as the number of cores in cpus grows, STM will become
when a long-lived transaction is rolled-back by small transactions
you can even switch between STM and locking: General and Efficient Locking
without Blocking. Yannis Smaragdakis, Anthony Kay, Reimer Behrends, Michal
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Size: 197 bytes
Desc: This is a digitally signed message part.
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20090612/dfd4f2ee/attachment.bin
More information about the Haskell-Cafe