Of course it is still early in the process, and while I’ve got some ideas for my implementation, and have started prototyping parts of it, most of the time has been spent catching up on all the existing work in the field.
Little did I know when I accepted the subject that there’d been written that many papers about it over the last decade. Phew… A commenter asked me for the references I found useful, so here’s an incomplete list:
Tranactional Memory Bibliography: This site contains an up-to-date and extremely comprehensive list of references to everything written aobut STM. Just the sheer number of links out from that site is depressing, but it’s obviously a wonderful place to get an overview of what’s available.
Transactional Memory: I bought this book after noticing that almost every paper on STM referenced it. And it was money well spent. The book is well written, explains the subject clearly, and covers pretty much everything I wanted to know. It is split into three main chapters (not counting the introduction):
The first chapter discusses TM purely from a user’s perspective. What should the API look like, what do we, as programmers want or need from a TM implementation, what should the semantics be, and what extensions might be useful? It explains a number of important concepts, such as weak/strong isolation, serializability and linearizability, direct and deferred update and many others. But mostly, this chapter is fantastic as a discussion of what TM research should aim towards. Without getting bogged down in implementation details, it focuses simply on how we’d like it to work (and on the many open questions where we still don’t know which semantics would make sense or be most useful).
The second chapter is useful as a shortcut, allowing newcomers such as me to catch up on the last decade’s research. It summarizes all the important papers on STM, from the earliest precursors dating back to the 70’s, up to 2006 when the book was published. The various implementations and results are briefly described, in enough detail for me to understand the main ideas presented, and determine whether to look up the paper in question and read it in full.
The third chapter gives a similar treatment to Hardware Transactional Memory, and since that is outside the scope of my project, I’ve skipped lightly over this for now, although I may just read it out of curiosity later on. In short, it’s a great book for anyone trying to find their way in the jungle of TM papers.
Haskell STM: Simon Peyton Jones and others at Microsoft Research have done some truly impressive work on a STM implementation for Concurrent Haskell. While those of us working in a messy language like C++ can’t aspire for such a clean and elegant implementation, there are still many good ideas we can borrow.
And finally, a few individual papers I’ve gotten a lot out of:
Software Transactional Memory Should Not be Obstruction-Free: As STM grew out of research into lock-free datastructures and distributed systems, the early work was downright obsessed about making transactions nonblocking. It took this paper to take a step back and ask whether this requirement actually makes sense for the rest of us. And guess what? It doesn’t. It complicates the STM implementations, and prevents some very useful optimizations.
What Really Makes Transactions Faster followed up on the above, discussing a number of other ways in which the performance of STM systems could be improved.
And finally, the earlier thesis that drew me into the subject:
A Software Transactional Memory Library for C++: This is the first implementation I’ve seen which seriously targets C++. Of course many prior C++ implementations exist, but they’ve generally relied on either C or Java idioms, resulting in an uglier, more error-prone interface, and the inability to perform a number of optimizations. This paper describes a proper modern C++ implementation, relying on generic programming, template metaprogramming and all the other tricks in a C++ programmer’s toolbox.