Re: [boost] Lightweight futures (was: Re: Final lightweight monad, next gen futures and upcoming AFIO review

Subject: Re: [boost] Lightweight futures (was: Re: Final lightweight monad, next gen futures and upcoming AFIO review
From: Niall Douglas (s_sourceforge_at_[hidden])
Date: 2015-07-01 06:29:40

On 30 Jun 2015 at 22:37, Michael Marcin wrote:

> Forgive me if this is dumb I haven't looked at the implementation of a 
> future/promise solution before and I was curious.
> 
> It seems the basic strategy is to have a member variant called 
> value_storage in both the promise and the future.
> 
> Let me see if I can enumerate the flows:
> 
> - If you set_value on a promise twice you get an already_set error.
> 
> - If you set_value on a promise that noone has gotten the future of you 
> set the storage of the promise to the value
> 
> - If you set_value on a promise that someone has gotten the future of 
> you set the storage of the future to the value and detach the promise 
> from the future
> 
> - If no one ever gets the future and the value is set then the value 
> gets destroyed in the promise's storage when the promise is destroyed
> 
> - If someone gets the future before the value is set then a future is 
> constructed and the promise's storage stores a pointer to the future
> 
> - If someone gets the future then gets it again while the first future 
> still exists it throws future_already_retrieved

Sounds about right so far.

> - If someone gets the future then destroys the future then gets the 
> future again it is now safe to call get_future again on the promise so 
> long as the value was never set (This seems rather complicated, is it 
> necessary?)

That's a bug! So thank you. What should happen is that the future 
destructor should set the promise to detached if no value was set. 
I'll fix that shortly.

> - If someone sets the promise value then gets the future this is the 
> fast path no lock is ever taken, the promise is left detached with empty 
> storage and the value has been moved to the future's storage

Until late last night, this was the case. I found I could shave off 
15% CPU cycles by removing this optimisation as it makes the output 
code less branchy and I'm overloading the branch predictor, so it 
makes a big difference. It's still in there for the unit testing to 
prevent me writing code which causes failure to constant expression 
reduce, but #ifdef'd out by default.

> Is this about right?
> 
> I'm not sure that _need_locks being changed inside of get_future is 
> always going to be visible other threads. The documentation says it will 
> be thread safe after you have called get_future but I don't see anything 
> that necessarily creates a happens-before relationship between other 
> threads reading _needs_locks. I am not an expert though.

It's a good question, and thank you for taking the time to review the 
code and the design.

What you are missing is that we assume that whoever is calling 
get_future() must issue some form of memory synchronisation to 
transmit the newly constructed future to another thread. That 
synchronises the changed _needs_locks to other threads. I suppose it 
is possible that someone could send the future to one thread, and 
have a different thread do a state read and in theory the state 
reading thread doesn't see any new state.

However, that is part of the design in general anyway, and it will be 
documented that any examination of promise-future state between 
synchronisation points (I have still to document which APIs are 
those) may be stale. I've taken care to make sure that unlocked state 
reads cannot be racy. Modulo bugs of course.

I have yet to write this up into the docs, but a very strong advice 
will be given to not concurrently consume lightweight future promise 
from more than one thread. Multiple threads able to set the promise 
are fine, but there should be only one thread able to inspect and get 
from the future at any one time. Lightweight future-promise should 
still be safe to get() from multiple threads concurrently as wait() 
synchronises, but any inspection of state from multiple threads 
concurrently will be racy.

Any design where multiple threads can consume a future concurrently 
is likely a very bad design. Use a shared_future instead where 
concurrent get() is intended.

Niall

-- 
ned Productions Limited Consulting
http://www.nedproductions.biz/ 
http://ie.linkedin.com/in/nialldouglas/