STM and Haskell Attention

Haskell has been garnering a fair bit of attention of late, largely as a result of Simon Peyton-Jones‘ presence 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.

• Transactional Memory: Architectural Support for Lock-Free Data Structures (actual pdf). This is actually hardware transactional memory (HTM), but is the paper which started the thinking about transactional memory in general.
• Lowering the Overhead of Nonblocking Software Transactional Memory. This gives an overview of the implementation and performance of a library-based approach to STM.
• Transactional Locking II. Another implementation of STM, with some very different design decisions from those made in the previous paper.
• Advanced Contention Management for Dynamic Software Transactional Memory. When two STM transactions conflict with each other, the system will allow one transaction to commit, and the other will fail and retry. Deciding which transaction(s) to commit can greatly affect performance of an STM system, and as a result much work has been done on choosing an algorithm for contention management. This does a good survey of some of the main approaches and their performance.

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.

So I Was On Reddit

So, apparently, less than two weeks after starting this blog, I ended up on programming.reddit.com (direct link) for this entry on the fact that most monad tutorials are awful, and offering a pointer to a paper . Apparently if you tag an entry with ‘monads,’ avid Haskell users flock to your blog (I exaggerate of course - just many more people than otherwise read my blog). Really, I suspect that using that tag just got more people to notice, and most of the hits came from Reddit, where I was probably only posted because I had a bit of an opinion, plus a link to Wadler’s paper. Interesting phenomenon.

Apparently I got a peak of 1,015 page views on August 2nd, as well as getting included in the “Blog Noise” section of Haskell Weekly News. Having never really blogged about anything other than my personal life before this summer, it’s interesting to see how certain keywords draw spikes of attention. For that reason, I’m specifically not tagging this entry with ‘haskell’ or ‘monads’ because I don’t want to distract that many people. Just thought it was interesting.

EDIT: Hello again, reddit-ors.

Living in the Periphery

As I’ve alluded to before, I’m currently in California for the summer, living in Sunnyale, doing an internship with the Solaris Kernel Group at Sun (work blog) in Menlo Park. Last summer I lived up in a nice part of San Francisco (West Portal) and commuted down to Sunnyvale, where I interned at Network Appliance (in a nutshell, they make easy to configure, high-end file servers). Right now I’m living in an apartment with three friends. One grew up in the Bay Area (Berkeley), and the other two are from Virginia, and had never been out here before. One of the latter’s friends from school is visiting, and I overheard part of my apartmentmate’s description of San Francisco in preparation for their trip tomorrow. And her description made me realize what an incredible difference in perception there is between those who have lived somewhere, and those who have visited.

Of course I’ve always been aware that such a discrepancy must exist, but it never truly hit home until just now. My apartment mate has visited San Francisco two or three times while we’ve been out here. Once she and our other apartmentmate who had never been to the area before just visited a few tourist-oriented spots in the city. Another time another friend was visiting, and they went to the Dike March (for those of you unfamiliar with the area, that’s actually the name - the parade the day before the huge pride parade in downtown San Francisco), walked through part of Haight-Ashbury, and then saw some teenagers smoke pot on board a BART train to Berkely on the way to dinner. These are her limited experiences with the city. Her explanation to her currently-visiting friend makes it seem like the city is incredibly, incredibly left-wing. While San Francisco is clearly quite liberal, some of her descriptions suggest a giant hippie commune. I only lived there for three months, and really only got to explore the city at large and interact with a variety of people on the weekends, but I’ve still walked through the financial district, Chinatown, Little Japan, the Sunset, and so on… And the reached the conclusion that despite being fairly liberal on a number of issues, the city is really not that drastically unlike any other (with the possible exception of the beautiful scenery of the Bay Area).

I feel like my apartmentmate only gathered experiences which reenforced her preconcieved ideas of what San Francisco would be like. Granted, the particular experiences she’s had truly do support those notions, and I don’t think she believes she has a true understanding of the city (for that matter, I’m not convinced I do either). But it’s still an interesting difference in perceptions. It makes me question my distaste for New York City - I’ve been there more times than I can count, growing up about as far from there as Sunnyvale is from San Francisco, but still dislike it. Even after a close friend going to school there showed me a great time there. Perhaps its time to give it another chance when I go back east near the end of August.

This post of course leads opens up something I was originally hoping to avoid with this blog - the potential drama from writing opinions on someone who reads your blog! As my apartmentmates all know of and perhaps read this blog, despite the fact that it has existed for less than a week. We’ll see.