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

N2561: An Asynchronous Future Value

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

Introduction

The three papers that serve as base for this paper 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.

State of Proposal

This paper is not a finished proposal. It is meant to serve as a base for discussion. The intent of the authors is to have this discussion on the reflector and provide a finished proposal for the pre-France mailing.
So, this paper provides hopefully enough details for people to know what can be done with this facility, and what can't be done, so that they can form an opinion whether they like this proposal the way it is or whether they would like to see changes to specific parts.

Overview

Motivating Example

Here's a small program to demonstrate how a task is distributed to a number of detached threads and how the results can be collected without explicit locking.

// simple example on usage of future

#include <thread>
#include <future>

struct MBLine
{
    // ...
};

void displayLine(MBLine const &);

struct ComputeMBLine
{
    ComputeMBLine(double y_, double x1_, double x2_)
        : y(y_), x1(x1_), x2(x2_)
    {}

    MBLine operator()()
    {
        MBLine myLine;
        // compute the line
        // ...

        return myLine;
    }

    double y, x1, x2;
};

int main()
{
    std::unique_future<MBLine> set[400];
    double y = 2.0;

    for (int i = 0; i != 400; ++i, y -= 0.01)
    {
        std::packaged_task<MBLine> t(ComputeMBLine(y, -2.0, 2.0));
        set[i] = t.get_future();
        std::thread(std::move(t)).detach();
    }

    bool done;
    do
    {
        done = true;
        for (int i = 0; i != 400; ++i)
        {
            MBLine l;
            if (!set[i].was_moved())
            {
                if (set[i].try_move(l) == std::unique_future<MBLine>::ready)
                {
                    displayLine(l);
                } else {
                    done = false;
                }
            }
        }
        // do some other work ...
    } while (!done);

    return 0;
}

This example uses a packaged_task to help to associate a future with a thread. Another option would have been to use a promise directly as a parameter to the ctor of ComputeMBLine.

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.

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.

Some Proposed Text

namespace std
{

    class future_unitialized : public logic_error { };
    class future_moved : public logic_error { };

    template <typename R> class unique_future;
    template <> class unique_future<void>;

    template <typename R> class shared_future;
    template <> class shared_future<void>;

    template <typename R> class promise;
    template <> class promise<void>;
    template <typename R> class promise<R&>;

    template <typename R> class packaged_task;
}

Class template unique_future

template <typename R>
class unique_future
{
public:
    enum state { uninitialized, waiting, ready, moved };

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

    ~unique_future();

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

    // retrieving the value
    R move();
    bool try_move(R &);
    bool timed_move(R &, some_rel_time rel_time);
    bool timed_move_until(R &, some_abs_time abs_time);

    // functions to check state, and wait for ready
    state get_state() const;

    bool is_ready() const;
    bool has_exception() const;
    bool has_value() const;
    bool was_moved() 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();

Effects: constructs a unique_future whose associated state holds no value, no exception and a null thread handle.

Postconditions: get_state() == uninitialized.

    unique_future(const unique_future&& rhs);

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

Postconditions: rhs.get_state() == uninitialized.

    ~unique_future();

Effects: destroys *this and its associated state if no other instance refers to it.

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

Effects: MoveAssigns rhs to *this whose associated state is the same as the state of rhs before.

Returns: *this.

Postconditions: rhs.get_state() == uninitialized.

    R move();

Effects: Retrieves the value stored in the associated promise or the return value of the callable object given to the constructor of the associated packaged_task.

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

Returns: the moved value.

Postconditions: get_state() == moved if get_state() == waiting on entry.

Throws:

• the stored exception, if an exception was stored and not retrieved before.
• an exception of type future_unitialized if get_state() == uninitialized on entry.
• an exception of type future_moved if get_state() == moved on entry.

    bool try_move(R & val);

Effects: If get_state() is ready on entry retrieves the value stored in the associated promise and moves it into val.

Returns: the value of get_state() on entry.

Postconditions:

• get_state() == moved if a value was moved or a stored exception was propagated,
• get_state() retains its value upon entry otherwise.

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

    bool timed_move(R & val, some_rel_time rel_time);

Effects: Blocks until *this is ready or until rel_time elapsed. If the future gets ready before the waiting time elapsed, the value stored in the associated promise is moved into val.

Returns:

• unitialized or moved if get_state() was uninitialized or moved on entry, respectively,
• waiting if the waiting time elapses before the future becomes ready,
• ready if a value was moved

Postconditions:

• get_state() == moved if a value was moved, or a stored exception was propagated,
• get_state() retains its value upon entry otherwise.

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

    bool timed_move_until(R & val, some_abs_time abs_time);

Same as timed_move, except that it blocks until abs_time is reached if the future is not ready.

    state get_state() const;

Returns:

• uninitialized if the future was not yet initialized.
• waiting if the future was initialized, but there wasn't yet assigned a value or exception to the associated promise,
• ready if the associated promise was assigned a value or exception that wasn't yet moved from the future.
• moved if a value was moved or a stored exception was propagated out of the future.

    bool is_ready() const;

Returns: get_state() == ready.

    bool has_exception() const;

Returns: true if get_state() == ready and the promise or packaged_task associated with the future contains an exception, false otherwise.

    bool has_value() const;

Returns: true if get_state() == ready and the promise or packaged_task associated with the future contains a value, false otherwise.

    bool was_moved() const;

Returns: get_state() == moved.

    void wait() const;

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

Postconditions: get_state() == ready.

Throws:

• an exception of type future_unitialized if get_state() == uninitialized on entry.
• an exception of type future_moved if get_state() == moved on entry.

    bool timed_wait(some_rel_time rel_time) const;

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

Returns:

• unitialized or moved if get_state() was uninitialized or moved on entry, respectively,
• waiting if the waiting time elapses before the future becomes ready,
• ready otherwise.

Postconditions: get_state() 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 future is not ready.

Specialization unique_future<void>

template <>
class unique_future<void>
{
public:
    enum state { uninitialized, waiting, ready, moved };

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

    ~unique_future();

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

    void move();
    bool try_move(void);
    bool timed_move(some_rel_time rel_time);
    bool timed_move_until(some_abs_time abs_time);

    // functions to check state, and wait for ready
    state get_state() const;

    // ???: do these functions throw if the future is not yet initialized?
    bool is_ready() const;
    bool has_exception() const;
    bool has_value() const;
    bool was_moved() const;

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

Class template shared_future

template <typename R>
class shared_future
{
public:
    shared_future();
    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);

    // retrieving the value
    operator R const & () const;
    R const & get() const;
    bool try_get(R &) const;
    bool timed_get(R &, some_rel_time rel_time) const;
    bool timed_get_until(R &, some_abs_time abs_time) 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;
};

Specialization shared_future<void>

template <>
class shared_future<void>
{
public:
    shared_future();
    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);

    // retrieving the value
    void get() const;

    bool try_get() const;
    bool timed_get(some_rel_time rel_time) const;
    bool timed_get_until(some_abs_time abs_time) 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;
};

Class template promise

template <typename R>
class promise
{
public:
    template <class Allocator> explicit promise(Allocator a);
    promise();
    promise(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);
};

Specialization promise<void>

template <>
class promise<void>
{
public:
    template <class Allocator> explicit promise(Allocator a);
    promise();
    promise(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<void> get_future();

    void set_value();
    void set_exception(exception_ptr p);
};

Specialization promise<R &>

template <typename R>
class promise<R &>
{
public:
    template <class Allocator> explicit promise(Allocator a);
    promise();
    promise(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& r);
    void set_exception(exception_ptr p);
};

Class template packaged_task

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

    packaged_task(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()();
};