Cの演算子とビット演算関連の最適化
mrubyの最新版に実行速度改善の修正が入った。arena_aiを必要なところのみに入れる、while最適化、無駄なOP_LOADNILの削除、だ。
これにより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_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_LT R4 :< 1 015 OP_JMPIF R4 003 016 OP_LOADSELF R4 017 OP_RETURN R4
OP_ADDの前にOP_LOADNILが出ているが、OP_LTからは消えた。なぜOP_ADDの前に出ているかというと、修正が入ったのはコードジェネレータのNODE_CALLだけでNODE_OP_ASGNは元のままだからだ。従って、i+=1と書くとOP_LOADNILが出力されるが、i = i + 1と書くと出力されない、ということになる。まあ、指摘して修正を求めるほどの問題ではないと思う。いずれGitを勉強したらなおしてPullRequestする。アカウントだけはあるんだけどね。
なお、実行速度は
D:\test>mruby test.rb 2.03125
という感じに劇的に速くなった。すばらしい。
今回は命令コードのデコードに関する話。
mrubyのopcode.hにこのようなコードがある。
/* instructions OP:A:B:C = 7:9:9:7 (32 bits) */ /* OP:A:Bx = 7:9:16 */ /* OP:Ax = 7:25 */ #define GET_OPCODE(i) ((int)(((mrb_code)(i)) & 0x7f)) #define GETARG_A(i) ((int)((((mrb_code)(i)) >> 23) & 0x1ff)) #define GETARG_B(i) ((int)((((mrb_code)(i)) >> 14) & 0x1ff)) #define GETARG_C(i) ((int)((((mrb_code)(i)) >> 7) & 0x7f))
mrubyの命令列セットは32bit長で、命令を表すOP以外はその種類によりコードの持ち方が変わる。コメントにあるとおりだ。このマクロは命令バイナリからOP:A:B:Cパターンの命令とオペランドを取得するためのものである。
だが、マクロ定義を見ているとコメントと何かが違うように見える。正しくは
/* instructions A:B:C:OP = 9:9:7:7 (32 bits) */ /* A:Bx:OP = 9:16:7 */ /* Ax:OP = 25:7 */
なのではなかろうか。
なんしか、ビットの一部分を右シフトで最下位に寄せて、論理積によるマスクで上位を0に倒して32/64bitの値として使えるようにしているわけだ。
この中でOPにあたる部分はオペランドよりも利用率が高い。だからシフトがいらない最下位に後から移動したのだが、コメントを変え忘れている。もしくは、なんらかの理由で変えていない。という感じではないかと想像している。
ところで最上位であればシフト時に上位ビットが0になってマスクがいらないのではないか、とか考える人もいるかもしれないが、Cの>>演算子は符号拡張されるかどうかは処理系依存になっているので最上位ビットが0固定でなければマスクは必要となる。Cの都合で計算が増えるという話で、まことに遺憾である。
まあとにかく最下位ビットに最も使うコードを割り当てるのは理にかなっている。という話だ。
アセンブラのコードはこのようになっている。最新のmrubyのOP_MOVEより。
L24: movl %ebx, %eax shrl $23, %eax sall $4, %eax addl -768(%ebp), %eax shrl $10, %ebx andl $8176, %ebx movl -768(%ebp), %edx addl %ebx, %edx movb 8(%edx), %cl movb %cl, 8(%eax) movl 4(%edx), %ecx movl (%edx), %edx movl %edx, (%eax) movl %ecx, 4(%eax) addl $4, -764(%ebp) movl -764(%ebp), %eax movl (%eax), %ebx movl %ebx, %eax andl $127, %eax movl _optable.3821(,%eax,4), %eax jmp *%eax
下から3行目にいかにもそれっぽいandl命令がいる。32bitで取ってきてマスクしているわけだ。
ところでこのOPのマスク。7bitなので0x7fをandしているが、あと1bitどうにかなれば1byteのメモリリードになって速くなったりしないのだろうか。
っつーのが今回のお題である。どうにかしてみよう。
まず、vm.cの#ifndef DIRECT_THREADEDの#elseに次のコードを追加する。
#undef GET_OPCODE #define GET_OPCODE(i) ((int)(((mrb_code)(i)) & 0xff))
0xffでマスクする処理はGCCにより1byteリードに変換される可能性が高い。
次に、optableを拡張する。
こうだ。
static void *optable[] = { &&L_OP_NOP, &&L_OP_MOVE, &&L_OP_LOADL, &&L_OP_LOADI, &&L_OP_LOADSYM, &&L_OP_LOADNIL, &&L_OP_LOADSELF, &&L_OP_LOADT, &&L_OP_LOADF, &&L_OP_GETGLOBAL, &&L_OP_SETGLOBAL, &&L_OP_GETSPECIAL, &&L_OP_SETSPECIAL, &&L_OP_GETIV, &&L_OP_SETIV, &&L_OP_GETCV, &&L_OP_SETCV, &&L_OP_GETCONST, &&L_OP_SETCONST, &&L_OP_GETMCNST, &&L_OP_SETMCNST, &&L_OP_GETUPVAR, &&L_OP_SETUPVAR, &&L_OP_JMP, &&L_OP_JMPIF, &&L_OP_JMPNOT, &&L_OP_ONERR, &&L_OP_RESCUE, &&L_OP_POPERR, &&L_OP_RAISE, &&L_OP_EPUSH, &&L_OP_EPOP, &&L_OP_SEND, &&L_OP_FSEND, &&L_OP_VSEND, &&L_OP_CALL, &&L_OP_SUPER, &&L_OP_ARGARY, &&L_OP_ENTER, &&L_OP_KARG, &&L_OP_KDICT, &&L_OP_RETURN, &&L_OP_TAILCALL, &&L_OP_BLKPUSH, &&L_OP_ADD, &&L_OP_ADDI, &&L_OP_SUB, &&L_OP_SUBI, &&L_OP_MUL, &&L_OP_DIV, &&L_OP_EQ, &&L_OP_LT, &&L_OP_LE, &&L_OP_GT, &&L_OP_GE, &&L_OP_ARRAY, &&L_OP_ARYCAT, &&L_OP_ARYPUSH, &&L_OP_AREF, &&L_OP_ASET, &&L_OP_APOST, &&L_OP_STRING, &&L_OP_STRCAT, &&L_OP_HASH, &&L_OP_LAMBDA, &&L_OP_RANGE, &&L_OP_OCLASS, &&L_OP_CLASS, &&L_OP_MODULE, &&L_OP_EXEC, &&L_OP_METHOD, &&L_OP_SCLASS, &&L_OP_TCLASS, &&L_OP_DEBUG, &&L_OP_STOP, &&L_OP_ERR, // もともとはここまで(76個) 0,0,0,0, 0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0, // ここまでで128個 &&L_OP_NOP, &&L_OP_MOVE, &&L_OP_LOADL, &&L_OP_LOADI, &&L_OP_LOADSYM, &&L_OP_LOADNIL, &&L_OP_LOADSELF, &&L_OP_LOADT, &&L_OP_LOADF, &&L_OP_GETGLOBAL, &&L_OP_SETGLOBAL, &&L_OP_GETSPECIAL, &&L_OP_SETSPECIAL, &&L_OP_GETIV, &&L_OP_SETIV, &&L_OP_GETCV, &&L_OP_SETCV, &&L_OP_GETCONST, &&L_OP_SETCONST, &&L_OP_GETMCNST, &&L_OP_SETMCNST, &&L_OP_GETUPVAR, &&L_OP_SETUPVAR, &&L_OP_JMP, &&L_OP_JMPIF, &&L_OP_JMPNOT, &&L_OP_ONERR, &&L_OP_RESCUE, &&L_OP_POPERR, &&L_OP_RAISE, &&L_OP_EPUSH, &&L_OP_EPOP, &&L_OP_SEND, &&L_OP_FSEND, &&L_OP_VSEND, &&L_OP_CALL, &&L_OP_SUPER, &&L_OP_ARGARY, &&L_OP_ENTER, &&L_OP_KARG, &&L_OP_KDICT, &&L_OP_RETURN, &&L_OP_TAILCALL, &&L_OP_BLKPUSH, &&L_OP_ADD, &&L_OP_ADDI, &&L_OP_SUB, &&L_OP_SUBI, &&L_OP_MUL, &&L_OP_DIV, &&L_OP_EQ, &&L_OP_LT, &&L_OP_LE, &&L_OP_GT, &&L_OP_GE, &&L_OP_ARRAY, &&L_OP_ARYCAT, &&L_OP_ARYPUSH, &&L_OP_AREF, &&L_OP_ASET, &&L_OP_APOST, &&L_OP_STRING, &&L_OP_STRCAT, &&L_OP_HASH, &&L_OP_LAMBDA, &&L_OP_RANGE, &&L_OP_OCLASS, &&L_OP_CLASS, &&L_OP_MODULE, &&L_OP_EXEC, &&L_OP_METHOD, &&L_OP_SCLASS, &&L_OP_TCLASS, &&L_OP_DEBUG, &&L_OP_STOP, &&L_OP_ERR, // 128+76個 };
つまり、OPを8bitで取得するが、最上位の1bitは別のオペランドの最下位bitが入っているため実際は不定の値であるので、optableに最上位bitが0の場合と1の場合両方を突っ込んでしまおう、という強引な理屈である。
結果として、OP_MOVEのアセンブラコードはこのように変わる。
L24: movl %ebx, %eax shrl $23, %eax sall $4, %eax addl -768(%ebp), %eax shrl $10, %ebx andl $8176, %ebx movl -768(%ebp), %edx addl %ebx, %edx movb 8(%edx), %cl movb %cl, 8(%eax) movl 4(%edx), %ecx movl (%edx), %edx movl %edx, (%eax) movl %ecx, 4(%eax) addl $4, -764(%ebp) movl -764(%ebp), %eax movl (%eax), %ebx movzbl %bl, %eax movl _optable.3821(,%eax,4), %eax jmp *%eax
下から4行目が消えて、下から3行目のandlがmovzblに変わった。movzblは1byteレジスタのデータを0拡張しながら32bitレジスタに転送する命令だ。と思う。見る限り効率は上がってそうだ。
D:\test>mruby_test test.rb 2.109375
遅くなってしまったorz
理由がさっぱりわからない。mrubyの最新版じゃないちょっと前のやつなら少し速くなっていたのだが。
まあ、この手の修正はそういったちょっとした修正で生死が分かれるようなきわどい話なので、こういう結果になるのも致し方ない。