mrubyのVMにバーストMOVEを実装する
ふと思いついたので久しぶりにmrubyのVMをいじる。久しぶりすぎてcodegenが分離したことを知らなくてしばらく探し回った。
VMというものの実装ではVM命令のディスパッチの負荷がどこまでもついてまわることになるが、これを0にするにはコードをCなどに変換してコンパイルするか、もしくはJITによる動的コード生成をする必要がある。減らすだけなら何かしらの命令を組み合わせたCISC的な命令を追加していけば、ある処理に限定してディスパッチをなくすことができる。
さて、今回思いついたものというのはこのディスパッチを減らすことでどれだけ効果が得られるのか、という実験である。mrubyのバイトコードでOP_MOVEが割とたくさん出てくるのは前に計測した結果として知っていたので、OP_MOVEが連続した場合にディスパッチなしで連続実行するような仕掛けを作ってみる。その結果、どれぐらい速くなるもんなのかな、と。
テスト用コード
テストとしてこのようなコードを書いてみた。OP_MOVEが並ぶだけの無意味なコードである。
before = Time.now 20000000.times do a = 1 b = 2 c = 3 a = b b = c a = b b = c a = b end p Time.now - before
mrubyではローカル変数間の転送はOP_MOVEでのレジスタ間転送となる。定数の代入はOP_LOADIなどになるのでそれだけ並べるわけにはいかない。また、同じa=bなどを並べるだけではピープホール最適化に引っかかってOP_MOVE1個になってしまうので複数の変数を並べる必要がある。このコードを--verbose付きで実行すると以下のような命令列が得られる。ループ内のみ抜粋。
irep 01895170 nregs=5 nlocals=4 pools=0 syms=0 reps=0
file: test.rb
4 000 OP_LOADI R1 1 ; R1:a
5 001 OP_LOADI R2 2 ; R2:b
6 002 OP_LOADI R3 3 ; R3:c
7 003 OP_MOVE R1 R2 ; R1:a R2:b
8 004 OP_MOVE R2 R3 ; R2:b R3:c
9 005 OP_MOVE R1 R2 ; R1:a R2:b
10 006 OP_MOVE R2 R3 ; R2:b R3:c
11 007 OP_MOVE R4 R2 ; R2:b
11 008 OP_MOVE R1 R4 ; R1:a
11 009 OP_RETURN R4 return 例えばbm_ao_render.rbなどはここまであからさまにOP_MOVEが並ばないし、それ以外の命令も多いのだが、とりあえずピンポイントで狙ったベンチマークとなる。
これをうちのPCで実行すると
9.880619
という結果になった。
改造
ではmrubyのVMとcodegenをいじる。まずVMから。opcode.hのOP_MOVEの後ろに命令を3つほど追加する。
OP_NOP=0,/* */ OP_MOVE,/* A B R(A) := R(B) */ OP_MOVE2,/* A B R(A) := R(B) */ OP_MOVE3,/* A B R(A) := R(B) */ OP_MOVE4,/* A B R(A) := R(B) */ OP_LOADL,/* A Bx R(A) := Pool(Bx) */ OP_LOADI,/* A sBx R(A) := sBx */ OP_LOADSYM,/* A Bx R(A) := Syms(Bx) */ OP_LOADNIL,/* A R(A) := nil */ OP_LOADSELF,/* A R(A) := self */ OP_LOADT,/* A R(A) := true */ OP_LOADF,/* A R(A) := false */
OP_MOVE2〜4というのがそれだ。これは後ろについている数字の分だけOP_MOVEが連続していることを表す。ループすると条件分岐が増えてしまうのでディスパッチを減らした意味が無く、このへんはVMのコードを細工することで効率を上げる。とりあえずこのようにvm.cの命令配列を増やして、
static void *optable[] = { &&L_OP_NOP, &&L_OP_MOVE, &&L_OP_MOVE2, &&L_OP_MOVE3, &&L_OP_MOVE4,
OP_MOVEをこうする。
INIT_DISPATCH {
CASE(OP_NOP) {
/* do nothing */
NEXT;
}
CASE(OP_MOVE4) {
/* A B R(A) := R(B) */
regs[GETARG_A(i)] = regs[GETARG_B(i)];
i=*++pc;
}
CASE(OP_MOVE3) {
/* A B R(A) := R(B) */
regs[GETARG_A(i)] = regs[GETARG_B(i)];
i=*++pc;
}
CASE(OP_MOVE2) {
/* A B R(A) := R(B) */
regs[GETARG_A(i)] = regs[GETARG_B(i)];
i=*++pc;
}
CASE(OP_MOVE) {
/* A B R(A) := R(B) */
regs[GETARG_A(i)] = regs[GETARG_B(i)];
NEXT;
}
OP_MOVE2〜4はNEXTマクロを使っていないのでジャンプせず、次の命令を取得して次に移る。フォールスルーである。結局はしょれるのはジャンプだけという話になる。
あと、codegen.cも少し修正しておく。scope_finish関数の最後に以下のコードを追加する。
{
int i, count = 0;
for (i = 0; i < irep->ilen; i++) {
switch(GET_OPCODE(irep->iseq[i])) {
case OP_MOVE:
count++;
if (count > 4) {
irep->iseq[i - 4] = MKOP_AB(OP_MOVE4, GETARG_A(irep->iseq[i - 4]), GETARG_B(irep->iseq[i - 4]));
count = 4;
}
break;
default:
switch(count) {
case 4:
irep->iseq[i-4] = MKOP_AB(OP_MOVE4, GETARG_A(irep->iseq[i-4]), GETARG_B(irep->iseq[i-4]));
case 3:
irep->iseq[i-3] = MKOP_AB(OP_MOVE3, GETARG_A(irep->iseq[i-3]), GETARG_B(irep->iseq[i-3]));
case 2:
irep->iseq[i-2] = MKOP_AB(OP_MOVE2, GETARG_A(irep->iseq[i-2]), GETARG_B(irep->iseq[i-2]));
}
count = 0;
break;
}
}
}
強引に命令列を検索して連続したOP_MOVEを置き換える。ここでもフォールスルーが大活躍。
結果
あと、まあ、codedump.cも追加命令に対応するようにちょっとだけ直して、これで--verbose付きで実行した結果、命令列はこのようになり、
irep 018E51B0 nregs=5 nlocals=4 pools=0 syms=0 reps=0
file: test.rb
4 000 OP_LOADI R1 1 ; R1:a
5 001 OP_LOADI R2 2 ; R2:b
6 002 OP_LOADI R3 3 ; R3:c
7 003 OP_MOVE4 R1 R2 ; R1:a R2:b
8 004 OP_MOVE4 R2 R3 ; R2:b R3:c
9 005 OP_MOVE4 R1 R2 ; R1:a R2:b
10 006 OP_MOVE3 R2 R3 ; R2:b R3:c
11 007 OP_MOVE2 R4 R2 ; R2:b
11 008 OP_MOVE R1 R4 ; R1:a
11 009 OP_RETURN R4 return 時間はこのようになった。
9.361417
極端なベンチマークで5%ちょいの改善。ディスパッチの負荷というのは実際には実行時間のほんの一部なのだなあ。確実に存在していて地味に時間を食っているというのがよろしくないイメージの原因か。全体的にはtimesメソッドの処理とかブロック呼び出しとかが食ってるのかもしれん。よくわからん。
ちなみにbm_ao_render.rbの実行時間計測では効果を全く検出できなかったので、実際にはバーストOP_MOVEに価値は無いだろう。思ったほどOP_MOVEは連続しないようだ。数だけは多いのだが。
mrubyのcodegenは書かれたコードの順に愚直に生成するから、例えばOP_MOVE/OP_LOADI/OP_MOVEと並んでいた場合は並べ替えても意味が変わらない(こともある)ので可能ならば並べ替えてしまうようにすればバーストOP_MOVEの効果が上がるかもしれない。ていうか生成後の命令列を並べ替えたり再構成したりする最適化(在りし日のWatcomOptimizerが思い出される)で実行性能を上げることできそうなので、実行性能が欲しい人向けのmrbgemsとしてそういうのがあってもいいのかもしれない。前に考えてみたこともあるが、実際どのようにすれば命令が減って速くなるのかというのはよくわからなかった。
