P2300R9
std::execution

1. Introduction

This paper proposes a self-contained design for a Standard C++ framework for managing asynchronous execution on generic execution resources. It is based on the ideas in A Unified Executors Proposal for C++ and its companion papers.

1.1. Motivation

Today, C++ software is increasingly asynchronous and parallel, a trend that is likely to only continue going forward. Asynchrony and parallelism appears everywhere, from processor hardware interfaces, to networking, to file I/O, to GUIs, to accelerators. Every C++ domain and every platform needs to deal with asynchrony and parallelism, from scientific computing to video games to financial services, from the smallest mobile devices to your laptop to GPUs in the world’s fastest supercomputer.

While the C++ Standard Library has a rich set of concurrency primitives (std::atomic, std::mutex, std::counting_semaphore, etc) and lower level building blocks (std::thread, etc), we lack a Standard vocabulary and framework for asynchrony and parallelism that C++ programmers desperately need. std::async/std::future/std::promise, C++11’s intended exposure for asynchrony, is inefficient, hard to use correctly, and severely lacking in genericity, making it unusable in many contexts. We introduced parallel algorithms to the C++ Standard Library in C++17, and while they are an excellent start, they are all inherently synchronous and not composable.

This paper proposes a Standard C++ model for asynchrony based around three key abstractions: schedulers, senders, and receivers, and a set of customizable asynchronous algorithms.

1.2. Priorities

• Be composable and generic, allowing users to write code that can be used with many different types of execution resources.

• Encapsulate common asynchronous patterns in customizable and reusable algorithms, so users don’t have to invent things themselves.

• Make it easy to be correct by construction.

• Support the diversity of execution resources and execution agents, because not all execution agents are created equal; some are less capable than others, but not less important.

• Allow everything to be customized by an execution resource, including transfer to other execution resources, but don’t require that execution resources customize everything.

• Care about all reasonable use cases, domains and platforms.

• Errors must be propagated, but error handling must not present a burden.

• Support cancellation, which is not an error.

• Have clear and concise answers for where things execute.

• Be able to manage and terminate the lifetimes of objects asynchronously.

1.3. Examples: End User

In this section we demonstrate the end-user experience of asynchronous programming directly with the sender algorithms presented in this paper. See § 4.19 User-facing sender factories, § 4.20 User-facing sender adaptors, and § 4.21 User-facing sender consumers for short explanations of the algorithms used in these code examples.

1.3.1. Hello world

using namespace std::execution;

scheduler auto sch = thread_pool.scheduler();                                 // 1

sender auto begin = schedule(sch);                                            // 2
sender auto hi = then(begin, []{                                              // 3
    std::cout << "Hello world! Have an int.";                                 // 3
    return 13;                                                                // 3
});                                                                           // 3
sender auto add_42 = then(hi, [](int arg) { return arg + 42; });              // 4

auto [i] = this_thread::sync_wait(add_42).value();                            // 5

This example demonstrates the basics of schedulers, senders, and receivers:

1. First we need to get a scheduler from somewhere, such as a thread pool. A scheduler is a lightweight handle to an execution resource.

2. To start a chain of work on a scheduler, we call § 4.19.1 execution::schedule, which returns a sender that completes on the scheduler. A sender describes asynchronous work and sends a signal (value, error, or stopped) to some recipient(s) when that work completes.

3. We use sender algorithms to produce senders and compose asynchronous work. § 4.20.2 execution::then is a sender adaptor that takes an input sender and a std::invocable, and calls the std::invocable on the signal sent by the input sender. The sender returned by then sends the result of that invocation. In this case, the input sender came from schedule, so its void, meaning it won’t send us a value, so our std::invocable takes no parameters. But we return an int, which will be sent to the next recipient.

4. Now, we add another operation to the chain, again using § 4.20.2 execution::then. This time, we get sent a value - the int from the previous step. We add 42 to it, and then return the result.

5. Finally, we’re ready to submit the entire asynchronous pipeline and wait for its completion. Everything up until this point has been completely asynchronous; the work may not have even started yet. To ensure the work has started and then block pending its completion, we use § 4.21.2 this_thread::sync_wait, which will either return a std::optional<std::tuple<...>> with the value sent by the last sender, or an empty std::optional if the last sender sent a stopped signal, or it throws an exception if the last sender sent an error.

1.3.2. Asynchronous inclusive scan

using namespace std::execution;

sender auto async_inclusive_scan(scheduler auto sch,                          // 2
                                 std::span<const double> input,               // 1
                                 std::span<double> output,                    // 1
                                 double init,                                 // 1
                                 std::size_t tile_count)                      // 3
{
  std::size_t const tile_size = (input.size() + tile_count - 1) / tile_count;

  std::vector<double> partials(tile_count + 1);                               // 4
  partials[0] = init;                                                         // 4

  return just(std::move(partials))                                            // 5
       | transfer(sch)
       | bulk(tile_count,                                                     // 6
           [ = ](std::size_t i, std::vector<double>& partials) {              // 7
             auto start = i * tile_size;                                      // 8
             auto end   = std::min(input.size(), (i + 1) * tile_size);        // 8
             partials[i + 1] = *--std::inclusive_scan(begin(input) + start,   // 9
                                                      begin(input) + end,     // 9
                                                      begin(output) + start); // 9
           })                                                                 // 10
       | then(                                                                // 11
           [](std::vector<double>&& partials) {
             std::inclusive_scan(begin(partials), end(partials),              // 12
                                 begin(partials));                            // 12
             return std::move(partials);                                      // 13
           })
       | bulk(tile_count,                                                     // 14
           [ = ](std::size_t i, std::vector<double>& partials) {              // 14
             auto start = i * tile_size;                                      // 14
             auto end   = std::min(input.size(), (i + 1) * tile_size);        // 14
             std::for_each(begin(output) + start, begin(output) + end,        // 14
               [&] (double& e) { e = partials[i] + e; }                       // 14
             );
           })
       | then(                                                                // 15
           [ = ](std::vector<double>&& partials) {                            // 15
             return output;                                                   // 15
           });                                                                // 15
}

This example builds an asynchronous computation of an inclusive scan:

1. It scans a sequence of doubles (represented as the std::span<const double> input) and stores the result in another sequence of doubles (represented as std::span<double> output).

2. It takes a scheduler, which specifies what execution resource the scan should be launched on.

3. It also takes a tile_count parameter that controls the number of execution agents that will be spawned.

4. First we need to allocate temporary storage needed for the algorithm, which we’ll do with a std::vector, partials. We need one double of temporary storage for each execution agent we create.

5. Next we’ll create our initial sender with § 4.19.2 execution::just and § 4.20.1 execution::transfer. These senders will send the temporary storage, which we’ve moved into the sender. The sender has a completion scheduler of sch, which means the next item in the chain will use sch.

6. Senders and sender adaptors support composition via operator|, similar to C++ ranges. We’ll use operator| to attach the next piece of work, which will spawn tile_count execution agents using § 4.20.9 execution::bulk (see § 4.12 Most sender adaptors are pipeable for details).

7. Each agent will call a std::invocable, passing it two arguments. The first is the agent’s index (i) in the § 4.20.9 execution::bulk operation, in this case a unique integer in [0, tile_count). The second argument is what the input sender sent - the temporary storage.

8. We start by computing the start and end of the range of input and output elements that this agent is responsible for, based on our agent index.

9. Then we do a sequential std::inclusive_scan over our elements. We store the scan result for our last element, which is the sum of all of our elements, in our temporary storage partials.

10. After all computation in that initial § 4.20.9 execution::bulk pass has completed, every one of the spawned execution agents will have written the sum of its elements into its slot in partials.

11. Now we need to scan all of the values in partials. We’ll do that with a single execution agent which will execute after the § 4.20.9 execution::bulk completes. We create that execution agent with § 4.20.2 execution::then.

12. § 4.20.2 execution::then takes an input sender and an std::invocable and calls the std::invocable with the value sent by the input sender. Inside our std::invocable, we call std::inclusive_scan on partials, which the input senders will send to us.

13. Then we return partials, which the next phase will need.

14. Finally we do another § 4.20.9 execution::bulk of the same shape as before. In this § 4.20.9 execution::bulk, we will use the scanned values in partials to integrate the sums from other tiles into our elements, completing the inclusive scan.

15. async_inclusive_scan returns a sender that sends the output std::span<double>. A consumer of the algorithm can chain additional work that uses the scan result. At the point at which async_inclusive_scan returns, the computation may not have completed. In fact, it may not have even started.

1.3.3. Asynchronous dynamically-sized read

using namespace std::execution;

sender_of<std::size_t> auto async_read(                                       // 1
    sender_of<std::span<std::byte>> auto buffer,                              // 1
    auto handle);                                                             // 1

struct dynamic_buffer {                                                       // 3
  std::unique_ptr<std::byte[]> data;                                          // 3
  std::size_t size;                                                           // 3
};                                                                            // 3

sender_of<dynamic_buffer> auto async_read_array(auto handle) {                // 2
  return just(dynamic_buffer{})                                               // 4
       | let_value([handle] (dynamic_buffer& buf) {                           // 5
           return just(std::as_writeable_bytes(std::span(&buf.size, 1))       // 6
                | async_read(handle)                                          // 7
                | then(                                                       // 8
                    [&buf] (std::size_t bytes_read) {                         // 9
                      assert(bytes_read == sizeof(buf.size));                 // 10
                      buf.data = std::make_unique<std::byte[]>(buf.size);     // 11
                      return std::span(buf.data.get(), buf.size);             // 12
                    })
                | async_read(handle)                                          // 13
                | then(
                    [&buf] (std::size_t bytes_read) {
                      assert(bytes_read == buf.size);                         // 14
                      return std::move(buf);                                  // 15
                    });
       });
}

This example demonstrates a common asynchronous I/O pattern - reading a payload of a dynamic size by first reading the size, then reading the number of bytes specified by the size:

1. async_read is a pipeable sender adaptor. It’s a customization point object, but this is what it’s call signature looks like. It takes a sender parameter which must send an input buffer in the form of a std::span<std::byte>, and a handle to an I/O context. It will asynchronously read into the input buffer, up to the size of the std::span. It returns a sender which will send the number of bytes read once the read completes.

2. async_read_array takes an I/O handle and reads a size from it, and then a buffer of that many bytes. It returns a sender that sends a dynamic_buffer object that owns the data that was sent.

3. dynamic_buffer is an aggregate struct that contains a std::unique_ptr<std::byte[]> and a size.

4. The first thing we do inside of async_read_array is create a sender that will send a new, empty dynamic_array object using § 4.19.2 execution::just. We can attach more work to the pipeline using operator| composition (see § 4.12 Most sender adaptors are pipeable for details).

5. We need the lifetime of this dynamic_array object to last for the entire pipeline. So, we use let_value, which takes an input sender and a std::invocable that must return a sender itself (see § 4.20.4 execution::let_* for details). let_value sends the value from the input sender to the std::invocable. Critically, the lifetime of the sent object will last until the sender returned by the std::invocable completes.

6. Inside of the let_value std::invocable, we have the rest of our logic. First, we want to initiate an async_read of the buffer size. To do that, we need to send a std::span pointing to buf.size. We can do that with § 4.19.2 execution::just.

7. We chain the async_read onto the § 4.19.2 execution::just sender with operator|.

8. Next, we pipe a std::invocable that will be invoked after the async_read completes using § 4.20.2 execution::then.

9. That std::invocable gets sent the number of bytes read.

10. We need to check that the number of bytes read is what we expected.

11. Now that we have read the size of the data, we can allocate storage for it.

12. We return a std::span<std::byte> to the storage for the data from the std::invocable. This will be sent to the next recipient in the pipeline.

13. And that recipient will be another async_read, which will read the data.

14. Once the data has been read, in another § 4.20.2 execution::then, we confirm that we read the right number of bytes.

15. Finally, we move out of and return our dynamic_buffer object. It will get sent by the sender returned by async_read_array. We can attach more things to that sender to use the data in the buffer.

1.4. Asynchronous Windows socket recv

To get a better feel for how this interface might be used by low-level operations see this example implementation of a cancellable async_recv() operation for a Windows Socket.

struct operation_base : WSAOVERALAPPED {
    using completion_fn = void(operation_base* op, DWORD bytesTransferred, int errorCode) noexcept;

    // Assume IOCP event loop will call this when this OVERLAPPED structure is dequeued.
    completion_fn* completed;
};

template<class Receiver>
struct recv_op : operation_base {
    using operation_state_concept = std::execution::operation_state_t;

    recv_op(SOCKET s, void* data, size_t len, Receiver r)
    : receiver(std::move(r))
    , sock(s) {
        this->Internal = 0;
        this->InternalHigh = 0;
        this->Offset = 0;
        this->OffsetHigh = 0;
        this->hEvent = NULL;
        this->completed = &recv_op::on_complete;
        buffer.len = len;
        buffer.buf = static_cast<CHAR*>(data);
    }

    void start() & noexcept {
        // Avoid even calling WSARecv() if operation already cancelled
        auto st = std::execution::get_stop_token(
          std::execution::get_env(receiver));
        if (st.stop_requested()) {
            std::execution::set_stopped(std::move(receiver));
            return;
        }

        // Store and cache result here in case it changes during execution
        const bool stopPossible = st.stop_possible();
        if (!stopPossible) {
            ready.store(true, std::memory_order_relaxed);
        }

        // Launch the operation
        DWORD bytesTransferred = 0;
        DWORD flags = 0;
        int result = WSARecv(sock, &buffer, 1, &bytesTransferred, &flags,
                             static_cast<WSAOVERLAPPED*>(this), NULL);
        if (result == SOCKET_ERROR) {
            int errorCode = WSAGetLastError();
            if (errorCode != WSA_IO_PENDING) {
                if (errorCode == WSA_OPERATION_ABORTED) {
                    std::execution::set_stopped(std::move(receiver));
                } else {
                    std::execution::set_error(std::move(receiver),
                                              std::error_code(errorCode, std::system_category()));
                }
                return;
            }
        } else {
            // Completed synchronously (assuming FILE_SKIP_COMPLETION_PORT_ON_SUCCESS has been set)
            execution::set_value(std::move(receiver), bytesTransferred);
            return;
        }

        // If we get here then operation has launched successfully and will complete asynchronously.
        // May be completing concurrently on another thread already.
        if (stopPossible) {
            // Register the stop callback
            stopCallback.emplace(std::move(st), cancel_cb{*this});

            // Mark as 'completed'
            if (ready.load(std::memory_order_acquire) ||
                ready.exchange(true, std::memory_order_acq_rel)) {
                // Already completed on another thread
                stopCallback.reset();

                BOOL ok = WSAGetOverlappedResult(sock, (WSAOVERLAPPED*)this, &bytesTransferred, FALSE, &flags);
                if (ok) {
                    std::execution::set_value(std::move(receiver), bytesTransferred);
                } else {
                    int errorCode = WSAGetLastError();
                    std::execution::set_error(std::move(receiver),
                                              std::error_code(errorCode, std::system_category()));
                }
            }
        }
    }

    struct cancel_cb {
        recv_op& op;

        void operator()() noexcept {
            CancelIoEx((HANDLE)op.sock, (OVERLAPPED*)(WSAOVERLAPPED*)&op);
        }
    };

    static void on_complete(operation_base* op, DWORD bytesTransferred, int errorCode) noexcept {
        recv_op& self = *static_cast<recv_op*>(op);

        if (self.ready.load(std::memory_order_acquire) ||
            self.ready.exchange(true, std::memory_order_acq_rel)) {
            // Unsubscribe any stop-callback so we know that CancelIoEx() is not accessing 'op'
            // any more
            self.stopCallback.reset();

            if (errorCode == 0) {
                std::execution::set_value(std::move(self.receiver), bytesTransferred);
            } else {
                std::execution::set_error(std::move(self.receiver),
                                          std::error_code(errorCode, std::system_category()));
            }
        }
    }

    using stop_callback_t = stop_callback_of_t<stop_token_of_t<env_of_t<Receiver>>, cancel_cb>;

    Receiver receiver;
    SOCKET sock;
    WSABUF buffer;
    std::optional<stop_callback_t> stopCallback;
    std::atomic<bool> ready{false};
};

struct recv_sender {
    using sender_concept = std::execution::sender_t;
    SOCKET sock;
    void* data;
    size_t len;

    template<class Receiver>
    recv_op<Receiver> connect(Receiver r) const {
        return recv_op<Receiver>{sock, data, len, std::move(r)};
    }
};

recv_sender async_recv(SOCKET s, void* data, size_t len) {
    return recv_sender{s, data, len};
}

1.4.1. More end-user examples

1.4.1.1. Sudoku solver

This example comes from Kirk Shoop, who ported an example from TBB’s documentation to sender/receiver in his fork of the libunifex repo. It is a Sudoku solver that uses a configurable number of threads to explore the search space for solutions.

The sender/receiver-based Sudoku solver can be found here. Some things that are worth noting about Kirk’s solution:

1. Although it schedules asychronous work onto a thread pool, and each unit of work will schedule more work, its use of structured concurrency patterns make reference counting unnecessary. The solution does not make use of shared_ptr.

2. In addition to eliminating the need for reference counting, the use of structured concurrency makes it easy to ensure that resources are cleaned up on all code paths. In contrast, the TBB example that inspired this one leaks memory.

For comparison, the TBB-based Sudoku solver can be found here.

1.4.1.2. File copy

This example also comes from Kirk Shoop which uses sender/receiver to recursively copy the files a directory tree. It demonstrates how sender/receiver can be used to do IO, using a scheduler that schedules work on Linux’s io_uring.

As with the Sudoku example, this example obviates the need for reference counting by employing structured concurrency. It uses iteration with an upper limit to avoid having too many open file handles.

You can find the example here.

1.4.1.3. Echo server

Dietmar Kuehl has proposed networking APIs that use the sender/receiver abstraction (see P2762). He has implemented an echo server as a demo. His echo server code can be found here.

Below, I show the part of the echo server code. This code is executed for each client that connects to the echo server. In a loop, it reads input from a socket and echos the input back to the same socket. All of this, including the loop, is implemented with generic async algorithms.

outstanding.start(
    EX::repeat_effect_until(
          EX::let_value(
              NN::async_read_some(ptr->d_socket,
                                  context.scheduler(),
                                  NN::buffer(ptr->d_buffer))
        | EX::then([ptr](::std::size_t n){
            ::std::cout << "read='" << ::std::string_view(ptr->d_buffer, n) << "'\n";
            ptr->d_done = n == 0;
            return n;
        }),
          [&context, ptr](::std::size_t n){
            return NN::async_write_some(ptr->d_socket,
                                        context.scheduler(),
                                        NN::buffer(ptr->d_buffer, n));
          })
        | EX::then([](auto&&...){})
        , [owner = ::std::move(owner)]{ return owner->d_done; }
    )
);

In this code, NN::async_read_some and NN::async_write_some are asynchronous socket-based networking APIs that return senders. EX::repeat_effect_until, EX::let_value, and EX::then are fully generic sender adaptor algorithms that accept and return senders.

This is a good example of seamless composition of async IO functions with non-IO operations. And by composing the senders in this structured way, all the state for the composite operation -- the repeat_effect_until expression and all its child operations -- is stored altogether in a single object.

1.5. Examples: Algorithms

In this section we show a few simple sender/receiver-based algorithm implementations.

1.5.1. then

namespace stdexec = std::execution;

template <class R, class F>
class _then_receiver : public R {
  F f_;

 public:
  _then_receiver(R r, F f) : R(std::move(r)), f_(std::move(f)) {}

  // Customize set_value by invoking the callable and passing the result to
  // the inner receiver
  template <class... As>
    requires std::invocable<F, As...>
  void set_value(As&&... as) && noexcept {
    try {
      stdexec::set_value(std::move(*this).base(), std::invoke((F&&) f_, (As&&) as...));
    } catch(...) {
      stdexec::set_error(std::move(*this).base(), std::current_exception());
    }
  }
};

template <stdexec::sender S, class F>
struct _then_sender {
  using sender_concept = stdexec::sender_t;
  S s_;
  F f_;

  template <class... Args>
    using _set_value_t = stdexec::completion_signatures<
      stdexec::set_value_t(std::invoke_result_t<F, Args...>)>;

  using _except_ptr_sig =
    stdexec::completion_signatures<stdexec::set_error_t(std::exception_ptr)>;

  // Compute the completion signatures
  template <class Env>
  auto get_completion_signatures(Env&& env) && noexcept
    -> stdexec::transform_completion_signatures_of<
        S, Env, _except_ptr_sig, _set_value_t> {
    return {};
  }

  // Connect:
  template <stdexec::receiver R>
  auto connect(R r) && -> stdexec::connect_result_t<S, _then_receiver<R, F>> {
    return stdexec::connect(
      (S&&) s_, _then_receiver{(R&&) r, (F&&) f_});
  }

  decltype(auto) get_env() const noexcept {
    return get_env(s_);
  }
};

template <stdexec::sender S, class F>
stdexec::sender auto then(S s, F f) {
  return _then_sender<S, F>{(S&&) s, (F&&) f};
}

This code builds a then algorithm that transforms the value(s) from the input sender with a transformation function. The result of the transformation becomes the new value. The other receiver functions (set_error and set_stopped), as well as all receiver queries, are passed through unchanged.

In detail, it does the following:

1. Defines a receiver in terms of receiver and an invocable that:

   • Defines a constrained set_value member function for transforming the value channel.

   • Delegates set_error and set_stopped to the inner receiver.

2. Defines a sender that aggregates another sender and the invocable, which defines a connect member function that wraps the incoming receiver in the receiver from (1) and passes it and the incoming sender to std::execution::connect, returning the result. It also defines a get_completion_signatures member function that declares the sender’s completion signatures when executed within a particular environment.

1.5.2. retry

using namespace std;
namespace stdexec = execution;

template<class From, class To>
concept _decays_to = same_as<decay_t<From>, To>;

// _conv needed so we can emplace construct non-movable types into
// a std::optional.
template<invocable F>
struct _conv {
  F f_;

  static_assert(is_nothrow_move_constructible_v<F>);
  explicit _conv(F f) noexcept : f_((F&&) f) {}

  operator invoke_result_t<F>() && {
    return ((F&&) f_)();
  }
};

template<class S, class R>
struct _retry_op;

// pass through all customizations except set_error, which retries
// the operation.
template<class S, class R>
struct _retry_receiver {
  _retry_op<S, R>* o_;

  void set_value(auto&&... as) && noexcept {
    stdexec::set_value(std::move(o_->r_), (decltype(as)&&) as...);
  }

  void set_error(auto&&) && noexcept {
    o_->_retry(); // This causes the op to be retried
  }

  void set_stopped() && noexcept {
    stdexec::set_stopped(std::move(o_->r_));
  }

  decltype(auto) get_env() const noexcept {
    return get_env(o_->r_);
  }
};

// Hold the nested operation state in an optional so we can
// re-construct and re-start it if the operation fails.
template<class S, class R>
struct _retry_op {
  using operation_state_concept = stdexec::operation_state_t;
  using _child_op_t =
    stdexec::connect_result_t<S&, _retry_receiver<S, R>>;

  S s_;
  R r_;
  optional<_child_op_t> o_;

  _op(_op&&) = delete;
  _op(S s, R r)
    : s_(std::move(s)), r_(std::move(r)), o_{_connect()} {}

  auto _connect() noexcept {
    return _conv{[this] {
      return stdexec::connect(s_, _retry_receiver<S, R>{this});
    }};
  }

  void _retry() noexcept {
    try {
      o_.emplace(_connect()); // potentially-throwing
      stdexec::start(*o_);
    } catch(...) {
      stdexec::set_error(std::move(r_), std::current_exception());
    }
  }

  void start() & noexcept {
    stdexec::start(*o_);
  }
};

// Helpers for computing the <code data-opaque bs-autolink-syntax='`then`'>then</code> sender’s completion signatures: 
template <class... Ts>
  using _value_t =
    stdexec::completion_signatures<stdexec::set_value_t(Ts...)>;

template <class>
  using _error_t = stdexec::completion_signatures<>;

using _except_sig =
  stdexec::completion_signatures<stdexec::set_error_t(std::exception_ptr)>;

template<class S>
struct _retry_sender {
  using sender_concept = stdexec::sender_t;
  S s_;
  explicit _retry_sender(S s) : s_(std::move(s)) {}

  // Declare the signatures with which this sender can complete
  template <class Env>
    using _compl_sigs =
      stdexec::transform_completion_signatures_of<
        S&, Env, _except_sig, _value_t, _error_t>;

  template <class Env>
  auto get_completion_signatures(Env&&) const noexcept -> _compl_sigs<Env> {
    return {};
  }

  template <stdexec::receiver R>
    requires stdexec::sender_to<S&, _retry_receiver<S, R>>
  _retry_op<S, R> connect(R r) && {
    return {std::move(s_), std::move(r)};
  }

  decltype(auto) get_env() const noexcept {
    return get_env(s_);
  }
};

template <stdexec::sender S>
stdexec::sender auto retry(S s) {
  return _retry_sender{std::move(s)};
}

The retry algorithm takes a multi-shot sender and causes it to repeat on error, passing through values and stopped signals. Each time the input sender is restarted, a new receiver is connected and the resulting operation state is stored in an optional, which allows us to reinitialize it multiple times.

This example does the following:

1. Defines a _conv utility that takes advantage of C++17’s guaranteed copy elision to emplace a non-movable type in a std::optional.

2. Defines a _retry_receiver that holds a pointer back to the operation state. It passes all customizations through unmodified to the inner receiver owned by the operation state except for set_error, which causes a _retry() function to be called instead.

3. Defines an operation state that aggregates the input sender and receiver, and declares storage for the nested operation state in an optional. Constructing the operation state constructs a _retry_receiver with a pointer to the (under construction) operation state and uses it to connect to the input sender.

4. Starting the operation state dispatches to start on the inner operation state.

5. The _retry() function reinitializes the inner operation state by connecting the sender to a new receiver, holding a pointer back to the outer operation state as before.

6. After reinitializing the inner operation state, _retry() calls start on it, causing the failed operation to be rescheduled.

7. Defines a _retry_sender that implements a connect member function to return an operation state constructed from the passed-in sender and receiver.

8. _retry_sender also implements a get_completion_signatures member function to describe the ways this sender may complete when executed in a particular execution resource.

1.6. Examples: Schedulers

In this section we look at some schedulers of varying complexity.

1.6.1. Inline scheduler

namespace stdexec = std::execution;

class inline_scheduler {
  template <class R>
  struct _op {
    using operation_state_concept = operation_state_t;
    R rec_;

    void start() & noexcept {
      stdexec::set_value(std::move(rec_));
    }
  };

  struct _env {
    template <class Tag>
    inline_scheduler query(stdexec::get_completion_scheduler_t<Tag>) const noexcept {
      return {};
    }
  };

  struct _sender {
    using sender_concept = stdexec::sender_t;
    using _compl_sigs = stdexec::completion_signatures<stdexec::set_value_t()>;
    using completion_signatures = _compl_sigs;

    template <stdexec::receiver_of<_compl_sigs> R>
    _op<R> connect(R rec) noexcept(std::is_nothrow_move_constructible_v<R>) {
      return {std::move(rec)};
    }

    _env get_env() const noexcept {
      return {};
    }
  };

 public:
  inline_scheduler() = default;

  _sender schedule() const noexcept {
    return {};
  }

  bool operator==(const inline_scheduler&) const noexcept = default;
};

The inline scheduler is a trivial scheduler that completes immediately and synchronously on the thread that calls std::execution::start on the operation state produced by its sender. In other words, start(connect(schedule(inline_scheduler()), receiver)) is just a fancy way of saying set_value(receiver), with the exception of the fact that start wants to be passed an lvalue.

Although not a particularly useful scheduler, it serves to illustrate the basics of implementing one. The inline_scheduler:

1. Customizes execution::schedule to return an instance of the sender type _sender.

2. The _sender type models the sender concept and provides the metadata needed to describe it as a sender of no values and that never calls set_error or set_stopped. This metadata is provided with the help of the execution::completion_signatures utility.

3. The _sender type customizes execution::connect to accept a receiver of no values. It returns an instance of type _op that holds the receiver by value.

4. The operation state customizes std::execution::start to call std::execution::set_value on the receiver.

1.6.2. Single thread scheduler

This example shows how to create a scheduler for an execution resource that consists of a single thread. It is implemented in terms of a lower-level execution resource called std::execution::run_loop.

class single_thread_context {
  std::execution::run_loop loop_;
  std::thread thread_;

public:
  single_thread_context()
    : loop_()
    , thread_([this] { loop_.run(); })
  {}
  single_thread_context(single_thread_context&&) = delete;

  ~single_thread_context() {
    loop_.finish();
    thread_.join();
  }

  auto get_scheduler() noexcept {
    return loop_.get_scheduler();
  }

  std::thread::id get_thread_id() const noexcept {
    return thread_.get_id();
  }
};

The single_thread_context owns an event loop and a thread to drive it. In the destructor, it tells the event loop to finish up what it’s doing and then joins the thread, blocking for the event loop to drain.

The interesting bits are in the execution::run_loop context implementation. It is slightly too long to include here, so we only provide a reference to it, but there is one noteworthy detail about its implementation: It uses space in its operation states to build an intrusive linked list of work items. In structured concurrency patterns, the operation states of nested operations compose statically, and in an algorithm like this_thread::sync_wait, the composite operation state lives on the stack for the duration of the operation. The end result is that work can be scheduled onto this thread with zero allocations.

1.7. Examples: Server theme

In this section we look at some examples of how one would use senders to implement an HTTP server. The examples ignore the low-level details of the HTTP server and looks at how senders can be combined to achieve the goals of the project.

General application context:

• server application that processes images

• execution resources:

  • 1 dedicated thread for network I/O

  • N worker threads used for CPU-intensive work

  • M threads for auxiliary I/O

  • optional GPU context that may be used on some types of servers

• all parts of the applications can be asynchronous

• no locks shall be used in user code

1.7.1. Composability with execution::let_*

Example context:

• we are looking at the flow of processing an HTTP request and sending back the response.

• show how one can break the (slightly complex) flow into steps with execution::let_* functions.

• different phases of processing HTTP requests are broken down into separate concerns.

• each part of the processing might use different execution resources (details not shown in this example).

• error handling is generic, regardless which component fails; we always send the right response to the clients.

Goals:

• show how one can break more complex flows into steps with let_* functions.

• exemplify the use of let_value, let_error, let_stopped, and just algorithms.

namespace stdexec = std::execution;

// Returns a sender that yields an http_request object for an incoming request
stdexec::sender auto schedule_request_start(read_requests_ctx ctx) {...}

// Sends a response back to the client; yields a void signal on success
stdexec::sender auto send_response(const http_response& resp) {...}

// Validate that the HTTP request is well-formed; forwards the request on success
stdexec::sender auto validate_request(const http_request& req) {...}

// Handle the request; main application logic
stdexec::sender auto handle_request(const http_request& req) {
  //...
  return stdexec::just(http_response{200, result_body});
}

// Transforms server errors into responses to be sent to the client
stdexec::sender auto error_to_response(std::exception_ptr err) {
  try {
    std::rethrow_exception(err);
  } catch (const std::invalid_argument& e) {
    return stdexec::just(http_response{404, e.what()});
  } catch (const std::exception& e) {
    return stdexec::just(http_response{500, e.what()});
  } catch (...) {
    return stdexec::just(http_response{500, "Unknown server error"});
  }
}

// Transforms cancellation of the server into responses to be sent to the client
stdexec::sender auto stopped_to_response() {
  return stdexec::just(http_response{503, "Service temporarily unavailable"});
}

//...

// The whole flow for transforming incoming requests into responses
stdexec::sender auto snd =
    // get a sender when a new request comes
    schedule_request_start(the_read_requests_ctx)
    // make sure the request is valid; throw if not
    | stdexec::let_value(validate_request)
    // process the request in a function that may be using a different execution resource
    | stdexec::let_value(handle_request)
    // If there are errors transform them into proper responses
    | stdexec::let_error(error_to_response)
    // If the flow is cancelled, send back a proper response
    | stdexec::let_stopped(stopped_to_response)
    // write the result back to the client
    | stdexec::let_value(send_response)
    // done
    ;

// execute the whole flow asynchronously
stdexec::start_detached(std::move(snd));

The example shows how one can separate out the concerns for interpreting requests, validating requests, running the main logic for handling the request, generating error responses, handling cancellation and sending the response back to the client. They are all different phases in the application, and can be joined together with the let_* functions.

All our functions return execution::sender objects, so that they can all generate success, failure and cancellation paths. For example, regardless where an error is generated (reading request, validating request or handling the response), we would have one common block to handle the error, and following error flows is easy.

Also, because of using execution::sender objects at any step, we might expect any of these steps to be completely asynchronous; the overall flow doesn’t care. Regardless of the execution resource in which the steps, or part of the steps are executed in, the flow is still the same.

1.7.2. Moving between execution resources with execution::on and execution::transfer

Example context:

• reading data from the socket before processing the request

• reading of the data is done on the I/O context

• no processing of the data needs to be done on the I/O context

Goals:

• show how one can change the execution resource

• exemplify the use of on and transfer algorithms

namespace stdexec = std::execution;

size_t legacy_read_from_socket(int sock, char* buffer, size_t buffer_len);
void process_read_data(const char* read_data, size_t read_len);
//...

// A sender that just calls the legacy read function
auto snd_read = stdexec::just(sock, buf, buf_len)
              | stdexec::then(legacy_read_from_socket);

// The entire flow
auto snd =
    // start by reading data on the I/O thread
    stdexec::on(io_sched, std::move(snd_read))
    // do the processing on the worker threads pool
    | stdexec::transfer(work_sched)
    // process the incoming data (on worker threads)
    | stdexec::then([buf](int read_len) { process_read_data(buf, read_len); })
    // done
    ;

// execute the whole flow asynchronously
stdexec::start_detached(std::move(snd));

The example assume that we need to wrap some legacy code of reading sockets, and handle execution resource switching. (This style of reading from socket may not be the most efficient one, but it’s working for our purposes.) For performance reasons, the reading from the socket needs to be done on the I/O thread, and all the processing needs to happen on a work-specific execution resource (i.e., thread pool).

Calling execution::on will ensure that the given sender will be started on the given scheduler. In our example, snd_read is going to be started on the I/O scheduler. This sender will just call the legacy code.

The completion-signal will be issued in the I/O execution resource, so we have to move it to the work thread pool. This is achieved with the help of the execution::transfer algorithm. The rest of the processing (in our case, the last call to then) will happen in the work thread pool.

The reader should notice the difference between execution::on and execution::transfer. The execution::on algorithm will ensure that the given sender will start in the specified context, and doesn’t care where the completion-signal for that sender is sent. The execution::transfer algorithm will not care where the given sender is going to be started, but will ensure that the completion-signal of will be transferred to the given context.

1.8. Design changes from P0443

1. The executor concept has been removed and all of its proposed functionality is now based on schedulers and senders, as per SG1 direction.

2. Properties are not included in this paper. We see them as a possible future extension, if the committee gets more comfortable with them.

3. Senders now advertise what scheduler, if any, their evaluation will complete on.

4. The places of execution of user code in P0443 weren’t precisely defined, whereas they are in this paper. See § 4.5 Senders can propagate completion schedulers.

5. P0443 did not propose a suite of sender algorithms necessary for writing sender code; this paper does. See § 4.19 User-facing sender factories, § 4.20 User-facing sender adaptors, and § 4.21 User-facing sender consumers.

6. P0443 did not specify the semantics of variously qualified connect overloads; this paper does. See § 4.7 Senders can be either multi-shot or single-shot.

7. This paper extends the sender traits/typed sender design to support typed senders whose value/error types depend on type information provided late via the receiver.

8. Support for untyped senders is dropped; the typed_sender concept is renamed sender; sender_traits is replaced with completion_signatures_of_t.

9. Specific type erasure facilities are omitted, as per LEWG direction. Type erasure facilities can be built on top of this proposal, as discussed in § 5.9 Customization points.

10. A specific thread pool implementation is omitted, as per LEWG direction.

11. Some additional utilities are added:

    • run_loop: An execution resource that provides a multi-producer, single-consumer, first-in-first-out work queue.

    • completion_signatures and transform_completion_signatures: Utilities for describing the ways in which a sender can complete in a declarative syntax.

1.9. Prior art

This proposal builds upon and learns from years of prior art with asynchronous and parallel programming frameworks in C++. In this section, we discuss async abstractions that have previously been suggested as a possible basis for asynchronous algorithms and why they fall short.

1.9.1. Futures

A future is a handle to work that has already been scheduled for execution. It is one end of a communication channel; the other end is a promise, used to receive the result from the concurrent operation and to communicate it to the future.

Futures, as traditionally realized, require the dynamic allocation and management of a shared state, synchronization, and typically type-erasure of work and continuation. Many of these costs are inherent in the nature of "future" as a handle to work that is already scheduled for execution. These expenses rule out the future abstraction for many uses and makes it a poor choice for a basis of a generic mechanism.

1.9.2. Coroutines

C++20 coroutines are frequently suggested as a basis for asynchronous algorithms. It’s fair to ask why, if we added coroutines to C++, are we suggesting the addition of a library-based abstraction for asynchrony. Certainly, coroutines come with huge syntactic and semantic advantages over the alternatives.

Although coroutines are lighter weight than futures, coroutines suffer many of the same problems. Since they typically start suspended, they can avoid synchronizing the chaining of dependent work. However in many cases, coroutine frames require an unavoidable dynamic allocation and indirect function calls. This is done to hide the layout of the coroutine frame from the C++ type system, which in turn makes possible the separate compilation of coroutines and certain compiler optimizations, such as optimization of the coroutine frame size.

Those advantages come at a cost, though. Because of the dynamic allocation of coroutine frames, coroutines in embedded or heterogeneous environments, which often lack support for dynamic allocation, require great attention to detail. And the allocations and indirections tend to complicate the job of the inliner, often resulting in sub-optimal codegen.

The coroutine language feature mitigates these shortcomings somewhat with the HALO optimization Halo: coroutine Heap Allocation eLision Optimization: the joint response, which leverages existing compiler optimizations such as allocation elision and devirtualization to inline the coroutine, completely eliminating the runtime overhead. However, HALO requires a sophisiticated compiler, and a fair number of stars need to align for the optimization to kick in. In our experience, more often than not in real-world code today’s compilers are not able to inline the coroutine, resulting in allocations and indirections in the generated code.

In a suite of generic async algorithms that are expected to be callable from hot code paths, the extra allocations and indirections are a deal-breaker. It is for these reasons that we consider coroutines a poor choise for a basis of all standard async.

1.9.3. Callbacks

Callbacks are the oldest, simplest, most powerful, and most efficient mechanism for creating chains of work, but suffer problems of their own. Callbacks must propagate either errors or values. This simple requirement yields many different interface possibilities. The lack of a standard callback shape obstructs generic design.

Additionally, few of these possibilities accommodate cancellation signals when the user requests upstream work to stop and clean up.

1.10. Field experience

1.10.1. libunifex

This proposal draws heavily from our field experience with libunifex. Libunifex implements all of the concepts and customization points defined in this paper (with slight variations -- the design of P2300 has evolved due to LEWG feedback), many of this paper’s algorithms (some under different names), and much more besides.

Libunifex has several concrete schedulers in addition to the run_loop suggested here (where it is called manual_event_loop). It has schedulers that dispatch efficiently to epoll and io_uring on Linux and the Windows Thread Pool on Windows.

In addition to the proposed interfaces and the additional schedulers, it has several important extensions to the facilities described in this paper, which demonstrate directions in which these abstractions may be evolved over time, including:

• Timed schedulers, which permit scheduling work on an execution resource at a particular time or after a particular duration has elapsed. In addition, it provides time-based algorithms.

• File I/O schedulers, which permit filesystem I/O to be scheduled.

• Two complementary abstractions for streams (asynchronous ranges), and a set of stream-based algorithms.

Libunifex has seen heavy production use at Meta. An employee summarizes it as follows:

As of June, 2023, Unifex is still used in production at Meta. It’s used to express the asynchrony in rsys, and is therefore serving video calling to billions of people every month on Meta’s social networking apps on iOS, Android, Windows, and macOS. It’s also serving the Virtual Desktop experience on Oculus Quest devices, and some internal uses that run on Linux.

One team at Meta has migrated from folly::Future to unifex::task and seen significant developer efficiency improvements. Coroutines are easier to understand than chained futures so the team was able to meet requirements for certain constrained environments that would have been too complicated to maintain with futures.

In all the cases mentioned above, developers mix-and-match between the sender algorithms in Unifex and Unifex’s coroutine type, unifex::task. We also rely on unifex::task's scheduler affinity to minimize surprise when programming with coroutines.

1.10.2. stdexec

stdexec is the reference implementation of this proposal. It is a complete implementation, written from the specification in this paper, and is current with \R8.

The original purpose of stdexec was to help find specification bugs and to harden the wording of the proposal, but it has since become one of NVIDIA’s core C++ libraries for high-performance computing. In addition to the facilities proposed in this paper, stdexec has schedulers for CUDA, Intel TBB, and MacOS. Like libunifex, its scope has also expanded to include a streaming abstraction and stream algorithms, and time-based schedulers and algorithms.

The stdexec project has seen lots of community interest and contributions. At the time of writing (March, 2024), the GitHub repository has 1.2k stars, 130 forks, and 50 contributors.

stdexec is fit for broad use and for ultimate contribution to libc++.

1.10.3. Other implementations

The authors are aware of a number of other implementations of sender/receiver from this paper. These are presented here in perceived order of maturity and field experience.

• HPX - The C++ Standard Library for Parallelism and Concurrency

  HPX is a general purpose C++ runtime system for parallel and distributed applications that has been under active development since 2007. HPX exposes a uniform, standards-oriented API, and keeps abreast of the latest standards and proposals. It is used in a wide variety of high-performance applications.

  The sender/receiver implementation in HPX has been under active development since May 2020. It is used to erase the overhead of futures and to make it possible to write efficient generic asynchronous algorithms that are agnostic to their execution resource. In HPX, algorithms can migrate execution between execution resources, even to GPUs and back, using a uniform standard interface with sender/receiver.

  Far and away, the HPX team has the greatest usage experience outside Facebook. Mikael Simberg summarizes the experience as follows:

  Summarizing, for us the major benefits of sender/receiver compared to the old model are:

  1. Proper hooks for transitioning between execution resources.

  2. The adaptors. Things like let_value are really nice additions.

  3. Separation of the error channel from the value channel (also cancellation, but we don’t have much use for it at the moment). Even from a teaching perspective having to explain that the future f2 in the continuation will always be ready here f1.then([](future<T> f2) {...}) is enough of a reason to separate the channels. All the other obvious reasons apply as well of course.

  4. For futures we have a thing called hpx::dataflow which is an optimized version of when_all(...).then(...) which avoids intermediate allocations. With the sender/receiver when_all(...) | then(...) we get that "for free".

• kuhllib by Dietmar Kuehl

  This is a prototype Standard Template Library with an implementation of sender/receiver that has been under development since May, 2021. It is significant mostly for its support for sender/receiver-based networking interfaces.

  Here, Dietmar Kuehl speaks about the perceived complexity of sender/receiver:

  ... and, also similar to STL: as I had tried to do things in that space before I recognize sender/receivers as being maybe complicated in one way but a huge simplification in another one: like with STL I think those who use it will benefit - if not from the algorithm from the clarity of abstraction: the separation of concerns of STL (the algorithm being detached from the details of the sequence representation) is a major leap. Here it is rather similar: the separation of the asynchronous algorithm from the details of execution. Sure, there is some glue to tie things back together but each of them is simpler than the combined result.

  Elsewhere, he said:

  ... to me it feels like sender/receivers are like iterators when STL emerged: they are different from what everybody did in that space. However, everything people are already doing in that space isn’t right.

  Kuehl also has experience teaching sender/receiver at Bloomberg. About that experience he says:

  When I asked [my students] specifically about how complex they consider the sender/receiver stuff the feedback was quite unanimous that the sender/receiver parts aren’t trivial but not what contributes to the complexity.

• C++ Bare Metal Senders and Receivers from Intel

  This is a prototype implementation of sender/receiver by Intel that has been under development since August, 2023. It is significant mostly for its support for bare metal (no operating system) and embedded systems, a domain for which senders are particularly well-suited due to their very low dynamic memory requirements.

1.10.4. Inspirations

This proposal also draws heavily from our experience with Thrust and Agency. It is also inspired by the needs of countless other C++ frameworks for asynchrony, parallelism, and concurrency, including:

• HPX

• Folly

• stlab

2. Revision history

2.1. R9

The changes since R8 are as follows:

Fixes:

• The tag_invoke mechanism has been replaced with member functions for customizations as per P2855.

• Per guidance from LWG and LEWG, receiver_adaptor has been removed.

• The receiver concept is tweaked to require that receiver types are not final. Without receiver_adaptor and tag_invoke, receiver adaptors are easily written using implementation inheritance.

• std::tag_t is made exposition-only.

• The types in_place_stop_token, in_place_stop_source, and in_place_stop_callback are renamed to inplace_stop_token, inplace_stop_source, and inplace_stop_callback, respectively.

Enhancements:

• The specification of the sync_wait algorithm has been updated for clarity.

• The specification of all the stop token, source, and callback types have been re-expressed in terms of shared concepts.

• Declarations are shown in their proper namespaces.

• Editorial changes have been made to clarify what text is added, what is removed, and what is an editorial note.

• The section numbers of the proposed wording now match the section numbers in the working draft of the C++ standard.

2.2. R8

The changes since R7 are as follows:

Fixes:

• get_env(obj) is required to be nothrow.

• get_env and the associated environment utilities are moved back into std::execution from std::.

• make_completion_signatures is renamed transform_completion_signatures_of and is expressed in terms of the new transform_completion_signatures, which takes an input set of completion signatures instead of a sender and an environment.

• Add a requirement on queryable objects that if tag_invoke(query, env, args...) is well-formed, then query(env, args...) is expression-equivalent to it. This is necessary to properly specify how to join two environments in the presence of queries that have defaults.

• The sender_in<Sndr, Env> concept requires that E satisfies queryable.

• Senders of more than one value are now co_await-able in coroutines, the result of which is a std::tuple of the values (which is suitable as the initializer of a structured binding).

Enhancements:

• The exposition-only class template basic-sender is greatly enhanced, and the sender algorithms are respecified in term of it.

• enable_sender and enable_receiver traits now have default implementations that look for nested sender_concept and receiver_concept types, respectively.

2.3. R7

The changes since R6 are as follows:

Fixes:

• Make it valid to pass non-variadic templates to the exposition-only alias template gather-signatures, fixing the definitions of value_types_of_t, error_types_of_t, and the exposition-only alias template sync-wait-result-type.

• Removed the query forwarding from receiver_adaptor that was inadvertantly left over from a previous edit.

• When adapting a sender to an awaitable with as_awaitable, the sender’s value result datum is decayed before being stored in the exposition-only variant.

• Correctly specify the completion signatures of the schedule_from algorithm.

• The sender_of concept no longer distinguishes between a sender of a type T and a sender of a type T&&.

• The just and just_error sender factories now reject C-style arrays instead of silently decaying them to pointers.

Enhancements:

• The sender and receiver concepts get explicit opt-in traits called enable_sender and enable_receiver, respectively. The traits have default implementations that look for nested is_sender and is_receiver types, respectively.

• get_attrs is removed and get_env is used in its place.

• The exposition-only type empty-env is made normative and is renamed empty_env.

• get_env gets a fall-back implementation that simply returns empty_env{} if a tag_invoke overload is not found.

• get_env is required to be insensitive to the cvref-qualification of its argument.

• get_env, empty_env, and env_of_t are moved into the std:: namespace.

• Add a new subclause describing the async programming model of senders in abstract terms. See § 34.3 Asynchronous operations [async.ops].

2.4. R6

The changes since R5 are as follows:

Fixes:

• Fix typo in the specification of in_place_stop_source about the relative lifetimes of the tokens and the source that produced them.

• get_completion_signatures tests for awaitability with a promise type similar to the one used by connect for the sake of consistency.

• A coroutine promise type is an environment provider (that is, it implements get_env()) rather than being directly queryable. The previous draft was inconsistent about that.

Enhancements:

• Sender queries are moved into a separate queryable "attributes" object that is accessed by passing the sender to get_attrs() (see below). The sender concept is reexpressed to require get_attrs() and separated from a new sender_in<Snd, Env> concept for checking whether a type is a sender within a particular execution environment.

• The placeholder types no_env and dependent_completion_signatures<> are no longer needed and are dropped.

• ensure_started and split are changed to persist the result of calling get_attrs() on the input sender.

• Reorder constraints of the scheduler and receiver concepts to avoid constraint recursion when used in tandem with poorly-constrained, implicitly convertible types.

• Re-express the sender_of concept to be more ergonomic and general.

• Make the specification of the alias templates value_types_of_t and error_types_of_t, and the variable template sends_done more concise by expressing them in terms of a new exposition-only alias template gather-signatures.

2.4.1. Environments and attributes

In earlier revisions, receivers, senders, and schedulers all were directly queryable. In R4, receiver queries were moved into a separate "environment" object, obtainable from a receiver with a get_env accessor. In R6, the sender queries are given similar treatment, relocating to a "attributes" object obtainable from a sender with a get_attrs accessor. This was done to solve a number of design problems with the split and ensure_started algorithms; _e.g._, see NVIDIA/stdexec#466.

Schedulers, however, remain directly queryable. As lightweight handles that are required to be movable and copyable, there is little reason to want to dispose of a scheduler and yet persist the scheduler’s queries.

This revision also makes operation states directly queryable, even though there isn’t yet a use for such. Some early prototypes of cooperative bulk parallel sender algorithms done at NVIDIA suggest the utility of forwardable operation state queries. The authors chose to make opstates directly queryable since the opstate object is itself required to be kept alive for the duration of asynchronous operation.

2.5. R5

The changes since R4 are as follows:

Fixes:

• start_detached requires its argument to be a void sender (sends no values to set_value).

Enhancements:

• Receiver concepts refactored to no longer require an error channel for exception_ptr or a stopped channel.

• sender_of concept and connect customization point additionally require that the receiver is capable of receiving all of the sender’s possible completions.

• get_completion_signatures is now required to return an instance of either completion_signatures or dependent_completion_signatures.

• make_completion_signatures made more general.

• receiver_adaptor handles get_env as it does the set_* members; that is, receiver_adaptor will look for a member named get_env() in the derived class, and if found dispatch the get_env_t tag invoke customization to it.

• just, just_error, just_stopped, and into_variant have been respecified as customization point objects instead of functions, following LEWG guidance.

2.6. R4

The changes since R3 are as follows:

Fixes:

• Fix specification of get_completion_scheduler on the transfer, schedule_from and transfer_when_all algorithms; the completion scheduler cannot be guaranteed for set_error.

• The value of sends_stopped for the default sender traits of types that are generally awaitable was changed from false to true to acknowledge the fact that some coroutine types are generally awaitable and may implement the unhandled_stopped() protocol in their promise types.

• Fix the incorrect use of inline namespaces in the <execution> header.

• Shorten the stable names for the sections.

• sync_wait now handles std::error_code specially by throwing a std::system_error on failure.

• Fix how ADL isolation from class template arguments is specified so it doesn’t constrain implmentations.

• Properly expose the tag types in the header <execution> synopsis.

Enhancements:

• Support for "dependently-typed" senders, where the completion signatures -- and thus the sender metadata -- depend on the type of the receiver connected to it. See the section dependently-typed senders below for more information.

• Add a read(query) sender factory for issuing a query against a receiver and sending the result through the value channel. (This is a useful instance of a dependently-typed sender.)

• Add completion_signatures utility for declaratively defining a typed sender’s metadata.

• Add make_completion_signatures utility for specifying a sender’s completion signatures by adapting those of another sender.

• Drop support for untyped senders and rename typed_sender to sender.

• set_done is renamed to set_stopped. All occurances of "done" in indentifiers replaced with "stopped"

• Add customization points for controlling the forwarding of scheduler, sender, receiver, and environment queries through layers of adaptors; specify the behavior of the standard adaptors in terms of the new customization points.

• Add get_delegatee_scheduler query to forward a scheduler that can be used by algorithms or by the scheduler to delegate work and forward progress.

• Add schedule_result_t alias template.

• More precisely specify the sender algorithms, including precisely what their completion signatures are.

• stopped_as_error respecified as a customization point object.

• tag_invoke respecified to improve diagnostics.

2.6.1. Dependently-typed senders

Background:

In the sender/receiver model, as with coroutines, contextual information about the current execution is most naturally propagated from the consumer to the producer. In coroutines, that means information like stop tokens, allocators and schedulers are propagated from the calling coroutine to the callee. In sender/receiver, that means that that contextual information is associated with the receiver and is queried by the sender and/or operation state after the sender and the receiver are connect-ed.

Problem:

The implication of the above is that the sender alone does not have all the information about the async computation it will ultimately initiate; some of that information is provided late via the receiver. However, the sender_traits mechanism, by which an algorithm can introspect the value and error types the sender will propagate, only accepts a sender parameter. It does not take into consideration the type information that will come in late via the receiver. The effect of this is that some senders cannot be typed senders when they otherwise could be.

Example:

To get concrete, consider the case of the "get_scheduler()" sender: when connect-ed and start-ed, it queries the receiver for its associated scheduler and passes it back to the receiver through the value channel. That sender’s "value type" is the type of the receiver’s scheduler. What then should sender_traits<get_scheduler_sender>::value_types report for the get_scheduler()'s value type? It can’t answer because it doesn’t know.

This causes knock-on problems since some important algorithms require a typed sender, such as sync_wait. To illustrate the problem, consider the following code:

namespace ex = std::execution;

ex::sender auto task =
  ex::let_value(
    ex::get_scheduler(), // Fetches scheduler from receiver.
    [](auto current_sched) {
      // Lauch some nested work on the current scheduler:
      return ex::on(current_sched, nested work...);
    });

std::this_thread::sync_wait(std::move(task));

The code above is attempting to schedule some work onto the sync_wait's run_loop execution resource. But let_value only returns a typed sender when the input sender is typed. As we explained above, get_scheduler() is not typed, so task is likewise not typed. Since task isn’t typed, it cannot be passed to sync_wait which is expecting a typed sender. The above code would fail to compile.

Solution:

The solution is conceptually quite simple: extend the sender_traits mechanism to optionally accept a receiver in addition to the sender. The algorithms can use sender_traits<Sender, Receiver> to inspect the async operation’s completion-signals. The typed_sender concept would also need to take an optional receiver parameter. This is the simplest change, and it would solve the immediate problem.

Design:

Using the receiver type to compute the sender traits turns out to have pitfalls in practice. Many receivers make use of that type information in their implementation. It is very easy to create cycles in the type system, leading to inscrutible errors. The design pursued in R4 is to give receivers an associated environment object -- a bag of key/value pairs -- and to move the contextual information (schedulers, etc) out of the receiver and into the environment. The sender_traits template and the typed_sender concept, rather than taking a receiver, take an environment. This is a much more robust design.

A further refinement of this design would be to separate the receiver and the environment entirely, passing then as separate arguments along with the sender to connect. This paper does not propose that change.

Impact:

This change, apart from increasing the expressive power of the sender/receiver abstraction, has the following impact:

• Typed senders become moderately more challenging to write. (The new completion_signatures and transform_completion_signatures utilities are added to ease this extra burden.)

• Sender adaptor algorithms that previously constrained their sender arguments to satisfy the typed_sender concept can no longer do so as the receiver is not available yet. This can result in type-checking that is done later, when connect is ultimately called on the resulting sender adaptor.

• Operation states that own receivers that add to or change the environment are typically larger by one pointer. It comes with the benefit of far fewer indirections to evaluate queries.

"Has it been implemented?"

Yes, the reference implementation, which can be found at https://github.com/NVIDIA/stdexec, has implemented this design as well as some dependently-typed senders to confirm that it works.

Implementation experience

Although this change has not yet been made in libunifex, the most widely adopted sender/receiver implementation, a similar design can be found in Folly’s coroutine support library. In Folly.Coro, it is possible to await a special awaitable to obtain the current coroutine’s associated scheduler (called an executor in Folly).

For instance, the following Folly code grabs the current executor, schedules a task for execution on that executor, and starts the resulting (scheduled) task by enqueueing it for execution.

// From Facebook’s Folly open source library:
template <class T>
folly::coro::Task<void> CancellableAsyncScope::co_schedule(folly::coro::Task<T>&& task) {
  this->add(std::move(task).scheduleOn(co_await co_current_executor));
  co_return;
}

Facebook relies heavily on this pattern in its coroutine code. But as described above, this pattern doesn’t work with R3 of std::execution because of the lack of dependently-typed schedulers. The change to sender_traits in R4 rectifies that.

Why now?

The authors are loathe to make any changes to the design, however small, at this stage of the C++23 release cycle. But we feel that, for a relatively minor design change -- adding an extra template parameter to sender_traits and typed_sender -- the returns are large enough to justify the change. And there is no better time to make this change than as early as possible.

One might wonder why this missing feature not been added to sender/receiver before now. The designers of sender/receiver have long been aware of the need. What was missing was a clean, robust, and simple design for the change, which we now have.

Drive-by:

We took the opportunity to make an additional drive-by change: Rather than providing the sender traits via a class template for users to specialize, we changed it into a sender query: get_completion_signatures(sender, env). That function’s return type is used as the sender’s traits. The authors feel this leads to a more uniform design and gives sender authors a straightforward way to make the value/error types dependent on the cv- and ref-qualification of the sender if need be.

Details:

Below are the salient parts of the new support for dependently-typed senders in R4:

• Receiver queries have been moved from the receiver into a separate environment object.

• Receivers have an associated environment. The new get_env CPO retrieves a receiver’s environment. If a receiver doesn’t implement get_env, it returns an unspecified "empty" environment -- an empty struct.

• sender_traits now takes an optional Env parameter that is used to determine the error/value types.

• The primary sender_traits template is replaced with a completion_signatures_of_t alias implemented in terms of a new get_completion_signatures CPO that dispatches with tag_invoke. get_completion_signatures takes a sender and an optional environment. A sender can customize this to specify its value/error types.

• Support for untyped senders is dropped. The typed_sender concept has been renamed to sender and now takes an optional environment.

• The environment argument to the sender concept and the get_completion_signatures CPO defaults to no_env. All environment queries fail (are ill-formed) when passed an instance of no_env.

• A type S is required to satisfy sender<S> to be considered a sender. If it doesn’t know what types it will complete with independent of an environment, it returns an instance of the placeholder traits dependent_completion_signatures.

• If a sender satisfies both sender<S> and sender<S, Env>, then the completion signatures for the two cannot be different in any way. It is possible for an implementation to enforce this statically, but not required.

• All of the algorithms and examples have been updated to work with dependently-typed senders.

2.7. R3

The changes since R2 are as follows:

Fixes:

• Fix specification of the on algorithm to clarify lifetimes of intermediate operation states and properly scope the get_scheduler query.

• Fix a memory safety bug in the implementation of connect-awaitable.

• Fix recursive definition of the scheduler concept.

Enhancements:

• Add run_loop execution resource.

• Add receiver_adaptor utility to simplify writing receivers.

• Require a scheduler’s sender to model sender_of and provide a completion scheduler.

• Specify the cancellation scope of the when_all algorithm.

• Make as_awaitable a customization point.

• Change connect's handling of awaitables to consider those types that are awaitable owing to customization of as_awaitable.

• Add value_types_of_t and error_types_of_t alias templates; rename stop_token_type_t to stop_token_of_t.

• Add a design rationale for the removal of the possibly eager algorithms.

• Expand the section on field experience.

2.8. R2

The changes since R1 are as follows:

• Remove the eagerly executing sender algorithms.

• Extend the execution::connect customization point and the sender_traits<> template to recognize awaitables as typed_senders.

• Add utilities as_awaitable() and with_awaitable_senders<> so a coroutine type can trivially make senders awaitable with a coroutine.

• Add a section describing the design of the sender/awaitable interactions.

• Add a section describing the design of the cancellation support in sender/receiver.

• Add a section showing examples of simple sender adaptor algorithms.

• Add a section showing examples of simple schedulers.

• Add a few more examples: a sudoku solver, a parallel recursive file copy, and an echo server.

• Refined the forward progress guarantees on the bulk algorithm.

• Add a section describing how to use a range of senders to represent async sequences.

• Add a section showing how to use senders to represent partial success.

• Add sender factories execution::just_error and execution::just_stopped.

• Add sender adaptors execution::stopped_as_optional and execution::stopped_as_error.

• Document more production uses of sender/receiver at scale.

• Various fixes of typos and bugs.

2.9. R1

The changes since R0 are as follows:

• Added a new concept, sender_of.

• Added a new scheduler query, this_thread::execute_may_block_caller.

• Added a new scheduler query, get_forward_progress_guarantee.

• Removed the unschedule adaptor.

• Various fixes of typos and bugs.

2.10. R0

Initial revision.

3. Design - introduction

The following three sections describe the entirety of the proposed design.

• § 3 Design - introduction describes the conventions used through the rest of the design sections, as well as an example illustrating how we envision code will be written using this proposal.

• § 4 Design - user side describes all the functionality from the perspective we intend for users: it describes the various concepts they will interact with, and what their programming model is.

• § 5 Design - implementer side describes the machinery that allows for that programming model to function, and the information contained there is necessary for people implementing senders and sender algorithms (including the standard library ones) - but is not necessary to use senders productively.

3.1. Conventions

The following conventions are used throughout the design section:

1. The namespace proposed in this paper is the same as in A Unified Executors Proposal for C++: std::execution; however, for brevity, the std:: part of this name is omitted. When you see execution::foo, treat that as std::execution::foo.

2. Universal references and explicit calls to std::move/std::forward are omitted in code samples and signatures for simplicity; assume universal references and perfect forwarding unless stated otherwise.

3. None of the names proposed here are names that we are particularly attached to; consider the names to be reasonable placeholders that can freely be changed, should the committee want to do so.

3.2. Queries and algorithms

A query is a callable that takes some set of objects (usually one) as parameters and returns facts about those objects without modifying them. Queries are usually customization point objects, but in some cases may be functions.

An algorithm is a callable that takes some set of objects as parameters and causes those objects to do something. Algorithms are usually customization point objects, but in some cases may be functions.

4. Design - user side

4.1. Execution resources describe the place of execution

An execution resource is a resource that represents the place where execution will happen. This could be a concrete resource - like a specific thread pool object, or a GPU - or a more abstract one, like the current thread of execution. Execution contexts don’t need to have a representation in code; they are simply a term describing certain properties of execution of a function.

4.2. Schedulers represent execution resources

A scheduler is a lightweight handle that represents a strategy for scheduling work onto an execution resource. Since execution resources don’t necessarily manifest in C++ code, it’s not possible to program directly against their API. A scheduler is a solution to that problem: the scheduler concept is defined by a single sender algorithm, schedule, which returns a sender that will complete on an execution resource determined by the scheduler. Logic that you want to run on that context can be placed in the receiver’s completion-signalling method.

execution::scheduler auto sch = thread_pool.scheduler();
execution::sender auto snd = execution::schedule(sch);
// snd is a sender (see below) describing the creation of a new execution resource
// on the execution resource associated with sch

Note that a particular scheduler type may provide other kinds of scheduling operations which are supported by its associated execution resource. It is not limited to scheduling purely using the execution::schedule API.

Future papers will propose additional scheduler concepts that extend scheduler to add other capabilities. For example:

• A time_scheduler concept that extends scheduler to support time-based scheduling. Such a concept might provide access to schedule_after(sched, duration), schedule_at(sched, time_point) and now(sched) APIs.

• Concepts that extend scheduler to support opening, reading and writing files asynchronously.

• Concepts that extend scheduler to support connecting, sending data and receiving data over the network asynchronously.

4.3. Senders describe work

A sender is an object that describes work. Senders are similar to futures in existing asynchrony designs, but unlike futures, the work that is being done to arrive at the values they will send is also directly described by the sender object itself. A sender is said to send some values if a receiver connected (see § 5.3 execution::connect) to that sender will eventually receive said values.

The primary defining sender algorithm is § 5.3 execution::connect; this function, however, is not a user-facing API; it is used to facilitate communication between senders and various sender algorithms, but end user code is not expected to invoke it directly.

The way user code is expected to interact with senders is by using sender algorithms. This paper proposes an initial set of such sender algorithms, which are described in § 4.4 Senders are composable through sender algorithms, § 4.19 User-facing sender factories, § 4.20 User-facing sender adaptors, and § 4.21 User-facing sender consumers. For example, here is how a user can create a new sender on a scheduler, attach a continuation to it, and then wait for execution of the continuation to complete:

execution::scheduler auto sch = thread_pool.scheduler();
execution::sender auto snd = execution::schedule(sch);
execution::sender auto cont = execution::then(snd, []{
    std::fstream file{ "result.txt" };
    file << compute_result;
});

this_thread::sync_wait(cont);
// at this point, cont has completed execution

4.4. Senders are composable through sender algorithms

Asynchronous programming often departs from traditional code structure and control flow that we are familiar with. A successful asynchronous framework must provide an intuitive story for composition of asynchronous work: expressing dependencies, passing objects, managing object lifetimes, etc.

The true power and utility of senders is in their composability. With senders, users can describe generic execution pipelines and graphs, and then run them on and across a variety of different schedulers. Senders are composed using sender algorithms:

• sender factories, algorithms that take no senders and return a sender.

• sender adaptors, algorithms that take (and potentially execution::connect) senders and return a sender.

• sender consumers, algorithms that take (and potentially execution::connect) senders and do not return a sender.

4.5. Senders can propagate completion schedulers

One of the goals of executors is to support a diverse set of execution resources, including traditional thread pools, task and fiber frameworks (like HPX Legion), and GPUs and other accelerators (managed by runtimes such as CUDA or SYCL). On many of these systems, not all execution agents are created equal and not all functions can be run on all execution agents. Having precise control over the execution resource used for any given function call being submitted is important on such systems, and the users of standard execution facilities will expect to be able to express such requirements.

A Unified Executors Proposal for C++ was not always clear about the place of execution of any given piece of code. Precise control was present in the two-way execution API present in earlier executor designs, but it has so far been missing from the senders design. There has been a proposal (Towards C++23 executors: A proposal for an initial set of algorithms) to provide a number of sender algorithms that would enforce certain rules on the places of execution of the work described by a sender, but we have found those sender algorithms to be insufficient for achieving the best performance on all platforms that are of interest to us. The implementation strategies that we are aware of result in one of the following situations:

1. trying to submit work to one execution resource (such as a CPU thread pool) from another execution resource (such as a GPU or a task framework), which assumes that all execution agents are as capable as a std::thread (which they aren’t).

2. forcibly interleaving two adjacent execution graph nodes that are both executing on one execution resource (such as a GPU) with glue code that runs on another execution resource (such as a CPU), which is prohibitively expensive for some execution resources (such as CUDA or SYCL).

3. having to customise most or all sender algorithms to support an execution resource, so that you can avoid problems described in 1. and 2, which we believe is impractical and brittle based on months of field experience attempting this in Agency.

None of these implementation strategies are acceptable for many classes of parallel runtimes, such as task frameworks (like HPX) or accelerator runtimes (like CUDA or SYCL).

Therefore, in addition to the on sender algorithm from Towards C++23 executors: A proposal for an initial set of algorithms, we are proposing a way for senders to advertise what scheduler (and by extension what execution resource) they will complete on. Any given sender may have completion schedulers for some or all of the signals (value, error, or stopped) it completes with (for more detail on the completion-signals, see § 5.1 Receivers serve as glue between senders). When further work is attached to that sender by invoking sender algorithms, that work will also complete on an appropriate completion scheduler.

4.5.1. execution::get_completion_scheduler

get_completion_scheduler is a query that retrieves the completion scheduler for a specific completion-signal from a sender’s environment. For a sender that lacks a completion scheduler query for a given signal, calling get_completion_scheduler is ill-formed. If a sender advertises a completion scheduler for a signal in this way, that sender must ensure that it sends that signal on an execution agent belonging to an execution resource represented by a scheduler returned from this function. See § 4.5 Senders can propagate completion schedulers for more details.

execution::scheduler auto cpu_sched = new_thread_scheduler{};
execution::scheduler auto gpu_sched = cuda::scheduler();

execution::sender auto snd0 = execution::schedule(cpu_sched);
execution::scheduler auto completion_sch0 =
  execution::get_completion_scheduler<execution::set_value_t>(get_env(snd0));
// completion_sch0 is equivalent to cpu_sched

execution::sender auto snd1 = execution::then(snd0, []{
    std::cout << "I am running on cpu_sched!\n";
});
execution::scheduler auto completion_sch1 =
  execution::get_completion_scheduler<execution::set_value_t>(get_env(snd1));
// completion_sch1 is equivalent to cpu_sched

execution::sender auto snd2 = execution::transfer(snd1, gpu_sched);
execution::sender auto snd3 = execution::then(snd2, []{
    std::cout << "I am running on gpu_sched!\n";
});
execution::scheduler auto completion_sch3 =
  execution::get_completion_scheduler<execution::set_value_t>(get_env(snd3));
// completion_sch3 is equivalent to gpu_sched

4.6. Execution resource transitions are explicit

A Unified Executors Proposal for C++ does not contain any mechanisms for performing an execution resource transition. The only sender algorithm that can create a sender that will move execution to a specific execution resource is execution::schedule, which does not take an input sender. That means that there’s no way to construct sender chains that traverse different execution resources. This is necessary to fulfill the promise of senders being able to replace two-way executors, which had this capability.

We propose that, for senders advertising their completion scheduler, all execution resource transitions must be explicit; running user code anywhere but where they defined it to run must be considered a bug.

The execution::transfer sender adaptor performs a transition from one execution resource to another:

execution::scheduler auto sch1 = ...;
execution::scheduler auto sch2 = ...;

execution::sender auto snd1 = execution::schedule(sch1);
execution::sender auto then1 = execution::then(snd1, []{
    std::cout << "I am running on sch1!\n";
});

execution::sender auto snd2 = execution::transfer(then1, sch2);
execution::sender auto then2 = execution::then(snd2, []{
    std::cout << "I am running on sch2!\n";
});

this_thread::sync_wait(then2);

4.7. Senders can be either multi-shot or single-shot

Some senders may only support launching their operation a single time, while others may be repeatable and support being launched multiple times. Executing the operation may consume resources owned by the sender.

For example, a sender may contain a std::unique_ptr that it will be transferring ownership of to the operation-state returned by a call to execution::connect so that the operation has access to this resource. In such a sender, calling execution::connect consumes the sender such that after the call the input sender is no longer valid. Such a sender will also typically be move-only so that it can maintain unique ownership of that resource.

A single-shot sender can only be connected to a receiver at most once. Its implementation of execution::connect only has overloads for an rvalue-qualified sender. Callers must pass the sender as an rvalue to the call to execution::connect, indicating that the call consumes the sender.

A multi-shot sender can be connected to multiple receivers and can be launched multiple times. Multi-shot senders customise execution::connect to accept an lvalue reference to the sender. Callers can indicate that they want the sender to remain valid after the call to execution::connect by passing an lvalue reference to the sender to call these overloads. Multi-shot senders should also define overloads of execution::connect that accept rvalue-qualified senders to allow the sender to be also used in places where only a single-shot sender is required.

If the user of a sender does not require the sender to remain valid after connecting it to a receiver then it can pass an rvalue-reference to the sender to the call to execution::connect. Such usages should be able to accept either single-shot or multi-shot senders.

If the caller does wish for the sender to remain valid after the call then it can pass an lvalue-qualified sender to the call to execution::connect. Such usages will only accept multi-shot senders.

Algorithms that accept senders will typically either decay-copy an input sender and store it somewhere for later usage (for example as a data-member of the returned sender) or will immediately call execution::connect on the input sender, such as in this_thread::sync_wait or execution::start_detached.

Some multi-use sender algorithms may require that an input sender be copy-constructible but will only call execution::connect on an rvalue of each copy, which still results in effectively executing the operation multiple times. Other multi-use sender algorithms may require that the sender is move-constructible but will invoke execution::connect on an lvalue reference to the sender.

For a sender to be usable in both multi-use scenarios, it will generally be required to be both copy-constructible and lvalue-connectable.

4.8. Senders are forkable

Any non-trivial program will eventually want to fork a chain of senders into independent streams of work, regardless of whether they are single-shot or multi-shot. For instance, an incoming event to a middleware system may be required to trigger events on more than one downstream system. This requires that we provide well defined mechanisms for making sure that connecting a sender multiple times is possible and correct.

The split sender adaptor facilitates connecting to a sender multiple times, regardless of whether it is single-shot or multi-shot:

auto some_algorithm(execution::sender auto&& input) {
    execution::sender auto multi_shot = split(input);
    // "multi_shot" is guaranteed to be multi-shot,
    // regardless of whether "input" was multi-shot or not

    return when_all(
      then(multi_shot, [] { std::cout << "First continuation\n"; }),
      then(multi_shot, [] { std::cout << "Second continuation\n"; })
    );
}

4.9. Senders support cancellation

Senders are often used in scenarios where the application may be concurrently executing multiple strategies for achieving some program goal. When one of these strategies succeeds (or fails) it may not make sense to continue pursuing the other strategies as their results are no longer useful.

For example, we may want to try to simultaneously connect to multiple network servers and use whichever server responds first. Once the first server responds we no longer need to continue trying to connect to the other servers.

Ideally, in these scenarios, we would somehow be able to request that those other strategies stop executing promptly so that their resources (e.g. cpu, memory, I/O bandwidth) can be released and used for other work.

While the design of senders has support for cancelling an operation before it starts by simply destroying the sender or the operation-state returned from execution::connect() before calling execution::start(), there also needs to be a standard, generic mechanism to ask for an already-started operation to complete early.

The ability to be able to cancel in-flight operations is fundamental to supporting some kinds of generic concurrency algorithms.

For example:

• a when_all(ops...) algorithm should cancel other operations as soon as one operation fails

• a first_successful(ops...) algorithm should cancel the other operations as soon as one operation completes successfuly

• a generic timeout(src, duration) algorithm needs to be able to cancel the src operation after the timeout duration has elapsed.

• a stop_when(src, trigger) algorithm should cancel src if trigger completes first and cancel trigger if src completes first

The mechanism used for communcating cancellation-requests, or stop-requests, needs to have a uniform interface so that generic algorithms that compose sender-based operations, such as the ones listed above, are able to communicate these cancellation requests to senders that they don’t know anything about.

The design is intended to be composable so that cancellation of higher-level operations can propagate those cancellation requests through intermediate layers to lower-level operations that need to actually respond to the cancellation requests.

For example, we can compose the algorithms mentioned above so that child operations are cancelled when any one of the multiple cancellation conditions occurs:

sender auto composed_cancellation_example(auto query) {
  return stop_when(
    timeout(
      when_all(
        first_successful(
          query_server_a(query),
          query_server_b(query)),
        load_file("some_file.jpg")),
      5s),
    cancelButton.on_click());
}

In this example, if we take the operation returned by query_server_b(query), this operation will receive a stop-request when any of the following happens:

• first_successful algorithm will send a stop-request if query_server_a(query) completes successfully

• when_all algorithm will send a stop-request if the load_file("some_file.jpg") operation completes with an error or stopped result.

• timeout algorithm will send a stop-request if the operation does not complete within 5 seconds.

• stop_when algorithm will send a stop-request if the user clicks on the "Cancel" button in the user-interface.

• The parent operation consuming the composed_cancellation_example() sends a stop-request

Note that within this code there is no explicit mention of cancellation, stop-tokens, callbacks, etc. yet the example fully supports and responds to the various cancellation sources.

The intent of the design is that the common usage of cancellation in sender/receiver-based code is primarily through use of concurrency algorithms that manage the detailed plumbing of cancellation for you. Much like algorithms that compose senders relieve the user from having to write their own receiver types, algorithms that introduce concurrency and provide higher-level cancellation semantics relieve the user from having to deal with low-level details of cancellation.

4.9.1. Cancellation design summary

The design of cancellation described in this paper is built on top of and extends the std::stop_token-based cancellation facilities added in C++20, first proposed in Composable cancellation for sender-based async operations.

At a high-level, the facilities proposed by this paper for supporting cancellation include:

• Add a std::stoppable_token concept that generalises the interface of the std::stop_token type to allow other stop token types with different implementation strategies.

• Add std::unstoppable_token concept for detecting whether a stoppable_token can never receive a stop-request.

• Add std::inplace_stop_token, std::inplace_stop_source and std::inplace_stop_callback<CB> types that provide a more efficient implementation of a stop-token for use in structured concurrency situations.

• Add std::never_stop_token for use in places where you never want to issue a stop-request.

• Add std::execution::get_stop_token() CPO for querying the stop-token to use for an operation from its receiver’s execution environment.

• Add std::execution::stop_token_of_t<T> for querying the type of a stop-token returned from get_stop_token().

In addition, there are requirements added to some of the algorithms to specify what their cancellation behaviour is and what the requirements of customisations of those algorithms are with respect to cancellation.

The key component that enables generic cancellation within sender-based operations is the execution::get_stop_token() CPO. This CPO takes a single parameter, which is the execution environment of the receiver passed to execution::connect, and returns a std::stoppable_token that the operation can use to check for stop-requests for that operation.

As the caller of execution::connect typically has control over the receiver type it passes, it is able to customise the std::execution::get_env() CPO for that receiver to return an execution environment that hooks the execution::get_stop_token() CPO to return a stop-token that the receiver has control over and that it can use to communicate a stop-request to the operation once it has started.

4.9.2. Support for cancellation is optional

Support for cancellation is optional, both on part of the author of the receiver and on part of the author of the sender.

If the receiver’s execution environment does not customise the execution::get_stop_token() CPO then invoking the CPO on that receiver’s environment will invoke the default implementation which returns std::never_stop_token. This is a special stoppable_token type that is statically known to always return false from the stop_possible() method.

Sender code that tries to use this stop-token will in general result in code that handles stop-requests being compiled out and having little to no run-time overhead.

If the sender doesn’t call execution::get_stop_token(), for example because the operation does not support cancellation, then it will simply not respond to stop-requests from the caller.

Note that stop-requests are generally racy in nature as there is often a race betwen an operation completing naturally and the stop-request being made. If the operation has already completed or past the point at which it can be cancelled when the stop-request is sent then the stop-request may just be ignored. An application will typically need to be able to cope with senders that might ignore a stop-request anyway.

4.9.3. Cancellation is inherently racy

Usually, an operation will attach a stop-callback at some point inside the call to execution::start() so that a subsequent stop-request will interrupt the logic.

A stop-request can be issued concurrently from another thread. This means the implementation of execution::start() needs to be careful to ensure that, once a stop-callback has been registered, that there are no data-races between a potentially concurrently-executing stop-callback and the rest of the execution::start() implementation.

An implementation of execution::start() that supports cancellation will generally need to perform (at least) two separate steps: launch the operation, subscribe a stop-callback to the receiver’s stop-token. Care needs to be taken depending on the order in which these two steps are performed.

If the stop-callback is subscribed first and then the operation is launched, care needs to be taken to ensure that a stop-request that invokes the stop-callback on another thread after the stop-callback is registered but before the operation finishes launching does not either result in a missed cancellation request or a data-race. e.g. by performing an atomic write after the launch has finished executing

If the operation is launched first and then the stop-callback is subscribed, care needs to be taken to ensure that if the launched operation completes concurrently on another thread that it does not destroy the operation-state until after the stop-callback has been registered. e.g. by having the execution::start implementation write to an atomic variable once it has finished registering the stop-callback and having the concurrent completion handler check that variable and either call the completion-signalling operation or store the result and defer calling the receiver’s completion-signalling operation to the execution::start() call (which is still executing).

For an example of an implementation strategy for solving these data-races see § 1.4 Asynchronous Windows socket recv.

4.9.4. Cancellation design status

This paper currently includes the design for cancellation as proposed in Composable cancellation for sender-based async operations - "Composable cancellation for sender-based async operations". P2175R0 contains more details on the background motivation and prior-art and design rationale of this design.

It is important to note, however, that initial review of this design in the SG1 concurrency subgroup raised some concerns related to runtime overhead of the design in single-threaded scenarios and these concerns are still being investigated.

The design of P2175R0 has been included in this paper for now, despite its potential to change, as we believe that support for cancellation is a fundamental requirement for an async model and is required in some form to be able to talk about the semantics of some of the algorithms proposed in this paper.

This paper will be updated in the future with any changes that arise from the investigations into P2175R0.

4.10. Sender factories and adaptors are lazy

In an earlier revision of this paper, some of the proposed algorithms supported executing their logic eagerly; i.e., before the returned sender has been connected to a receiver and started. These algorithms were removed because eager execution has a number of negative semantic and performance implications.

We have originally included this functionality in the paper because of a long-standing belief that eager execution is a mandatory feature to be included in the standard Executors facility for that facility to be acceptable for accelerator vendors. A particular concern was that we must be able to write generic algorithms that can run either eagerly or lazily, depending on the kind of an input sender or scheduler that have been passed into them as arguments. We considered this a requirement, because the _latency_ of launching work on an accelerator can sometimes be considerable.

However, in the process of working on this paper and implementations of the features proposed within, our set of requirements has shifted, as we understood the different implementation strategies that are available for the feature set of this paper better, and, after weighting the earlier concerns against the points presented below, we have arrived at the conclusion that a purely lazy model is enough for most algorithms, and users who intend to launch work earlier may use an algorithm such as ensure_started to achieve that goal. We have also come to deeply appreciate the fact that a purely lazy model allows both the implementation and the compiler to have a much better understanding of what the complete graph of tasks looks like, allowing them to better optimize the code - also when targetting accelerators.

4.10.1. Eager execution leads to detached work or worse

One of the questions that arises with APIs that can potentially return eagerly-executing senders is "What happens when those senders are destructed without a call to execution::connect?" or similarly, "What happens if a call to execution::connect is made, but the returned operation state is destroyed before execution::start is called on that operation state"?

In these cases, the operation represented by the sender is potentially executing concurrently in another thread at the time that the destructor of the sender and/or operation-state is running. In the case that the operation has not completed executing by the time that the destructor is run we need to decide what the semantics of the destructor is.

There are three main strategies that can be adopted here, none of which is particularly satisfactory:

1. Make this undefined-behaviour - the caller must ensure that any eagerly-executing sender is always joined by connecting and starting that sender. This approach is generally pretty hostile to programmers, particularly in the presence of exceptions, since it complicates the ability to compose these operations.

   Eager operations typically need to acquire resources when they are first called in order to start the operation early. This makes eager algorithms prone to failure. Consider, then, what might happen in an expression such as when_all(eager_op_1(), eager_op_2()). Imagine eager_op_1() starts an asynchronous operation successfully, but then eager_op_2() throws. For lazy senders, that failure happens in the context of the when_all algorithm, which handles the failure and ensures that async work joins on all code paths. In this case though -- the eager case -- the child operation has failed even before when_all has been called.

   It then becomes the responsibility, not of the algorithm, but of the end user to handle the exception and ensure that eager_op_1() is joined before allowing the exception to propagate. If they fail to do that, they incur undefined behavior.

2. Detach from the computation - let the operation continue in the background - like an implicit call to std::thread::detach(). While this approach can work in some circumstances for some kinds of applications, in general it is also pretty user-hostile; it makes it difficult to reason about the safe destruction of resources used by these eager operations. In general, detached work necessitates some kind of garbage collection; e.g., std::shared_ptr, to ensure resources are kept alive until the operations complete, and can make clean shutdown nigh impossible.

3. Block in the destructor until the operation completes. This approach is probably the safest to use as it preserves the structured nature of the concurrent operations, but also introduces the potential for deadlocking the application if the completion of the operation depends on the current thread making forward progress.

   The risk of deadlock might occur, for example, if a thread-pool with a small number of threads is executing code that creates a sender representing an eagerly-executing operation and then calls the destructor of that sender without joining it (e.g. because an exception was thrown). If the current thread blocks waiting for that eager operation to complete and that eager operation cannot complete until some entry enqueued to the thread-pool’s queue of work is run then the thread may wait for an indefinite amount of time. If all threads of the thread-pool are simultaneously performing such blocking operations then deadlock can result.

There are also minor variations on each of these choices. For example:

4. A variation of (1): Call std::terminate if an eager sender is destructed without joining it. This is the approach that std::thread destructor takes.

5. A variation of (2): Request cancellation of the operation before detaching. This reduces the chances of operations continuing to run indefinitely in the background once they have been detached but does not solve the lifetime- or shutdown-related challenges.

6. A variation of (3): Request cancellation of the operation before blocking on its completion. This is the strategy that std::jthread uses for its destructor. It reduces the risk of deadlock but does not eliminate it.

4.10.2. Eager senders complicate algorithm implementations

Algorithms that can assume they are operating on senders with strictly lazy semantics are able to make certain optimizations that are not available if senders can be potentially eager. With lazy senders, an algorithm can safely assume that a call to execution::start on an operation state strictly happens before the execution of that async operation. This frees the algorithm from needing to resolve potential race conditions. For example, consider an algorithm sequence that puts async operations in sequence by starting an operation only after the preceding one has completed. In an expression like sequence(a(), then(src, [] { b(); }), c()), one may reasonably assume that a(), b() and c() are sequenced and therefore do not need synchronisation. Eager algorithms break that assumption.

When an algorithm needs to deal with potentially eager senders, the potential race conditions can be resolved one of two ways, neither of which is desirable:

1. Assume the worst and implement the algorithm defensively, assuming all senders are eager. This obviously has overheads both at runtime and in algorithm complexity. Resolving race conditions is hard.

2. Require senders to declare whether they are eager or not with a query. Algorithms can then implement two different implementation strategies, one for strictly lazy senders and one for potentially eager senders. This addresses the performance problem of (1) while compounding the complexity problem.

4.10.3. Eager senders incur cancellation-related overhead

Another implication of the use of eager operations is with regards to cancellation. The eagerly executing operation will not have access to the caller’s stop token until the sender is connected to a receiver. If we still want to be able to cancel the eager operation then it will need to create a new stop source and pass its associated stop token down to child operations. Then when the returned sender is eventually connected it will register a stop callback with the receiver’s stop token that will request stop on the eager sender’s stop source.

As the eager operation does not know at the time that it is launched what the type of the receiver is going to be, and thus whether or not the stop token returned from execution::get_stop_token is an std::unstoppable_token or not, the eager operation is going to need to assume it might be later connected to a receiver with a stop token that might actually issue a stop request. Thus it needs to declare space in the operation state for a type-erased stop callback and incur the runtime overhead of supporting cancellation, even if cancellation will never be requested by the caller.

The eager operation will also need to do this to support sending a stop request to the eager operation in the case that the sender representing the eager work is destroyed before it has been joined (assuming strategy (5) or (6) listed above is chosen).

4.10.4. Eager senders cannot access execution resource from the receiver

In sender/receiver, contextual information is passed from parent operations to their children by way of receivers. Information like stop tokens, allocators, current scheduler, priority, and deadline are propagated to child operations with custom receivers at the time the operation is connected. That way, each operation has the contextual information it needs before it is started.

But if the operation is started before it is connected to a receiver, then there isn’t a way for a parent operation to communicate contextual information to its child operations, which may complete before a receiver is ever attached.

4.11. Schedulers advertise their forward progress guarantees

To decide whether a scheduler (and its associated execution resource) is sufficient for a specific task, it may be necessary to know what kind of forward progress guarantees it provides for the execution agents it creates. The C++ Standard defines the following forward progress guarantees:

• concurrent, which requires that a thread makes progress eventually;

• parallel, which requires that a thread makes progress once it executes a step; and

• weakly parallel, which does not require that the thread makes progress.

This paper introduces a scheduler query function, get_forward_progress_guarantee, which returns one of the enumerators of a new enum type, forward_progress_guarantee. Each enumerator of forward_progress_guarantee corresponds to one of the aforementioned guarantees.

4.12. Most sender adaptors are pipeable

To facilitate an intuitive syntax for composition, most sender adaptors are pipeable; they can be composed (piped) together with operator|. This mechanism is similar to the operator| composition that C++ range adaptors support and draws inspiration from piping in *nix shells. Pipeable sender adaptors take a sender as their first parameter and have no other sender parameters.

a | b will pass the sender a as the first argument to the pipeable sender adaptor b. Pipeable sender adaptors support partial application of the parameters after the first. For example, all of the following are equivalent:

execution::bulk(snd, N, [] (std::size_t i, auto d) {});
execution::bulk(N, [] (std::size_t i, auto d) {})(snd);
snd | execution::bulk(N, [] (std::size_t i, auto d) {});

Piping enables you to compose together senders with a linear syntax. Without it, you’d have to use either nested function call syntax, which would cause a syntactic inversion of the direction of control flow, or you’d have to introduce a temporary variable for each stage of the pipeline. Consider the following example where we want to execute first on a CPU thread pool, then on a CUDA GPU, then back on the CPU thread pool:

auto snd = execution::then(
             execution::transfer(
               execution::then(
                 execution::transfer(
                   execution::then(
                     execution::schedule(thread_pool.scheduler())
                     []{ return 123; }),
                   cuda::new_stream_scheduler()),
                 [](int i){ return 123 * 5; }),
               thread_pool.scheduler()),
             [](int i){ return i - 5; });
auto [result] = this_thread::sync_wait(snd).value();
// result == 610

auto snd0 = execution::schedule(thread_pool.scheduler());
auto snd1 = execution::then(snd0, []{ return 123; });
auto snd2 = execution::transfer(snd1, cuda::new_stream_scheduler());
auto snd3 = execution::then(snd2, [](int i){ return 123 * 5; })
auto snd4 = execution::transfer(snd3, thread_pool.scheduler())
auto snd5 = execution::then(snd4, [](int i){ return i - 5; });
auto [result] = *this_thread::sync_wait(snd4);
// result == 610

auto snd = execution::schedule(thread_pool.scheduler())
         | execution::then([]{ return 123; })
         | execution::transfer(cuda::new_stream_scheduler())
         | execution::then([](int i){ return 123 * 5; })
         | execution::transfer(thread_pool.scheduler())
         | execution::then([](int i){ return i - 5; });
auto [result] = this_thread::sync_wait(snd).value();
// result == 610

Certain sender adaptors are not pipeable, because using the pipeline syntax can result in confusion of the semantics of the adaptors involved. Specifically, the following sender adaptors are not pipeable.

• execution::when_all and execution::when_all_with_variant: Since this sender adaptor takes a variadic pack of senders, a partially applied form would be ambiguous with a non partially applied form with an arity of one less.

• execution::on: This sender adaptor changes how the sender passed to it is executed, not what happens to its result, but allowing it in a pipeline makes it read as if it performed a function more similar to transfer.

Sender consumers could be made pipeable, but we have chosen to not do so. However, since these are terminal nodes in a pipeline and nothing can be piped after them, we believe a pipe syntax may be confusing as well as unnecessary, as consumers cannot be chained. We believe sender consumers read better with function call syntax.

4.13. A range of senders represents an async sequence of data

Senders represent a single unit of asynchronous work. In many cases though, what is being modeled is a sequence of data arriving asynchronously, and you want computation to happen on demand, when each element arrives. This requires nothing more than what is in this paper and the range support in C++20. A range of senders would allow you to model such input as keystrikes, mouse movements, sensor readings, or network requests.

Given some expression R that is a range of senders, consider the following in a coroutine that returns an async generator type:

for (auto snd : R) {
  if (auto opt = co_await execution::stopped_as_optional(std::move(snd)))
    co_yield fn(*std::move(opt));
  else
    break;
}

This transforms each element of the asynchronous sequence R with the function fn on demand, as the data arrives. The result is a new asynchronous sequence of the transformed values.

Now imagine that R is the simple expression views::iota(0) | views::transform(execution::just). This creates a lazy range of senders, each of which completes immediately with monotonically increasing integers. The above code churns through the range, generating a new infine asynchronous range of values [fn(0), fn(1), fn(2), ...].

Far more interesting would be if R were a range of senders representing, say, user actions in a UI. The above code gives a simple way to respond to user actions on demand.

4.14. Senders can represent partial success

Receivers have three ways they can complete: with success, failure, or cancellation. This begs the question of how they can be used to represent async operations that partially succeed. For example, consider an API that reads from a socket. The connection could drop after the API has filled in some of the buffer. In cases like that, it makes sense to want to report both that the connection dropped and that some data has been successfully read.

Often in the case of partial success, the error condition is not fatal nor does it mean the API has failed to satisfy its post-conditions. It is merely an extra piece of information about the nature of the completion. In those cases, "partial success" is another way of saying "success". As a result, it is sensible to pass both the error code and the result (if any) through the value channel, as shown below:

// Capture a buffer for read_socket_async to fill in
execution::just(array<byte, 1024>{})
  | execution::let_value([socket](array<byte, 1024>& buff) {
      // read_socket_async completes with two values: an error_code and
      // a count of bytes:
      return read_socket_async(socket, span{buff})
          // For success (partial and full), specify the next action:
        | execution::let_value([](error_code err, size_t bytes_read) {
            if (err != 0) {
              // OK, partial success. Decide how to deal with the partial results
            } else {
              // OK, full success here.
            }
          });
    })

In other cases, the partial success is more of a partial failure. That happens when the error condition indicates that in some way the function failed to satisfy its post-conditions. In those cases, sending the error through the value channel loses valuable contextual information. It’s possible that bundling the error and the incomplete results into an object and passing it through the error channel makes more sense. In that way, generic algorithms will not miss the fact that a post-condition has not been met and react inappropriately.

Another possibility is for an async API to return a range of senders: if the API completes with full success, full error, or cancellation, the returned range contains just one sender with the result. Otherwise, if the API partially fails (doesn’t satisfy its post-conditions, but some incomplete result is available), the returned range would have two senders: the first containing the partial result, and the second containing the error. Such an API might be used in a coroutine as follows:

// Declare a buffer for read_socket_async to fill in
array<byte, 1024> buff;

for (auto snd : read_socket_async(socket, span{buff})) {
  try {
    if (optional<size_t> bytes_read =
          co_await execution::stopped_as_optional(std::move(snd))) {
      // OK, we read some bytes into buff. Process them here....
    } else {
      // The socket read was cancelled and returned no data. React
      // appropriately.
    }
  } catch (...) {
    // read_socket_async failed to meet its post-conditions.
    // Do some cleanup and propagate the error...
  }
}

Finally, it’s possible to combine these two approaches when the API can both partially succeed (meeting its post-conditions) and partially fail (not meeting its post-conditions).

4.15. All awaitables are senders

Since C++20 added coroutines to the standard, we expect that coroutines and awaitables will be how a great many will choose to express their asynchronous code. However, in this paper, we are proposing to add a suite of asynchronous algorithms that accept senders, not awaitables. One might wonder whether and how these algorithms will be accessible to those who choose coroutines instead of senders.

In truth there will be no problem because all generally awaitable types automatically model the sender concept. The adaptation is transparent and happens in the sender customization points, which are aware of awaitables. (By "generally awaitable" we mean types that don’t require custom await_transform trickery from a promise type to make them awaitable.)

For an example, imagine a coroutine type called task<T> that knows nothing about senders. It doesn’t implement any of the sender customization points. Despite that fact, and despite the fact that the this_thread::sync_wait algorithm is constrained with the sender concept, the following would compile and do what the user wants:

task<int> doSomeAsyncWork();

int main() {
  // OK, awaitable types satisfy the requirements for senders:
  auto o = this_thread::sync_wait(doSomeAsyncWork());
}

Since awaitables are senders, writing a sender-based asynchronous algorithm is trivial if you have a coroutine task type: implement the algorithm as a coroutine. If you are not bothered by the possibility of allocations and indirections as a result of using coroutines, then there is no need to ever write a sender, a receiver, or an operation state.

4.16. Many senders can be trivially made awaitable

If you choose to implement your sender-based algorithms as coroutines, you’ll run into the issue of how to retrieve results from a passed-in sender. This is not a problem. If the coroutine type opts in to sender support -- trivial with the execution::with_awaitable_senders utility -- then a large class of senders are transparently awaitable from within the coroutine.

For example, consider the following trivial implementation of the sender-based retry algorithm:

template<class S>
  requires single-sender<S&> // see [exec.as.awaitable]
task<single-sender-value-type<S>> retry(S s) {
  for (;;) {
    try {
      co_return co_await s;
    } catch(...) {
    }
  }
}

Only some senders can be made awaitable directly because of the fact that callbacks are more expressive than coroutines. An awaitable expression has a single type: the result value of the async operation. In contrast, a callback can accept multiple arguments as the result of an operation. What’s more, the callback can have overloaded function call signatures that take different sets of arguments. There is no way to automatically map such senders into awaitables. The with_awaitable_senders utility recognizes as awaitables those senders that send a single value of a single type. To await another kind of sender, a user would have to first map its value channel into a single value of a single type -- say, with the into_variant sender algorithm -- before co_await-ing that sender.

4.17. Cancellation of a sender can unwind a stack of coroutines

When looking at the sender-based retry algorithm in the previous section, we can see that the value and error cases are correctly handled. But what about cancellation? What happens to a coroutine that is suspended awaiting a sender that completes by calling execution::set_stopped?

When your task type’s promise inherits from with_awaitable_senders, what happens is this: the coroutine behaves as if an uncatchable exception had been thrown from the co_await expression. (It is not really an exception, but it’s helpful to think of it that way.) Provided that the promise types of the calling coroutines also inherit from with_awaitable_senders, or more generally implement a member function called unhandled_stopped, the exception unwinds the chain of coroutines as if an exception were thrown except that it bypasses catch(...) clauses.

In order to "catch" this uncatchable stopped exception, one of the calling coroutines in the stack would have to await a sender that maps the stopped channel into either a value or an error. That is achievable with the execution::let_stopped, execution::upon_stopped, execution::stopped_as_optional, or execution::stopped_as_error sender adaptors. For instance, we can use execution::stopped_as_optional to "catch" the stopped signal and map it into an empty optional as shown below:

if (auto opt = co_await execution::stopped_as_optional(some_sender)) {
  // OK, some_sender completed successfully, and opt contains the result.
} else {
  // some_sender completed with a cancellation signal.
}

As described in the section "All awaitables are senders", the sender customization points recognize awaitables and adapt them transparently to model the sender concept. When connect-ing an awaitable and a receiver, the adaptation layer awaits the awaitable within a coroutine that implements unhandled_stopped in its promise type. The effect of this is that an "uncatchable" stopped exception propagates seamlessly out of awaitables, causing execution::set_stopped to be called on the receiver.

Obviously, unhandled_stopped is a library extension of the coroutine promise interface. Many promise types will not implement unhandled_stopped. When an uncatchable stopped exception tries to propagate through such a coroutine, it is treated as an unhandled exception and terminate is called. The solution, as described above, is to use a sender adaptor to handle the stopped exception before awaiting it. It goes without saying that any future Standard Library coroutine types ought to implement unhandled_stopped. The author of Add lazy coroutine (coroutine task) type, which proposes a standard coroutine task type, is in agreement.

4.18. Composition with parallel algorithms

The C++ Standard Library provides a large number of algorithms that offer the potential for non-sequential execution via the use of execution policies. The set of algorithms with execution policy overloads are often referred to as "parallel algorithms", although additional policies are available.

Existing policies, such as execution::par, give the implementation permission to execute the algorithm in parallel. However, the choice of execution resources used to perform the work is left to the implementation.

We will propose a customization point for combining schedulers with policies in order to provide control over where work will execute.

template<class ExecutionPolicy>
unspecified executing_on(
    execution::scheduler auto scheduler,
    ExecutionPolicy && policy
);

This function would return an object of an unspecified type which can be used in place of an execution policy as the first argument to one of the parallel algorithms. The overload selected by that object should execute its computation as requested by policy while using scheduler to create any work to be run. The expression may be ill-formed if scheduler is not able to support the given policy.

The existing parallel algorithms are synchronous; all of the effects performed by the computation are complete before the algorithm returns to its caller. This remains unchanged with the executing_on customization point.

In the future, we expect additional papers will propose asynchronous forms of the parallel algorithms which (1) return senders rather than values or void and (2) where a customization point pairing a sender with an execution policy would similarly be used to obtain an object of unspecified type to be provided as the first argument to the algorithm.

4.19. User-facing sender factories

A sender factory is an algorithm that takes no senders as parameters and returns a sender.

4.19.1. execution::schedule

execution::sender auto schedule(
    execution::scheduler auto scheduler
);

Returns a sender describing the start of a task graph on the provided scheduler. See § 4.2 Schedulers represent execution resources.

execution::scheduler auto sch1 = get_system_thread_pool().scheduler();

execution::sender auto snd1 = execution::schedule(sch1);
// snd1 describes the creation of a new task on the system thread pool

4.19.2. execution::just

execution::sender auto just(
    auto ...&& values
);

Returns a sender with no completion schedulers, which sends the provided values. The input values are decay-copied into the returned sender. When the returned sender is connected to a receiver, the values are moved into the operation state if the sender is an rvalue; otherwise, they are copied. Then xvalues referencing the values in the operation state are passed to the receiver’s set_value.

execution::sender auto snd1 = execution::just(3.14);
execution::sender auto then1 = execution::then(snd1, [] (double d) {
  std::cout << d << "\n";
});

execution::sender auto snd2 = execution::just(3.14, 42);
execution::sender auto then2 = execution::then(snd2, [] (double d, int i) {
  std::cout << d << ", " << i << "\n";
});

std::vector v3{1, 2, 3, 4, 5};
execution::sender auto snd3 = execution::just(v3);
execution::sender auto then3 = execution::then(snd3, [] (std::vector<int>&& v3copy) {
  for (auto&& e : v3copy) { e *= 2; }
  return std::move(v3copy);
}
auto&& [v3copy] = this_thread::sync_wait(then3).value();
// v3 contains {1, 2, 3, 4, 5}; v3copy will contain {2, 4, 6, 8, 10}.

execution::sender auto snd4 = execution::just(std::vector{1, 2, 3, 4, 5});
execution::sender auto then4 = execution::then(std::move(snd4), [] (std::vector<int>&& v4) {
  for (auto&& e : v4) { e *= 2; }
  return std::move(v4);
});
auto&& [v4] = this_thread::sync_wait(std::move(then4)).value();
// v4 contains {2, 4, 6, 8, 10}. No vectors were copied in this example.

4.19.3. execution::just_error

execution::sender auto just_error(
    auto && error
);

Returns a sender with no completion schedulers, which completes with the specified error. If the provided error is an lvalue reference, a copy is made inside the returned sender and a non-const lvalue reference to the copy is sent to the receiver’s set_error. If the provided value is an rvalue reference, it is moved into the returned sender and an rvalue reference to it is sent to the receiver’s set_error.

4.19.4. execution::just_stopped

execution::sender auto just_stopped();

Returns a sender with no completion schedulers, which completes immediately by calling the receiver’s set_stopped.

4.19.5. execution::read

execution::sender auto read(auto tag);

execution::sender auto get_scheduler() {
  return read(execution::get_scheduler);
}
execution::sender auto get_delegatee_scheduler() {
  return read(execution::get_delegatee_scheduler);
}
execution::sender auto get_allocator() {
  return read(execution::get_allocator);
}
execution::sender auto get_stop_token() {
  return read(execution::get_stop_token);
}

Returns a sender that reaches into a receiver’s environment and pulls out the current value associated with the customization point denoted by Tag. It then sends the value read back to the receiver through the value channel. For instance, get_scheduler() (with no arguments) is a sender that asks the receiver for the currently suggested scheduler and passes it to the receiver’s set_value completion-signal.

This can be useful when scheduling nested dependent work. The following sender pulls the current schduler into the value channel and then schedules more work onto it.

execution::sender auto task =
  execution::get_scheduler()
    | execution::let_value([](auto sched) {
        return execution::on(sched, some nested work here);
    });

this_thread::sync_wait( std::move(task) ); // wait for it to finish

This code uses the fact that sync_wait associates a scheduler with the receiver that it connects with task. get_scheduler() reads that scheduler out of the receiver, and passes it to let_value's receiver’s set_value function, which in turn passes it to the lambda. That lambda returns a new sender that uses the scheduler to schedule some nested work onto sync_wait's scheduler.

4.20. User-facing sender adaptors

A sender adaptor is an algorithm that takes one or more senders, which it may execution::connect, as parameters, and returns a sender, whose completion is related to the sender arguments it has received.

Sender adaptors are lazy, that is, they are never allowed to submit any work for execution prior to the returned sender being started later on, and are also guaranteed to not start any input senders passed into them. Sender consumers such as § 4.21.1 execution::start_detached and § 4.21.2 this_thread::sync_wait start senders.

For more implementer-centric description of starting senders, see § 5.5 Sender adaptors are lazy.

4.20.1. execution::transfer

execution::sender auto transfer(
    execution::sender auto input,
    execution::scheduler auto scheduler
);

Returns a sender describing the transition from the execution agent of the input sender to the execution agent of the target scheduler. See § 4.6 Execution resource transitions are explicit.

execution::scheduler auto cpu_sched = get_system_thread_pool().scheduler();
execution::scheduler auto gpu_sched = cuda::scheduler();

execution::sender auto cpu_task = execution::schedule(cpu_sched);
// cpu_task describes the creation of a new task on the system thread pool

execution::sender auto gpu_task = execution::transfer(cpu_task, gpu_sched);
// gpu_task describes the transition of the task graph described by cpu_task to the gpu

4.20.2. execution::then

execution::sender auto then(
    execution::sender auto input,
    std::invocable<values-sent-by(input)...> function
);

then returns a sender describing the task graph described by the input sender, with an added node of invoking the provided function with the values sent by the input sender as arguments.

then is guaranteed to not begin executing function until the returned sender is started.

execution::sender auto input = get_input();
execution::sender auto snd = execution::then(input, [](auto... args) {
    std::print(args...);
});
// snd describes the work described by pred
// followed by printing all of the values sent by pred