Fiber

はじめに

「見た目は JavaScript、頭脳(中身)は Ruby、（安定感は AC/DC）」 でお届けしているスクリプト言語 Kinx。作ったものの紹介だけではなく実現のために使った技術を紹介していくのも貢献。その道の人には当たり前でも、そうでない人にも興味をもって貰えるかもしれない。

前回のテーマは Garbage Collection。今回のテーマは Fiber。

参考
- 最初の動機 ... スクリプト言語 KINX（ご紹介）
  - 個別記事へのリンクは全てここに集約してあります。
- リポジトリ ... https://github.com/Kray-G/kinx
  - Pull Request 等お待ちしております。

Fiber はこれまで使ったことがなかったのだが、途中で関数を中断できる機能は結構便利かも。効果的な使い道は 誰か教えてください。

尚、今回の記事を書いている途中で当初考えたやり方ではうまく行かないケースがあり、急遽修正しました。今回は反省の意味を含め、その流れも書いておきます。その方が何やっているか分かりやすそうというのもあり。恥ずかしすぎるが致し方ない。むむむ、見落とした…

実現方法

当初の発想

「基本、その時のフレームと実行再開位置が保存されていればうまくいくんじゃね？」

結果

「うまくいったぜ！チョロいもんだ」

本記事を書いてる途中

「マジか、動かねえ。何でだ？つか、あぁ、なるほど。当たり前だ。なぜ気付かなかった俺。」

改めた発想

「スタック状態と実行再開位置が保存されていればうまくいくに違いない」

結果

「かぁさん、俺やったよ！」

やったこと

当初

yield の時の フレーム と 次回開始位置 を呼び出し元関数オブジェクトに保存。
return の際、フレーム情報はクリアせず に 実行開始位置だけクリアして リターン。これは後で使う。
次回の関数呼び出しの際、関数オブジェクトに フレーム情報があれば yield 後の再開とみなす。
再開と判断した後、実行開始位置がクリアされて いれば return したということで FiberException 例外を発行。

何がダメ？

Fiber 中にさらに関数呼び出しされてそこで yield された場合、期待する関数オブジェクトにコンテキストが保存されない。
そらそうだ。結局、Fiber 中のスタック状態は全部保存しとかないとダメだった。

具体的にはこの記事の最後の Ruby の例が動かなかったんですね。

修正

関数オブジェクトに ファイバーであるという情報 と ファイバー開始時のフレーム以降のスタック と 実行位置 を保持できるフィールドを追加。
yield の際、ファイバー開始時のフレーム以降のスタックをコピー し、次の実行開始位置 を記録してリターン。
return の際、ファイバーである情報はクリアせず に 実行開始位置だけクリアして リターン。これは後で使う。
次回の関数呼び出しの際、関数オブジェクトがファイバーとなって いたら yield 後の再開とみなす。
再開と判断した後、実行開始位置がクリアされて いれば return したということで FiberException 例外を発行。
resume する際、どこからファイバーをスタートさせたかの情報 をスタック上に残しておく（コピー開始地点の記録）。

解説

スタック状態について

当初はローカル変数がフレームに格納されているので、フレームを復元すれば良いと単純に考えてしまった。こんな感じ。

ところが、Fiber 中に関数呼び出しするとこんな感じに。これは正しく動かない。

これを正しく動かすためにはこうしないといけない。

今回は、スタックにマーキングするようにした。例外スタックのように実行コンテキストに分離する手もあるが何度も保存・復元する必要があるのでスタックのほうが楽。どちらにしても特急で直したためコード的に若干無駄があるので、後でリファクタリングします。

命令追加

もしかしたらもっと簡単にできたかもしれないが、ファイバー開始マークをするためだけの命令が1つ追加されています。もうちょっと汎用的にしたほうが良かったかな。まぁ、まずは動くことが重要なのでこれで。後でリファクタリングもできるし。

謎の特殊命令 _coroutine キーワードが追加されていますが、当然、通常 使ってはいけません 。以下のようになっており、実際、return とほぼ同じ動きをしますが、式を評価する前にスタック上に ファイバー開始したよ！ というマークをスタックに残す動作をします。このマークを頼りに、yield するときにどこまでのスタックを保存しておくのかをサーチします。

Fiberクラスの内部定義(ちょっと違うけどイメージ)

class Fiber(fiber) {
    public resume(...arg) {
        _coroutine fiber(...arg);
    }
}

書いててキーワードの位置が意味的に合っていない気がしたので、修正するかも。内部仕様なので、勿論動作は変わらずですが。

GC 対応

あと、忘れてはいけないのが GC でのマーキング。関数オブジェクトがスタックを持っている場合、そこからの参照先にも全部マークさせに行きます。

全部合わせると

具体的な差分は以下です。

https://github.com/Kray-G/kinx/compare/da19d6c5a65040141c49124259ac1c97cc297255...824453e8fabb3c3525695637197ae0e105e5f4e4

はー、やっちまった感が半端ない。一応、直して動くことは確認したけれど。

isAlive が必要とか、ファイバー例外まわりが多少おかしいので、もう少し修正する予定です。

サンプル

Fibonacci

私自身は良い使い道がイマイチ(モヤっと)しているのですが、まずはどこかにあった Fiber によるフィボナッチ数列を Kinx で実現してみましょう。

こんな感じに無限ループで yield。

var fib = new Fiber(&{
    var a = 0, b = 1;
    while (true) {
        yield b;
        [a, b] = [b, a + b];
    }
});

var r = 35.times().map(&(i) => fib.resume());
r.each(&(v, i) => System.println("fibonacci[%2d] = %7d" % i % v));

実行。

fibonacci[ 0] =       1
fibonacci[ 1] =       1
fibonacci[ 2] =       2
fibonacci[ 3] =       3
fibonacci[ 4] =       5
fibonacci[ 5] =       8
fibonacci[ 6] =      13
fibonacci[ 7] =      21
fibonacci[ 8] =      34
fibonacci[ 9] =      55
fibonacci[10] =      89
fibonacci[11] =     144
fibonacci[12] =     233
fibonacci[13] =     377
fibonacci[14] =     610
fibonacci[15] =     987
fibonacci[16] =    1597
fibonacci[17] =    2584
fibonacci[18] =    4181
fibonacci[19] =    6765
fibonacci[20] =   10946
fibonacci[21] =   17711
fibonacci[22] =   28657
fibonacci[23] =   46368
fibonacci[24] =   75025
fibonacci[25] =  121393
fibonacci[26] =  196418
fibonacci[27] =  317811
fibonacci[28] =  514229
fibonacci[29] =  832040
fibonacci[30] = 1346269
fibonacci[31] = 2178309
fibonacci[32] = 3524578
fibonacci[33] = 5702887
fibonacci[34] = 9227465

よっしゃ、グッジョブ！

Ruby の例をいくつか

Ruby 2.7.0 Fiberクラスより。

Ruby

f = Fiber.new do
  n = 0
  loop do
    Fiber.yield(n)
    n += 1
  end
end

5.times do
 p f.resume
end

#=> 0
    1
    2
    3
    4

これを素直に Kinx に書き直してみる。

Kinx

var f = new Fiber(&{
  var n = 0;
  while (true) {
    yield n;
    n++;
  }
});

5.times(&{
 System.println(f.resume());
});

実行。

お・ん・な・じー。も一つの例も。

Ruby

def enum2gen(enum)
  Fiber.new do
    enum.each{|i|
      Fiber.yield(i)
    }
  end
end

g = enum2gen(1..100)

p g.resume  #=> 1
p g.resume  #=> 2
p g.resume  #=> 3

ただし、Range オブジェクトは今はないので代替手段で。enum は Kinx では予約語なので変数名も変えておきます。

Kinx

function enum2gen(enumArray) {
  return new Fiber(&{
    enumArray.each(&(i) => {
      yield i;
    });
  });
}

var g = enum2gen(100.times().map(&(i) => i+1));

System.println(g.resume());
System.println(g.resume());
System.println(g.resume());

実行。

1
2
3

やったね。

これが動かなかった…

おわりに

やはりそもそも Fiber を使ったことがない、というのが敗因でしょう。色々使ってみよう。

結局協調スレッドなので、実際にスレッドである必要はないし、単一スレッドの中でのコンテキスト（スタック状態）を関数オブジェクトに保持して切り替えている、といった実装になっているだけ。スレッドという言葉に惑わされなければこれで悪くない気がしているのですが、何か根本的なところで思い違いをしているようであれば、ぜひぜひ ご指摘ください。

ということで、最初に紹介しようとしたものは紹介しましたね。一先ず、ライブラリの使い方とか、サンプルコードとかを紹介していくフェーズに戻ろうかと思います。

では、次回。

Kinx 実現技術 - Fiber