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)?

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.

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.

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