Hatena::ブログ(Diary)

hogeなlog

プロフィール

hogelog

hogelog

小室 直(こむろ すなお)。電気通信大学2003年入学。2010年修士卒業。プログラミングとかしてます。

カレンダー
1984 | 01 |
2006 | 07 | 08 | 09 | 10 | 11 | 12 |
2007 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2008 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2009 | 01 | 02 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 |
2010 | 01 | 06 | 08 | 09 | 10 | 11 | 12 |
2011 | 01 | 02 | 03 | 05 | 08 | 09 | 10 | 12 |
2012 | 01 | 04 | 06 |

July 06(Sun), 2008

[][][] no titleを読む (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回中身の無いループするプログラム実行、こんなものと。るびま第3回見ると、とりあえず++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学ぶのに良さそうですね。えーとここまででno titleの「高速化を考えてみる」までですかね。眠いので一旦ここまで。

最近のコメント
Connection: close