ダイレクトスレッデッドコード化

速いのかどうなのかさっぱりわからないのでイマイチ自慢できないのだが、せっかくそれっぽく動いているので公開。
とりあえずswitch-case動かすようにコンパイルすると動かなくなるようなひどい修正。でも誰も困らない気がするのでそこまでやってない。このような感じに実装してみました、というサンプル的に。

https://github.com/mirichi/mruby/tree/dt

ちなみに初github。使い方がよくわからないので手探り的にやってみた。まあ、そうそう変なことにはならないんじゃないかなあ、と楽観的に。
今回はこのダイレクトスレッデッドコード化の解説。


コード自体は上のリンクに飛んでcommitsってところを押して、一番上のdirect threaded codeてコミット内容を見れば出てくる。ので、ここでは部分的に切り出すだけの感じにしておこう。
ダイレクトスレッデッドコードとは何か、というのは3日の記事にチラっと書いたが、命令列から各種命令を判定してその実行コードへ飛ぶときのやり方の一つだ。
・switch-case:命令の番号で分岐する。しょぼいコンパイラだとifが並ぶ。テーブルジャンプに変換されると速くなるが、分岐するためのコードが1つにまとまっている。
・スレッデッドコード:命令の番号で分岐する。命令の番号とジャンプ先アドレスの配列を自分で作って(switch-caseでコンパイラが作るテーブルと同じもの)、各命令の最後でgotoする。switch-caseと比べると共有のジャンプコードに飛ぶ処理が不要になる。
・ダイレクトスレッデッドコード:命令列に対応するアドレスをプログラムの全命令分保持する。次に実行する命令のアドレスを取得して、命令の最後にgotoする。スレッデッドコードと比べると変換テーブルの参照が不要になる。

この分類で言うとmrubyはスレッデッドコードなので、ダイレクトスレッデッドコードを実装してみた、というわけだ。

どういう思想で実装しているかを順番に。
いきなり核心部分。

-#define NEXT i=*++pc; goto *optable[GET_OPCODE(i)]
-#define JUMP i=*pc; goto *optable[GET_OPCODE(i)]
+#define NEXT pc++; i=pc->iseq; asm(""); goto *(pc->addr)
+#define JUMP i=pc->iseq;asm(""); goto *(pc->addr)

元は命令コードをpcから取得して、それをGET_OPCODEしてoptableを参照していた。pcはmrb_codeという命令を表す型のポインタだったのだが、これをmrb_dtcodeというダイレクトスレッデッド用の構造体のポインタに変更している。中身は

+typedef struct mrb_dtcode {
+  mrb_code iseq;
+  void *addr;
+} mrb_dtcode;

という感じで構造体1つに命令1つと対応するアドレスが入っている。上のマクロではその命令を取り出してiに、アドレスを取り出して命令の実行コードに飛ぶ感じになっている。これによりNEXTルーチンのアセンブラが短くなる。ついでにインラインアセンブラをはさんで共有化を防いでおいた。
以下のコードが(NEXT部分)

	addl	$4, -764(%ebp)
	movl	-764(%ebp), %edi
	movl	(%edi), %ebx
	movl	%ebx, %eax
	andl	$127, %eax
	movl	_optable.3821(,%eax,4), %eax
	jmp	*%eax

このようになる。

	addl	$8, -764(%ebp)
	movl	-764(%ebp), %eax
	movl	(%eax), %ebx
	movl	4(%eax), %eax
	jmp	*%eax

arena_aiの代入を消したときは3命令減ったので、それよりかは改善率は劣る。苦労したわりにはしょぼい。
mrb_dtcodeそのものはどこに持っているかというと、irepの中だ。

typedef struct mrb_irep {
  int idx;

  int flags;
  int nlocals;
  int nregs;

  mrb_code *iseq;
  mrb_value *pool;
  mrb_sym *syms;
  mrb_dtcode *dtcode; //←ココ!

  int ilen, plen, slen;
} mrb_irep;

で、irepを生成するあちこちにdtcodeをNULLで初期化するように仕込んでおいた。irepを生成するタイミングでdtcodeは作っておらず、実行する際にこれがNULLだったら変換テーブルを参照してdtcode列を作っている。なぜかというと、dtcodeが持つアドレスは命令コードのラベルで、ラベルはそれが存在する関数内でしか参照できないためだ。
変換するロジックはこれ。

+#define MAKE_DTCODE \
+  if (!irep->dtcode) {\
+    int index;\
+    irep->dtcode = (mrb_dtcode *)mrb_malloc(mrb, sizeof(mrb_dtcode) * irep->ilen);\
+    for(index = 0; index < irep->ilen; index++) {\
+      irep->dtcode[index].addr = optable[GET_OPCODE(irep->iseq[index])];\
+      irep->dtcode[index].iseq = irep->iseq[index];\
+    }\
+  }

動的にメモリを確保してしまう。どうせいつ確保しても処理量合計は同じだからどこでやっても問題は無い。irepはブロック単位になっているし、ブロック呼び出し時にこれをやるようにすれば動かないブロックについては変換されないのでどちらかというとこのほうが効率が良い。
あと、ここでiseqもコピーしている。iseqはirepの中にあるからコピーする必要は特にないのだが、そもそもpcが数値じゃなくポインタだから、別のポインタになると計算が増えてダイレクトスレッデッドコードの利点がなくなってしまう。メモリ効率、dtcode生成効率で言うとiseqの型を変えてその中に書き込むようにしたほうがよいが、iseq生成側をいじるのが面倒だった。

あとはこのコードを動かすタイミングだ。基本的にはmrb_runの頭。でもそこだけだとトップレベルのiseqしか変換されないから、各種OP_SEND系のブロックを呼び出す命令時の、VM命令を呼ぶ処理の中にいくつか入れてある。
もともとOP_ENTERでやればいいんじゃないかと考えていたのだが、実装してみたら動かなかった。理由はOP_ENTER呼び出し時にはまだOP_ENTERのアドレスがirep->dtcodeに入っていないからだ。アホかと。あと引数の無いブロックはOP_ENTERが生成されないのでそれもダメだった。デュアルアホかと。

んで、これが実際に速いのかというと、うちで動かした限りぜんぜん速くない。ほとんど変わらないというか、ちょっと遅いぐらい。この間から悩んでいる問題だ。IntelのCPUで動かしたら速くなるのか、どうなのか。誰か試した人がいたら結果を教えてもらえたら嬉しいかも。