The central concept of this library is the executor as a policy. An executor embodies a set of rules about where, when and how to run a submitted function object. Executors are intended to be lightweight, copyable, and with interfaces defined by type requirements, similar to the other -ors of the standard library, iterators and allocators.

An execution context is the venue where the submitted function objects are executed. Where executors are lightweight and cheap to copy, an execution context is typically long-lived and non-copyable. It may contain additional state such as timer queues, socket reactors, or hidden threads to emulate asynchronous functionality.

For example, we say that a thread_pool is an execution context, and that it has an executor. The thread pool contains long-lived state, namely the threads that persist until the pool is shut down. The thread pool's executor embodies the rule: run functions in the pool and nowhere else.

The proposed text included in this paper defines type requirements for two different kinds of executor:

A concrete execution context, such as the proposed text's thread_pool, can support both kinds of executor. The precise design of these executors is beyond the scope of this particular discussion, and readers are invited to read papers such as P0008R0, P0112R1, and P0113R0 for more information.

This approach breaks down executor type requirements into small, coherent units that focus on the intended use cases. This offers a simpler design and better extensibility than a monolithic Executor concept, such as the executor_traits approach of P0058. Additional executor type requirements may be non-intrusively added, and we will illustrate this extensibility below by showing how parallel algorithm executors might be introduced.

To obtain a trivial executor for an execution context we use get_trivial_executor:

std::experimental::thread_pool pool;
auto ex = std::experimental::get_trivial_executor(pool);

Similarly, to obtain an event executor we use get_event_executor:

std::experimental::thread_pool pool;
auto ex = std::experimental::get_event_executor(pool);

Both get_trivial_executor and get_event_executor are customization points, which are function objects as described in N4381. This pattern is extensively utilised by the draft Ranges Technical Specification.

Users may hook the customization point non-intrusively by providing a free function of the same name in their namespace:

namespace my_namespace {
  class my_thread_pool { ... };
  class my_trivial_executor { ... };
  my_trivial_executor get_trivial_executor(my_thread_pool&);
}

or intrusively as a friend function:

namespace my_namespace {
  class my_trivial_executor { ... };
  class my_thread_pool {
    friend my_trivial_executor get_trivial_executor(my_thread_pool&);
  };
}

Alternatively, the default get_trivial_executor implementation may be used, which automatically calls a get_trivial_executor member function if one is present:

namespace my_namespace {
  class my_trivial_executor { ... };
  class my_thread_pool {
    my_trivial_executor get_trivial_executor();
  };
}

The expression std::experimental::get_trivial_executor(E) is a valid expression if, and only if, it produces a syntactically valid trivial executor. This means we can use it in conjunction with SFINAE to detect at compile time whether a given execution context supports a particular kind of executor.

To introduce a new kind of executor we follow the steps below. For the sake of exposition, let us assume we are adding a new parallel executor.

Step 1: Define the type requirements

We begin by defining the new ParallelExecutor type requirements. These requirements refine the Executor type requirements by adding member functions such as execute, and async_execute. A type that satisfies the ParallelExecutor requirements represents an execution model for determining how parallel algorithms are performed. For example, we might implement the type requirements to utilise a work stealing thread pool. (Note: This example is not intended to prescribe how these type requirements will look. It is expected that this analysis and design would be done by experts in this field.)

Step 2: Define the trait

Next we define a helper trait that lets us determine whether some type T satisfies the syntactic requirements of a ParallelExecutor.

namespace parallel {
  template<class T> struct is_parallel_executor;
} // namespace parallel

Step 3: Define the customization point

Then we define a get_parallel_executor customization point. The customization point is implemented using the mechanism described in N4381.

namespace parallel {
  namespace {
    constexpr unspecified get_parallel_executor = unspecified;
  }
} // namespace parallel

The effect of the expression parallel::get_parallel_executor(E) for some expression E is equivalent to:

— (E).get_parallel_executor() if, for its type X, is_parallel_executor<X>::value is true. If is_parallel_executor<X>::value is false, the program is ill-formed with no diagnostic required.

— Otherwise, get_parallel_executor(E) if, for its type X, is_parallel_executor<X>::value is true, with overload resolution performed in a context that includes the declaration void get_parallel_executor(auto&) = delete; and does not include a declaration of parallel::get_parallel_executor. If is_parallel_executor<X>::value is false, the program is ill-formed with no diagnostic required.

— Otherwise, parallel::get_parallel_executor(E) is ill-formed.

Whenever parallel::get_parallel_executor(E) is a valid expression, the type of parallel::get_parallel_executor(E) satisfies the requirements for ParallelExecutor. This allows us to use SFINAE to detect whether a parallel executor is supported.

Since it is possible to implement our parallel executor in terms of a trivial executor, we may also wish to introduce a new, penultimate case above, that automatically adapts trivial executors to the ParallelExecutor requirements:

— Otherwise, make_parallel_executor_adapter(std::experimental::get_trivial_executor(E)) if std::experimental::get_trivial_executor(E) is a valid expression.

Step 4: Define a template alias

To make it easier for users to name the executor type, we provide a template alias:

namespace parallel {
  template<class T> using parallel_executor_t
    = decltype(get_parallel_executor(declval<T&>()));
} // namespace parallel

Step 5: Use the customization point

Finally, we use the new customization point when implementing our parallel algorithms. For example:

template<class E, class RandomAccessIterator>
auto parallel_sort(E& e, RandomAccessIterator begin, RandomAccessIterator end)
  -> decltype(parallel::get_parallel_executor(e), void())
{
  parallel_executor_t<E> ex = get_parallel_executor(e);
  ...
}

This algorithm can then be used with the thread_pool class defined in this proposal:

std::experimental::thread_pool pool;
parallel_sort(pool, big_vector.begin(), big_vector.end());

One of the motivations for having lightweight, copyable executors is to allow us to encapsulate all sorts of additional information and behaviour on a fine-grained basis, such as:

Sometimes, however, we will need to store information for longer than the lifetime of an individual executor object. As an example, let us say we want to implement a delayed_trivial_executor<> adapter which delays execution of a function object until some time has been reached. This would likely be implemented in terms of a timer queue, and we need this timer queue to live for as long as the underlying execution context (such as a thread pool).

For this reason, the core Executor requirements specify that all executors have an associated execution_context object. The execution_context is a polymorphic set that is indexed by type, and allows us to:

— store long-lived data; and

— register a callback to be notified when execution context shuts down.

Thus, to implement our delayed_trivial_executor<> adapter we begin by defining our timer queue as an execution_context's service:

template<class Clock>
class timer_queue : std::experimental::execution_context::service
{
public:
  timer_queue(std::experimental::execution_context& owner)
  {
    // launch a new background thread to wait for timers to expire
  }

  void shutdown() noexcept override
  {
    // Join the thread and discard any unexecuted functions from the queue.
  }

  void enqueue(typename Clock::time_point expiry, std::function<void()> f)
  {
    // Add the function to the queue with the specified expiry time.
  }

private:
  // Timer queue state
  // ...
};

Our lightweight executor adapter is then implemented in terms of this timer queue:

template<class InnerExecutor, class Clock>
class delayed_trivial_executor
{
public:
  explicit delayed_trivial_executor(
      const InnerExecutor& inner_executor,
      typename Clock::duration delay)
    : inner_executor_(inner_executor), delay_(delay)
  {
  }

  auto context() const noexcept { return inner_executor_.context(); }

  bool operator==(const delayed_trivial_executor& other) const noexcept
  {
    return inner_executor_ == other.inner_executor_ && delay_ == other.delay_;
  }

  bool operator!=(const trivial_executor& other) const noexcept
  {
    return !(*this == other);
  }

  template<class F> void execute(F f)
  {
    auto& timer_q =
      std::experimental::use_service<timer_queue<Clock>>(
        inner_executor_.context()):

    timer_q.enqueue(Clock::now() + delay_,
        [inner_executor_, f=std::move(f)] mutable
        {
          inner_executor.executor(std::move(f));
        });
  }

private:
  InnerExecutor inner_executor_;
  typename Clock::duration delay_;
};

Throughout this Technical Specification, the names of the template parameters are used to express type requirements, as listed in the table below.

namespace std {
namespace experimental {
inline namespace concurrency_v2 {

  enum class fork_event {
    prepare,
    parent,
    child
  };

  class execution_context;

  class service_already_exists;

  template<class Service> Service& use_service(execution_context& ctx);
  template<class Service, class... Args> Service&
    make_service(execution_context& ctx, Args&&... args);
  template<class Service> bool has_service(execution_context& ctx) noexcept;

  namespace {
    constexpr unspecified get_trivial_executor = unspecified;
  }

  template<class T> using trivial_executor_t
    = decltype(get_trivial_executor(declval<T&>()));

  template<class T> struct is_trivial_executor;

  namespace {
    constexpr unspecified get_event_executor = unspecified;
  }

  template<class T> using event_executor_t
    = decltype(get_event_executor(declval<T&>()));

  template<class T> struct is_event_executor;

  // async:

  template<class TrivialExecutor, class F, class... Args>
    future<result_of_t<decay_t<F>(decay_t<Args>...)>>
       async(const TrivialExecutor& ex, F&& f, Args&&... args);
  template<class EventExecutor, class F, class... Args>
    future<result_of_t<decay_t<F>(decay_t<Args>...)>>
       async(const EventExecutor& ex, F&& f, Args&&... args);
  template<class E, class F, class... Args>
    future<result_of_t<decay_t<F>(decay_t<Args>...)>>
       async(E& e, F&& f, Args&&... args);

} // inline namespace concurrency_v2
} // namespace experimental
} // namespace std

Class execution_context implements an extensible, type-safe, polymorphic set of services, indexed by service type.

namespace std {
namespace experimental {
inline namespace concurrency_v2 {

  class execution_context
  {
  public:
    class service;

    // construct / copy / destroy:

    execution_context();
    execution_context(const execution_context&) = delete;
    execution_context& operator=(const execution_context&) = delete;
    virtual ~execution_context();

    // execution context operations:

    void notify_fork(fork_event e);

  protected:

    // execution context protected operations:

    void shutdown() noexcept;
    void destroy() noexcept;
  };

  // service access:
  template<class Service> typename Service::key_type&
    use_service(execution_context& ctx);
  template<class Service, class... Args> Service&
    make_service(execution_context& ctx, Args&&... args);
  template<class Service> bool has_service(const execution_context& ctx) noexcept;
  class service_already_exists : public logic_error { };

} // inline namespace concurrency_v2
} // namespace experimental
} // namespace std

Access to the services of an execution_context is via three function templates, use_service<>, make_service<> and has_service<>.

In a call to use_service<Service>(), the type argument chooses a service. If the service is not present in an execution_context, an object of type Service is created and added to the execution_context. A program can check if an execution_context implements a particular service with the function template has_service<Service>().

Service objects may be explicitly added to an execution_context using the function template make_service<Service>(). If the service is already present, make_service exits via an exception of type service_already_exists.

Once a service reference is obtained from an execution_context object by calling use_service<>, that reference remains usable until a call to destroy().

execution_context();

~execution_context();

void notify_fork(fork_event e);

void shutdown() noexcept;

void destroy() noexcept;

template<class Service> typename Service::key_type&
  use_service(execution_context& ctx);

template<class Service, class... Args> Service&
  make_service(execution_context& ctx, Args&&... args);

template<class Service> bool has_service(const execution_context& ctx) noexcept;

namespace std {
namespace experimental {
inline namespace concurrency_v2 {

  class execution_context::service
  {
  protected:
    // construct / copy / destroy:

    explicit service(execution_context& owner);
    service(const service&) = delete;
    service& operator=(const service&) = delete;
    virtual ~service();

    // service observers:

    execution_context& context() noexcept;

  private:
    // service operations:

    virtual void shutdown() noexcept = 0;
    virtual void notify_fork(fork_event e) {}

    execution_context& context_; // exposition only
  };

} // inline namespace concurrency_v2
} // namespace experimental
} // namespace std

explicit service(execution_context& owner);

execution_context& context() noexcept;

The class template is_trivial_executor can be used to detect executor types satisfying the TrivialExecutor type requirements.

namespace std {
namespace experimental {
inline namespace concurrency_v2 {

  template<class T> struct is_trivial_executor;

} // inline namespace concurrency_v2
} // namespace experimental
} // namespace std

T shall be a complete type.

Class template is_trivial_executor is a UnaryTypeTrait (C++Std [meta.rqmts]) with a BaseCharacteristic of true_type if the type T meets the syntactic requirements for TrivialExecutor, otherwise false_type.

namespace std {
namespace experimental {
inline namespace concurrency_v2 {

  namespace {
    constexpr unspecified get_trivial_executor = unspecified;
  }

} // inline namespace concurrency_v2
} // namespace experimental
} // namespace std

The name get_trivial_executor denotes a customization point. The effect of the expression concurrency_v2::get_trivial_executor(E) for some expression E is equivalent to:

— (E).get_trivial_executor() if, for its type X, is_trivial_executor<X>::value is true. [Note: This means that X meets the syntactic requirements for TrivialExecutor. —end note] If is_trivial_executor<X>::value is false, the program is ill-formed with no diagnostic required.

— Otherwise, get_trivial_executor(E) if, for its type X, is_trivial_executor<X>::value is true, with overload resolution performed in a context that includes the declaration void get_trivial_executor(auto&) = delete; and does not include a declaration of concurrency_v2::get_trivial_executor. If is_trivial_executor<X>::value is false, the program is ill-formed with no diagnostic required.

— Otherwise, concurrency_v2::get_trivial_executor(E) is ill-formed.

Remark: Whenever concurrency_v2::get_trivial_executor(E) is a valid expression, the type of concurrency_v2::get_trivial_executor(E) satisfies the requirements for TrivialExecutor.

The class template is_event_executor can be used to detect executor types satisfying the EventExecutor type requirements.

namespace std {
namespace experimental {
inline namespace concurrency_v2 {

  template<class T> struct is_event_executor;

} // inline namespace concurrency_v2
} // namespace experimental
} // namespace std

T shall be a complete type.

Class template is_event_executor is a UnaryTypeTrait (C++Std [meta.rqmts]) with a BaseCharacteristic of true_type if the type T meets the syntactic requirements for EventExecutor, otherwise false_type.

namespace std {
namespace experimental {
inline namespace concurrency_v2 {

  namespace {
    constexpr unspecified get_event_executor = unspecified;
  }

} // inline namespace concurrency_v2
} // namespace experimental
} // namespace std

The name get_event_executor denotes a customization point. The effect of the expression concurrency_v2::get_event_executor(E) for some expression E is equivalent to:

— (E).get_event_executor() if, for its type X, is_event_executor<X>::value is true. [Note: This means that X meets the syntactic requirements for EventExecutor. —end note] If is_event_executor<X>::value is false, the program is ill-formed with no diagnostic required.

— Otherwise, get_event_executor(E) if, for its type X, is_event_executor<X>::value is true, with overload resolution performed in a context that includes the declaration void get_event_executor(auto&) = delete; and does not include a declaration of concurrency_v2::get_event_executor. If is_event_executor<X>::value is false, the program is ill-formed with no diagnostic required.

— Otherwise, concurrency_v2::get_event_executor(E) is ill-formed.

Remark: Whenever concurrency_v2::get_event_executor(E) is a valid expression, the type of concurrency_v2::get_event_executor(E) satisfies the requirements for EventExecutor.

The function template async provides a mechanism to submit a function to an executor, and provides the result of the function in a future object with which it shares a shared state (C++Std [futures.state]).

template<class TrivialExecutor, class F, class... Args>
  future<result_of_t<decay_t<F>(decay_t<Args>...)>>
    async(const TrivialExecutor& ex, F&& f, Args&&... args);
template<class EventExecutor, class F, class... Args>
  future<result_of_t<decay_t<F>(decay_t<Args>...)>>
    async(const EventExecutor& ex, F&& f, Args&&... args);

template<class E, class F, class... Args>
  future<result_of_t<decay_t<F>(decay_t<Args>...)>>
    async(E& e, F&& f, Args&&... args);

namespace std {
namespace experimental {
inline namespace concurrency_v2 {

  class thread_pool;

} // inline namespace concurrency_v2
} // namespace experimental
} // namespace std

Class thread_pool implements a fixed-size pool of threads.

namespace std {
namespace experimental {
inline namespace concurrency_v2 {

  class thread_pool : public execution_context
  {
  public:
    // types:

    class trivial_executor;
    class event_executor;

    // construct / copy / destroy:

    thread_pool();
    explicit thread_pool(std::size_t num_threads);
    thread_pool(const thread_pool&) = delete;
    thread_pool& operator=(const thread_pool&) = delete;
    ~thread_pool();

    // thread_pool operations:

    trivial_executor get_trivial_executor() noexcept;
    event_executor get_event_executor() noexcept;

    void stop();

    void join();
  };

} // inline namespace concurrency_v2
} // namespace experimental
} // namespace std

The class thread_pool satisfies the ExecutionContext requirements.

For an object of type thread_pool, outstanding work is defined as the sum of:

— the total number of calls to the on_work_started function, less the total number of calls to the on_work_finished function, to any event executor of the thread_pool.

— the number of function objects that have been added to the thread_pool via the thread_pool trivial executor or event executor, but not yet executed; and

— the number of function objects that are currently being executed by the thread_pool.

The thread_pool member functions get_trivial_executor, get_event_executor, stop, and join, the thread_pool::trivial_executor copy constructors, member functions and comparison operators, and the thread_pool::event_executor copy constructors, member functions and comparison operators, do not introduce data races as a result of concurrent calls to those functions from different threads of execution.

thread_pool();
explicit thread_pool(std::size_t num_threads);

~thread_pool();

trivial_executor get_trivial_executor() noexcept;

event_executor get_event_executor() noexcept;

void stop();

void join();

namespace std {
namespace experimental {
inline namespace concurrency_v2 {

  class thread_pool::trivial_executor
  {
  public:
    // construct / copy / destroy:

    trivial_executor(const trivial_executor& other) noexcept;
    trivial_executor(trivial_executor&& other) noexcept;

    trivial_executor& operator=(const trivial_executor& other) noexcept;
    trivial_executor& operator=(trivial_executor&& other) noexcept;

    // executor operations:

    thread_pool& context() noexcept;
    template<class Func> void execute(Func&& f);
  };

  bool operator==(const thread_pool::trivial_executor& a,
                  const thread_pool::trivial_executor& b) noexcept;
  bool operator!=(const thread_pool::trivial_executor& a,
                  const thread_pool::trivial_executor& b) noexcept;

} // inline namespace concurrency_v2
} // namespace experimental
} // namespace std

thread_pool::trivial_executor is a type satisfying TrivialExecutor requirements. Objects of type thread_pool::trivial_executor are associated with a thread_pool, and function objects submitted using the dispatch, post, or defer member functions will be executed by the thread_pool.]

trivial_executor(const trivial_executor& other) noexcept;

trivial_executor(trivial_executor&& other) noexcept;

trivial_executor& operator=(const trivial_executor& other) noexcept;

trivial_executor& operator=(trivial_executor&& other) noexcept;

thread_pool& context() noexcept;

template<class Func> void execute(Func&& f);

bool operator==(const thread_pool::trivial_executor& a,
                const thread_pool::trivial_executor& b) noexcept;

bool operator!=(const thread_pool::trivial_executor& a,
                const thread_pool::trivial_executor& b) noexcept;

namespace std {
namespace experimental {
inline namespace concurrency_v2 {

  class thread_pool::event_executor
  {
  public:
    // construct / copy / destroy:

    event_executor(const event_executor& other) noexcept;
    event_executor(event_executor&& other) noexcept;

    event_executor& operator=(const event_executor& other) noexcept;
    event_executor& operator=(event_executor&& other) noexcept;

    // executor operations:

    bool running_in_this_thread() const noexcept;

    thread_pool& context() noexcept;

    void on_work_started() noexcept;
    void on_work_finished() noexcept;

    template<class Func, class ProtoAllocator>
      void dispatch(Func&& f, const ProtoAllocator& a);
    template<class Func, class ProtoAllocator>
      void post(Func&& f, const ProtoAllocator& a);
    template<class Func, class ProtoAllocator>
      void defer(Func&& f, const ProtoAllocator& a);
  };

  bool operator==(const thread_pool::event_executor& a,
                  const thread_pool::event_executor& b) noexcept;
  bool operator!=(const thread_pool::event_executor& a,
                  const thread_pool::event_executor& b) noexcept;

} // inline namespace concurrency_v2
} // namespace experimental
} // namespace std

thread_pool::event_executor is a type satisfying EventExecutor requirements. Objects of type thread_pool::event_executor are associated with a thread_pool, and function objects submitted using the dispatch, post, or defer member functions will be executed by the thread_pool.]

event_executor(const event_executor& other) noexcept;

event_executor(event_executor&& other) noexcept;

event_executor& operator=(const event_executor& other) noexcept;

event_executor& operator=(event_executor&& other) noexcept;

bool running_in_this_thread() const noexcept;

thread_pool& context() noexcept;

void on_work_started() noexcept;

void on_work_finished() noexcept;

template<class Func, class ProtoAllocator>
  void dispatch(Func&& f, const ProtoAllocator& a);

template<class Func, class ProtoAllocator>
  void post(Func&& f, const ProtoAllocator& a);

template<class Func, class ProtoAllocator>
  void defer(Func&& f, const ProtoAllocator& a);

bool operator==(const thread_pool::event_executor& a,
                const thread_pool::event_executor& b) noexcept;

bool operator!=(const thread_pool::event_executor& a,
                const thread_pool::event_executor& b) noexcept;