コードジェネレータとwhileアルゴリズム
最近mrubyをいじって遊んでいるわけだが、mrubyを気合入れて速くするぜ貢献するぜ、という感じではなくて、どのように変更を加えたらどのぐらい速度が変わるのか、を色々試している感じ。だからとても取り込まれそうにない修正もするし、すぐにでも取り込めそうな修正もする(かもしれない)。まあ、結果として有効な手法が見えてこれば、その方向にパワーをかけるというのはありかもしれない。
今回はwhileを書いたときのコード生成に関して。
昨日こんなコードをためした。
class Numeric def times(&block) i = 0 while(i < self) block.call(i) i += 1 end self end end from = Time.now 10000000.times do end to = Time.now p to-from
このコードが出力する命令列はこのような感じだった(times内)
irep 150 nregs=6 nlocals=4 pools=0 syms=3 000 OP_ENTER 0:0:0:0:0:0:1 001 OP_LOADI R2 0 002 OP_MOVE R4 R2 003 OP_LOADSELF R5 004 OP_LOADNIL R6 005 OP_LT R4 :< 1 006 OP_JMPNOT R4 017 007 OP_MOVE R4 R1 008 OP_MOVE R5 R2 009 OP_LOADNIL R6 010 OP_SEND R4 :call 1 011 OP_MOVE R4 R2 012 OP_LOADI R5 1 013 OP_LOADNIL R6 014 OP_ADD R4 :+ 1 015 OP_MOVE R2 R4 016 OP_JMP 002 017 OP_LOADSELF R4 018 OP_RETURN R4
この命令をじっと眺めていると、このようなアルゴリズムになっているのが見えてくる。
i = 0
:label_a
unless i < 1000000
goto :label_b
endif
i = i + 1
goto label_a
:label_b
return self
まあ、見たままwhileの動きだ。が、whileはこのように書くほうが速い。
i = 0
goto :label_b
:label_a
i = i + 1
:label_b
if i < 1000000
goto :label_a
endif
return self
なぜかというと、上のコードはunlessの際に偽だったら最後に飛ぶためのコードが出力されるからだ。下のコードは真だったら戻るジャンプになってループ用のジャンプと共有できる。goto1個ぶん違う。微々たるものだが。
せっかくなのでコードジェネレータを修正してみよう。codegen.cの該当部分はここ。
case NODE_WHILE:
{
struct loopinfo *lp = loop_push(s, LOOP_NORMAL);
lp->pc1 = new_label(s);
codegen(s, tree->car, VAL);
pop();
lp->pc2 = new_label(s);
genop(s, MKOP_AsBx(OP_JMPNOT, cursp(), 0));
codegen(s, tree->cdr, NOVAL);
genop(s, MKOP_sBx(OP_JMP, lp->pc1 - s->pc));
dispatch(s, lp->pc2);
loop_pop(s, val);
}
break;ここで使われているsは命令列の現在の出力先をあらわす構造体へのポインタ。lpのpc1やpc2はラベルとしてアドレスを保存できる。codegen()はこのコードが書かれている関数自身で、現在の位置にtreeの命令列を出力する。genopは単体の命令の生成だ。
動きとしては以下のような感じに読める。
・はじめの位置をpc1に保存する。
・tree->carには判定の構文木が入っているので、まずそれを生成する。
・OP_JMPNOTの位置をpc2に保存する。
・↑↑の判定命令の結果を判定して分岐するためのOP_JMPNOTを生成する。
ここで最後の引数の0は本来はジャンプ先への相対位置が入るのだが、この時点ではそれが不明なので0にしてある。直前のnew_label()でpc2にこの命令の位置を保存して、後ろのほうで飛び先アドレスが確定した時点でdispatch()を呼んでこの0のところに相対アドレスを書き込む。この飛び先はwhileを抜けた次の命令となる。
・tree->cdrはwhileの中身なのでそれを生成する。
・pc1から現在の位置を引いたぶん(pc1に戻るための相対アドレス)ジャンプするOP_JMPを生成する。
・dispatch()でOP_JMPNOTを完成させる。
このコードを次のようになおす。
case NODE_WHILE:
{
struct loopinfo *lp = loop_push(s, LOOP_NORMAL);
lp->pc1 = new_label(s);
genop(s, MKOP_sBx(OP_JMP, 0));
lp->pc2 = new_label(s);
codegen(s, tree->cdr, NOVAL);
dispatch(s, lp->pc1);
codegen(s, tree->car, VAL);
pop();
genop(s, MKOP_AsBx(OP_JMPIF, cursp(), lp->pc2 - s->pc));
loop_pop(s, val);
}
break;しょっぱなJMPするのでpc1にアドレス保存と飛び先0でJMPを生成。ループ時の飛び先はJMP直後になるのでそこでpc2を保存。tree->cdr(whileの中身)の命令を生成してからアドレスをpc1にdispatch()で書き込み、tree->car(判定式)を生成してOP_JMPIFでpc2に戻る。
この修正でVM命令列はこのようになる。
irep 150 nregs=6 nlocals=4 pools=0 syms=3 000 OP_ENTER 0:0:0:0:0:0:1 001 OP_LOADI R2 0 002 OP_JMP 012 003 OP_MOVE R4 R1 004 OP_MOVE R5 R2 005 OP_LOADNIL R6 006 OP_SEND R4 :call 1 007 OP_MOVE R4 R2 008 OP_LOADI R5 1 009 OP_LOADNIL R6 010 OP_ADD R4 :+ 1 011 OP_MOVE R2 R4 012 OP_MOVE R4 R2 013 OP_LOADSELF R5 014 OP_LOADNIL R6 015 OP_LT R4 :< 1 016 OP_JMPIF R4 003 017 OP_LOADSELF R4 018 OP_RETURN R4
全体の命令数は変わらないが、ループの中の命令は1個減った。011と012のOP_MOVEが無駄なことをしているように見えるが、002のOP_JMPから飛び込むのが012なのでこれは必要な処理だ。
この2つを動かして比較してみる。
D:\test>mruby test.rb 2.515625 D:\test>mruby_test test.rb 2.453125
元のほうの数字が昨日と若干違うのは誤差なのだが、誤差範囲にとどまりそうな勢いであまり変わらない。
ループ内の命令が減ったのは事実なので速くなったのはなったんじゃないかなと思う。
