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の最新版じゃないちょっと前のやつなら少し速くなっていたのだが。
まあ、この手の修正はそういったちょっとした修正で生死が分かれるようなきわどい話なので、こういう結果になるのも致し方ない。