Peter Seibel - Coders at Work - Reflections on the craft of programming

Seibel:In a locks-and-condition-variables program it would probably go the other way—the librarian would lock the library and nobody could check out books until it’s completely reorganized. So you would probably look at this problem and immediately say, “We can’t lock the library until we’re done,” disallowing checkouts so we have to come up with some hairier locking scheme.

Peyton Jones:Right. Make a little sub-library or something—put the commonly borrowed books out there so undergraduates can borrow them while you lock the main library and reorganize it or something. So now you’ve got to think of an application-specific strategy and now you’ve got to express it in some way. Well, the same problem arises in both cases—you need an application-specific strategy so you can reorganize the library despite not wanting to block out all sorts of borrowing. Once you’ve done the hard thinking about how you wish to do it, now you’ve got to express that. What is the medium in which to express it? STM is a clear win. It’s just much better than locks and condition variables for expressing concurrent programs.

Seibel:What if I don’t even want to allow for the possibility that someone comes in and looks for the 21st most-requested book and gets blocked? In the physical world you can imagine that when someone checks out a book we swap in a proxy for the book that the librarian then reorganizes and whenever a book comes back we put it back wherever the proxy is now. But you are modifying the library which seems, in an STM world, like it would cause the librarian to have to retry his whole transaction.

Peyton Jones:But there’s something that stayed the same—the key on the book is guaranteed not to change somehow, right? So there’s a number of ways you could do this. One is you could say, “What you do when you replace it with a proxy is you don’t modify the library at all”—that’s unchanged. What you do is you modify the book itself. And you don’t modify its key field—you only modify its value field, where it’s currently living. Now the index can be reorganized while the book is somewhere else. That’s cool—and you can express that perfectly naturally.

With STM, at the end the librarian looks through all the memory locations that he has read and sees if they contain now the same values that they did when he read them. So the locations that he has read will include the key field of the book because that determined where he put it. But he hasn’t read the contents of the book. So he’ll say, “Ah, this book—does this key field still contain 73; oh, yes it does.”

But I don’t want to minimize the problem of starvation because it’s a bit insidious. You need good profiling tools that point you at transactions that are failing to commit because they keep getting bumped so that, rather than the program just silently not doing very much, you get some feedback about it. The same is true of a lock-based program. I hate it when those hourglasses appear.

Seibel:I guess in locked-based programs we’ve just learned to try hold locks for as short a duration as possible since that will give us the least contention.

Peyton Jones:Right. But, of course, then it’s harder to program. Finergrained locking is tricky to get right. I think this is one of the huge wins of STM, is it gives you the fine granularity of very fine-grained locking along with very simple reasoning principles.

Here’s a reasoning principle that STM gives you that locks absolutely do not. I’ll establish my top-level invariants—I’ve got a bunch of bank accounts, the total sum of money in all the bank accounts added together is N . Money moves between bank accounts—that’s all. So there’s my invariant. Any transaction assumes that invariant at the beginning and restores it at the end. How do you reason that it does? We look at any one transaction that says, “Take three out of that one and put three into that one.” Good, invariant maintained. How is my reasoning in that done? Purely sequential reasoning. Once I’ve described some top-level invariants, I can reason completely sequentially about each transaction separately.

Seibel:Because you have transaction isolation.

Peyton Jones:Because they are put in isolation. So that’s really rather a powerful reasoning principle. Because it says you can use your sequential reasoning about imperative code despite the fact that the program’s concurrent. You’ve got to establish what those top-level invariants are, but that’s good for your soul, too. Because then you know what things you are trying to maintain. If you get an exception thrown in the middle of a transaction, that’s cool, too—that can’t destroy the invariants because the transaction is abandoned without effect. I think this is fabulous. Then reasoning about performance issues is a different level—you’ve guaranteed a certain sort of correctness; now you want to make sure you haven’t got any performance holes. Those are harder to get at—at the moment I don’t know anything better than profiling and directed feedback tools for doing that.

Seibel:It strikes me that while optimistic concurrency has been used from time to time in persistent databases, it’s never really gotten a foothold there compared to lock-based concurrency.

Peyton Jones:Of course STM can be implemented in all sorts of ways—optimistic concurrency is only one of them. You can lock as you go, which is more like a pessimistic concurrency model.

Seibel:But there’s also a reason that lock managers are the hairiest part of databases.

Peyton Jones:Right. So the thing about STM is you want to make sure that one person, or one team, gets to implement STM and everybody else gets to use it. You can pay them a lot of money and shut them in a small dark room for a year to try to make sure they do a really good job.

But then that work is usable by everybody through a very simple interface. That’s what I think is nice about it. What I want to avoid is having that level of expertise in everybody’s head. The example that I used at a talk I gave yesterday—this comes from Maurice Herlihy—is a double-ended queue: insert and delete elements.

A sequential implementation of a double-ended queue is a first-year undergraduate programming problem. For a concurrent implementation with a lock per node, it’s a research paper problem. That is too big a step. It’s absurd for something to be so hard. With transactional memory it’s an undergraduate problem again. You simply wrap “atomic” around the insert and delete operations—job done. That’s amazing, I think. It’s a qualitative difference. Now the people who implement the STM, they’d have to make sure they atomically commit a bunch of changes to memory as one. That’s not easy to do, just with compare and swaps. It can be done but you have to be careful about it.

And then if there are performance problems to do with starvation then you may need to do some application-level thinking about how to avoid that. But then you express the results of your application-level thinking, again using STM. I do think for that kind of program it’s a leap forward.

There was one other thing I wanted to mention—this goes back to functional programming. STM, of course, has nothing directly to do with functional programming at all. It’s really about mutating shared state—that doesn’t sound very functional.

But what happened is this, I went to a talk given by Tim Harris about STM in Java. I’d never heard about STM before; I just happened to go to his talk. He was describing an STM in which he had “atomic” but really not much else. You could implement these atomic transactions.