mrubyのop_enter_optimizeの話
一昨日、mrubyにNaN boxingが実装された。
https://github.com/mruby/mruby/commit/7d02df3016b0c6eb3f4ee945198772cf4ebca3fa
前に俺が試したナンチャッテNaN boxingではttが32bitのためにMRUBY_OBJECT_HEADERが大きくなっていたり、その他未解決の問題がいっぱいあったのだが、その辺きちんとされているようだ。さすがだ。
AOベンチを動かしたらうちの環境で6分8秒→4分59秒となり、大幅な高速化となった。初めは7分台だったのだからずいぶん速くなったもんだ。
ただ、デフォルトではOFFになっているので試してみる人は気を付けよう。
さて、それとは別に昨日、OP_ENTER命令の実行速度をちょっぴり改善してpull requestしてみたところ、無事取り込まれた。
https://github.com/mruby/mruby/commit/2900b01a3dfe8cbc6fe8e96446d8a1c138379462
修正内容は非常にしょぼいがそれなりに効果がある。NaN boxing後のAOベンチが4分59秒→4分44秒になるぐらいには。
今回はどういう経緯でOP_ENTERに目をつけたのか、と、それにまつわるアレコレについて。
１．命令の実行回数
VM命令はgotoで飛び回っているので、どれにどれだけの時間がかかっているのか、というのはプロファイラでも取得するのは難しい。難しいというかできるのか？って感じ。でも命令ごとの実行回数ならちょっと細工すれば取得可能じゃないかな、ということで試してみた。
vm.cに
int ins_count[256]; //#define CASE(op) L_ ## op: #define CASE(op) L_ ## op:\ ins_count[op]++;
こんなようなコード(だったと思う)を突っ込んで、mruby.cで中身を初期化したり結果を出力したり。長くなるのでこっちは割愛。
これでAOベンチを動かして結果を取ってソートしてみると以下のようになった。ちょっと長いので0回の命令は省いた。
total = 8697972919 OP_MOVE = 1559886083 (17.93%) OP_LOADNIL = 1161434427 (13.35%) OP_SEND = 1158971928 (13.32%) OP_GETIV = 1046973951 (12.04%) OP_RETURN = 808442493 (9.29%) OP_ENTER = 808442486 (9.29%) OP_MUL = 438549513 (5.04%) OP_ADD = 253658225 (2.92%) OP_SETIV = 248418877 (2.86%) OP_LOADL = 193142608 (2.22%) OP_GETCONST = 183613123 (2.11%) OP_LOADI = 180222648 (2.07%) OP_SUB = 164566012 (1.89%) OP_GETUPVAR = 97118423 (1.12%) OP_JMPNOT = 82066784 (0.94%) OP_SETCV = 72887812 (0.84%) OP_GETCV = 72887808 (0.84%) OP_GT = 41336947 (0.48%) OP_DIV = 33577822 (0.39%) OP_LT = 33508613 (0.39%) OP_LOADSELF = 16772745 (0.19%) OP_JMPIF = 12756388 (0.15%) OP_CALL = 10708856 (0.12%) OP_LOADF = 9373120 (0.11%) OP_JMP = 3518298 (0.04%) OP_SETUPVAR = 1590549 (0.02%) OP_LOADT = 1478313 (0.02%) OP_LAMBDA = 1478135 (0.02%) OP_ARRAY = 196611 (0.00%) OP_ARYCAT = 196611 (0.00%) OP_STRING = 196611 (0.00%) OP_METHOD = 39 (0.00%) OP_TCLASS = 38 (0.00%) OP_EXEC = 7 (0.00%) OP_SETCONST = 6 (0.00%) OP_CLASS = 6 (0.00%) OP_MODULE = 1 (0.00%) OP_SCLASS = 1 (0.00%) OP_STOP = 1 (0.00%)
桁がとんでもないことになっている。まあ、AOベンチは負荷100%でぶんまわすモノだから多くもなろう。これを見ながら考える。
OP_MOVEがとにかく多い。OP_LOADNILも多いが、これら2つはVM命令をいじって高速化がほぼ不可能なので、どうにかするならコードジェネレータ側で数自体を減らすしかない。
OP_SENDとOP_GETIVはハッシュ計算をする。その部分の高速化はそっち方面に強い人に頑張ってもらうしかない。インラインキャッシュにも期待がかかる。
OP_RETURNとOP_ENTERはほぼ同数で、メソッド呼び出しの最初と最後で1セットとなっている。微妙にOP_RETURNのほうが多いのはよくわからないが、特殊なパスがあるのかしらん。
ここまでで全体の75%。
四則演算命令は個別にするのもあまり意味が無い。4つ全部足すと8.9億回となって5位に食い込む。
で、まあ、このあたりでちょっといじって改善できそうな命令はどれかな、というと、OP_ENTERしか無かったわけだ。
２．OP_ENTERの修正と考え方
OP_ENTERのコードはこのあいだ載せたが、もう一度。
CASE(OP_ENTER) {
/* Ax arg setup according to flags (24=5:5:1:5:5:1:1) */
/* number of optional arguments times OP_JMP should follow */
int ax = GETARG_Ax(i);
int m1 = (ax>>18)&0x1f;
int o = (ax>>13)&0x1f;
int r = (ax>>12)&0x1;
int m2 = (ax>>7)&0x1f;
/* unused
int k = (ax>>2)&0x1f;
int kd = (ax>>1)&0x1;
int b = (ax>>0)& 0x1;
*/
int argc = mrb->ci->argc;
mrb_value *argv = regs+1;
int len = m1 + o + r + m2;
mrb_value *blk = &argv[argc < 0 ? 1 : argc];
if (argc < 0) {
struct RArray *ary = mrb_ary_ptr(regs[1]);
argv = ary->ptr;
argc = ary->len;
mrb_gc_protect(mrb, regs[1]);
}
if (mrb->ci->proc && MRB_PROC_STRICT_P(mrb->ci->proc)) {
if (argc >= 0) {
if (argc < m1 + m2 || (r == 0 && argc > len)) {
argnum_error(mrb, m1+m2);
goto L_RAISE;
}
}
}
else if (len > 1 && argc == 1 && argv[0].tt == MRB_TT_ARRAY) {
argc = mrb_ary_ptr(argv[0])->len;
argv = mrb_ary_ptr(argv[0])->ptr;
}
mrb->ci->argc = len;
if (argc < len) {
regs[len+1] = *blk; /* move block */
memmove(®s[1], argv, sizeof(mrb_value)*(argc-m2)); /* m1 + o */
memmove(®s[len-m2+1], &argv[argc-m2], sizeof(mrb_value)*m2); /* m2 */
if (r) { /* r */
regs[m1+o+1] = mrb_ary_new_capa(mrb, 0);
}
if (o == 0) {
pc++;
}
else {
pc += argc - m1 - m2 + 1;
}
}
else {
memmove(®s[1], argv, sizeof(mrb_value)*(m1+o)); /* m1 + o */
if (r) { /* r */
regs[m1+o+1] = mrb_ary_new_elts(mrb, argc-m1-o-m2, argv+m1+o);
}
memmove(®s[m1+o+r+1], &argv[argc-m2], sizeof(mrb_value)*m2);
regs[len+1] = *blk; /* move block */
pc += o + 1;
}
JUMP;
}ざっとコードを眺めてみると、100%のフローでmemmoveを2回実行する。引数の領域のレジスタをコピーしているようだが、通常、レジスタに積まれたレシーバ/引数/ブロックはそのままその場所でメソッドのself/ローカル変数/ブロックとして使われるはずだ。何のためにレジスタのコピーをしているのか。
転送元のargvという変数がキーで、それは最初はregs+1なので転送先と同じになっている。これを書き換える条件は、引数が配列で渡されて展開されるパターンだ。つまり、それ以外の場合ではregs+1とargvは一致しているので、memmoveを呼び出す必要は無い。また、もう一つのmemmoveは変数m2の値がコピーのサイズになっている。これも0ならmemmoveする必要は無い。
pull requestした修正はこれらをifで呼ばないようにしただけだ。コストとしてはmemmoveの処理(同じアドレスならコピーしないとかなってるかもしれないけど)と、引数で渡すアドレスの計算をカットすることができる。memmoveが実行される条件にヒットすることはほとんど無いと個人的には思う。
３．マイナーな引数
ところで、2つ目のmemmoveに使われているm2という変数、これは一体なんだろう。
このあいだの記事で見たのは通常引数のm1とオプション引数のoと、ブロック引数(変数は未使用)だけだった。他にrとm2が使われている。ちなみにブロック引数の変数が使われないのは、Rubyはメソッドの仮引数で明示的に指定していなくても暗黙的にブロックを受け取ることができるためだ。無条件で受け取らないといけないし、だから逆にOP_SENDの前にOP_LOADNILが必要となる。
で、rとm2なのだが、これはCode Reading Wikiさまを見るとヒントがある。
http://www.dzeta.jp/~junjis/code_reading/index.php?mruby%2F%BC%C2%B9%D4%A5%B3%A1%BC%A5%C9%C0%B8%C0%AE%A4%F2%C6%C9%A4%E0
どうやら残余引数とポスト引数らしい。残余引数はrest引数とも呼ばれる。残余引数については検索すると色々出てくる。ようは仮引数に*付で定義した引数で、余ったぶんを全部配列に突っ込んでくれる引数のことだ。
ではポスト引数とは何か。
これが困ったことに、検索しても出てこない。そんな仕様あるのか？っていうレベル。るりま(http://doc.ruby-lang.org/ja/1.9.3/doc/spec=2fdef.html#method)を見ると(後述の post 引数を除く)と書いてあるのに後述が無い。ぎりぎり文法の中にpostという記述がある。でもこれだけではよくわからない。文法を見るのは苦手なのだ。
色々探してたらruby-coreのMatzのポスト(http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-core/40188)が検索にひっかかった。Ruby2.0の話題で、元発言は遠藤さん。引用しよう。
- 引数の順番はこれでよいか？
def foo(
a, b, c, # mandatory arguments
opt = 1, # optional arguments
*rest, # rest argument
x, y, z, # post mandatory arguments
k1: 1, k2:2, # keyword arguments
**kh, # keyword rest argument
&blk # block argument
)
これだ。post mandatory arguments。つまりmrubyではこういう感じに。
def foo(a, b = 100, *c, d, e, &f) p a # mandatory arguments p b # optional arguments p c # rest argument p d # post mandatory arguments p e # keyword rest argument p f # block argument end foo(1, 2, 3, 4, 5, :hoge=>nil, :fuga=>"piyo") {} #=> 1 2 [3, 4] 5 {:hoge=>nil, :fuga=>"piyo"} #<Proc:0x637d3c>
rest引数は余りが入るが、post引数はrest引数の後ろにあって、後ろの必須部分の引数を表すのだ。引数の数を減らすとrest引数、optional引数の順に省略される。
foo(1, 2, 3, :hoge=>nil, :fuga=>"piyo") {} #=> 1 2 [] 3 {:hoge=>nil, :fuga=>"piyo"} #<Proc:0x637968> foo(1, 2, :hoge=>nil, :fuga=>"piyo") {} #=> 1 100 [] 2 {:hoge=>nil, :fuga=>"piyo"} #<Proc:0x637690>
更に減らすとArgumentErrorになる。
うまく使えば真ん中を省略可能引数にしたメソッドが作れる。DXRubyでいうと
Window.draw(x, y [,z], image)
みたいなことが可能になって、これは非常に面白い。わけがわからない。こんなメソッド誰かに提案されてもたぶん採用しない。っていうかどこかで使われているんだろうか・・・。
４．OP_ENTERを更に。
OP_ENTERはもう一歩進むことができる。OP_ENTERの後ろに続くOP_JMPの省略という作戦だ。
mrubyはディスパッチの負荷が結構高いと個人的には見ていて、だからアレコレと対策を考えてきたのだが、いまのところいい案が無い。完全に実力不足だ。しかしディスパッチを高速化する代わりに、命令の実行そのものを減らせばディスパッチ自体が減る。
OP_ENTERはoptional引数が存在した場合にOP_JMPにpcを進めるが、そこにOP_JMPが存在することが確定しているのだから、命令コードからジャンプ先を取得して直接飛んでしまえば命令の実行がカットできる。
こんな感じだ。飛び先がOP_JMPじゃない、という可能性があるのでifが必要となった。
else {
pc += argc - m1 - m2 + 1;
if (GET_OPCODE(*pc) == OP_JMP) {
pc += GETARG_sBx(*pc);
}
}しかしこのコードは実行してみるとぜんぜん速くない。Rubyのプログラムにおいて、optional引数が無いメソッド呼び出しが多いというのと、すべての場合に影響するオーバーヘッドがあるということが原因だろう。
それ以前に、OP_JMPを生成するのにOP_JMPとして実行しないでOP_ENTERの処理のネタにしてしまうというのがトリッキーすぎてよろしくない。もし速かったとしても提案しにくい。程度によるが。
まあ、そういう手を使って最適化するのはまだ先の話だと思う。
