Software Transactional Memory

As I men­tioned a few weeks ago, I’m writ­ing my master’s the­sis on soft­ware trans­ac­tional mem­ory (STM).

Of course it is still early in the process, and while I’ve got some ideas for my imple­men­ta­tion, and have started pro­to­typ­ing parts of it, most of the time has been spent catch­ing up on all the exist­ing work in the field.

Lit­tle did I know when I accepted the sub­ject that there’d been writ­ten that many papers about it over the last decade. Phew… A com­menter asked me for the ref­er­ences I found use­ful, so here’s an incom­plete list:

Tran­ac­tional Mem­ory Bib­li­og­ra­phy: This site con­tains an up-to-date and extremely com­pre­hen­sive list of ref­er­ences to every­thing writ­ten aobut STM. Just the sheer num­ber of links out from that site is depress­ing, but it’s obvi­ously a won­der­ful place to get an overview of what’s available.

Trans­ac­tional Mem­ory: I bought this book after notic­ing that almost every paper on STM ref­er­enced it. And it was money well spent. The book is well writ­ten, explains the sub­ject clearly, and cov­ers pretty much every­thing I wanted to know. It is split into three main chap­ters (not count­ing the introduction):

The first chap­ter dis­cusses TM purely from a user’s per­spec­tive. What should the API look like, what do we, as pro­gram­mers want or need from a TM imple­men­ta­tion, what should the seman­tics be, and what exten­sions might be use­ful? It explains a num­ber of impor­tant con­cepts, such as weak/strong iso­la­tion, seri­al­iz­abil­ity and lin­eariz­abil­ity, direct and deferred update and many oth­ers. But mostly, this chap­ter is fan­tas­tic as a dis­cus­sion of what TM research should aim towards. With­out get­ting bogged down in imple­men­ta­tion details, it focuses sim­ply on how we’d like it to work (and on the many open ques­tions where we still don’t know which seman­tics would make sense or be most useful).

The sec­ond chap­ter is use­ful as a short­cut, allow­ing new­com­ers such as me to catch up on the last decade’s research. It sum­ma­rizes all the impor­tant papers on STM, from the ear­li­est pre­cur­sors dat­ing back to the 70’s, up to 2006 when the book was pub­lished. The var­i­ous imple­men­ta­tions and results are briefly described, in enough detail for me to under­stand the main ideas pre­sented, and deter­mine whether to look up the paper in ques­tion and read it in full.

The third chap­ter gives a sim­i­lar treat­ment to Hard­ware Trans­ac­tional Mem­ory, and since that is out­side the scope of my project, I’ve skipped lightly over this for now, although I may just read it out of curios­ity later on. In short, it’s a great book for any­one try­ing to find their way in the jun­gle of TM papers.

Haskell STM: Simon Pey­ton Jones and oth­ers at Microsoft Research have done some truly impres­sive work on a STM imple­men­ta­tion for Con­cur­rent Haskell. While those of us work­ing in a messy lan­guage like C++ can’t aspire for such a clean and ele­gant imple­men­ta­tion, there are still many good ideas we can borrow.

And finally, a few indi­vid­ual papers I’ve got­ten a lot out of:

Soft­ware Trans­ac­tional Mem­ory Should Not be Obstruction-Free: As STM grew out of research into lock-free datas­truc­tures and dis­trib­uted sys­tems, the early work was down­right obsessed about mak­ing trans­ac­tions non­block­ing. It took this paper to take a step back and ask whether this require­ment actu­ally makes sense for the rest of us. And guess what? It doesn’t. It com­pli­cates the STM imple­men­ta­tions, and pre­vents some very use­ful optimizations.

What Really Makes Trans­ac­tions Faster fol­lowed up on the above, dis­cussing a num­ber of other ways in which the per­for­mance of STM sys­tems could be improved.

And finally, the ear­lier the­sis that drew me into the subject:

A Soft­ware Trans­ac­tional Mem­ory Library for C++: This is the first imple­men­ta­tion I’ve seen which seri­ously tar­gets C++. Of course many prior C++ imple­men­ta­tions exist, but they’ve gen­er­ally relied on either C or Java idioms, result­ing in an uglier, more error-prone inter­face, and the inabil­ity to per­form a num­ber of opti­miza­tions. This paper describes a proper mod­ern C++ imple­men­ta­tion, rely­ing on generic pro­gram­ming, tem­plate metapro­gram­ming and all the other tricks in a C++ programmer’s toolbox.

Share and Enjoy: These icons link to social book­mark­ing sites where read­ers can share and dis­cover new web pages.
  • Digg
  • del.icio.us
  • StumbleUpon
  • Reddit
  • Technorati

Tags: , , ,

4 Responses to Software Transactional Memory

  1. “Of course it is still early in the process, and while I’ve got some ideas for my imple­men­ta­tion“ Can you describe in gen­eral what are you up to? Are you plan­ing to build a new STM? For which language?

  2. jalf says:

    Sure. As I men­tioned in http://jalf.dk/blog/2009/08/thesis-yay/ I’m going to try to imple­ment a STM in C++, mak­ing some use of the var­i­ous new C++0x features.

    At the moment, I’m plan­ning to use deferred update (so trans­ac­tions will have to store local copies of the objects they mod­ify, and over­write the global ver­sions when com­mit­ting). Rvalue ref­er­ences in C++0x solve some of the prob­lems with this approach, both speed­ing it up by turn­ing the sec­ond final copy oper­a­tion into a move, and improv­ing excep­tion safety.

    Set­tling on C++ makes some aspects a lot eas­ier than in, say, Java, but obvi­ously also presents some chal­lenges. Some of the advan­tages are the high level of type safety enabled by tem­plates, and the built-in mech­a­nism for copy­ing objects. Rather than Java’s Clone() which never really worked well in the first place, and pass-by-reference seman­tics, C++ passes by value and has a copy­ing mech­a­nism built in at the low­est level with copy con­struc­tors, which means tak­ing backup copies of objects is pretty triv­ial, and can be done on exist­ing types with­out requir­ing any intru­sive changes (inher­it­ing from some STM base class, for exam­ple, or requir­ing users to imple­ment spe­cific interfaces).

    I’ll post some more details soon.

  3. Ben Karel says:

    Awe­some!

    Dunno if you’ve seen this paper, but — con­sid­er­ing the C++0x mem­ory model work — you might find it inter­est­ing: What Do High-Level Mem­ory Mod­els Mean for Transactions?

  4. jalf says:

    Thanks! No, hadn’t seen that one, but will give it a read immediately. :)

Leave a Reply

Name and Email Address are required fields. Your email will not be published or shared with third parties.