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/
signature.asc
Description: This is a digitally signed message part.
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe