C++
coroutine

C++コルーチン拡張メモ

次期標準 C++20 に向けて導入が検討されている「コルーチン(Coroutine)」のお勉強メモ。

2018年4月現在、プログラミング言語C++の正式機能としてではなく、コルーチン拡張(Coroutines TS)として仕様定義される。Clang 5以降でサポート(要-fcoroutines-tsオプション)。


遅延実行

https://wandbox.org/permlink/v3DCYQ97szuIy6kk


C++11

#include <future>

#include <iostream>

// 通常関数の定義
int AtLtUaE()
{
std::cout << "answer to life the universe and everything" << std::endl;
return 42;
}

int main()
{
// 通常関数AtLtUaEを遅延実行する
auto ftr = std::async(std::launch::deferred, AtLtUaE);

// (その他の処理)
std::cout << "(other stuff)" << std::endl;

// 関数の遅延実行&結果取得
int answer = ftr.get();
std::cout << "answer=" << answer << std::endl;
}


https://wandbox.org/permlink/mqGsm6BRVpXmR6Jz


CoroutinesTS

#include <iostream>

#include <experimental/coroutine> // CoroutinesTS

// コルーチンの戻り値my_future型
struct my_future {
// コルーチン内部で利用されるpromise_type型
struct promise_type {
int result_ = 0;
auto get_return_object() { return my_future{handle_type::from_promise(*this)}; }
std::experimental::suspend_always initial_suspend() { return {}; }
std::experimental::suspend_always final_suspend() { return {}; }
void return_value(int value) { result_ = value; }
void unhandled_exception() { std::terminate(); }
};
using handle_type = std::experimental::coroutine_handle<promise_type>;

explicit my_future(handle_type h)
: coro_(h) {}
my_future(const my_future&) = delete;
my_future(my_future&& rhs)
: coro_(rhs.coro_) { rhs.coro_ = nullptr; }
~my_future()
{
if (coro_)
coro_.destroy();
}

int get()
{
// コルーチン完了までコルーチン側の進行を促す
while (!coro_.done()) {
coro_.resume();
}
return coro_.promise().result_;
}

handle_type coro_;
};

// コルーチン(coroutine)定義
my_future AtLtUaE()
{
std::cout << "answer to life the universe and everything" << std::endl;
co_return 42;
// return ではなく co_return キーワードを利用することで、
// 通常関数ではなくコルーチン(coroutine)として解釈される。
}

int main()
{
// コルーチンを開始する
auto ftr = AtLtUaE();
// promise_type::initial_suspendがsuspend_alwaysを返すため、
// コルーチン本体実行は開始されず(suspend状態)後続処理が実行される。

// (その他の処理)
std::cout << "(other stuff)" << std::endl;

// コルーチン完了待ち&結果取得
int answer = ftr.get();
std::cout << "answer=" << answer << std::endl;
}


実行結果:

(other stuff)

answer to life the universe and everything
answer=42


ジェネレータ(1)

https://wandbox.org/permlink/QdmuJQyztvF3BqDV


CoroutinesTS

#include <iostream>

#include <experimental/coroutine> // CoroutinesTS

// コルーチンの戻り値generator型
struct generator {
// コルーチン内部で利用されるpromise_type型
struct promise_type {
int value_ = 0;
auto get_return_object() { return generator{handle_type::from_promise(*this)}; }
std::experimental::suspend_always initial_suspend() { return {}; }
std::experimental::suspend_always final_suspend() { return {}; }
std::experimental::suspend_always yield_value(int value)
{
value_ = value;
// co_yield文のたびにコルーチン(ジェネレータ)処理をsuspendし、
// ジェネレータ利用側からの値取得current_valueと処理進行を促す。
return {};
}
void return_void() {}
void unhandled_exception() { std::terminate(); }
};
using handle_type = std::experimental::coroutine_handle<promise_type>;

explicit generator(handle_type h)
: coro_(h) {}
generator(const generator&) = delete;
generator(generator&& rhs)
: coro_(rhs.coro_) { rhs.coro_ = nullptr; }
~generator()
{
if (coro_)
coro_.destroy();
}

int current_value() {
return coro_.promise().value_;
}

bool move_next() {
// コルーチン処理を次のco_yield/co_returnまで進める
coro_.resume();
// 本プログラムの場合、ジェネレータはco_returnを呼び出さないため
// coro_.done()は常にfalseとなり、本関数の戻り値は常にtrueとなる。
return !coro_.done();
}

handle_type coro_;
};

// コルーチン(coroutine)定義
generator fibonacci()
{
int a = 1, b = 1;
co_yield a;
while (true) {
co_yield a;
int t = a;
a += b;
b = t;
}
// 無限ループ構造となっているが、co_yieldキーワードによって
// 値を1回生成するたびにコルーチン処理をsuspendしている。

// 仕様上はコルーチン末尾到達時は暗黙にco_return;が呼ばれるが、
// 本コルーチン実装では無限ループ構造により到達することはない。
}

int main()
{
// コルーチン(ジェネレータ)を開始する
auto g = fibonacci();
// promise_type::initial_suspendがsuspend_alwaysを返すため、
// コルーチン本体実行は開始されず(suspend状態)後続処理が実行される。

while ( g.move_next() ) {
// コルーチン(ジェネレータ)処理を次のco_yieldまで1ステップ進める。
// 本プログラムの場合、ジェネレータはco_returnを呼び出さないため
// move_next()関数呼び出しは常に値true(処理継続)を返す。
int n = g.current_value();
if (100 < n)
break;
std::cout << n << " ";
}
}


実行結果:

1 1 2 3 5 8 13 21 34 55 89


ジェネレータ(2)

https://wandbox.org/permlink/OuHWIATnpsyxdKhg


CoroutinesTS

#include <iostream>

#include <experimental/coroutine> // CoroutinesTS

// コルーチンの戻り値generator型
struct generator {
// コルーチン内部で利用されるpromise_type型
struct promise_type {
int value_ = 0;
auto get_return_object() { return generator{handle_type::from_promise(*this)}; }
std::experimental::suspend_never initial_suspend() { return {}; }
std::experimental::suspend_always final_suspend() { return {}; }
std::experimental::suspend_always yield_value(int value)
{
value_ = value;
// co_yield文のたびにコルーチン(ジェネレータ)処理をsuspendし、
// ジェネレータ利用側からのiterator経由値取得と処理進行を促す。
return {};
}
void return_void() {}
void unhandled_exception() { std::terminate(); }
};
using handle_type = std::experimental::coroutine_handle<promise_type>;

explicit generator(handle_type h)
: coro_(h) {}
generator(const generator&) = delete;
generator(generator&& rhs)
: coro_(rhs.coro_) { rhs.coro_ = nullptr; }
~generator()
{
if (coro_)
coro_.destroy();
}

// range-based for構文サポート用イテレータ
struct iterator {
generator* owner_;
iterator& operator++()
{
// イテレータの前置インクリメント演算子呼び出し時に、
// コルーチン(ジェネレータ)の処理を1ステップ進める。
if (!owner_->coro_.done())
owner_->coro_.resume();
return *this;
}
int operator*()
{
return owner_->coro_.promise().value_;
}
bool operator!=(const iterator&) const
{
return (!owner_ || !owner_->coro_.done());
}
};

iterator begin() { return {this}; }
iterator end() { return {nullptr}; }

handle_type coro_;
};

// コルーチン(coroutine)定義
generator gen_range(int minval, int maxval)
{
// promise_type::initial_suspendはsuspend_neverを返すため、
// コルーチン呼び出しによって初回のco_yield呼び出しまで実行される。
for (int i = minval; i <= maxval; i++)
co_yield i;

// コルーチン末尾到達時は暗黙にco_return;が呼ばれる。
}

int main()
{
for (auto n : gen_range(1, 10)) {
std::cout << n << " ";
}
}


実行結果:

1 2 3 4 5 6 7 8 9 10 

最適化:https://godbolt.org/g/MFx3w4


ジェネレータ(3)

https://wandbox.org/permlink/LkIT42bSX4PSlve5


CoroutinesTS

#include <iostream>

#include <experimental/coroutine> // CoroutinesTS

// コルーチンの戻り値generator型
struct generator {
// コルーチン内部で利用されるpromise_type型
struct promise_type {
double send_val_ = 0;
double yield_val_ = 0;
auto get_return_object() { return generator{handle_type::from_promise(*this)}; }
std::experimental::suspend_never initial_suspend() { return {}; }
std::experimental::suspend_always final_suspend() { return {}; }
auto yield_value(double value)
{
yield_val_ = value;
// await_resumeメンバ関数を除いてsuspend_alwaysと同じ動作をする型
// await_resumeメンバ関数の戻り値がco_yield式の評価結果となる。
struct awaiter {
promise_type* self_;
bool await_ready() { return false; }
void await_suspend(std::experimental::coroutine_handle<>) {}
auto await_resume() { return self_->send_val_; }
};
// co_yield式のたびにコルーチン(ジェネレータ)処理をsuspendし、
// ジェネレータ利用側への値返却(next戻り値)と処理進行を促す。
// またco_yield式評価結果としてnext関数への指定値を返す。
return awaiter{this};
}
void return_void() {}
void unhandled_exception() { std::terminate(); }
};
using handle_type = std::experimental::coroutine_handle<promise_type>;

explicit generator(handle_type h)
: coro_(h) {}
generator(const generator&) = delete;
generator(generator&& rhs)
: coro_(rhs.coro_) { rhs.coro_ = nullptr; }
~generator()
{
if (coro_)
coro_.destroy();
}

double send(double value) {
coro_.promise().send_val_ = value;
if (!coro_.done())
coro_.resume();
return coro_.promise().yield_val_;
}

handle_type coro_;
};

// コルーチン(coroutine)定義
generator average()
{
double acc = co_yield 0;
size_t num = 1;
for (;;) {
acc += co_yield (acc / num);
num += 1;
}
}

int main()
{
auto g = average();
std::cout << g.send(10) << " ";
std::cout << g.send(20) << " ";
std::cout << g.send(5) << " ";
std::cout << g.send(15) << " ";
}


出力結果:

10 15 11.6667 12.5

最適化:https://godbolt.org/g/iS5dw8


非同期処理

https://wandbox.org/permlink/rPKkxpz2oWuv21mx


CoroutinesTS

#include <future>

#include <iostream>
#include <thread>
#include <experimental/coroutine> // CoroutinesTS

// コルーチンの戻り値my_future型
struct my_future {
// コルーチン内部で利用されるpromise_type型
struct promise_type {
std::promise<int> promise_;
auto get_return_object()
{
// promise/futureペアとコルーチンハンドラを生成し、
// promise_type型からmy_future型を構築する。
return my_future{promise_.get_future(), handle_type::from_promise(*this)};
}
std::experimental::suspend_never initial_suspend() { return {}; }
std::experimental::suspend_always final_suspend() { return {}; }
void return_value(int value) { promise_.set_value(value); }
void unhandled_exception() { std::terminate(); }

// コルーチン内の co_await <duration>待機処理 をサポート
template <class Rep, class Period>
auto await_transform(const std::chrono::duration<Rep, Period>& d)
{
struct awaiter {
std::chrono::duration<Rep, Period> d_;
bool await_ready() { return false; }
void await_suspend(handle_type h)
{
// 指定時間経過後にコルーチンをresumeするワーカスレッドを生成。
std::thread([h, d=d_]() mutable {
std::this_thread::sleep_for(d);
if (!h.done())
h.resume();
}).detach();
// 本プログラムでは簡単のためワーカスレッドを毎回生成しているが、
// より効率的な実装としてスレッドプール方式などが考えられる。
// 非同期I/Oを行う場合も同様にresume操作を行うスレッドが必要。
}
void await_resume() {}
};
return awaiter{d};
}
};
using handle_type = std::experimental::coroutine_handle<promise_type>;

explicit my_future(std::future<int> f, handle_type h)
: future_(std::move(f)), coro_(h) {}
my_future(const my_future&) = delete;
my_future(my_future&& rhs)
: future_(std::move(rhs.future_)), coro_(rhs.coro_) { rhs.coro_ = nullptr; }
~my_future()
{
if (coro_)
coro_.destroy();
}

int get()
{
// promise_type::initial_suspendがsuspend_neverを返すため、
// コルーチンはco_await待機中または実行完了状態のいずれかにある。
return future_.get();
}

std::future<int> future_;
handle_type coro_;
};

// コルーチン(coroutine)定義
my_future async_AtLtUaE()
{
using namespace std::chrono_literals;
std::cout << "answer to life the universe and everything" << std::endl;
co_await 2s;
std::cout << "." << std::flush;
co_await 2s;
std::cout << "." << std::flush;
co_await 2s;
std::cout << "." << std::endl;
co_return 42;
// co_await式の前後で実行スレッドが切り替わることに注意。
// 本コルーチンの処理は4個のスレッドにより順次実行されることになる。
// (1個目のco_wait式まではメインスレッドで実行される)
}

// コルーチン(coroutine)定義
my_future sync_AtLtUaE()
{
std::cout << "(prepare)" << std::endl;

auto ftr = async_AtLtUaE();

std::cout << "(processing)" << std::endl;

co_return ftr.get();
}

int main()
{
auto ftr = sync_AtLtUaE();

std::cout << "(other stuff)" << std::endl;

int answer = ftr.get();
std::cout << "answer=" << answer << std::endl;
}


実行結果:

(prepare)

answer to life the universe and everything
(processing)
...
(other stuff)
answer=42


Optionalモナド風

https://wandbox.org/permlink/rHpvhyar77P493Ij


CoroutinesTS

#include <optional>

#include <iostream>
#include <experimental/coroutine> // CoroutinesTS

template <typename T>
struct coro_optional;

// コルーチン内部で利用されるoptional_promise型
template <typename T>
struct optional_promise {
std::optional<T> value_;

coro_optional<T> get_return_object();
std::experimental::suspend_never initial_suspend() { return {}; }
std::experimental::suspend_always final_suspend() { return {}; }
void return_value(T value) { value_ = value; }
void return_value(std::nullopt_t) { value_ = std::nullopt; }
void unhandled_exception() { std::terminate(); }

// コルーチン内の co_await optional<T> 式 をサポート
auto await_transform(std::optional<T> opt)
{
// ここではco_await式を待機処理ではなく、Optionalモナド的な挙動
// a) 有効値を保持しているときは、同値を返してコルーチンを継続実行する
// b) 無効値(nullopt)を保持しているときは、コルーチンを継続しない
// の実現のために利用する。
struct awaiter {
std::optional<T> opt_;
// a) await_ready==trueのとき、コルーチンはsuspendされずに
// await_resumeの戻り値がco_await式の評価結果となる。
// b) await_ready==falseのとき、コルーチンはsuspendされて
// await_suspendが呼び出される。同関数は何も処理を行わないため
// susupend状態が維持されたまま、最終的に破棄(destroy)される。
bool await_ready() { return opt_.has_value(); }
void await_suspend(std::experimental::coroutine_handle<>) {}
T await_resume() { return std::move(opt_.value()); }
};
return awaiter{std::move(opt)};
}
};

// コルーチンの(内部的)戻り値coro_optional型
template <typename T>
struct coro_optional {
using handle_type = std::experimental::coroutine_handle<optional_promise<T>>;

explicit coro_optional(handle_type h)
: coro_(h) {}
coro_optional(const coro_optional&) = delete;
coro_optional(coro_optional&& rhs)
: coro_(rhs.coro_) { rhs.coro_ = nullptr; }
~coro_optional()
{
if (coro_)
coro_.destroy();
}

// コルーチンの(外部的)戻り値型optional<T>への型変換を提供
operator std::optional<T>() const { return {coro_.promise().value_}; }

handle_type coro_;
};

template <typename T>
inline
coro_optional<T> optional_promise<T>::get_return_object()
{
using handle_type = std::experimental::coroutine_handle<optional_promise<T>>;
return coro_optional<T>{ handle_type::from_promise(*this) };
}

// std::experimental::coroutine_traitsトレイトの特殊化によって、
// 戻り値型std::optional<T>を持つ関数をコルーチンとしてアダプトする。
namespace std::experimental {
template <typename T, typename... ArgTypes>
struct coroutine_traits<std::optional<T>, ArgTypes...> {
// 該当コルーチンの(内部的)戻り値型はoptional_promise<T>となり、
// 最終的にoperator std::optional<T>ユーザ定義型変換を適用する。
using promise_type = optional_promise<T>;
};
}

// コルーチン(coroutine)定義: r = x - y
std::optional<int> minus(int x, int y)
{
if (0 < x && 0 < y && x > y)
co_return (x - y);
else
co_return std::nullopt;
}

// コルーチン(coroutine)定義: r = x / y
std::optional<int> division(int x, int y)
{
if (0 < x && 0 < y && (x % y) == 0)
co_return (x / y);
else
co_return std::nullopt;
}

// コルーチン(coroutine)定義: r = (x - 5) / y
std::optional<int> calc(int x, int y)
{
// auto a = co_await minus(x, 5);
// auto b = co_await division(a, y);
// co_return b;
co_return (co_await division(co_await minus(x, 5), y));

// co_await optional<int>部分式では、optionalがnulloptのとき
// それ以降の処理は継続せず、本コルーチンの戻り値もnulloptとなる。
}

int main()
{
auto dump_opt = [](auto&& opt) {
if (opt)
std::cout << opt.value() << std::endl;
else
std::cout << "(nullopt)" << std::endl;
};

// 自然数の範囲内のみで (x - 5) / y を計算する
dump_opt( calc(11, 3) ); // (11 - 5) / 3 == 2
dump_opt( calc(7, 3) ); // (7 - 5) / 3 == NA
dump_opt( calc(4, 3) ); // (4 - 5) == NA
}


実行結果:

2

(nullopt)
(nullopt)


おまけ: Sleep Sort

https://gist.github.com/yohhoy/a5ec6d4aeeb4c60d3e4f3adfd1df9ebf

https://wandbox.org/permlink/5WhRC2ylx9P9QUwQ

Alt. ver: https://gist.github.com/yohhoy/ecdf00cb2a7852929954a1e6c79bdc25


WG21