Detlef Vollmann <dv@vollmann.ch>
Howard Hinnant <howard.hinnant@gmail.com>
Anthony Williams <anthony@justsoftwaresolutions.co.uk>

N2627: An Asynchronous Future Value (revised)

'WG21 resolves that for this revision of the C++ standard (aka "C++0x") the scope of concurrency extensions shall be constrained as follows:

• Include a memory model, atomic operations, threads, locks, condition variables, and asynchronous future values.
• Exclude thread pools, task launching, and reader-writer locks.'

• N2094 Howard Hinnant: Multithreading API for C++0X - A Layered Approach,
• N2185 Peter Dimov: Proposed Text for Parallel Task Execution,
• N2276 Anthony Williams: Thread Pools and Futures.

State of Proposal

This paper is a revision of N2561 and is the result of quite some discussion among the authors and also with a number of other people commenting.

Anthony Williams has implemented a prototype for an earlier version of this propsal, available at http://www.justsoftwaresolutions.co.uk/threading/updated-implementation-of-c++-futures.html.

The authors would like to thank all who contributed comments to the discussion about this proposal:
Peter Dimov
Jeffrey Yasskin
Lawrence Crowl
Hans Boehm
Herb Sutter
Bjarne Stroustrup

Introduction

The three papers that serve as base for the original paper N2561 all propose essentially the same machanism for transferring results from one thread to the other, but differ in some minor aspects. This paper is a joint effort to provide a proposal to implement the "concurrency compromise".
N2094 provides some background information on the design decisions though this proposal differs from N2094 in naming and structuring.
N2276 provides proposed wording, but this proposal again is a bit differently structured.

The mechanism here and its definition is kept minimal. A consequence of this is that little additions would make it more useful for one purpose. But such additions would probably disallow other additions to make it more useful for other purposes.
So the only purpose this proposal explicitely supports is to capture the result (a return value or an exception) of a function running in a thread in something called promise and provide something called future to wait for the result and retrieve it.

Overview

Building Blocks

This paper proposes a kind of return buffer that takes a value (or an exception) in one (sub-)thread and provides the value in another (controlling) thread. This buffer provides essentially two interfaces:

• an interface to assign a value as class promise and
• an interface to wait for, query and retrieve the value (or exception) from the buffer as classes unique_future and shared_future.

Internally, a promise and its associated future(s) share a common value buffer, called associated state. Multiple shared_futures can share the same associated state.

While a unique_future provides move semantics where the value (or exception) can be retrieved only once, the shared_future provides copy semantics where the value can be retrieved arbitrarily often.

A typical procedure for working with promises and futures looks like:

1. control thread creates a promise,
2. control thread gets associated future from promise,
3. control thread starts sub-thread,
4. sub-thread calls actual function and assigns the return value to the promise,
5. control thread waits for future to become ready,
6. control thread retrieves value from future.

Also proposed is a packaged_task that wraps one callable object and provides another one that can be started in its own thread and assigns the return value (or exception) to a return buffer that can be accessed through one of the future classes.

With a packaged_task a typical procedure looks like:

1. control thread creates a packaged_task with a callable object,
2. control thread gets associated future from packaged_task,
3. control thread starts sub-thread, which invokes the packaged_task,
4. packaged_task calls the callable function and assigns the return value,
5. control thread waits for future to become ready,
6. control thread retrieves value from future.

Omissions

There are some interfaces missing from this proposal that were in former proposals, and it's worth to say that explicitely:

assignment / default construction:

With assignment a future is not thread safe any more in the sense that the same future (not different shared_futures sharing the same internal buffer) could be modified in different threads. Whether such kind of thread safety should be provided is an open question, but to avoid any final decision assignment is left out from this proposal.

unique_future::was_moved():

was_moved() might have consequences for the exception safety of get(). But note that the exception safety of unique_future::get() is not guaranteed here to allow for possible later addition of was_moved().

try_get()/timed_get():

These functions have different signatures for normal value types, references and void.

Proposed Text

namespace std
{
    template <typename R> class unique_future;

    template <typename R> class shared_future;

    template <typename R> class promise;

    template <typename R> class packaged_task;
}

Exception Classes

namespace std
{
    class broken_promise:
        public std::logic_error
    {
    public:
        broken_promise();
    };
    class future_already_retrieved:
        public std::logic_error
    {
    public:
        future_already_retrieved();
    };
    class promise_already_satisfied:
        public std::logic_error
    {
    public:
        promise_already_satisfied();
    };

    class task_already_started:
        public std::logic_error
    {
    public:
        task_already_started();
    };
    class task_moved:
        public std::logic_error
    {
    public:
        task_moved();
    };
}

Class template unique_future

namespace std
{
template <typename R>
class unique_future
{
public:
    unique_future(unique_future &&);
    unique_future(unique_future const & rhs) = delete;

    ~unique_future();

    unique_future& operator=(unique_future const & rhs) = delete;

    // retrieving the value
    R&& get();

    // functions to check state, and wait for ready
    bool is_ready() const;
    bool has_exception() const;
    bool has_value() const;

    void wait() const;
    bool timed_wait(some_rel_time rel_time) const;
    bool timed_wait_until(some_abs_time abs_time) const;
};
}

    unique_future(const unique_future&& rhs);

Effects: MoveConstructs a unique_future whose associated state is the same as the state of rhs before. The associated state is the state and the (possibly not yet evaluated) result (value or exception) associated with the promise or packaged_task that provided the original future.

Postconditions: rhs can be safely destroyed.

    ~unique_future();

Effects: destroys *this and its associated state if no other object refers to that.

    R&& get();
    R& unique_future<R&>::get();
    void unique_future<void>::get();

Effects: Retrieves the value stored in the associated state.

Sychronization: If *this is associated with a promise, the completion of set_value() or set_exception() to that promise happens before ([intro.multithread]) get() returns.
If *this is associated with a packaged_task, the completion of the call to the operator()() happens before ([intro.multithread]) get() returns.

Returns: If the result type R is a reference, returns the stored reference. If R is void, there is no return value. Otherwise, returns an rvalue-reference to the value stored in the asynchronous result.

Throws: the stored exception, if an exception was stored and not retrieved before.

[Note: The return value of is_ready is unspecified after a call to get(). -- end note]

[Note: It is unspecified what happens when get() is called a second time on the same unique_future. -- end note]

    bool is_ready() const;

Returns: true if the associated state holds a value or an exception ready for retrieval.

    bool has_exception() const;

Returns: true if is_ready() == true and the associated state contains an exception, false otherwise.

    bool has_value() const;

Returns: true if is_ready() == true and the associated state contains a value, false otherwise.

    void wait() const;

Effects: Blocks until *this is ready.

Sychronization: If *this is associated with a promise, the completion of set_value() or set_exception() to that promise happens before ([intro.multithread]) get() returns.
If *this is associated with a packaged_task, the completion of the call to the operator()() happens before ([intro.multithread]) get() returns.

Postconditions: is_ready() == true.

    bool timed_wait(some_rel_time rel_time) const;

Effects: Blocks until *this is ready or until rel_time elapsed.

Returns: true if the function returns because *this is ready, false otherwise.

Postconditions: is_ready() equals the return value.

    bool timed_wait_until(some_abs_time abs_time);

Same as timed_wait(), except that it blocks until abs_time is reached if the associated state is not ready.

[Editorial note: The names and signatures of timed_wait() and timed_wait_until() should mirror those of the respective member functions of condition_variable [thread.condition.condvar].

Class template shared_future

namespace std
{
template <typename R>
class shared_future
{
public:
    shared_future(shared_future const & rhs);

    shared_future(unique_future<R> &&);
    shared_future(const unique_future<R> &) = delete;

    ~shared_future();

    shared_future & operator=(shared_future const & rhs) = delete;

    // retrieving the value
    R const & get() const;

    // functions to check state, and wait for ready
    bool is_ready() const;
    bool has_exception() const;
    bool has_value() const;

    void wait() const;
    bool timed_wait(some_rel_time rel_time) const;
    bool timed_wait_until(some_abs_time abs_time) const;
};
}

    shared_future(const shared_future& rhs);

Effects: CopyConstructs a shared_future whose associated state is the same as the state of rhs before. The associated state is the state and the (possibly not yet evaluated) result (value or exception) associated with the promise or packaged_task that provided the original future.

    shared_future(const unique_future&& rhs);

Effects: MoveConstructs a shared_future whose associated state is the same as the state of rhs before.

Postconditions: rhs can be safely destroyed.

    ~shared_future();

Effects: destroys *this and its associated state if no other object refers to that.

    R const & get();
    R& shared_future<R&>::get();
    void shared_future<void>::get();

Effects: retrieves the value stored in the associated state.

Sychronization: If *this is associated with a promise, the completion of set_value() or set_exception() to that promise happens before ([intro.multithread]) get() returns.
If *this is associated with a packaged_task, the completion of the call to the operator()() happens before ([intro.multithread]) get() returns.

Returns: If the result type R is a reference, returns the stored reference. If R is void, there is no return value. Otherwise, returns a const reference to the value stored in the asynchronous result.

Throws: the stored exception, if an exception was stored and not retrieved before.

    bool is_ready() const;

Returns: true if the associated state holds a value or an exception ready for retrieval.

    bool has_exception() const;

Returns: true if is_ready() == true and the associated state contains an exception, false otherwise.

    bool has_value() const;

Returns: true if is_ready() == true and the associated state contains a value, false otherwise.

    void wait() const;

Effects: Blocks until *this is ready.

Sychronization: If *this is associated with a promise, the completion of set_value() or set_exception() to that promise happens before ([intro.multithread]) get() returns.
If *this is associated with a packaged_task, the completion of the call to the operator()() happens before ([intro.multithread]) get() returns.

Postconditions: is_ready() == true.

    bool timed_wait(some_rel_time rel_time) const;

Effects: Blocks until *this is ready or until rel_time elapsed.

Returns: true if the functions returns because *this is ready, false otherwise.

Postconditions: is_ready() equals the return value.

    bool timed_wait_until(some_abs_time abs_time);

Same as timed_wait(), except that it blocks until abs_time is reached if the associated state is not ready.

[Editorial note: The names and signatures of timed_wait() and timed_wait_until() should mirror those of the respective member functions of condition_variable [thread.condition.condvar].

Class template promise

namespace std
{
template <typename R>
class promise
{
public:
    promise();
    template <class Allocator>
        promise(allocator_arg_t, Allocator const A&);
    promise(promise && rhs);
    template <class Allocator>
        promise(allocator_arg_t, Allocator const A&,
                promise & rhs);
    promise(promise const & rhs) = delete;
    ~promise();

    // Assignment
    promise & operator=(promise && rhs);
    promise & operator=(promise const & rhs) = delete;
    void swap(promise& other);

    // Result retrieval
    unique_future<R> get_future();

    void set_value(R const & r);
    void set_value(R && r);
    void set_exception(exception_ptr p);
};

template <typename R, class Alloc>
    struct uses_allocator&promise<R>, Alloc>;

template <typename R>
    struct constructible_with_allocator_prefix<promise<T2>>;
}

template <typename R, class Alloc>
    struct uses_allocator&promise<R>, Alloc>
     : true_type { };

Requires: Alloc shall be an Allocator ([allocator.requirements] 20.1.2)

Remarks: Specialization of this trait informs other library components that promise can be constructed with an allocator, even though it does not have an allocator_type associated type.

template <typename R>
    struct constructible_with_allocator_prefix<promise<T2>>
     : true_type { };

Remarks: Specialization of this trait informs other library components that a promise can always be constructed with an allocator prefix argument.

    promise();
    template <class Allocator>
        promise(allocator_arg_t, Allocator const &a);

Effects: constructs a promise and an associated state, using a if given for allocating the memory for the associated state.

    promise(promise && rhs);
    template <class Allocator>
        promise(allocator_arg_t, Allocator const A&,
                promise & rhs);

Effects: MoveConstructs a promise whose associated state is the same as the state of rhs before.

Postcondition: rhs has no associated state.

    ~promise();

Effects: destroys *this and its associated state if no other object refers to it. If another object refers to the associated state and that state is not ready, sets that state to ready and stores a broken_promise exception as result.

    promise & operator=(promise && rhs);

Effects: MoveAssigns its associated state to rhs.

Postcondition: *this has no associated state.

Returns: *this.

Throws: nothing.

    void swap(promise& other);

Effects: swap(*this, other);

Throws: nothing.

    unique_future<R> get_future();

Returns: a unique_future<R> with the same associated state as *this.

Throws: future_already_retrieved if *this has no associated state.

    void set_value(R const & r);
    void set_value(R && r);
    void promise<R&>::set_value(R & r);
    void promise<void>::set_value();

Effects: stores r in the associated state and sets that state to ready. Any blocking waits on the associated state are woken up.

Throws: promise_already_satisfied if its associated state is already ready.

    void set_exception(exception_ptr p);

Effects: stores p in the associated state sets that state to ready. Any blocking waits on the associated state are woken up.

Throws: promise_already_satisfied if its associated state is already ready.

Class template packaged_task

namespace std
{
template<typename R>
class packaged_task
{
public:
    // construction and destruction
    template <class F>
        explicit packaged_task(F const& f);
    template <class F, class Allocator>
        packaged_task(allocator_arg_t, Allocator a, F const& f);

    template <class F>
        explicit packaged_task(F&& f);
    template <class F, class Allocator>
        packaged_task(allocator_arg_t, Allocator a, F&& f);

    explicit packaged_task(R(*f)());
    template <class Allocator>
        packaged_task(allocator_arg_t, Allocator a, R(*f)());

    packaged_task(packaged_task&& other);
    template <class Allocator>
        packaged_task(allocator_arg_t, Allocator a,
                      packaged_task&& other);

    packaged_task(packaged_task&) = delete;
    ~packaged_task();

    // assignment
    packaged_task& operator=(packaged_task&& other);
    packaged_task& operator=(packaged_task&) = delete;

    void swap(packaged_task& other);

    // result retrieval
    unique_future<R> get_future();

    // execution
    void operator()();
};

template <typename R, class Alloc>
    struct uses_allocator&packaged_task<R>, Alloc>;

template <typename R>
    struct constructible_with_allocator_prefix<packaged_task<T2>>;
}

template <typename R, class Alloc>
    struct uses_allocator&packaged_task<R>, Alloc>
     : true_type { };

Requires: Alloc shall be an Allocator ([allocator.requirements] 20.1.2)

Remarks: Specialization of this trait informs other library components that packaged_task can be constructed with an allocator, even though it does not have an allocator_type associated type.

template <typename R>
    struct constructible_with_allocator_prefix<packaged_task<T2>>
     : true_type { };

Remarks: Specialization of this trait informs other library components that a packaged_task can always be constructed with an allocator prefix argument.

    template <class F>
        explicit packaged_task(F const& f);
    template <class F, class Allocator>
        packaged_task(allocator_arg_t, Allocator a, F const& f);

    template <class F>
        explicit packaged_task(F&& f);
    template <class F, class Allocator>
        packaged_task(allocator_arg_t, Allocator a, F&& f);

    explicit packaged_task(R(*f)());
    template <class Allocator>
        packaged_task(allocator_arg_t, Allocator a, R(*f)());

Requires: f() is a valid expression with a return type convertible to R. Invoking a copy of f shall behave the same as invoking f.

Effects: constructs a packaged_task with a copy of f and a new associated state. Any dynamic memory allocated is allocated through a if given.

    packaged_task(packaged_task&& other);
    template <class Allocator>
        packaged_task(allocator_arg_t, Allocator a,
                      packaged_task&& other);

Effects: MoveConstructs a packaged_task whose associated state and function object is the same as the state of rhs before.

Postcondition: rhs has no associated state.

    ~packaged_task();

Effects: destroys *this and its associated state if no other object refers to it. If another object refers to the associated state and that state is not ready, sets that state to ready and stores a broken_promise exception as result.

Throws: nothing.

    packaged_task& operator=(packaged_task&& other);

Effects: MoveAssigns its associated state to rhs.

Postcondition: *this has no associated state.

Returns: *this.

Throws: nothing.

    void swap(packaged_task& other);

Effects: swap(*this, other);

Throws: nothing.

    unique_future<R> get_future();

Returns: a unique_future<R> with the same associated state as *this.

Throws: future_already_retrieved if *this has no associated state.

    void operator()();

Effects: invokes the stored function object, stores the result in the associated state and sets that state to ready. Any blocking waits on the associated state are woken up.

Throws: task_moved if *this has no associated state. task_already_started if the function was already called.