Rubyist Magazine - YARV Maniacs 【第 3 回】 命令ディスパッチの高速化を読む (1)
http://d.hatena.ne.jp/hogelog/20080704/p1 で書いたVMを高速化。というかコンパイラさんの頑張りを見てみよう。
まず前回書いたvm.cをちょっとだけ修正。
@@ -1,6 +1,9 @@ #include <stdio.h> #define STACK_SIZE 30000 +#ifndef LOOPNUM +#define LOOPNUM 100000 +#endif typedef enum Instruction Instruction; typedef struct Code Code; @@ -90,7 +93,7 @@ {I_PUSH, 1}, {I_ADD, 0}, {I_DUP, 0}, - {I_PUSH, 100000}, + {I_PUSH, LOOPNUM}, {I_GT, 0}, {I_IF, 1} };
でまあ適当にコンパイルして実行
$ gcc -DLOOPNUM=100000000 vm.c -o vm $ time ./vm 100000000 8.061 user 0.004 system 8.062 total
100000000回中身の無いループするプログラム実行、こんなものと。るびま第３回見ると、とりあえず++pcはjump, if命令との兼ね合いからして中入れちゃった方が良さげ。というわけでforの中身を書き換える。
for(pc=0;pc<program_len;) { Code code = program[pc]; switch(code.inst) { case I_PUSH: stack[stack_index++] = code.value; ++pc; break; case I_POP: --stack_index; ++pc; break; case I_DUP: x = stack[stack_index-1]; stack[stack_index++] = x; ++pc; break; case I_ADD: x = stack[--stack_index]; stack[stack_index-1] += x; ++pc; break; case I_SUB: x = stack[--stack_index]; stack[stack_index-1] -= x; ++pc; break; case I_MUL: x = stack[--stack_index]; stack[stack_index-1] *= x; ++pc; break; case I_DIV: x = stack[--stack_index]; stack[stack_index-1] /= x; ++pc; break; case I_NOT: x = stack[stack_index-1]; stack[stack_index-1] = !x; ++pc; break; case I_JUMP: pc = code.value; break; case I_IF: x = stack[--stack_index]; if(x) { pc = code.value; } else { ++pc; } break; case I_EQ: x = stack[--stack_index]; y = stack[stack_index-1]; stack[stack_index-1] = x==y; ++pc; break; case I_LT: x = stack[--stack_index]; y = stack[stack_index-1]; stack[stack_index-1] = x<y; ++pc; break; case I_GT: x = stack[--stack_index]; y = stack[stack_index-1]; stack[stack_index-1] = x>y; ++pc; break; default: ++pc; break; } }
で実行。
$ gcc -DLOOPNUM=100000000 vmopt.c -o vmopt $ time ./vmopt 100000000 7.756 user 0.000 system 7.769 total
まあきっと速くなってますね。if命令のときに余計なcode.value-1と++pcしなくて済んでるからか。で、これって本当にswitchを展開できてるのかな*1。objdump -S vmopt|lvなどしてeval部分を眺める
080483a4 <eval>: 80483a4: 55 push %ebp 80483a5: 89 e5 mov %esp,%ebp 80483a7: 81 ec ec d4 01 00 sub $0x1d4ec,%esp 80483ad: c7 45 f0 00 00 00 00 movl $0x0,-0x10(%ebp) 80483b4: c7 45 f4 00 00 00 00 movl $0x0,-0xc(%ebp) 80483bb: e9 b7 02 00 00 jmp 8048677 <eval+0x2d3> 80483c0: 8b 45 f4 mov -0xc(%ebp),%eax 80483c3: c1 e0 03 shl $0x3,%eax 80483c6: 03 45 08 add 0x8(%ebp),%eax 80483c9: 8b 50 04 mov 0x4(%eax),%edx 80483cc: 8b 00 mov (%eax),%eax 80483ce: 89 85 28 2b fe ff mov %eax,-0x1d4d8(%ebp) 80483d4: 89 95 2c 2b fe ff mov %edx,-0x1d4d4(%ebp) 80483da: 8b 85 28 2b fe ff mov -0x1d4d8(%ebp),%eax 80483e0: 89 85 1c 2b fe ff mov %eax,-0x1d4e4(%ebp) 80483e6: 83 bd 1c 2b fe ff 0c cmpl $0xc,-0x1d4e4(%ebp) 80483ed: 0f 87 80 02 00 00 ja 8048673 <eval+0x2cf> 80483f3: 8b 95 1c 2b fe ff mov -0x1d4e4(%ebp),%edx 80483f9: 8b 04 95 00 88 04 08 mov 0x8048800(,%edx,4),%eax 8048400: ff e0 jmp *%eax
x86わかんねー！ というわけでcと合わせて読もう*2。gccにデバッグオプション-gオプション追加。
$ gcc -DLOOPNUM=100000000 vmopt.c -o vmopt -g $ objdump -S vmopt |lv
でevalを探すと
int eval(Code program[], int program_len) {
80483a4: 55 push %ebp
80483a5: 89 e5 mov %esp,%ebp
80483a7: 81 ec ec d4 01 00 sub $0x1d4ec,%esp
int stack[STACK_SIZE];
int stack_index = 0;
80483ad: c7 45 f0 00 00 00 00 movl $0x0,-0x10(%ebp)
int pc;
int x, y;こんな感じでcのコードと一緒に書いてあるので嬉しい。それで肝心のループ内部を見ると
for(pc=0;pc<program_len;) {
80483b4: c7 45 f4 00 00 00 00 movl $0x0,-0xc(%ebp) # pc(= -0xc(%ebp))に0入れる
80483bb: e9 b7 02 00 00 jmp 8048677 <eval+0x2d3>pcに0入れて8048677に飛べと。
for(pc=0;pc<program_len;) {
8048677: 8b 45 f4 mov -0xc(%ebp),%eax # %eaxにpc入れて
804867a: 3b 45 0c cmp 0xc(%ebp),%eax # pcとprogram_len(= 0xc(%ebp))比較
804867d: 0f 8c 3d fd ff ff jl 80483c0 <eval+0x1c> # pc<lenだったらジャンプpc<program_lenなら80483c0にジャンプ。80483c0から8048677はディスパッチ部分。
Code code = program[pc]; 80483c0: 8b 45 f4 mov -0xc(%ebp),%eax # eax = pc 80483c3: c1 e0 03 shl $0x3,%eax 80483c6: 03 45 08 add 0x8(%ebp),%eax # eax = program[pc] 80483c9: 8b 50 04 mov 0x4(%eax),%edx # edx = program[pc].value 80483cc: 8b 00 mov (%eax),%eax # eax = program[pc].inst 80483ce: 89 85 28 2b fe ff mov %eax,-0x1d4d8(%ebp) # code.inst = program[pc].inst 80483d4: 89 95 2c 2b fe ff mov %edx,-0x1d4d4(%ebp) # code.value = program[pc].value
と、今回実行する命令をcodeに入れてswitch
switch(code.inst) {
80483da: 8b 85 28 2b fe ff mov -0x1d4d8(%ebp),%eax # eax = code.inst
80483e0: 89 85 1c 2b fe ff mov %eax,-0x1d4e4(%ebp)
80483e6: 83 bd 1c 2b fe ff 0c cmpl $0xc,-0x1d4e4(%ebp) # 12(ラベル数13 - 1) とcode.inst比較
80483ed: 0f 87 80 02 00 00 ja 8048673 <eval+0x2cf> # code.inst>12ならジャンプ8048673ってのはdefault:のことです。
default:
++pc;
8048673: 83 45 f4 01 addl $0x1,-0xc(%ebp)そうじゃなくて定めた命令だったら
80483f3: 8b 95 1c 2b fe ff mov -0x1d4e4(%ebp),%edx # edx = code.inst 80483f9: 8b 04 95 00 88 04 08 mov 0x8048800(,%edx,4),%eax 8048400: ff e0 jmp *%eax
えーとなんかこう、{8048402(= case I_PUSH:), 804841f(= case I_POP:), ...}といったジャンプ先を保持したテーブル0x8048800(,%edx,4)から引いて飛んでるのだと思う。0x8048800(,%edx,4)の読み方がわからん後で調べる。cmpとjeの連続とかになってなくてjmp一発で嬉しいですね！ それ以降、各種命令つらつらと
case I_PUSH:
stack[stack_index++] = code.value;
8048402: 8b 55 f0 mov -0x10(%ebp),%edx
8048405: 8b 85 2c 2b fe ff mov -0x1d4d4(%ebp),%eax
804840b: 89 84 95 30 2b fe ff mov %eax,-0x1d4d0(%ebp,%edx,4)
8048412: 83 45 f0 01 addl $0x1,-0x10(%ebp)
++pc;
8048416: 83 45 f4 01 addl $0x1,-0xc(%ebp)
804841a: e9 58 02 00 00 jmp 8048677 <eval+0x2d3>
break;
case I_POP:
--stack_index;
804841f: 83 6d f0 01 subl $0x1,-0x10(%ebp)
++pc;
8048423: 83 45 f4 01 addl $0x1,-0xc(%ebp)
8048427: e9 4b 02 00 00 jmp 8048677 <eval+0x2d3>
...それぞれのVM命令処理を終えたら8048677にジャンプ。8048677は上にも書いた、ループ終了判定部分。
for(pc=0;pc<program_len;) {
8048677: 8b 45 f4 mov -0xc(%ebp),%eax
804867a: 3b 45 0c cmp 0xc(%ebp),%eax
804867d: 0f 8c 3d fd ff ff jl 80483c0 <eval+0x1c>
default:
++pc;
break;
}
}pc<program_lenになったら以下のコードを実行、evalおしまい。
return stack[0]; 8048683: 8b 85 30 2b fe ff mov -0x1d4d0(%ebp),%eax } 8048689: c9 leave 804868a: c3 ret
と。
gcc先生すごいですね、switchの展開してくれてよかった。objdumpはx86学ぶのに良さそうですね。えーとここまででRubyist Magazine - YARV Maniacs 【第 3 回】 命令ディスパッチの高速化の「高速化を考えてみる」までですかね。眠いので一旦ここまで。
