[Haskell-cafe] Software Transactional Memory and LWN

[Marcin Kosiba]

On Thursday 11 June 2009, Ketil Malde wrote:
> Hi,
>
> Browsing LWN, I ran across this comment:
>
> http://lwn.net/Articles/336039/
>
> 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?

Hi,
	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 
other threads).

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 
the hood.

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[3]. And you can't forget about composability -- code written 
using locks is less modular than code written using STM.

While either optimistic[1] or pessimistic[2] 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[4]).
It is also true, that as the number of cores in cpus grows, STM will become 
more attractive. 

Thanks!
	Marcin Kosiba

[1]http://en.wikipedia.org/wiki/Software_transactional_memory#Implementation_issues
[2]when a long-lived transaction is rolled-back by small transactions
[3]you can even switch between STM and locking: General and Efficient Locking 
without Blocking. Yannis Smaragdakis, Anthony Kay, Reimer Behrends, Michal 
Young
[4]http://software.intel.com/en-us/articles/intel-c-stm-compiler-prototype-edition-20/
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 197 bytes
Desc: This is a digitally signed message part.
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20090612/dfd4f2ee/attachment.bin