Cool stuff: Composable memory transactions

By
Posted on
Tags: haskell, stm, transactions, concurrency

If you write software that deals with concurrency, you are doubtless familiar with the painful limitations of the concurrency abstractions that most programming languages, runtimes, and operating systems offer us humble programmers. The one-big-select idiom, the need to impose a global ordering policy on lock taking, and the myriad things that can unexpectedly bite you in the behind when managing threads are not-so-subtle reminders that the programming world still has a few fundamental problems to solve.

Thus I was impressed when I read Tim Harris, Simon Marlow, Simon Peyton Jones, and Maurice Herlihy’s paper on Composable memory transactions a couple of months ago. The paper introduced some Very Cool Stuff (especially if you program in Haskell, for which there is an implementation available). More recently at the Links meeting at ETAPS (another cool thing a’brewing), the same team gave a talk on the subject: Concurrency Unlocked: transactional memory for composable concurrency. Check out the slides from the talk for a summary of the problem and the STM solution.

The gist is that today’s ubiquitous concurrency abstraction – the lock – is fundamentally at odds with the most successful technique we humans have for building complex systems: gluing simple systems together. Composable memory transactions, on the other hand, do not have this problem. As a result, they offer a fundamentally simpler and more mentally scalable solution for building complex concurrent systems.

To quantify this coolness, we have only to look at section 4.2 of the paper. In about 25 lines of code the authors give an implementation for what is effectively the heart of an instant messaging server. I am not kidding. Multiple writers with serialized writes into each channel, multiple readers on each channel with independent read positions and buffering. Yeah, it’s in there.

Do yourself a favor. Check out the slides from the talk and then read the paper. This is some seriously cool stuff. You ought to know about it.

Update 2007-01-16: Since I wrote this article, Software Transactional Memory has received a lot of attenttion. Here are a couple of pointers worth checking out: