Moonbase

As we reach the limit of speed for memory and individual CPUs, parallel programming is going to become increasingly important.

Yet, explicit locking is difficult to get right, and nastily pierces abstractions. It also has memory access characteristics which are inappropriate to today’s wide gap between CPU and memory speed.

I think Software Transactional Memory is an idea whose time is coming. Given an existing STM API, it’s quite easy to do properly, compared to the ugly global analysis that needs to be performed to get nontrivial locking arrangements to work.

I’m fond of the approach taken in Harris, Marlow, Jones and Herlihy but despite its elgance, it has some problems with starvation of long transactions. Its reference implementation is also written in Haskell, which I think is cool, but isn’t immediately useful to most programmers.

The approach which I think shows the most promise for immediate utility is Rob Ennals’ Cache-sensitive Software Transactional Memory, which even has an associated project on SourceForge. This reference implementation is written in C.

Unlike most STM implementations, it’s not lock-free, but since the locking is not explicit, it’s still much easier for programmers to work with. The author also claims that it is the fastest STM implementation currently in exististence.