Document Number: N2561=08-0071
Date: 2008-03-10
Project: Programming Language C++

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

N2561: An Asynchronous Future Value

This is a proposal to implement the "Kona concurrency compromise", i.e. motion SP2 in N2452 and N2453:

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

This proposal tries to merge three papers: And it tries to keep out everything that looks like thread pools or task launching.

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:

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:

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

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:

Postconditions:

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:

    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:

.
    bool timed_wait(some_rel_time rel_time) const;

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

Returns:

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