- プロデューサとコンシューマのコードが相互にデータを受け渡すとき、片方を被呼び出し側の形にひっくり返して書き換えると、本来見えていた アルゴリズム構造 が状態遷移の中に埋もれやすい
- Knuth流のコルーチンは、2つのルーチンが実行位置を保存しながら制御を受け渡すモデルだが、Cの スタックベースの呼び出し構造 では移植可能な方法で直接実装するのが難しい
- この記事の中核となるトリックは、
switch の下位ブロックに case を置けるCの文法と __LINE__ マクロを使って、return 後の位置に再入する 暗黙の状態機械 を作ることにある
crBegin, crReturn, crFinish マクロにより、伸長器とパーサの元のループ構造を保てるが、保持すべきローカル変数は static でなければならず、crReturn を明示的な switch の中に置いたり同じ行に置いたりしてはならない- 実際のコードでは、再入可能性とマルチスレッド制約のためにコンテキスト構造体を渡す改良版が必要であり、
coroutine.h は単純な scr マクロと再入可能な ccr マクロの両方を提供する
プロデューサとコンシューマをつなぐときに生じる構造上の問題
- 大きなプログラムでは、あるコードがデータを作り、別のコードがそれを消費することが多く、このときどちらが 呼び出し側 でどちらが 被呼び出し側 になるかが設計を難しくする
- 例は2つの小さなルーチンで構成される
- 実行長伸長コードは
getchar() で入力を読み、emit() で文字を1つずつ出力する
- パーサコードは
getchar() で文字を読み、アルファベットの連続区間は WORD、それ以外の文字は PUNCT として扱う
- 2つのルーチンはそれぞれ単独で見れば自然だが、伸長器の
emit() 出力をパーサの getchar() 入力へそのままつなぐには、その間を接続する構造が必要になる
- これは2つのプロセスまたは2つのスレッド間のパイプでも解決できる
- 伸長器の
emit() はパイプに書き込み、パーサの getchar() は反対側から読む
- この方法は単純で堅牢だが重く、移植性も低いため、単純な作業のためにスレッドを分けたくない場合が多い
関数の書き換えで生じる可読性の低下
- 伝統的な解決法は、通信チャネルの片側の端を呼び出し可能な関数の形に 書き換える ことだ
- 伸長器を、呼び出すたびに文字を1つ返す関数に変えれば、既存のパーサは
getchar() の代わりに decompressor() を呼び出せる
- 逆にパーサを、文字を1つ受け取るたびに呼ばれる関数に変えれば、既存の伸長コードは
emit() の代わりに parser() を呼び出せばよい
- 両方を変える必要はなく、片方だけでも接続は可能だが、書き換え後のコードは元のものよりはるかに読みにくくなる
- 元の伸長器とパーサでは、アルゴリズムの流れがループの中に自然に現れている
- 書き換え後の形は
static な状態変数と switch による状態遷移に依存するため、圧縮形式やパーサ文法をコードから読み取りにくい
- 目標は、どちらも明示的な状態機械のようにひっくり返して書き換えずに接続することだ
Knuth流コルーチンとCの限界
- Donald Knuth のコルーチン解法は、呼び出し側と被呼び出し側の区別を捨て、2つのプロセスを協調する対等な存在として扱う
- このモデルでの呼び出し原理は通常の関数呼び出しとは異なる
- 現在の実行位置をスタックではなく別の場所に保存する
- 別のルーチンが最後に保存しておいた実行位置へジャンプする
- 伸長器が文字を放出するときは、自分のプログラムカウンタを保存してパーサの保存位置へ移動する
- パーサが次の文字を必要とするときは、自分のプログラムカウンタを保存して伸長器の保存位置へ移動する
- 制御は2つのルーチンの間を必要なだけ往復する
- この方式は理論的には優れているが、実際にはアセンブリ言語でしか実現できない
- Cのような高級言語は スタックベースの構造 に依存しているため、関数間で制御を移動させるには片方が呼び出し側でもう片方が被呼び出し側でなければならない
- 移植可能なCコードでは、純粋なコルーチン方式は Unix パイプによる解法と同じくらい実用性が低い
Cで真似する「return and continue」
- Cで必要なのは、被呼び出し関数が
return したあと、次の呼び出し時にその return の直後から実行を再開する return and continue である
- たとえば
for (i = 0; i < 10; i++) return i; という形の関数が10回呼ばれたときに、0から9まで順に返せるのが理想的だ
- 最初の実装は状態変数と
goto を使う
- 関数の先頭と各
return の後ろにラベルを置く
- 呼び出し間で保持される
state 変数が次に再開するラベルを指す
- 関数の開始時に
switch(state) で適切なラベルへ移動する
return の直前に、次回の呼び出しで戻るラベルを state に保存する
- この方法は動作するが、ラベル管理が手動のため保守の負担が大きい
return を追加するたびに新しいラベルを作り、先頭の switch にも追加しなければならないreturn を削除するときは対応するラベルも削除しなければならない- 関数本体と
switch の一覧の整合性を常に保つ必要がある
Duff’s device で隠した状態機械
- Cで有名な Duff’s device は、
switch に対応する case 文をその下位ブロック内にも置けるという文法を活用する
- この性質をコルーチントリックに適用すると、
switch がどの goto を実行するかを選ぶのではなく、switch 自体が再入ジャンプのように機能する
- 基本形は次のとおり
static int state が次の再開地点を保存する- 関数の先頭で
switch(state) { case 0: ... } として入る
return の直前に state に次の case の値を保存するreturn の直後に対応する case ラベルを置く
- これをマクロで包むと、コルーチンのように見えるインターフェースになる
crBegin: static int state=0; switch(state) { case 0: を隠すcrReturn: state を保存して値を返したあと、同じ位置に case ラベルを配置するcrFinish: 開いているブロックを閉じる
crReturn は do ... while(0) で包まれているので、中括弧なしで if と else の間に書いても文法上の問題が起きない- 当初は
crReturn(1, i) のように状態番号を直接与える必要があるが、ANSI C の __LINE__ マクロを使えば、現在のソース行番号を状態値として利用できる
- この改善後は
crReturn(x) だけで済むが、同じ行に crReturn を2つ置いてはいけないというルールが加わる
マクロ使用ルールと例
- マクロベースのコルーチンはいくつかのルールを前提とする
- 関数本体を
crBegin と crFinish で囲む
crReturn をまたいで保持される必要のあるローカル変数は static として宣言する- 明示的な
switch 文の中には絶対に crReturn を入れない
__LINE__ ベースの実装では、同じ行に crReturn を2つ置かない
- 伸長器の例では、元のループ構造を保ったまま、文字を放出する際に
emit(c) の代わりに crReturn(c) を使う
- パーサの例では、新しい文字が必要になったときに
crReturn() で呼び出し側へ戻り、次の呼び出しでは引数 c に新しい文字を受け取った状態で処理を続ける
- パーサには小さな構造変更がある
- 最初の文字は関数への入り口で既に
c に入っているため、元のループ先頭の getchar() に相当する crReturn はループ末尾へ移される
- 必要なら、パーサには初期化呼び出しが必要だと定めることもできる
- 両方のルーチンをコルーチンマクロに変える必要はなく、片方だけを変えてもう片方は呼び出し側のままでもよい
- 結果として、ANSI C とプリプロセッサ、そして
switch のあまり使われない文法を組み合わせることで、プロデューサとコンシューマ間のデータ受け渡しを明示的な状態機械への書き換えなしに処理できる
コーディング標準とアルゴリズム明快性の衝突
- この手法は一般的なコーディング標準に大きく違反する
- マクロの中に不釣り合いな中括弧が入る
- 下位ブロック内の
case を使う
crReturn は switch, return, case を1つのマクロに隠す
- 文法構造を隠すマクロは、コーディング標準の観点では明確性を損なうと見なされうる
- しかし、明示的な状態機械へ書き換えた関数も、小さな
case STATE ブロックと状態遷移で構成されており、goto ラベルブロックを並べた関数と見た目の構造は大きく変わらない
- 関数が長くなるほど、状態機械への書き換えは元のアルゴリズム構造をより大きく損なう
- この手法は、文法的構造を一部隠す代わりに アルゴリズム構造 をよりよく表すための折衷案である
再入可能な改良版と提供コード
- 単純な玩具実装は
static 変数に依存するため再入可能ではなく、マルチスレッドにも向かない
- 実際のアプリケーションでは、同じ関数を複数のコンテキストから呼び出し、各コンテキストごとに最後の
return の後から実行を再開できる必要がある
- 改良方法は、追加引数としてコンテキスト構造体へのポインタを渡すことだ
- ローカル状態とコルーチン状態変数の両方を構造体メンバに入れる
- ループカウンタのような変数も
i ではなく ctx->i のようにアクセスしなければならない
- コードは多少見た目が悪くなるが、再入可能性の問題を取り除きつつルーチン全体の構造は維持できる
- C++ ユーザーなら、コルーチンをクラスメンバにし、ローカル変数に相当する状態をクラス内に置くことで、スコープをより自然に扱える
- 提供されている
coroutine.h は、このコルーチントリックをあらかじめ定義されたマクロ群として実装している
scr 接頭辞のマクロは static 変数を使う単純版であるccr 接頭辞のマクロは再入可能な上級版である- 詳細なドキュメントはヘッダファイル内のコメントに含まれている
- Visual C++ 6 は、既定のデバッグ設定である “Program Database for Edit and Continue” では
__LINE__ マクロを奇妙に処理するため、このトリックとうまく合わない
- VC++ 6 でコルーチン使用プログラムをコンパイルするには Edit and Continue を無効にする必要がある
- プロジェクト設定の “C/C++” タブ、「General」カテゴリの「Debug info」設定で、“Program Database for Edit and Continue” 以外のオプションを選ぶ必要がある
- ヘッダファイルは MIT ライセンスで提供される
関連参考文献と実使用例
- Donald Knuth の The Art of Computer Programming, Volume 1, Section 1.4.2 では純粋な形のコルーチンを扱っている
- Tom Duff の Duff’s device に関する議論には、類似のコルーチントリックを独立に思いついていた可能性を示す内容があり、2005-03-07 の更新で Tom Duff がブログコメントでこれを確認 している
- PuTTY の SSH プロトコルコードは、このコルーチントリックを実際に使用している
- PuTTY の事例は、シリアスな本番コードでは珍しいほど強烈な Cハック の水準にある
1件のコメント
Hacker News のコメント
C プロジェクトで API の複雑さを減らそうとしてこのページを何度も見返すことになったが、制御フローの説明が素晴らしいと思う
スタック内外での状態保存や、アプローチごとの可読性の違いをより明確に考える助けにもなった
今の結論としては、C のコルーチンを使うかどうかはライブラリ利用者が決めるのがよいということ。たとえば Mongoose(https://github.com/cesanta/mongoose) は非同期処理をイベントコールバックで扱うが、こうしたライブラリは、神話的なクロスプラットフォーム C コルーチンや、さらに悪い
std::threadへ移植しようとするより、各システムのスレッド/タスクの基本要素でラップするほうがずっと快適である[1] https://www.chiark.greenend.org.uk/~sgtatham/putty/
[2] https://www.chiark.greenend.org.uk/~sgtatham/puzzles/
コルーチンは本当にすばらしい概念で、特に Microsoft 系の人たちが主に発表している CppCon の C++ コルーチン動画を見るのも楽しい。「負のコスト抽象化」というフックもかなりよい
数年前、Meta の友人たちが C++ コルーチンを使い始めたが、最終的には大きな失敗だったと言っていた。コンパイラ実装のバグに直面する必要があり、追跡するのは相当に厄介だったはずだ。Google では、google3/ にきちんと統合する優秀な人たちが、もう使ってよいと知らせてくれるのを待っているところだ
この記事は Duff のデバイス [1] を通じて、マクロベースの構造化
gotoを C コルーチンの実装戦略として説明している。要点は、switchブロック内のほぼどこにでもcase文を置けるという点で、関数全体をswitchで包み、static変数で最後にコルーチンが返った位置を保存し、各coReturnをcaseとしてラベル付けする、という形だSustrik の C コルーチン記事も興味深いかもしれない [2]
[1] https://en.wikipedia.org/wiki/Duff%27s_device
[2] https://250bpm.com/blog:48/index.html
co_yield、co_return、co_awaitのような非同期コードが散らばっていることには長所も短所もあるgoogle3 内部のやり方と比べた長所は、コードを読むとき各部分の非同期性がはっきり見えることだ。Google の一部のプログラマは、分岐単位以上のスレッディングモデルを知らないまま過ごし、後で深刻なバグを作ることもあった
短所はもっと単純だ。多くのコードが「非同期かもしれない」ため、時間がたつにつれ、プログラマがそのモードで書くというだけの理由で全体が非同期になっていく。スピンロックと譲歩するミューテックスのどちらを使うかは、クリティカルセクションの大きさとその時点のスレッディング状況に応じて決めるべきだが、可読性と一貫性を合わせようとすると、プロジェクト全体が一方に偏りやすい
デフォルトをどちらか一方に置かず、前回実行のプロファイルに基づいて次回実行をさらに最適化しつつ、コード変更やバグなしでそれを行うスレッディング言語実装についてもっと知りたい
lc-addrlabels.hに入っているコードを寄稿したGCC のローカルラベル機能も使って
__LINE__の使用を完全に避け、1 行に複数のcoReturnを置くこともできたswitchブロック内のほぼどこにでもcase文を置けると気づいた、という話はおそらく正しいが、その機能自体はほぼ間違いなく意図された機能だ記事の下部にもあるように、Duff はその上にコルーチンを作れることにも気づいていたが、その考えを「気持ち悪い」と見ていた
C の
switchを表現力の低いパターンマッチングのように考えると、「fallthrough」はバグのように見えがちだが、そうではない。Fortran のものと同系列の計算済みgotoであり、値が連続している必要もなく、ラベルを最上部に全部並べる必要もないので、より便利だ。書いてみると、計算済みCOMEFROMにより近い気もする「広く使われている高水準言語はコルーチンをサポートしていない」という言い方は、2000 年には正しかったかもしれないが、今では C++20、Lua、Python、Ruby など多くの言語がサポートしている
yieldキーワードもその時か、それほど時間がたたないうちにできたのだと思う記事末尾の改善案である「コンテキスト構造体ポインタを追加の関数引数として置き、すべてのローカル状態とコルーチン状態変数をその構造体の要素として宣言する」という方式は、クロージャの実装のように見える。呼び出される側をラムダにし、外部変数/コンテキスト/状態を使って、何をするか、どの値で行うかを決めさせるようなものだと思うが、この理解で合っているのか気になる
switch方式はそれほど珍しくはないものの、通常は初期化関数とコルーチン関数に渡される状態ポインタを持たせる組み込みプロジェクトでこの方式をよく使っていて、あるコルーチンはモーターの加速/減速を処理し、別のコルーチンはどの方向へ進むかだけを知らせる、といった形だった。ネットワークライブラリ[1]でも使ったことがある。標準ライブラリにも
strtok()[2] のようなコルーチン関数がある管理可能にするためにマクロ地獄まで導入する必要はないが、
switch/caseの流れを読んで楽しかったことはない[1]: https://github.com/REONTeam/libmobile/blob/master/relay.c#L3...
[2]: https://manpages.debian.org/bookworm/manpages-dev/strtok.3.e...
同じ著者による Simon Tatham's Portable Puzzle Collection もある
https://www.chiark.greenend.org.uk/~sgtatham/puzzles/
これが C の黒魔術のように見えるなら、同じ著者がマクロで任意の制御構造を作る記事も読む価値がある: https://www.chiark.greenend.org.uk/~sgtatham/mp/
コルーチンは面白いが、実際のコードでは本物のスレッドの使用も検討すべき。現代のプロセッサはコアが多いが、コルーチンはしばしば単一コアしか使わない
これは実際の問題でもある。最近まで、コルーチンを多用する qemu はブロックデバイス I/O のかなりの部分を単一スレッドに送っており、そのため性能問題があった。Kevin Wolf らが数年かけて修正し、現代の qemu は I/O に複数スレッドを使うようになっており、この作業は RHEL 9.4 に入る予定
コルーチンは単一スレッド実行を構造化する方法であり、それ自体有用である。本文の例である producer-consumer パターンが良い例で、ストリームをパーサーにつなぐことは並列アルゴリズムではないので、スレッドはそれを書くのに役に立たない
並列に実行できる作業に単一スレッドのパラダイムを使えば当然非効率だが、コルーチンは貧者の並列性ではなく、独立して意味のある制御構造である。Web サーバーでイベントループがディスパッチャーとともに複数のブロッキングイベントの間にコルーチンを通すように、スレッドと生産的に組み合わせることもできるし、ランタイムがコアごとにスレッドを立てて並列化すれば、スレッド間の調整は各作業キューの深さを確認して、より空いている側にリクエストを渡す程度に抑えられる
コルーチンの考え方は、何らかの局所的な作業と同期的なデータがあり、呼び出し側が内側のループを「引っ張る」関数型パラダイムよりも、関数が何かをループしながら結果を別の場所にある抽象化されたコンシューマへ「押し込む」反転した形で表現するほうが簡単なときに使うものである
そのうえで、スケジューラ間でコルーチンを移動することはほとんどせず、別のスケジューラ上のコルーチン同士でデータを共有することもほとんどしない
コルーチンは協調的スケジューリングにより、ロックをまったく必要としない快適な並行プログラミングスタイルを可能にする。通常はスケジューリング遅延は大きくなるが、アトミック操作/ロックのオーバーヘッドが消え、プリエンプティブスケジューリングのためにタイマーが実行を絶えず中断しないので、スループットはかなり高くなり得る
このアプローチの C++ 版: https://www.codeproject.com/Tips/29524/Generators-in-C
私の Sciter でも念のため使っているが、かなりうまく動き、便利である
これをモジュール化された安全な形で実現する方法は、おそらくエフェクトハンドラだろう。Python の
yieldに似ているが、値を返すことができ、関数呼び出しに限定されず例外のようにスコープが定まる。馴染みがなければ、この記事は良い動機づけになる直接スタイルで書かれた各関数は、制御が別の場所へ移る必要があるときに「エフェクト」を実行できる。ここでは
c=getchar()とemit(c)がそれにあたるすると制御はエフェクトハンドラへ移り、この場合はおそらく 2 つの関数の呼び出し元が次に何をするかを決める。伸長器が文字を出力したら、その文字をパーサーコードに渡して再開し、パーサーがさらに必要だと言うところまで進めた後、再び伸長器を再開する、という具合である
エフェクトは効率的に実装でき、特に continuation を一度だけ呼び出せるように制限すればなおさらである。OCaml がその例だ。直接スタイルのコードと型/メモリ安全性を両立でき、並行性の環境でも非常に有用である
例はこちら: https://effekt-lang.org/docs/casestudies/lexer
「このトリックは当然ながらあらゆるコーディング標準に違反している……コーディング標準のほうが間違っていると主張したい」という部分にはまったく同意しない
コーディング標準がこのコードを拒否するのは間違いではなく、このコードはただのかわいいトリックにすぎない。大規模なソフトウェア工学とは、驚きを取り除き、午前3時に呼び出されてデバッグする寝不足の人にも読めるコードを作ることだ。プログラマーが常に基本ルール4つを覚えていると期待することはできない
switch、return、caseのような重要な要素を「難読化」マクロの中に隠して文法構造をぼかした一方で、アルゴリズム構造を明らかにしたという主張にも納得しにくい。良いプログラムは文法構造とアルゴリズム構造の両方が明確であるべきで、この方法はそこに届いていない。Rust がasync関数で暗黙の状態機械を作るやり方が、ここでのモデルになるべきだと思うC の世界では三項条件演算子でさえ刺激が強すぎ、C99 も新しもの扱いだ。C++ の世界でテンプレートメタプログラミングを止める唯一の理由は、使っている標準で
constexprによって同じことができるからだ