2015年3月2日月曜日

RPythonを用いたPyrlangのいくつかの実験

PyrlangRPythonで書かれたErlang BEAMバイトコードインタープリタです。
Pyrlangでは、BEAMの約25%の命令を実装しました。現在Pyrlangがサポートしている機能は、整数の計算、クロージャ、例外処理や、アトム(atom)、リスト、組みへのいくつかの操作、ユーザーモジュール、及びシングルコア上のマルチプロセスです。Pyrlangはまだ開発している最中です。
BEAMPyPyVMには、いくつか違うところがあります:
  BEAMはレジスタVMですが、PyPyVMはスタックVMです。
  BEAMには、伝統的なコールスタックがありません。BEAMYレジスタの振る舞いとコールスタックと似ていますが、時折他の変数を保存することもあります。
  BEAMには、言語レベルとOSレベルのスレッドがありません。言語レベルのプロセスのみを持っています。このようなプロセスの振る舞いはアクターモデルと非常に似ています。

バイトコードディスパッチループですが、PyrlangWhileループに命令とオペランドを読み込み、その命令に対応した関数を呼び出し、またループの先頭に戻ります。我々はコールスタックとYレジスタと差があるため、手でYレジスタの実装と管理を施しました。一方、PyPyRPythonのコールスタックでこのままPythonのコールスタックを実装しました。結果的に、PyPyのディスパッチループの関数は自分自身を再帰呼び出すことがありますが、Pyrlangは呼び出しません。
Erlangコンパイラ(erlc)は通常、Erlangソースコードの関数呼び出しをCALL(普通の関数呼び出し)とCALL_ONLY(末尾呼び出し)という二種類のバイトコード命令に変換します。これらの命令は、トランポリン意味論で実装することが可能:
  CALL命令:VMが現在の命令ポインタ(つまりPyPy中のプログラムカウンタ)をYレジスタにpushし、目標ラベルに飛びます。そしてRETURN命令に遭遇したときに、VMYレジスタから命令ポインタをpopし、命令ポインタが指しているところに戻り、外層の関数の実行を再開します。
  CALL_ONLY命令:VMYレジスタを触れずに、直接目標ラベルへ飛びます。よって、末尾再帰呼び出しはYレジスタを増やしません。

現在のPyrlangの実装はCALL_ONLY命令の直後のみにcan_enter_jitを挿入します。つまり、JITErlangコードの再帰呼び出しのみを記録します。この再帰呼び出しの意味論はPythonのような命令型プログラミング言語と非常に似ています。

我々はシングルスケジューラも書き、シングルコアでの言語レベルプロセスを実装しました。スケジューラに実行列(runable queue)があります。毎回の反復に、スケジューラは一つの要素を列からpopし、その要素(プロセスオブジェクト)のディスパッチループを実行します。ちなみにこのディスパッチループの内部には、「reduction」というカウンタがあります。このカウンタの値はループ実行の間に減り、最後0になるときに、ディスパッチループが一時停止します。そしてスケジューラはこの要素を再び実行列にプッシュし、次の要素をポップし、繰り返し処理をします。
我々はこれからマルチコアのCPU上でマルチプロセスのスケジューラを実装する予定もあります。この場合には、複数のスケジューラ及び複数を実行列を実装する必要がありますが、これは別の話です。:-)

実験方法

我々はまずErlangで二つのベンチマークプログラムを書きました:
  FACT:末尾再帰のスタイルの階乗計算ベンチマーク。ただし、数値を大きくしすぎないため剰余計算を施しました。
  REVERSE:このベンチマークはまず[20000, 19999, 19998, ]みたいな降順リストを作り、それからバブルソートを適用します。

実験結果

reductionの値


我々はREVERSEのベンチマーク用いて、いろんなreductionの値でJITの性能を評価しました。
この図の横軸はreductionの値、縦軸は実行時間(秒で)です。
この図から、reductionの値が小さければ小さいほど、reductionがパフォーマンスへの影響が激しくなるとわかりました。逆にreductionの値が大きい場合には、reductionがパフォーマンスへの影響にはほとんどありません。実は、我々はPyrlangで2000程度のreductionの値を用いました(公式のErlangインタープリタと同じ)。
しかし驚いたことに、reductionの値がすごく小さくなっても、トレースがちゃんと生成してくれることです。例えばreductionの値がの場合、つまりディスパッチループがごく少ないステップしか実行できず、言語レベルのプロセスはスケジューラの一回のスイッチに実行したバイトコード命令がErlangのループ全般より少ない場合です。しかもどんなreductionの値にしても、生成したトレースがほとんど一緒です。
実際には、RPython JITは記録するコードのみを気にし、誰かこのコードを実行するのは気になりません。ですから、前の実験でいつも同じトレースが生成したわけです。同じコードを実行する限り、トレースは違うスレッドの間に共用することもできます。
以下はArmin Rigoさんからの詳しい説明です:
「あなたがアプリケーションレベルのループで毎回1ずつカウンタを減らす(そして0になるとソフトスレッドのループを一時停止)という手法をとると、JITがちゃんと動きます。このソフトスレッドのスイッチがあるスケジューラに戻るによって完成しました。そして次のソフトスレッドを呼び出して再開します。そしたら、JITが普通のループのようなコンパイルできるし、生成したコードにも「カウンタを減らす。0になることをチェックし、trueだったらアセンブラから脱出する」という振る舞いもちゃんと含まれました。」

公平的なプロセススイッチング vs. 不公平的なプロセススイッチング


我々はreductionの値を減らすタイミングにも気になります。本来のPyrlangには、公式のErlangインタープリタと同じように、ローカル関数呼び出し、モジュール関数呼び出しと内蔵関数呼び出しの場合でreductionの値を減らします。しかし、JITが基本的に目標言語のループ(Pyrlangの場合は末尾再帰)を記録するため、一般的には、言語レベルのプロセスをスイッチするときに、ループの完全性を保ったほうがいいと考えられます。我々はPyrlangを「reductionの値をCALL_ONLYの直後(つまり目標言語のループの界隈)のみ減らす」というように書き直しました。
もちろん、こういうやり方は言語レベルのプロセスの間に「不公平な」実行になる恐れがあります。例えば、あるプロセスに一列の長い逐次実行コードしかない場合、このプロセスが一回のスイッチングで全部のコードを実行してしまいました。逆に、あるプロセスがごく短いループを持っている場合、ほんの少しステップで実行されたらすぐにスイッチングされてしまいます。しかし、実用の世界には、このような不公平さは通常許されています。実は、全般的なパフォーマンスを向上するため、PyPyを含む多数のVMがこういうやり方を取ります
我々はFACTのベンチマークで二つバージョンのPyrlangを比較しました。ベンチマークのループには複数の内蔵関数を呼び出しているため、reductionの値の減らすことはかなり異なります。古いバージョンでは、プロセスがループの界隈とほかの関数呼び出しのところで一時停止になることがありますが、新しいバージョンにはループの界隈のみで一時停止になることがあります。
実験の結果によってこのやり方が効率的だとわかりました。約7%のオーバヘッドが除去されました。我々はREVERSEベンチマークも試しま

したが、このベンチマークのループには関数呼び出しが一切ないためパフォーマンスが向上しません。実用の世界には、一つのループは複数の関数呼び出しが一般的で考えられますので、このやり方はほぼ有効的であると我々は信じています。

公式のErlangHiPEとの比較

我々はPyrlangErlangHiPEHigh Performance Erlang)三種類の処理系の性能を比較しました。HiPEErlangソースコードからネイティブコードにコンパイルする公式コンパイラであり、著しくパフォーマンスを向上することがありますが、その代わりにコードの普遍性が失いました。
Pyrlangはいま開発中のため、公式の処理系より少ない動作をする場合がありますので、(実行時のチェックが足りない、実行列のロックを掛けないなど)予想より早い場合があるのはご了承ください。最終のPyrlangのバージョンは現在より遅い可能性があります。


まずFACTREVERSEのベンチマークの結果を見ましょう。この二つのベンチマークがそれぞれ5秒以上の時間で走らせるとRPythonJIT Warming Timeを超えます。FACTでは、PyrlangErlangより大体177.41%の速さを達成しました。しかもHiPEとの比較も引き分け程度になりました。ところでREVERSEでは、PyrlangErlangよりすこし速いですが、HiPEよりだいぶ負けています。とくにベンチマークの規模が大きい場合には、Erlangさえ超えれない状況になります。この原因は現在あまりはっきりしないですが、我々は推測では、おそらく大きいリストに対するGCのパフォーマンスが悪いからかもしれません。その原因の一つは、実はBEAMバイトコードにGCに関するヒントが出してくれるわけです。例えばBIF命令の代わりにGC_BIFの命令を使用して「この命令の実行がGCをやるチャンスだ」とか、そのオペランドにいま「生きている」変数の数などの情報をVMに伝えます。によって、より効率的なGCを行う可能性が持っています。しかし現在のPyrlangは、GCの仕事を全部RPythonに任せて、こういうヒントを一切無視してしまいました。


我々もPyrlangが走らせる限りのErlangベンチマークも実行してみました。図のベンチマークの通り、Pyrlangはこれらのベンチマークで結構理想的なパフォーマンスを得られました。しかし、図のベンチマークは、全部末尾再帰のスタイルで書かれたものです。逆に末尾再帰ではない場合には、Pyrlangのパフォーマンスが非常に悪い結果(3倍から100倍までの遅さ)でした。