coroutineとasync/awaitのあれこれ

  • 6
    いいね
  • 0
    コメント

mixiグループ Advent Calendar 2016の11日目の記事です。
皆さん、こんにちは、こんばんは、おはようございます。natsu1211です。仕事ではゲームクライアントの開発をやっています。今日はcoroutineのあれこれについて語りたいと思います。

前書き

さて、ゲーム開発をする以上、スプライト/モデルを制御する必要が必ず出てくる。
ある引っ張りハンティングRPGSTGゲームのボスを以下のように制御したいと仮定しよう。
- エフェクトを再生(大技の予告)
- 10 frameで現在位置(300,300)から(100,100)まで移動(エフェクト再生が終了するまで待つ)
- 弾を10発撃つ(発射間隔5frame)(移動が終了まで待つ)

このニーズに対して、
理想:

1.cpp

void Enemy::update()
{
    auto ef = playEffect(EFFECT_ID_BOSS);
    //ここでずっと待つことはできない
    waitUntilEffectEnd(ef);    
    moveToInFrames(Vector2(100,100), 10);
    for(int i=0; i<10; ++i)
    {
        fireBullet(BULLET_ID_BOSS);
        //ここでずっと待つことはできない
        waitForFrames(5);
    }
}

こういう風なコードを書きたいですが、updateのなかでずっと待っていると(blockingな処理)、ほかの処理ができなくなり、ゲームが止まってしまいます。そのため、一旦この関数から脱出して、ほかの処理をしに行かないといけないです。しかし、皆さんがご存知の通り、c/c++などの言語での関数の呼び出しでは、stackFrameにレジスタの値、引数、ローカル変数などのコンテキストを保存しています。呼び出された関数からreturnしたあと、その関数のstackFrameがクリアされます。つまり、呼び出された関数が実行途中でreturnして、もう一回呼び出して、returnの後の位置から処理を再開するといった操作ができない。必然に、メンバー変数なり、何らかの形で現在ボスの状態を保存しないといけないです。

現実:
大体こんな感じのコードなってしまいます(あくまで例なので、汚いです><)。

2.cpp

void Enemy::update()
{
    switch(phase_)
    {
        case 0: //エフェクト再生中
            ef_ = playEffect();
            if(ef_->isEndEffect()) 
            {
                ++phase_;
            }
            break;
        case 1: //エフェクト再生完了、移動中
            if(pos_ == Vector2(100, 100))
            {
                ++phase_;
            }
            else
            {
                const Vector2 dir = (Vector2(300,300)- pos_).normalize();
                const float speed = (Vector2(300,300)- Vector2(100,100)).dist() / 10;
                pos_ += dir*speed;
            }
            break;
        case 2://移動終了、弾発射
            if(frame_++ < 5) 
            {
                break;
            }
            fireBullet();
            this->frame_ = 0;
            if(fireCount_++ >= 10)
            {
                ++phase_;
            }
            break;
        default:
            break;
    }
}

うーん、switch-case文の中にバラさせられてしまい、処理の流れが見えづらくなり、状態の管理もしないといけなくなった(非同期処理の面影が出てきたんじゃないでしょうか)。もっといい方法はないでしょうか?ちょっと待って、Unityならこういうコードを書けるよ(あくまで例なので、汚いです><)。

unity.cs
private IEnumrator fireBullets(int count, float interval){
    for (int i = 0; i < count; ++i) {
        fireBullet();
        //厳密ではないです
        yield return new WaitForSeconds(interval/FRAME_RATE);
    }
}

void Update(){
    //移動の部分も大体同じようにできるので、省略します
    if(this.gameObject.shouldFire){
        startCoroutine(fireBullets(10, 5));
    }
}

startCoroutineという起動関数が若干気になりますが、かなり理想の形に近づきましたね(処理の流れを沿ってそのまま書ける)。これはまさにcoroutineの威力です。

coroutineとは

随分と長い前書きとなりました。ここからは本題に入ります。
そして、coroutineとはco-operative routine(協調するルーチン)の意味です。1つ重要なポイントはcoroutineはもっと一般化したルーチンです。普通のルーチンの機能を加え、ほかのcoroutineと協調して、制御権を譲り合う(yield)ことができる。つまり、関数の呼び出しではできない、実行を一旦中断して、制御を外部に渡し何らかの処理を行い、また前回中断したところから実行を再開することができる。主従関係を持つ関数の呼び出しとは違い(呼び出されるほうの実行は常に先に終わる)、coroutineの間の「呼び出し」は平等な関係にある。

さらに細かく言うと、coroutineは以下の特徴を持つ。

  • ローカルデータの状態保存(コンテキストスイッチ)
  • 実行の一時中断と一定時間後の再開
  • 対称と非対称の制御権受け渡し
    • 対称とは呼び出されるほうのルーチンもyieldで制御権を譲る。そして、呼び出されるほうのルーチンもyieldで。必ず呼び出すのルーチンに戻すわけではないので、yieldの対象を明記する必要がある。
    • 非対称とは呼び出されるほうのルーチンはyieldではなく、resume構文で呼び出すのルーチンに戻す。
    • 2つの表現力は同じことはすで証明されているが、対称coroutineのyieldは濫用されプログラムの処理順番が分かりづらくなる恐れがあります。非対称のほうが見通しがよいため、広く使われている。
  • first-classオブジェクトであること
  • スタックあり(stackfull)とスタックなし(stackless)
    • stackfull coroutineは機能面で優れているが、メモリの消耗はstackless couroutineより激しい (4KB〜2MB)。c#,python,javascriptのcoroutineはこのタイプです
    • stackless coroutineは機能面で制限されているが、メモリの消耗が少ない(4KB〜数十KB程度)。go,rubyのcoroutineはこのタイプです

そして、coroutineを使った典型的なコントロールフローはマルチスレッドのとかなり近いですが、threadはprocess上に存在するに対し、coroutineはthread上に存在しています。
threadはOSによってスケジュールされているため、thread自身がスケジューリングに気にする必要がありません。しかし、coroutineはユーザースペースでのただのルーチンのため、自分自身でスケジューリングをしないといけません(制御権を譲ることを明言する)。逆に言うと、マルチスレッドプログラムとは違い、ユーザーがプログラムの実行フローを完全にコントロールすることができる(coroutineの数が多くなると、スケジューラでcoroutineの制御権をスケジューリングする場合も多くある。さらcoroutineを複数のスレッドの間で移動させることも可能です。Goroutineのスケジューラーの実装はいい例です。)。

coroutineの中身を覗いてみる

それでは、いったいcoroutineはどうやって前述の挙動を実現したのか。
言うば単純ですが、coroutineが制御権を譲る前でその時のコンテキストを全部保存して、処理を再開したいときにコンテキストを復元できれば、前述の挙動が実現できるわけです。
そこで答えなければならない問題が2つあります。

Q:ここでいうコンテキストはなんですか?
A:stackfull coroutineに対してはcall stackです。レジスタの値、ローカル変数、呼び出し階層などの情報がすべて含まれているため、コンテキストと呼び出し階層を完全に復元することは可能。stackless coroutineに対してはローカル変数だけです、呼び出し階層を保存していないため、coroutineの内部で呼び出されたルーチンでは制御権を譲ることはできないです。

Q:コンテキストをどこに保存するんですか?
A:stackfull coroutineは通常heapでstackを作ります。stackless coroutineはスクープ内のローカル変数をメンバー変数あるいはstatic変数として保存します。

多くの言語(c#、python、javascriptなど)が持つgenerator関数はまさに一種のstackless coroutineです。そして、コンテキスト保存の仕事を担うのはyield構文です。動きから見ると、yieldをするたびに、generator関数の実行が一旦中止し、外部に実行権を譲ります。そして、外部でresume意味を持ち構文で実行権をgenerator関数に戻し、次のyieldまで実行する。
簡単な例で説明すると、

gen.cs
class Gen
{
    public IEnumerable<int> Example()
    {
        yield return 1;
        yield return 2;
        yield return 3;
    }
}
class Program
{
    static void Main()
    {
    Gen g = new Gen();
    foreach(var a in g.Example())
        Console.WriteLine(a);
    }
}

ご存知の方も多いと思いますが、Genクラスの内部に、コンパイラが新しい私有Enumeratorを作ってくれます。yieldするものはcurrentとして保存しています。
そして、外部からみるとmoveNext()は非対称coroutineのresume構文として見られる。内部的にmoveNext()は状態機械になっていて、foreachでmoveNext()がfalseを返すまで呼び続けます。

gen_compiled.cs
[CompilerGenerated]
private sealed class __Enumerator1 : 
   IEnumerable<object>, IEnumerator<object>
{
    private int state;
    private int current;
    public Gen owner;
    private int initialThreadId;

    [DebuggerHidden]
    public __Enumerator1(int state);
    private bool MoveNext();
    [DebuggerHidden]
    IEnumerator<int> IEnumerable<int>.GetEnumerator();
    [DebuggerHidden]
    IEnumerator IEnumerable.GetEnumerator();
    [DebuggerHidden]
    void IEnumerator.Reset();
    void IDisposable.Dispose();

    object IEnumerator<object>.Current 
    { [DebuggerHidden] get; }

    object IEnumerator.Current 
    { [DebuggerHidden] get; }
}

bool MoveNext()
{
    switch (state)
    {
        case 0:
            state = -1;
            current = 1;
            state = 1;
            return true;
        case 1:
            state = -1;
            current = 2;
            state = 2;
            return true;
        case 2:
            state = -1;
            current = 3;
            state = 3;
            return true;
        case 3:
            state = -1;
            break;
    }
    return false;
}

javascriptのほうはfacebook製のregeneratorを使い、コンパイル後のコードを見てみましょう。

gen.js
function* Example() {
  yield 1;
  yield 2;
  yield 3;
}
var g=Example();
console.log(g.next().value)
gen_compiled.js
var _marked = [Example].map(regeneratorRuntime.mark);

function Example() {
  return regeneratorRuntime.wrap(function Example$(_context) {
    while (1) {
      switch (_context.prev = _context.next) {
        case 0:
          _context.next = 2;
          return 1;

        case 2:
          _context.next = 4;
          return 2;

        case 4:
          _context.next = 6;
          return 3;

        case 6:
        case "end":
          return _context.stop();
      }
    }
  }, _marked[0], this);
}
var g = Example();
console.log(g.next().value);

regeneratorRuntimeも絡んでいるので、完全に説明すると長くなるため、詳しい説明は割愛しますが、_contextにコンテキストを保存していると、雰囲気的に分かれるかと思います。

では、コンパイラはいかにしてgenerator関数を状態機械に変換したのでしょうか。基本的はgenerator関数に対してCPS変換を行い、継続を状態に更に変換し、自動的に状態機械を作っています。

yield構文がない言語でのcoroutine実装

schemeには強力なcall/ccがあるので、coroutineが難なく作れますが、c/c++は少々骨が折れる。
もちろん、偉大な先人たちはすでに多くの仕事をしました。

stackless coroutineの実装

C
duff's deviceという実装は基本です。マクロとswitch-case文だけで状態機械を作り(闇です...)、generator関数を実現しました。static変数で状態を保存していますので、基本シングルスレッドでしか使えません。

C++
Boost.Asio.Coroutine, これもduff's deviceを利用しました。
ほかの標準化提案もあります。

stackfull coroutineの実装

C
setjmp/longjmpは基本です。setjmp/longjmpはいわばCにおいてのcall/ccの弱化版で、setjmpで現在のコンテキストをjmp_bufという構造体のインスタンスenvに保存しています。当たり前ですが、setjmp/longjmpの実装とjmp_bufの中身はアーキテクチャによって異なります。そして、longjmpでenvで保存されているコンテキストを復元する。第二引数のvalueがsetjmpの戻り値になる。
これは割りと本質的なところを触れているので、ちょっと中身を見てみましょう。

setjmpのi386においての実装(state-threadsより)

#define JB_BX  0
#define JB_SI  1
#define JB_DI  2
#define JB_BP  3
#define JB_SP  4
#define JB_PC  5
        /* _st_setjmp(__jmp_buf env) */
.globl _st_setjmp
        .type st_setjmp, @function
        .align 16
_st_setjmp:
        // envのアドレスをeaxに保存
        movl 4(%esp), %eax
        // レジスタをenvに保存
        movl %ebx, (JB_BX*4)(%eax)
        movl %esi, (JB_SI*4)(%eax)
        movl %edi, (JB_DI*4)(%eax)
        // SPを保存
        leal 4(%esp), %ecx
        movl %ecx, (JB_SP*4)(%eax)
        // PCを保存、longjmpで戻る
        movl 0(%esp), %ecx
        movl %ecx, (JB_PC*4)(%eax)
        // 呼び出し側のBPを保存
        movl %ebp, (JB_BP*4)(%eax)
        // return eax
        xorl %eax, %eax
        ret
        .size md_cxt_save, .-md_cxt_save

突き詰めところ、コンテキストの保存はいわばこういうことです。threadだとOSがやってくれますが、coroutineだとユーザー自分でやらないといけないです。rubyやGoのstackfull coroutineの実装も同じようなことをやっているはずです。

次に、longjmpのi386においての実装。

        /* _st_longjmp(__jmp_buf env, int val) */
.globl _st_longjmp
        .type _st_longjmp, @function
        .align 16
_st_longjmp:
        // 第一引数envをecxに保存
        movl 4(%esp), %ecx
        // 第二引数valueをeaxに保存
        movl 8(%esp), %eax
        // envからPCを取り出す
        movl (JB_PC*4)(%ecx), %edx
        // envからebx,esi,edi,ebp,espを取り出す
        movl (JB_BX*4)(%ecx), %ebx
        movl (JB_SI*4)(%ecx), %esi
        movl (JB_DI*4)(%ecx), %edi
        movl (JB_BP*4)(%ecx), %ebp
        movl (JB_SP*4)(%ecx), %esp
        // ensure eax is not 0
        testl %eax, %eax
        jnz  1f
        incl %eax
        // Jump to saved PC
1:      jmp *%edx
        .size _st_md_cxt_restore, .-_st_md_cxt_restore

コンテキストの復元です。これをみると、なぜlongjmpの第二引数valueの値がsetjmpの戻り値になるのも明らかになりましたね。初回呼び出しでのsetjmpの戻り値が必ず0で、二度目以降の戻り値はvalue、つまりeaxの値になります。それだけですね。

ucontext、setjmp/longjmpの強化版、現在実際プロジェクトに使われているCのcoroutineライブラリは基本ucontextを使って実装されたものです。
cloudwu/coroutine

C++
Boost.Coroutine2Boost.Contextに依存。こちらも内部的にアセンブリ言語
ほかの標準化提案もあります(stackless派とstackfull派の戦争...)。

簡単にまとめると、自前でstackless coroutineを実装するということは、yield意味を持つ構文を自動的に状態機械に変換してくれる機構を実装することです。stackfull coroutineはコンテキストスイッチのためレジスタを操作する必要があり、低レベルのアセンブリ言語の手助けが必要。

async/awaitへ

ESNextで入るキーワードです。非同期処理の最終兵器として最近Javascript界隈で大注目されている(2012年のc# 5.0ですでに出来ているですが)。
これもcoroutineに深い関係があります。async/await、実はstackless coroutine(generator関数)のsyntax sugarです。
javascriptでは、async/awaitは以下のように変換されます。(c#のasync/awaitに関してはすでにすばらしい記事がありますので、ここでは割愛します)

async.js
async function fn(args){
  await asyncFunc();
}

//becomes

function fn(args){ 
  return spawn(function*() {
    yield asyncFunc();
  }); 
}

spawnはcoみたいな起動関数です(内部的にnext()が再帰的に呼ばわれる。promiseオブジェクトが帰ってくる)。コンパイラが起動関数を用意してくれるため、サードパーティのライブラリを依存する必要もなくなり、簡潔になりました。
そして、コードの見通しがさらに良くなりました。asyncは関数の中に非同期処理があること,awaitはこの処理は非同期処理であることを示しています。yieldより意味が明確です。

まとめ

  • coroutineは強力なフローコントロール能力を提供してくれました。非同期処理みたいな本来一つのまとまった処理が分割処理しないといけない場合、coroutineをうまく活用すれば、意図通りのコードを書けることができ、見通しと保守性が一段と上がります。
  • クライアントに限らず、concurreny性能が求められるサーバーでもcoroutineが威力が発揮します。coroutineはthreadより軽量的で、コンテキストスイッチのオーバーヘッドが少ない。同じメモリでより多くのcoroutineを作ることができ、concurreny性能の向上が期待できる。
この投稿は mixiグループ Advent Calendar 201611日目の記事です。