Software! Math! Data! The blog of R. Sean Bowman
The blog of R. Sean Bowman
June 10 2015

Previously we looked at a simple counter using STM, software transactional memory. It’s maybe not the best example of showing off the power of STM, so let’s have another look.

People sometimes tout STM as being composable. What does that mean? Let’s have a look at a hypothetical bank account system:

class Account {
    int amount;
public:
    void deposit(int funds) {
        __transaction_atomic {
            amount += funds;
        }
    }

    void withdraw(int funds) {
        __transaction_atomic {
            amount -= funds;
        }
    }
};

No big deal, we have an account which is thread safe by virtue of using the atomic operations we talked about last time. (Of course, it’s a completely brain dead implementation that only keeps track of whole dollars, etc., etc., but it’s for illustration, so bear with me.)

What happens if we want to transfer funds from one account to another? A naive attempt looks like this:

void transfer(Account& from, Account& to, int amount) {
    from.withdraw(amount);
    to.deposit(amount);
}

But think for a second. If the account holder is not spending or receiving money, we want to maintain the invariant that from.value + to.value is constant. That invariant is violated in between the withdraw and deposit operations. A thread doing other things while this transfer takes place may see the wrong total amount of money! Unacceptable!

If we were using traditional locks (std::mutex, say), we’d have a hard time making this work correctly: we need to lock the deposit and withdraw methods of both accounts, and we also need to lock the statements in transfer. I’m sure it can be done, but it seems tricky. The STM solution is as simple as can be: just wrap the transfer in an atomic block:

void transfer(Account& from, Account& to, int amount) {
    __transaction_atomic {
        from.withdraw(amount);
        to.deposit(amount);
    }
}

This works because STM transactions can be nested. That, essentially, is what’s meant by composable. In this case, we have all the code right there in front of us. But suppose we were designing some library that might in turn be used by other library designers, or end users. We have no way of knowing what they might do with our library, and in particular how their code needs to behave with respect to concurrency. With traditional locks, this can be an issue. But it’s not with STM! We just use atomic blocks where we need to, knowing that our downstream clients can use atomic blocks as well, without worrying about nesting.

Conclusion

So we’ve seen several cool things about STM: first, it’s pretty easy to use, even for folks like me who have to cogitate real hard on matters of concurrency. Second, it’s composable, which is important for lots of reasons, with library design being a crucial one. A third (and much more controversial) note is that STM can perform well in certain situations. STM is optimistic in the sense that it allows threads to do whatever they want to at the same time, and only rolls back the transaction if it detects that two threads have stepped on each others’ toes. For applications with many reads and few writes (what this means is application dependent, but whatever), this might give a performance benefit over locking or other approaches.

Here are a few links that I found helpful in understanding this stuff and getting it to work under gcc:

Approx. 577 words, plus code