Coroutines for Go のメモ

Coroutines for Go のメモ

Coroutines for Go を読んでのメモ

コルーチンとはなんぞや?

普通の関数コール(サブルーチン)を解説している。
サブルーチンとの比較でコルーチンを語るため。
以下は関数Fが関数Gを読んだという前提。

サブルーチンは、Gが全部終わってからFに戻り、Fの続きを実行するモデル、である。
1つのスタックのトップにある1つの関数のみが実行状態となる。

コルーチンでは、FとGが異なるスタックになるが、実行状態になるのはサブルーチンと同じく1つの関数である。
Gはすぐには実行状態にならず、Fにより明示的にresumeする必要がある。
GはいつでもFに譲る(yield)ことができ、Gはスタックを維持したまま一時停止する
再度FがGをresumeすることでGは実行を再開する。
Gが最後まで到達した後に、Fがresumeしたらそれは失敗になる必要がある。

コルーチンでは1度に1つのコルーチンのみが実行状態になり、
呼び出し側は異なるスタックで待機する。

以上を踏まえて、他の言語の実装例を見ていこう。

Luaの例

二分木の値をvisitorパターンで列挙するようなケース。
コルーチンを使って、木の構造に関わらず値だけを比較する、という例。
二分木をコルーチンにバインド(coroutine.wrap)できる。

Pythonの例

お題はLuaと一緒。
が、コルーチンとは言えないジェネレーターなので単純な移植では動作しない。
ネストしたyieldが大域脱出をしないことが、Luaとの違い。
(なんか昔これにハマった記憶がよみがえったw)
yield from なんて書き方が増えてるのね。

yield キーワードでそこまでのスタックが保存され、再呼び出しでそれが復元される。
つまりジェネレーターはスタックに呼び出し側と同じものを使っており、分離してない。
フルコルーチンを実装する必要がなくなるが、このような混乱を招く制限となる。
(yieldはスタックのトップフレーム≒呼び出された関数でしか実行できない、ということ)

この方式はCLUのコピーと言える。
CLUではイテレーターと呼んでいた。
CLUは静的な型付け言語だからイテレーターと関数を区別できるので、Pythonみたいな混乱は起きない(コンパイラが検出できる)。

CLUの実装者は元のスタックを使うイテレーターと、独立したスタックで動くコルーチンの違いを認識しており、それがプロシージャー≒関数を使うより低コストであると言っている。

コルーチンとスレッドとジェネレーター

この3つはcuncurrencyを提供する点で似ているけども、以下の重要な点で異なってる。

• コルーチンはparallelism抜きでconcurrencyを提供する

  明示的に実行を切り替える(resumeやyeild)

• スレッドはconcurrencyに加えparallelismも提供するがコストが高い

  コストとはスケジューリングとコンテキストスイッチと何らかの形でのプリエンプションのこと。

  Goはスケジューリングの一部をGoランタイム自身が引き受けるので、安価なスレッドと言える。
  OSのスレッドのコンテキストスイッチは数マイクロ秒なのに対し、goroutineは数百ナノ秒。
  Javaの新しい軽量スレッドはgoroutineと同等。

• ジェネレーターは弱いコルーチン

  スタックのトップフレームでしかyieldが許されないから。
  これはスタックを分離せず、フレームの保存と復帰で実装されているから。

コルーチンとジェネレータの違いをまとめると以下の通り:

コルーチンではスタックを完全に分離して管理している。なのでyieldがコルーチンのスタック内のどこで実行されても正しく実行される。

ジェネレーターは、yeildを呼び出したフレームの保存と復帰で実装している。
そのためトップフレーム≒ジェネレーターとして呼び出した関数そのものでしかyeildできない。

なぜGoにcoroutineが必要なの?

text/templateの例をあげて、goroutineではtoo muchなシーンもあることを示している。
そしてジェネレーターでは足りない。
レキサーはコルーチンをシミュレーションをしようとして、競合でひどいことになったらしい。
(まぁそれはなんとなく想像がつく)
コルーチンがあればそんな競合はなく、goroutineよりも効率が良かったであろう。

ジェネリック・コレクションへの反復操作の用途が想定される。
(前のLuaのvisitパターンね)
コルーチンがあればイテレーターが定義でき、rangeに渡すこともできるであろう。
現在の書き方であるプッシュイテレーターをプルイテレーターへ書き換えられる。

Goでどのようにcoroutineを実装するか

言語的な変更はしない。
Goの既存の語彙でcoroutineを定義・実装する必要がある。
ランタイムによる最適化された実装は後に議論する必要があるが、その実装は純粋なGoの定義とは区別できるべきではない。
(ちょっと意味不明)

まず yield 無しでgoroutine & chan x2で実装したシンプルな例。

次にユーザー定義関数(コルーチン)内から使える yield を定義した例。

例: 文字列パーサー

(どうやって構成するかの例なので省略)

例: 素数の篩(ふるい)

(どうやって構成するかの例なので省略)

複数のコルーチン間の呼び出し関係が変化(逆転)するところがポイントか。
(スタックが独立している意味を示してる?)

コルーチンとgoroutine

goroutine使った実装をコルーチンと呼ぶには語弊がある。
普通にgoroutineを使うとは並列性が上がるが、このコルーチンでは上がらない。
コルーチンで上がってるのはconcurrencyのみである。

goroutineはconcurrent & parallel制御フローを作る。
corouitneはconcurrent & non-parallel制御フローを作る。
どのgoroutineがnon-parallelなのかは、変わる可能性があることに留意が必要。

頑強な再開≒resume

coro.Newの改良。

1点目は関数終了後のresumeの呼び出し。いまはデッドロックする。
実行状態(running)を保存して管理する。

例: イテレーター転換

resumeを終了後に呼び出せるようになったので、プルイテレーターが実現できるようになった。

panicの伝搬

2点目の改良はコルーチン内で発生したpanicを呼び出し元へ戻すこと。
goroutineを跨いでpanicを伝搬させる必要があるため、少し難しい。
が呼び出し元はブロックしているので、伝搬させるのは理に適っている。

goroutine側でdefer & recoverしてchan経由で成功時の値 or panic時の値を返せば良い
(このあたりは直和なのにそうではないから突っかかる人がいそうだねw)

キャンセル

panic伝搬はコルーチンから呼び出し元に停止を伝えるが、逆に呼び出し元からコルーチンへ停止を伝えるのがキャンセル。
coro.Newがresumeだけじゃなくcancel関数も返すようにする。
キャンセル用の専用panic値を用意する。

例: 素数の篩(ふるい) 再び

前述のキャンセルを使って素数の篩を再実装。
(ループ内側のdefer cancel()がココで良いかが気になる)

API

ここまでに論じてきたcoroのAPIのまとめ

• Newは関数fを実行する、初期状態として停止したcoroutineを作る。

  このcoroutineはgoroutineではあるが、Newが返すresumeかcancelが呼ばれない限り、決して実行されることはない。

• このgoroutineは別のcoroutineのresume(in)を呼ぶことで、自身を停止できる。

• 最初のresumeの呼び出しがf(in, yeild)を開始する。

  fが実行中はresumeはブロックし、fがyieldを呼ぶか終了するまでブロックし続ける。
  fがyeildを呼ぶとyeildはブロックし、resumeはout(その値)とtrueを返す。
  fが終了すると、resumeはoutとfalseを返す。
  yeildによりresumeが終了すると、次のresume(in)の呼び出しはfがyieldの後から再開する。

• cancel()はfの実行を停止し、コルーチンをシャットダウンする。

  resumeされてなければfはまったく実行されない。
  cancelはブロックしているyeildの呼び出しがpanicを引き起こす。
  その際のエラーはerrors.Is(err, ErrCanceled)で識別できる。

• fがpanicしrecoverしない場合、そのパニックはfのコルーチン内でせき止められ、fを待つgoroutineで再開される。

  cancelは、自身が引き起こしたpanicである場合、再度panicすることはない。
  (前述のコードをちゃんと見てないので、どのように実現していたかわかってない。再確認する必要がありそう)

• いったんfが終了するかpanicすると、coroutineはもはや存在しない。

  そのあとのresumeの呼び出しはzero, falseを返す。
  そのあとのcancelは単にreturnする。

• resume, cancle, yeildの各関数は、別のgoroutineに渡すことができ、どのgoroutineがcoroutineであるかは動的に変わる。

  Newが作るgoroutineは常に初期状態でブロックされる。
  resume, cancel, yeildを読んだgoroutineもブロックされる。
  これらのブロックの関係は不変で、fが戻るまで保持される。
  結果、coro.Newは新たなparallelを伴わずに、新たなconcurrencyを導入する。

• 複数のgoroutineがresumeやcancelを呼んだ場合、その呼び出しは直列化される。

  複数のgoroutineがyieldを呼んだ場合も同様。

効率

ここまで見たような既存のGoで実装できるcoroutineの定義は重要だが、実際には最適化されたランタイムがあるべきだ。
2019年のMacBookProでは各関数の呼び出しに数百ナノ秒単位のオーバーヘッドがある。

ランタイムがcoroutine関連について、スケジューラをバイパスできるようなハックを、コンパイラに施してみた。
このハックでは38%高速化したが、まだ必要な水準には不十分。
チャンネルの汎用性がオーバーヘッドになりすぎている。

次にランタイムにコルーチンを実装して、チャンネルを完全に排除した。
実装は3つのアトミックなcompare & swapになった。
各オーバーヘッドは数十ナノ秒となり、もとより10倍速くなった。
このくらいであれば十分だろう。

<a name="conclusion">まとめ</a>

おおよそ以下のような構成だった。

1. coroutineの定義を確定する
2. 既存の実装(Lua & Python)を検証する
3. Goでcoroutineを(incremental)に実装する
4. 3を通じて必要となったAPIの要件を確定する
5. パフォーマンスを計測し、改善案を提示する

Goへcoroutineを実装するのに必要な手続き全部、という印象。

メモの原本

このメモの原本は以下のURLです。

https://github.com/koron/techdocs/blob/main/coroutines-for-go/memo.md