A second executor compromise

executor_compromise_the_return.md

Compromise part 2 - a lazy simplification of P0443

This document arose out of offline discussion largely between Lee, Bryce and David, as promised during the 2018-08-10 executors call.

The discussed compromise is that we should replace the enqueue functions with a limited set of lazy task factories. Any syntactic cost of providing a trivial output receiver to these operations can be hidden in wrapper functions. We do not expect a runtime cost assuming we also provide a trivial parameter-dropping receiver in the standard library that the implementation can optimize against.

By passing a full set of parameters to a task construction functions, any task we place in a task graph may be type erased with no loss of efficiency. There may still be some loss of efficiency if the executor is type erased before task construction because the compiler may no longer be able to see from the actual executor into the passed functions. The earlier we perform this operation, however, the more chance there is of making this work effectively.

The fundamental executor concepts

An executor should either be a sender of a sub executor, or a one way fire and forget entity. These can be implemented in terms of each other, and so can be adapted if necessary, potentially with some loss of information.

We may require or prefer to switch between these.

SenderExecutor

A SenderExecutor is a Sender and meets the requirements of Sender. The interface of the passed receiver should be noexcept.

Function	Semantics
void submit(Receiver<SenderExecutor::SubExecutorType>) noexcept	At some future point calls on_value(subExecutor) on the receiver on success, where subExecutor is *this or some subset of *this as useful. At some future point calls on_error(ErrorType on failure.
ExecutorType executor() noexcept	Returns an executor. By default, *this.

submit and executor are required on an executor that has task constructors. Submit is a fundamental sender operation that may be called by a task at any point. To avoid deep recursion, a task may post itself directly onto the underlying executor, giving the executor a chance to pass a new sub executor. For example, if a prior task completes on one thread of a thread pool, the next task may reenqueue rather than running inline, and the thread pool may decide to post that task to a new thread. Hence, at any point in the chain the sub executor passed out of the executor may be utilized.

OneWayExecutor

The passed function may or may not be noexcept. The behavior on an exception escaping the passed task is executor-defined.

Function	Semantics
void execute(void(void))	At some future point calls the passed callable.

Task construction functions

An executor may provide one of the following task construction functions at a minimum. This minimal set is intended to cover the functionality in P0443.

We may require or prefer an executor with support for any of these task construction functions.

In all cases, an exception that escapes the passed function will be passed to the on_error function of the outgoing receiver.

Function	Semantics
Sender<T'> make_value_task(Sender<T>, T'(T))	Accepts a sender that triggers the work, returns a Sender that confirms completion of the work. Either T or T' may be void. If the Sender calls on_error(E) or done() then those operations will propagate from Sender'
Sender<T'> make_bulk_value_task(Sender<T>, T'(T), size_t ShF(), S SF(), R RF())	Accepts a sender that triggers the work, returns a Sender that confirms completion of the work. Either T or T' may be void. If the Sender calls on_error(E) or done() then those operations will propagate from Sender'. Other parameters are as in P0443.

In the above Sender<Type> and Sender<Type> refer to:

• a NoneSender or a SingleSender<NoneSender> if Type is void
• a SingleSender<Type> or a SingleSender<SingleSender<Type>> if Type is not void

The option to pass a sender through the value propagation path above allows the system to encapsulate a subexecutor in the propagation, or to provide greedy enqueue. The actual value is boxed into a sender explicitly in the type system and under control of the executor.

The type propagated through the graph here will be either T, as defined by the function, or a sender of T. The reason for this is that any executor may choose to wrap its value in some information - that information may be propagation of a sub executor, it may be asynchronous information so that the tasks can be greedily enqueued and run in some other context, out of band of calls to on_value. At any point the passed Sender<T> can take a receiver of T to collapse the Sender back into a value, providing compatibility with an arbitrary receiver and a terminal point for asynchronous work chaining.

Sender and Receiver concepts

Required additional concepts from P1055:

• NoneSender
• NoneReceiver
• SingleSender
• SingleReceiver

Ordering guarantees

There are two strong guarantees made here, to allow eager execution:

• Memory operations made before the call to a task constructor happen-before the execution of the task.
• Completion of the task happens-before a call to set_value on the next receiver in the chain, including the implicit receiver implied by a task constructor.

A task may therefore run at any point between constructing it, and being able to detect that it completed, for example, by seeing side effects in a subsequent task. This allows tasks to run on construction, in an eager fashion, and does not allow a user to rely on laziness.

The definition of the API does, however, allow laziness and as such no sender is guaranteed to run its contained work until a receiver is passed to its submit method (or it is passed to a task constructor that calls submit implicitly).

As an optional extension, we may define properties that define whether tasks are guaranteed, or allowed, to run eagerly on construction, assuming that their inputs are ready.

Before and after

In the table below, where a future is returned this is represented by the promise end of a future/promise pair in the compromise version. Any necessary synchronization or storage is under the control of that promise/future pair, rather than the executor, which will often allow an entirely synchronization-free structure.

Before	After
executor.execute(f)	executor.execute(f)
executor.execute(f)	executor.make_value_task(NoneSender{}, f).submit(SinkReceiver{})
fut = executor.two_way_execute(f)	executor.make_value_task(NoneSender{}, f).submit(futPromise)
fut' = executor.then_execute(f, fut)	executor.make_value_task(fut, f).submit(fut'Promise)
executor.bulk_execute(f, shf, sf)	executor.make_bulk_value_task(NoneSender{}, f, shf, sf, [](){}).submit(SinkReceiver{})
fut = executor.bulk_twoway_execute(f, shf, sf, rf)	executor.make_bulk_value_task(NoneSender{}, f, shf, sf, rf).submit(futPromise{})
fut' = executor.bulk_then_execute(f, shf, sf, rf, fut')	executor.make_bulk_value_task(fut, f, shf, sf, rf).submit(fut'Promise{})

If a constructed task is type erased, then it may benefit from custom overloads for known trivial receiver types to optimize. If a constructed task is not type erased then the outgoing receiver will trivially inline.

We do not expect any performance difference between the two forms of the one way execute definition. The task factory-based design gives the opportunity for the application to provide a well-defined output channel for exceptions. For example, the provided output receiver could be an interface to a lock-free exception list if per-request exceptions are not required.