Mutually Excluded Composibility

The other day there was a post over at Bartosz Milewski’s Programming Cafe about the recent upsurge in interest in functional programming among the C++ community. There was some push-back in the comments – there always seems to be when functional programming comes up, especially if STM is mentioned (as it was). There was one comment in particular that offered up std::lock as the solution to dead-lock that demolishes any need to resort to STM. Suffice it to say that I think the commenter missed the point of Bartosz’ post a bit, and he’s putting a but too much faith in std::lock as well. While std::lock can remove any chance of dead-lock when using multiple mutexes, it can only do so in certain cases and if you’re going to rely on it to solve all your problems you’re going to need to sacrifice all the composibility you once had at your disposal.

Here I’m defining composibility as the ability to combine solutions to small problems into solutions to larger problems without having to know all the implementation details of the small solutions – in programming this takes the form of writing and calling functions. Being able to do this greatly lessens the cognitive load on the programmer freeing up lots of cycles to work on harder problems.

Mutexes completely destroy composibility. Let’s say thread A locks mutex one and while holding that mutex calls function foo. Unless there is a guarantee that foo locks no mutexes we’ve just introduced the possibility of dead-lock into our program: thread B could have already locked mutex two, the mutex that foo is going to lock, and is then attempting to lock mutex one, the mutex that thread A already has locked. A classic dead-lock. So in order to safely call any functions while holding a lock you need to know the implementation detail that the function locks no mutexes: blam, composibility is dead.

But maybe std::lock can come to our rescue. Maybe there’s some way for std::lock to juggle the locks so that dead-lock is avoided. In order to do this when crossing function boundaries it would have to be able to release and reacquire locks that are already held by the thread when it is called. This would be a disaster since the caller of the function is relying on the mutual exclusion that those already existing locks are providing. If a lock is released during the function call and then reacquired lord only knows what has been done to the resource that was being protected and any state that is being relied in the caller could be lost. In fact std::lock only provides dead-lock avoidance among the locks passed to it in any given call. Once you make a second call to std:lock while still holding the locks from the first call any guarantees of dead-lock avoidance are gone.

So even when using std::lock, composibility is dead: you can still only call functions that take no locks while holding locks. Sure, you could arrange things so that this is the case and you use std::lock to lock all your mutexes ahead of time. But this is a lot more to think about than when composibility is alive and well. Now a system like STM still has impacts on composibility, the avoidance of side-effects in transactions being the big one. But it is usually built-in to the interface of the system (e.g. Haskell’s STM monad that disallows side-effects at compile time) and much easier to work around then dealing with locks: when you need the lock there’s no way around getting the lock and to avoid dead-lock you’ll have to restructure your code to obtain that lock without introducing the chance of dead-lock. In an STM system, when you’ve determined that you need side-effects you can normally save up the side-effects for when your transaction commits. In my experience the latter is much easier to reason about and requires no restructuring of code. A similar case could probably be made for the actor model and other higher-level concurrency abstractions.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: