What algorithms are used in Clojure, Haskell (and other languages) for STM?

Question

As I understand there are several different algorithms for implementing Software Transactional Memory (and this is a quite active research area). Where can I find (without having to dive into source code) which are used in different languages and libraryes, particularly in Clojure and Haskell (GHC)?

Ratafia

Answer 1

The ultimate resource on Clojure's STM -- apart from the code itself -- is the Software Transactional Memory article by Mark Volkmann.

It presents a brief high level overview of STM-the-approach (as compared to other approaches to concurrency), summarises the various concurrency features available in Clojure, then dives into Clojure's STM, describing exactly what happens during a transaction and ultimately going right down to the level of the individual classes involved. In addition to offering a lot of hard information on the inner workings of Clojure's STM machinery, it contains a good number of very insightful remarks relating to Clojure's concurrency-oriented features as they are used in idiomatic Clojure programmes.

The actual entry point to Mark's STM resources is this page, currently featuring some STM slides in addition to the link to the latest version of the main STM article.

Smegma

Thank you! That is the kind of information I was looking for (and that page contains a very clear explanation of Clojure STM BTW). – Ratafia

Answer 2

At a very high level, one thing that is interesting about Clojure's implementation of STM, is that it is very much different from all other implementations. Rich has looked much more towards actual real-world high-performance databases than academic papers about hypothetical STMs. For example, Clojure's STM is to my knowledge the only STM that uses Multi Version Concurrency Control (MVCC), which is a well-known technique in the database world (in fact, there's pretty much no serious database out there, which doesn't use MVCC) but is pretty much not discussed at all in the STM world.

Phototelegraphy

At this moment, there's still no good comparison between the various STM algorithms/implementations. So yes, they're quite distinct. And we can talk about which semantics are the most natural. But we have no basis outside of predisposition to say that MVCC is better/worse than any other implementation technique in terms of efficiency. We can note that MVCC exposes the possibility of write skew, which implementations that preserve genuinely serializable semantics do not. (Although there are ways to work against this too). – Sechrist

Answer 3

See http://www.haskell.org/haskellwiki/Software_transactional_memory for Haskell (and GHC), and http://clojure.org/concurrent_programming for Clojure.

I believe that GHC comes with an STM library, and there are some techniques for STM in Clojure.

For other languages, see http://en.wikipedia.org/wiki/Software_transactional_memory#Implementations

Eckenrode