Re: [boost] Non-allocating future-promise

Subject: Re: [boost] Non-allocating future-promise
From: Hartmut Kaiser (hartmut.kaiser_at_[hidden])
Date: 2014-10-17 20:42:10

Niall,

> > > __attribute__((noinline)) int test1()
> > > {
> > >   promise<int> p;
> > >   auto f(p.get_future());
> > >   p.set_value(5);
> > >   return f.get();
> > > }
> > >
> > > ... reduces to exactly:
> > >
> > > _Z5test1v:                              # @_Z5test1v
> > > 	.cfi_startproc
> > > # BB#0:                                 # %_ZN7promiseIiJEED2Ev.exit2
> > > 	movl	$5, %eax
> > > 	ret
> >
> > That's cool! I assume all of the necessary synchronization is done
> > lock-free?
> 
> Yep. Using my new spinlock library, the one I built the safe erasing
> concurrent_unordered_map with. 

What suspension mechanism does this rely on? Does it suspend the kernel
thread?

> I can absolutely guarantee that this
> sequence always reduces to nothing:
> 
> basic_promise<int> p;
> p.set_value(5);
> auto f(p.get_future());
> return f.get();
> 
> This is because we can detach the future from the promise in
> get_future() and therefore skip use of atomics, and it turns out that
> clang and GCC are clever here and spot the opportunity to reduce. I
> am currently deciding what to do about this sequence:
> 
> basic_promise<int> p;
> auto f(p.get_future());
> p.set_value(5);
> return f.get();
> 
> The big problem is that you can't have non-trivial destructors with
> constexpr which rules that out (we need destructors to zero out the
> pointer to self in the other side). We cannot switch on atomic use if
> we wish to retain constexpr reduction, so the default safe choice is:
> 
> 1. Switch on atomic use in get_future(), so get_future() halts
> constexpr onwards.
> 
> 2. We add an atomic_basic_future which turns on atomics like this:
> 
> basic_promise<int> p;
> auto f(make_atomic(p.get_future())); // switches on locking
> // Locks promise, locks future, sets value, detaches relationship,
> unlocks
> p.set_value(5);
> // constexpr
> return f.get();
> 
> The future<T> convenience template alias would therefore always alias
> to atomic_basic_future<> for compatibility.

While all of this demonstrates impressive optimization technologies, I don't
think it's a relevant use case. In 99.9% of all use cases this is not
applicable. So why worry?

> > > The non-allocating future-promise is intended to be compatible with
> > > the Concurrency TS extensions
> > > (http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n4123.html)
> > > where futures can have continuations scheduled against them via a
> > > future.then(callable). However, this involves an unavoidable memory
> > > allocation, which while fine for dynamically assigned continuations
> > > is overkill for statically assigned continuations.
> > >
> > > There is no reason why one could not also have a method of statically
> > > adding continuations which uses type extension to store the
> > > additions. Let us say we have a template<class T, class...
> > > Continuations> class promise and that this promise also provides a
> > > .then(callable) like this:
> >
> > FWIW, N4123 adds .then to the future<> type, not the promise<>.
> 
> Sure. That's because future.then() executes its continuations at the
> point of someone doing a future.get().

No, future.then() is called whenever somebody else sets the value (using
promise.set_value()) - well except when using launch::deferred, but there
all bets are off anyways.

> As promise.then() attaches continuations to the promise instead, it
> would execute its continuations at the point of someone doing a
> promise.set_value() or promise.set_exception().
> 
> (Some might wonder why not subclass basic_promise<> and override the
> set_value()/set_exception() with custom behaviour? Unlike promise,
> basic_promise is designed to be customised and subclassed in a family
> of future-ish promise-ish types. It's a very valid point, but I worry
> about generic extension, see below).

I'd be absolutely against attaching continuations through the promise. It's
conceptually wrong.

> > I don't
> > think it makes a lot of sense to add it to the promise in the first
> place as
> > continuations are something local to the consumer, not the producer.
> 
> There is a very valid use case for continuations being executed at
> both places: at the point of value release AND/OR at the point of
> value acquire. AFIO, for example, schedules its continuations in the
> thread where an op completes, not in the thread which gets the result
> of an op (which may be never). I currently have a struct async_io_op
> containing a shared_future and a routine which wraps set_value() to
> launch the continuations, I would much rather prefer a native
> afio::future<> with customised behaviour.
> 
> The really key part is that all futures belonging to the future
> family can work together. If I therefore feed to when_all() a
> heterogenous sequence of future family types, that "just works"
> because every future turns into a permit object fundamentally. Right
> now one has to hoop jump a bit mixing when_all() with AFIO because
> AFIO needs to store extra stuff with each future, hence the struct
> async_io_op wrapping the future when ideally we'd have the future
> wrap the extra stuff.
> 
> However, it is exactly implementing things like when_all() where
> being able to statically hook arbitrary continuations to either side
> of the future-promise relationship *from the outside* can make life
> vastly easier. One simply needs to accept that your basic_future<...>
> may contain a very long sequence of variadic lambda types, and
> therefore you can only ever use auto or decltype/result_of for its
> storage declaration.
> 
> Obviously if you don't use static continuations, one need not worry
> about unwritable type declarators.

Sorry, you lost me here.

> > > template<class F> promise<T, Continuations..., F> then(F &&c)
> > > {
> > >   return promise<T, Continuations..., F>(std::move(*this),
> > > std::forward<F>(c));
> > > }
> > >
> > > ... and therefore to statically add continuations to the future
> > > promise, one simply iterates .then(callable) on the promise like
> > > this:
> > >
> > > auto p=promise<int>().then([]).then([]) ...;
> > > auto f=p.get_future();
> > > p.set_value(5); // executes all the continuations
> > >
> > > My first question to the Boost community is this: is there some less
> > > ugly way? I'm thinking maybe the promise's constructor could take a
> > > set of continuations, and then a make_promise(callable, callable,
> > > ...) could construct a statically continued future-promise?
> >
> > You seldom want to chain .then() calls, in my experience.
> 
> You're right for non-generic code. The trouble with families of
> futures is that the metaprogramming can explode. I don't want bad
> design choices now to break the genericity later.

I have not seen this happening even for generic code for our use cases, but
I probably don't understand yours.

> > Most of the time to attach one continuation and pass the resulting
> future
> > to some other place where you might attach another continuation, etc.
> 
> I have no issue with this and dynamic continuations.
> 
> With static continuations I can't see how to do static continuations
> without either (a) elaborating the type of both future and promise to
> store those continuations or (b) type slice the pointer from promise
> to future, and have a virtual function be invoked to set values.
> 
> The (a) scenario forces the programmer to add all static
> continuations to promise before fetching a future.
> 
> The (b) scenario is a big vote in favour of an atomic_basic_future<>
> which turns on atomics and contains a virtual type uneraser function
> for promise to set the value through. It would all still be no alloc
> and still very, very fast - we are talking dozens of opcodes versus
> thousands with std::future.

What do you mean by 'static continuation'? What's the difference to a
continuation as defined in N4123?

> Some might wonder why do we need constexpr reduction of future
> promise anyway? Well, monadically speaking, a promise suspends
> execution and a future resumes execution. When combined with
> expected<T, E>, you effectively get coroutined monadic programming
> via future promise because you can squirrel away a monadic operation
> into a promise, and resume execution from a future.
> 
> This isn't as good as C++ 17 resumable functions. But it may be handy
> enough, and we get this now not later.
>
> > > My second question to the Boost community is this: should static
> > > continuations be able to see the value being set? Or indeed, to
> > > modify it before it gets sent to future.get()?
> >
> > What would be the point of having a continuation which does not see the
> > value once set?
> 
> I was thinking that basic_future and basic_promise wouldn't force any
> particular continuations policy on subclasses - basic_future<void> is
> a good example why.
> 
> I was thinking that basic_future<T>.then(callable) would do the
> following outcomes:
> 
> 1. If callable(basic_future<T>), the future just set/got is passed to
> the continuation. As future<U> is template aliased to
> basic_future<expected<U, exception_ptr>> this matches the then() in
> the Concurrency TS.
> 
> 2. If callable(T) i.e. the type carried by the basic_future, this is
> equivalent to calling the callable with the future.value(). If T were
> expected<U, E>, that means one resumes a monadic sequence.
> 
> 3. If callable(), the callable is simply invoked. It costs me nothing
> to add this, so you might as well. I can see atexit_future() type use
> cases.

Sure. 

Regards Hartmut
---------------
http://boost-spirit.com
http://stellar.cct.lsu.edu