Sunday, December 17, 2017

waiting for a condition: another way

I've recently encountered another way of doing synchronization without condition variables in the Abseil library: their mutex has the method Await(). It provides an alternative to the construction (copied from their description):

mu.Lock();
... // arbitrary code A
while (!f(arg)) {
  mu.cv.Wait(&mu);
}
... // arbitrary code B
mu.Unlock();

as

mu.Lock();
... // arbitrary code A
mu.Await(Condition(f, arg));
... // arbitrary code B
mu.Unlock();

Here the condition is given in the argument of Await() as a functor, an object that keeps the related context and executes a function in this context, in the new-fangled C++14 code that's usually given as a lambda.

This works by evaluating all the currently requested conditions on unlock, and if one of them becomes true, waking up the appropriate thread. Looks kind of wasteful on the first sight but there are good sides to it too.

One of the typical problems with the classic condition variables is "how fine-grained should they be made"?  Should there be a separate condition variable for every possible condition or can the conditions be mixed sometimes on the same variable? The Await() solves this problem: it can easily allocate a separate variable per condition, and do it right on the stack in Await().  The obvious problem with multiple conditions sharing the same condition variable is that then on a signal multiple threads would wake up, some of them will find their condition and continue, some will not find it and go back to sleep, creating the churn. Await() clearly solves this problem.

But it can do one better too. Another problem is when the right thread wakes up but has to go back to sleep because before it woke up some other thread snuck in, got the mutex and ruined the condition. Await() can guarantee that it won't happen by simply keeping the mutex locked but passing its ownership to the waiting thread. Then when the waiting thread wakes up, it doesn't even need to check the condition again, because it's been already checked for it. This is one of those times where having your own low-level thread library pays off, you couldn't do such a trick with a Posix mutex.

So when they say that it about evens out on performance with the classic condition variables, I think there are good reasons to believe that.