STM and Haskell Attention

12 08 2007

Haskell has been garnering a fair bit of attention of late, largely as a result of Simon Peyton-Jonespresence at OSCON (and the ensuing flurry of Reddit postings of related blog posts). He gave a keynote on Software Transactional Memory (STM), which is an alternative to using explicit locks and condition variables in writing parallel programs. He also gave an introduction to Haskell, and a smaller talk on data parallelism.

I’m quite pleased by this recent attention, for a couple reasons.

The first is that I really agree with Simon that STM is going to be the way to go soon*. I also just think it’s damn cool – that’s why I did an independent study on it with Maurice Herlihy last semester, working with a slightly more recent version of Microsoft’s SXM implementation of STM for C# than that available at the link I just gave. Simon gives excellent motivation for STM in his talk, but there are still others if you’re unconvinced after watching it. Consider a datastructure which you traverse in multiple directions – perhaps a grid, which can be traversed in either direction in either dimension depending on the contents at a given location – or perhaps a mutable graph representation. What locking scheme do you use for scalable (read: not coarse-grained) access to a large instance of this datastructure? You could establish a total ordering of nodes and corresponding locks, or do a row/column at a time with an ordering on rows/columns in a table, and acquire locks only in that order. But since you can traverse in any direction, this would sometimes require building lists of locks to acquire, releasing later locks which were acquired in reaching the current point of traversal, and then walking the list reacquiring locks. How expensive is this, possibly acquiring the same lock over and over? How hard is it to write that code correctly? How much effort does it take to document, and for a new maintainer to learn, this locking scheme? All of this makes fine-grained locking a poor idea at best.

How much easier would it be to write such code naïvely and mark it as atomic? And with a proper implementation of STM, how much faster could this be on a large structure than a coarse-grained lock, or repeated acquisition and release of the same fine-grained locks? And this is a bonus on top easier coding for simple concurrent structures (and partial failures), and composition of atomic transactions, which cannot be done with normal locks.

If, like me, you’re curious about how STM is implemented, I suggest you check out a few papers. Understanding of all of these benefits from understanding the basic ideas and terminology of concurrency, as well as a bit of computer architecture knowledge.

There are certainly many, many more implementations, and many more papers, and more ways to tune an implementation than these couple papers spend much time on. Check out the related work in these papers.

I’m also pleased, because I feel Haskell has been underrated by the programming populus at large for a long time.** I’m interested in becoming more familiar with Haskell largely because of some of my pet peeves with OCaml, and because Haskell’s type system particulars are both richer and closer to category theory, which interests me mainly as an intellectual curiosity (and for its relation to type theory in general). Well written Haskell can also beat out many more well-known languages performance-wise (example, definitely poke around the language shootout). And it’s always nice to see a real functional language (read: one in which functional style is the norm, not just an option) getting mainstream attention.

I can only hope that people continue to take note of Haskell.


* Please note, those of you who are itching to start a flamewar about shared state vs. message passing, that STM does not claim to be the be-all and end-all of concurrent programming. It is designed to make programming with shared state easier than it is today. And shared state is not going away, because it’s the model with which chips are currently designed. So at the very least, operating systems, compilers, and some runtime systems will still need to deal with it, even if all other development switches to message passing concurrency.

** I should probably mention that I have not used Haskell a great deal, though this is not for lack of desire. A couple years ago I wrote a short assignment in Haskell (largely to play with lazy evaluation). I’ve also spent a fair amount of time writing OCaml over the past couple years, for the course I TAed and head TAed which uses OCaml to introduce students to currying and static typing (following an introduction to CS with Scheme), and last semester in a group software engineering course (perhaps I’ll elaborate on this experience another time). So I’m familiar with a similar type system.


Actions

Information

4 responses

12 08 2007
Phil Rand

For that matter, how do erlang and the other message passing languages implement their message passing? Isn’t some form of shared-state concurrency inevitable at the implementation level unless you’re running on special hardware like the transputer? I wonder if STM would be a good choice at this level.

12 08 2007
Top Posts « WordPress.com

[...] STM and Haskell Attention Haskell has been garnering a fair bit of attention of late, largely as a result of Simon Peyton-Jones‘ presence […] [...]

13 08 2007
Top English WP Blogs « KHỦNG LONG IT

[...] STM and Haskell Attention Haskell has been garnering a fair bit of attention of late, largely as a result of Simon Peyton-Jones‘ presence […] [...]

15 08 2007
Ashwin Jayaprakash

Isn’t this very similar to Multi Version Concurrency Control in Databases? I think Azul Systems does something similar too in their modified JVMs.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s




Follow

Get every new post delivered to your Inbox.

%d bloggers like this: