std::future and std::promise are two ends of a single-item queue. A typical implementation has the future and the promise sharing a 3rd struct that is the queue. Typically via a shared_ptr. Is this 3rd wheel necessary? Wouldn’t it be nice if the allocation could be avoided, and instead, all the bookkeeping was in the future and promise?
Well, it would be nice, but is it possible? Note that each object may be moved or destroyed at any time – how can they communicate (for example, commit the result, or wake a thread waiting on the result, etc) when each may have moved or be moving? How can they track each other? If each has a pointer to the other, the pointers would become invalid (on move, delete), and it would not be safe for one side to update the other. The shared 3rd wheel seems safest.
If we had a lock (eg, a mutex) we could grab the lock before a move/destruction and update the other’s state. ie in the future‘s implementation of a move-constructor, it could obtain the lock, update the promise‘s pointer to the future, complete the move, then release the lock. Similarly, the promise would also grab the lock whenever it needed to read/write the future. But where is the lock? If it was, for example, in the future, then the promise would need to traverse its pointer before grabbing the lock, defeating the purpose. Also, std::mutex is not movable, so it can’t be placed inside either the future nor the promise as those both are movable.
One answer, that is mostly non-allocating, would be to have a cache of mutexes available for the future/promise pairs to use. You would need a way to ensure they both get the same mutex out of the cache, whenever a mutex was needed. ie if the promise wants to write the result into the future, it goes to the mutex-cache hands it an ID (possibly the address of the promise), and locks the returned mutex before writing the result. Meanwhile, if the future wants to move, it also goes to the mutex-cache, gives it the same ID, gets the same mutex, and finds that it needs to wait for the mutex to become available.
The only problem with this answer is what happens when we run out of mutexes in the cache? Two options – either allocate some more mutexes, or re-use currently in-use mutexes. Allocating more works fine, but does mean our future/promise is no longer non-allocating, just mostly non-allocating. Re-using an in-use mutex is an interesting idea. Since the mutex is only locked for ‘small’ actions, like moving the future (which in our scenario is only a few pointers), there would seem to be no problem. HOWEVER, we need to lock the mutex while we move the result into the future. And the result is of type T – ie anything. Does T’s move operator also grab a lock? Does it depend on another future/promise? Does it grab a lock the leads to a chain of dependencies that leads to another promise/future that is colliding/deadlocking on the same from-the-cache mutex? Highly unlikely, but possible. Which is the worst kind of bug – almost impossible to track down, particularly for a user who doesn’t even know that promise/futures could deadlock with each other via an implementation detail. So sharing mutexes cannot be allowed…
Do we need the mutex-cache at all. Short answer: no. Read on…
So the future on the left has a pointer to the promise on the right, and vice-versa.
But we need to be careful before following a pointer, as the other side may be moving or in mid-destruction. How do we synchronize?
The basic pattern is built upon 2 rules, which form a bit of a love story:
1) State “I need you” before accessing your partner
2) “Don’t leave without saying goodbye”
#1 is an acceptance and admittance of personal state, so is proclaimed and manifested on the side doing the claiming/needing.
ie if the promise needs to talk to the future (for example, to set the result) it first sets its own state to N for “I need you”.
It can then (if set successfully) venture over to the future side, and set the result. It knows the future is not going to go away, because the future won’t leave without saying goodbye – which includes checking in on its partner’s state…
// CAS is like compare_exchage for when you don't want the old val back in 'comp' bool CAS(atomic& target, int comp, int val, memory_order order = memory_order_seq_cst) { return target.compare_exchange(comp, val, order); } void promise::set_value(R && r) { // if nothing is going on, then our state should be 0, // and we can set it to N signifying that we Need to talk to our partner if (CAS(state, 0, 'N')) { // now check/set our partner's state: if (CAS(future->state, 0, 'R')) // we are setting 'R'esult { // somehow set the result into the future // (this would more likely be an in-place new // as the result would not have been previously initialized) future->result = r; } else { // this gets tricky. for now imagine looping/waiting and trying again } } else { // well, various scenarios could be here // but we probably need to loop around and try again. // for now, let's leave this blank to focus on other things... } }
Now, setting your own state first is only useful if your partner abides by it.
For example, on move, a future needs to check with the promise, and let it know it is moving.
ie “don’t leave without saying goodbye – don’t even change addresses without telling me”
void future::do_move(future & destination)
{
// signal we need to talk:
if (CAS(state, 0, 'N'))
{
// if successful, go talk
if (CAS(promise->state, 0, 'M')) // I'm 'M'oving
{
move_to_dest(dest);
promise->future = &dest; // inform partner of new address
promise->state = 0; // done
}
// else partner is busy, wait (somehow)...
}
// else loop, try again, etc...
}
So the rules are that you first check/set your own state – you either see that your partner is the middle of using you (and thus you need to wait) or you successfully declare your need for your partner.
Second step is to check on your partners state.
There are lots of problems still, but you can hopefully see that with these two rules we can safely make our intent known, and then read/write your partner without fear of your partner going away.
Now, onto some of the problems. The devil is always in the details…