Rubyist Magazine - YARV Maniacs 【第 3 回】 命令ディスパッチの高速化を読む (2)
Structured GOTO Programming World へようこそ！
前回はコンパイラさんのやってくれるswitch展開の妙技をobjdumpで眺めました。最適化オプションをつけていったらまたどんどん色々なことしてくわけですけどそれはYARV Maniacsとは逸れていくので割愛。コンパイラにできない最適化、スレッデッドコードをしてやります。
いきなりダイレクトスレッデッドコード化。先にできあがったソースコードを。
#include <stdio.h> #define STACK_SIZE 30000 #ifndef LOOPNUM #define LOOPNUM 100000 #endif typedef enum Instruction Instruction; typedef struct Code Code; enum Instruction { I_PUSH, I_POP, I_DUP, I_ADD, I_SUB, I_MUL, I_DIV, I_NOT, I_JUMP, I_IF, I_EQ, I_LT, I_GT, I_END }; struct Code { union { Instruction type; void *ptr; } inst; int value; }; int eval(Code program[], Code *program_end) { int stack[STACK_SIZE]; int stack_index = 0; int x, y; Code *pc = &program[0]; static void *table[] = { &&I_PUSH, &&I_POP, &&I_DUP, &&I_ADD, &&I_SUB, &&I_MUL, &&I_DIV, &&I_NOT, &&I_JUMP, &&I_IF, &&I_EQ, &&I_LT, &&I_GT, &&I_END }; for(;pc!=program_end;++pc) { pc->inst.ptr = table[pc->inst.type]; } pc = &program[0]; goto *pc->inst.ptr; I_PUSH: stack[stack_index++] = pc->value; ++pc; goto *pc->inst.ptr; I_POP: --stack_index; ++pc; goto *pc->inst.ptr; I_DUP: x = stack[stack_index-1]; stack[stack_index++] = x; ++pc; goto *pc->inst.ptr; I_ADD: x = stack[--stack_index]; stack[stack_index-1] += x; ++pc; goto *pc->inst.ptr; I_SUB: x = stack[--stack_index]; stack[stack_index-1] -= x; ++pc; goto *pc->inst.ptr; I_MUL: x = stack[--stack_index]; stack[stack_index-1] *= x; ++pc; goto *pc->inst.ptr; I_DIV: x = stack[--stack_index]; stack[stack_index-1] /= x; ++pc; goto *pc->inst.ptr; I_NOT: x = stack[stack_index-1]; stack[stack_index-1] = !x; ++pc; goto *pc->inst.ptr; I_JUMP: pc = &program[pc->value]; goto *pc->inst.ptr; I_IF: x = stack[--stack_index]; if(x) { pc = &program[pc->value]; } else { ++pc; } goto *pc->inst.ptr; I_EQ: x = stack[--stack_index]; y = stack[stack_index-1]; stack[stack_index-1] = x==y; ++pc; goto *pc->inst.ptr; I_LT: x = stack[--stack_index]; y = stack[stack_index-1]; stack[stack_index-1] = x<y; ++pc; goto *pc->inst.ptr; I_GT: x = stack[--stack_index]; y = stack[stack_index-1]; stack[stack_index-1] = x>y; ++pc; goto *pc->inst.ptr; I_END: return stack[0]; } int main(int argc, char **argv) { Code program[] = { {I_PUSH, 1}, {I_PUSH, 1}, {I_ADD, 0}, {I_DUP, 0}, {I_PUSH, LOOPNUM}, {I_GT, 0}, {I_IF, 1}, {I_END, 0} }; Code *program_end = &program[sizeof(program)/sizeof(Code)]; int result; result = eval(program, program_end); printf("%d\n", result); return 0; }
いいかげんに解説。
前回書いたVMの「プログラム」の定義は以下のようなものでした。
struct Code { Instruction inst; int value; } *program;
「命令」がstruct Codeで、「プログラム」は「命令」の列。じゃあ今回はダイレクトスレッデッドコードで命令の種類からジャンプ先ポインタに変換するのでこんな定義に。
struct Code { union { Instruction type; void *ptr; } inst; int value; };
変数名が気色悪いけどまあ勘弁してもらって。定義するときの「プログラム」はtypeとvalue、実行するときの「プログラム」はptrとvalue。
プログラムを終了を示す命令I_ENDを追加しました。それに従って与えるプログラムもちょっと変更。
なんか前回解説しなかった気がしますけど、valueを使わない命令(I_PUSH, I_JUMP, I_IF以外全部)においてvalueに入れる値に意味はありません。無駄ですけど気にしないことにしましょう。
「出力されるアセンブラ」のところに書いてるように、pcをintからCode*に変えました。
それにともないevalに渡すのはprogramと、の末端を示すポインタprogram_endに。
eval関数の中へ。
Code *pc = &program[0]; static void *table[] = { &&I_PUSH, &&I_POP, &&I_DUP, &&I_ADD, &&I_SUB, &&I_MUL, &&I_DIV, &&I_NOT, &&I_JUMP, &&I_IF, &&I_EQ, &&I_LT, &&I_GT, &&I_END }; for(;pc!=program_end;++pc) { pc->inst.ptr = table[pc->inst.type]; }
ラベルの値取れて嬉しいですね。programのinstをInstructionからvoid*に変換します。で、そこから先はYARV Maniacsで解説してる通りのコード。
pc = &program[0]; goto *pc->inst.ptr; I_PUSH: stack[stack_index++] = pc->value; ++pc; goto *pc->inst.ptr; I_POP: --stack_index; ++pc; goto *pc->inst.ptr;
で、速くなってるんですか……？
$ gcc -DLOOPNUM=100000000 vmopt.c -o vmopt $ gcc -DLOOPNUM=100000000 vmopt_direct.c -o vmopt_direct $ time ./vmopt 100000000 7.004 user 0.004 system 7.012 total $ time ./vmopt_direct 100000000 4.408 user 0.000 system 4.408 total
速くなってる！ じゃあ前回と同様に以下のようにしてコンパイル結果を見る。
$ gcc -DLOOPNUM=100000000 vmopt_direct.c -o vmopt_direct -g $ objdump -S vmopt_direct|lv
ほんでevalのディスパッチ部分を見る。
pc = &program[0]; 80483d9: 8b 45 08 mov 0x8(%ebp),%eax 80483dc: 89 45 fc mov %eax,-0x4(%ebp) goto *pc->inst.ptr; 80483df: 8b 45 fc mov -0x4(%ebp),%eax 80483e2: 8b 00 mov (%eax),%eax 80483e4: 89 85 2c 2b fe ff mov %eax,-0x1d4d4(%ebp) 80483ea: ff a5 2c 2b fe ff jmp *-0x1d4d4(%ebp) I_PUSH: stack[stack_index++] = pc->value; 80483f0: 8b 55 f0 mov -0x10(%ebp),%edx 80483f3: 8b 45 fc mov -0x4(%ebp),%eax 80483f6: 8b 40 04 mov 0x4(%eax),%eax 80483f9: 89 84 95 30 2b fe ff mov %eax,-0x1d4d0(%ebp,%edx,4) 8048400: 83 45 f0 01 addl $0x1,-0x10(%ebp) ++pc; 8048404: 83 45 fc 08 addl $0x8,-0x4(%ebp) goto *pc->inst.ptr; 8048408: 8b 45 fc mov -0x4(%ebp),%eax 804840b: 8b 00 mov (%eax),%eax 804840d: 89 85 2c 2b fe ff mov %eax,-0x1d4d4(%ebp) 8048413: eb d5 jmp 80483ea <eval+0x46> I_POP: --stack_index; 8048415: 83 6d f0 01 subl $0x1,-0x10(%ebp) ++pc; 8048419: 83 45 fc 08 addl $0x8,-0x4(%ebp) goto *pc->inst.ptr; 804841d: 8b 45 fc mov -0x4(%ebp),%eax 8048420: 8b 00 mov (%eax),%eax 8048422: 89 85 2c 2b fe ff mov %eax,-0x1d4d4(%ebp) 8048428: eb c0 jmp 80483ea <eval+0x46>
VM命令の最後、jmp 80483eaとかされてますね。各VM命令最後のgotoも
goto *pc->inst.ptr; 80483df: 8b 45 fc mov -0x4(%ebp),%eax 80483e2: 8b 00 mov (%eax),%eax 80483e4: 89 85 2c 2b fe ff mov %eax,-0x1d4d4(%ebp) 80483ea: ff a5 2c 2b fe ff jmp *-0x1d4d4(%ebp)
としてほしいが為のダイレクトスレッデッドコードだというのに。じゃあ最適化させたらどうなるよと、
$ gcc -DLOOPNUM=100000000 vmopt_direct.c -o vmopt_direct-O1 -O1 -g $ objdump -S vmopt_direct-O1 |lv
goto *pc->inst.ptr; 80483ea: 8b 06 mov (%esi),%eax 80483ec: eb ea jmp 80483d8 <eval+0x34>
なんか色々してるけど肝心のところ変わらない。じゃあもっと最適化
I_PUSH:
stack[stack_index++] = pc->value;
80483e8: 8b 46 04 mov 0x4(%esi),%eax
++pc;
80483eb: 83 c6 08 add $0x8,%esi
}
pc = &program[0];
goto *pc->inst.ptr;
I_PUSH:
stack[stack_index++] = pc->value;
80483ee: 89 84 9d 34 2b fe ff mov %eax,-0x1d4cc(%ebp,%ebx,4)
80483f5: 83 c3 01 add $0x1,%ebx
++pc;
goto *pc->inst.ptr;
80483f8: 8b 06 mov (%esi),%eax
for(;pc!=program_end;++pc) {
pc->inst.ptr = table[pc->inst.type];
}
pc = &program[0];
goto *pc->inst.ptr;
80483fa: ff e0 jmp *%eax命令の順序とか入れ替えられたりしててすげーわかりにくいなあと思いつつもかろうじてjmp *%eaxは目に入るのでうんダイレクトスレッデッドコードて感じですよね。じゃ-O2でコンパイルしたもの同士比較
$ gcc -DLOOPNUM=100000000 vmopt.c -o vmopt-O2 -O2 $ gcc -DLOOPNUM=100000000 vmopt_direct.c -o vmopt_direct-O2 -O2 $ time ./vmopt-O2 100000000 1.784 user 0.000 system 1.786 total $ time ./vmopt_direct-O2 100000000 1.060 user 0.004 system 1.065 total
他のところもちょいちょい変えてるわけだけども、わー最適化コンパイラができない仕事したぜーと喜べるわけです。
