K.Sasada's Home Page

Diary - 2017 September

研究日記

長月

_17(Sun)

RubyKaigi 2017 では、Fiber in the 10th year という話をします。 本稿では、この発表でしゃべる内容を(できれば)全部書いておこうと思います。

タイトルなんですが、Fiber を作って Ruby に導入して、ちょうど10年なんですよね。 しかし、Fiber の歴史とか、ちゃんと発表したことがなかったので、今回の機会を使って、まとめておこうと思います。昔の仕事についての自慢話ですね。 ただ、最近の仕事なんかも紹介しようと思います。


まず、そもそも Fiber の復習です。

fib = Fiber.new do
  Fiber.yield a = b = 1
  loop{
    a, b = b, a+b
    Fiber.yield a
  }
end
10.times{ p fib.resume }

fib は、無限にフィボナッチ数を返していく Fiber で、fib.resume するたびに、どんどん次の値を返していきます。

Fiber の基本です。Fiber.new で Fiber の生成(渡したブロックの中身を実行するものになります)、Fiber#resume で開始、Fiber.yield で呼び出し元に戻る、というもので、Proc と似ています。Proc に対応させるとすると、それぞれ Proc.new、Proc#call、break (lambda の場合は return)にあたります。ただ、Proc と違うのは、Fiber.yield で停止した Fiber に対して、Fiber#resume で再開することができます。つまり、処理の一時停止と再開を行うことができます。

もうちょっと細かく説明します。Fiber#resume で Fiber に処理を移します(再開)。この時、resume した Fiber を親 Fiber、resume で処理を移した Fiber を子 Fiber と言います。 Fiber.yield すると、親 Fiber に処理を移します。このとき、Fiber.yield の引数が Fiber#resume の返値になります。Fiber.new で生成された Fiber は、一時停止の状態で生成されます。

Fiber を何のために使うかですが、まず internal iterator を external iterator にする、ということがあげられます。

f1 = Fiber.new do
  2.times{|i| Fiber.yield i}
end

p f1.resume #=> 0
p f1.resume #=> 1
p f1.resume #=> 2 # return value of #times
p f1.resume #=> dead fiber called
                (FiberError)

繰り返しごとにブロックが呼ばれるのが内部イテレータで、ブロックを使わないのが外部イテレータ、というのは雑な説明ですかね。 コード例のように、ブロックの外側から、繰り返しを制御する、と言ってもいいかもしれません。

数値の繰り返しなら、単にカウンタ変数を用いれば簡単に同じことができます。Fiber を使わないとできないこと、やりづらいことはなんでしょう。

etc_passwd_ex_iter = Fiber.new do
  open('/etc/passwd').each_line{|line|
    Fiber.yield line
  }
end
p etc_passwd_ex_iter.resume #=> 1st line
p etc_passwd_ex_iter.resume #=> 2nd line
…

この例では、each_line の各繰り返しを、ブロックの外側で制御しています。これも、ファイルに対して gets を行えばできると言えばできるのですが、 外部イテレータ化した場合、それらの細かいことは知らなくてよく、each_line というメソッドの存在さえ知っていれば実現できる、というのが良いところだと思います。

この Fiber を用いた外部イテレータ化ですが、まさにそれを行うのが Enumerator です。

# make Enumerator
iter = open('/etc/passwd').each_line

# Enumerator#next use Fiber implicitly
p iter.next #=> 1st line
p iter.next #=> 2nd line
…

Enumerator#next では、Fiber を暗黙のうちに利用して、先ほどの Fiber を使った例のように、外部イテレータを実現します。

さて、利用例は、おそらくエージェントシミュレーションになるかと思います。物々しい言葉ですが、ゲームのキャラクターとでも考えてもらえばいいと思いますが、各キャラクターが独自のルールで動いている時、それをちょっとずつ進めていく方法を考える、というものです。

characters << Fiber.new{
  loop{cat.move_up; Fiber.yield}
}
characters << Fiber.new{
  loop{dog.move_left; Fiber.yield}
}
…
loop{cs.each{|e| e.resume}; redraw}

配列 characters に Fiber を突っ込んでいきます。Fiber は、キャラクターを表しており、最初のは猫、次のは犬を表しているとします。猫はずっと上に移動、を繰り返し、犬は左に移動、というのを繰り返す、というものだとします。この Fibers を、それぞれ resume すると、各キャラクターがちょっとずつ動いていく、というものです。

ずっと上や左にいく、というキャラクターは、毎回それを繰り返せばいいだけなので、簡単そうです。しかし、こんなのはどうでしょうあk。

characters << Fiber.new{
  # you can specify complex rule for chars
  loop{
    cow.move_up;    Fiber.yield
    cow.move_right; Fiber.yield
    cow.move_down;  Fiber.yield
    cow.move_left;  Fiber.yield
  }
}

牛は上→右→下→左→上...と方向を変えながら移動するものとします。Fiber を用いると、このような処理を上記のように、自然な並びで表現することができます。もし、Fiber がなく、例えば Proc で実装するとすれば、前の状態を何か数字で覚えておいて、その数字に応じた処理を行う、みたいなものになるでしょう。

n = 0
characters << Proc.new{
  # you can specify complex rule for chars
  case n
  when 0
    cow.move_up
  when 1
    cow.move_right
  when 2
    cow.move_down
  when 3
    cow.move_left
    n = -1
  end
  n = n+1
}

さらに複雑なロジックを書いたとき(例えば、分岐があったらどうでしょう)、このようなことを毎回やるのは面倒です。Fiber を使えば、こんなようなコードをすっきり綺麗に書くことができます。 ちなみに、まさに n がプログラムカウンタを示しており、つまり Fiber は状態としてプログラムカウンタ(やローカル変数など)を記憶しているもの、と考えても良いかと思います。

同じような応用ですが、IO のブロッキング時に別の Fiber に切り替えるようにする、みたいなものも書くことができます。

さて、Fiber と似たようなものに Thread があります。同じく実行を中断し、別のスレッドを実行、そしていつかはそのスレッドが再開します。違いは何でしょうか。

違いは、一時停止と再開のタイミングです。スレッドは、「勝手に」スイッチしていきます。例えば、一定時間がたったらとか(preemption と言います)、IO でブロックしたときなどです。が、Fiber は完全に手動でスイッチすることになります。手動だと面倒、というべきか、手動だからすべてコントロールできて良いかは、問題によります。なお、スレッドプログラミングで必要になる同期処理等は、(一般的には)Fiberでは不要です。なぜなら、同期処理はどのようなタイミングで切り替わるかわからないからであって、Fiber ではそのタイミングを問題ないように制御することができるので、不要であるというわけです。

ここまでが Fiber の概要でした。


発表では、Fiber の歴史について、ちょっと振り返ります。

2007/05/23 cont.c (for callcc)
2007/05/25 Fiber impl. [ruby-dev:30827] 
2007/05/28 Fiber introduced into cont.c
2007/08/25 Fix Fiber spec

おおまかにはこんな感じです。始めてから一週間くらいでとりあえずの実装ができ(こっそり導入されて)、3ヶ月後くらいに仕様が変わって fix した、というものです。

最初は Fiber#pass というインターフェースしか持たない、コルーチンを提供する API でしたが、検討の結果、Fiber#resume、Fiber.yield という対による、親子関係をもつセミコルーチンを提供する API となりました。

なお、Fiber という名前は Microsoft が提供している名前が由来です。Thread よりも細いやつ、みたいな感じで付けたんじゃ無いかと思います。

発表では、経緯をもう少し掘り下げて紹介する予定です。いちいち書くのが面倒...。


さて、実装です。

3つのトピックがあります。どうやって、コンテキストを制御するか、ということになるんですが、3つの大きなステップがありました。

  • (1) 2007/05 Copy all machine stack
  • (2) 2010/05 FIBER_USE_NATIVE
  • (3) 2017/09 Switch only pointer

MRI のもつ実行コンテキストには、大雑把に言って、(a) スレッドの状態(例えば、プログラムカウンタやスタックポインタといったもの)、(b) VM スタック、(c) マシンスタックの3つがあります。どうにかしてこいつらを(現状のモノは再開可能にするために保存して)別のもににすり替えることができれば、別の Fiber を再開することができるということです。

(a) については、定数個なので、コピーで対応しても、そんなに重くありません。(b) については、複数の VM スタックを用意して、ポインタを切り替えるだけで実現できます。では、(c) マシンスタックについてはどうでしょうか。

まず最初の実装。Ruby 1.8 と同じように、マシンスタックをコピーする、という実装でした。Ruby 1.8 でのユーザレベルスレッドと同じというか、それを強く参考にして作りました。

この方法だと利点欠点があるんですが、欠点はスタックが深くなるとコピーする量が増えて重くなる、という欠点があります。

そこで、(2) で3年後に、マシンスタックのコピーを行う代わりに、OSなどが提供する(いわゆる)コルーチンを実現するための API を用いて、先に確保しておいたマシンスタックにすり替える、ということを実現しました。対応しているのは POSIX makecontext/setcontext と Win32 Fiber API です。これは、私が大学の教員をしていたとき、学生だった芝君という方にやってもらった仕事になります(参考資料:Ruby1.9での高速なFiberの実装)。これによって、スタックの深さに比例せず、O(1) でスイッチすることができるようになりました。

で、最後に残っているのは、先ほどは「(a) については、定数個なので、コピーで対応しても、そんなに重くありません。」といったここで、数えてみるとそこそこメモリコピーを発生させていました。今回、この辺を整理して、コピーしないといけないデータを「rb_executon_context_t」という構造体にまとめ、その構造体へのポインタを切り替えるだけで Fiber のスイッチを可能にしました。

それからもう一点、setcontext を使う場面なんですが、sigprocmask を内部で毎回呼び出しています。というのも、シグナルマスクを適切に戻すためなのですが、そもそも MRI ではシグナルマスクは変更しないので、 これは純粋なオーバヘッドになります。ということで、こいつをなくしたバージョンの setcontext を用意すれば、そこそこ早くなりそうです(ただ、まだ未実装)。

さて、測ってみると、コピーからポインタ変更にすることで、Fiber のスイッチが 5% くらい速くなりました。ほとんど変わりませんね。まぁ、この変更は、将来 Guild を実装するときのために整理する、という側面が大きかったので、と言い訳しておきます。


最後に、auto-Fiber という提案についてご紹介します。

先ほど、「スレッドは、「勝手に」スイッチしていきます。例えば、一定時間がたったらとか(preemption と言います)、IO でブロックしたときなどです。」と書きました。選択肢としては IO でブロックしたときだけ切り替わる、という Fiber があっても良さそうです(実際、win16 などでは昔のシステムにはそういう API がありました)。それを作ろう、というのが [PATCH] auto fiber schedule for rb_wait_for_single_fd and rb_waitpid での提案になります。

Fiber で IO スケジューラを作ることが出来るよ、と先ほど述べましたが、システムがそれを標準で提供しよう、というものです。

スレッドはいつ切り替わるかわからないけど、auto Fiber はそこそこ予測可能になるので(それから、スレッド使うよりも色々軽いし、で)、better thread としてつかえるのでは、という提案です。

実は、まつもとさんとも同様の機能を検討しており、渡りに船だったわけですが、進めていく上で、これはスレッドと同様の非決定的なバグを埋めやすくする機能では無いか、と思い直し、私自信は反対派です。それよりも Guild 使おうよ(まだ実装ないけど...)。


というのが、明日の発表の内容です。かなり駆け足なので、よくわからないところもあると思いますが、お気軽に聞いていただければ幸いです。 では、RubyKaigi でお会いしましょう。

_6(Wed)

ふと、サラリーをもらうようになってからの、自分の上司が誰だったか思い出してみる。日本人限定で。

  • 竹内郁夫先生
  • まつもとゆきひろさん
  • よしおりさん

なんというか、蒼々たる面子だなぁ。

Sasada Koichi / ko1 at atdot dot net
$Date: 2003/04/28 10:27:51 $