Re: [boost] Non-allocating future-promise

Subject: Re: [boost] Non-allocating future-promise
From: Niall Douglas (s_sourceforge_at_[hidden])
Date: 2014-10-17 20:08:19

On 17 Oct 2014 at 16:07, Hartmut Kaiser wrote:

> > __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. 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.

> > 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().

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 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.

> > 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.

> 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.

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.

Niall

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