2009-06-23

ひどく単純なVM

#include <stdio.h>

#define STACK_SIZE 30000

enum Instruction {
  I_PUSH, I_POP, I_DUP,
  I_ADD, I_SUB,
  I_JUMP, I_IF,
  I_NOT, I_EQ,
  I_RETURN
};
typedef enum Instruction Instruction;
struct Code {
  Instruction inst;
  int value;
};
typedef struct Code Code;

int exec(Code *program) {
  int stack[STACK_SIZE];
  int stack_top = 0;
  int pc;

  for(pc=0;;++pc) {
    Code code = program[pc];
    switch(code.inst) {
      case I_PUSH:
        stack[stack_top++] = code.value;
        break;
      case I_POP:
        --stack_top;
        break;
      case I_DUP:
        stack[stack_top] = stack[stack_top-1];
        ++stack_top;
        break;
      case I_ADD:
        stack[stack_top-2] += stack[stack_top-1];
        --stack_top;
        break;
      case I_SUB:
        stack[stack_top-2] -= stack[stack_top-1];
        --stack_top;
        break;
      case I_JUMP:
        pc = code.value-1;
        break;
      case I_IF:
        if(stack[stack_top-1]) {
          pc = code.value-1;
        }
        --stack_top;
        break;
      case I_NOT:
        stack[stack_top-1] = !stack[stack_top-1];
        break;
      case I_EQ:
        stack[stack_top-2] = stack[stack_top-1]==stack[stack_top-2];
        --stack_top;
        break;
      case I_RETURN:
        return stack[--stack_top];
    }
  }
}
int main(int argc, char **argv) {
  Code program[] = {
    {I_PUSH, 0},
    {I_PUSH, 1},
    {I_ADD, 0},
    {I_DUP, 0},
    {I_PUSH, 20000000},
    {I_EQ, 0},
    {I_NOT, 0},
    {I_IF, 1},
    {I_RETURN, 0}
  };
  int result = exec(program);
  printf("%d\n", result);
  return 0;
}

ひどく単純なVMをダイレクトスレッデッドコード

#include <stdio.h>

#define STACK_SIZE 30000

enum Operation {
  I_PUSH, I_POP, I_DUP,
  I_ADD, I_SUB,
  I_JUMP, I_IF,
  I_NOT, I_EQ,
  I_RETURN
};
union Instruction {
  enum Operation op;
  void *addr;
};
typedef union Instruction Instruction;
struct Code {
  Instruction inst;
  int value;
};
typedef struct Code Code;

int exec(Code *program, size_t len) {
  const static void *j_table[] = {
    &&I_PUSH, &&I_POP, &&I_DUP,
    &&I_ADD, &&I_SUB,
    &&I_JUMP, &&I_IF,
    &&I_NOT, &&I_EQ,
    &&I_RETURN
  };
  int stack[STACK_SIZE];
  int stack_top = 0;
  int pc;

  for(pc=0;pc<len;++pc) {
    program[pc].inst.addr = (void*)j_table[program[pc].inst.op];
  }

  goto *program[pc=0].inst.addr;

I_PUSH:
  stack[stack_top++] = program[pc].value;
  goto *program[++pc].inst.addr;
I_POP:
  --stack_top;
I_DUP:
  stack[stack_top] = stack[stack_top-1];
  ++stack_top;
  goto *program[++pc].inst.addr;
I_ADD:
  stack[stack_top-2] += stack[stack_top-1];
  --stack_top;
  goto *program[++pc].inst.addr;
I_SUB:
  stack[stack_top-2] -= stack[stack_top-1];
  --stack_top;
  goto *program[++pc].inst.addr;
I_JUMP:
  pc = program[pc].value-1;
  goto *program[++pc].inst.addr;
I_IF:
  if(stack[stack_top-1]) {
    pc = program[pc].value-1;
  }
  --stack_top;
  goto *program[++pc].inst.addr;
I_NOT:
  stack[stack_top-1] = !stack[stack_top-1];
  goto *program[++pc].inst.addr;
I_EQ:
  stack[stack_top-2] = stack[stack_top-1]==stack[stack_top-2];
  --stack_top;
  goto *program[++pc].inst.addr;
I_RETURN:
  return stack[--stack_top];
}
int main(int argc, char **argv) {
  Code program[] = {
    {{I_PUSH}, 0},
    {{I_PUSH}, 1},
    {{I_ADD}, 0},
    {{I_DUP}, 0},
    {{I_PUSH}, 20000000},
    {{I_EQ}, 0},
    {{I_NOT}, 0},
    {{I_IF}, 1},
    {{I_RETURN}, 0}
  };
  int result = exec(program, sizeof(program)/sizeof(Code));
  printf("%d\n", result);
  return 0;
}

やってることはRubyist Magazine - YARV Maniacs 【第 3 回】命令ディスパッチの高速化そのまんま。

計測

AMD Athlon(tm)64 X2 Dual Core Processor 4600+ x86_64 Linux環境

% gcc -O2 vm.c -o vm
% time ./vm
20000000
1.540 user 0.000 system 1.541 total
% gcc -O2 vm_dthreadead.c -o vm_dthreadead
% time ./vm_dthreadead
20000000
0.760 user 0.000 system 0.760 total

まあここで実行した

  Code program[] = {
    {{I_PUSH}, 0},
    {{I_PUSH}, 1},
    {{I_ADD}, 0},
    {{I_DUP}, 0},
    {{I_PUSH}, 20000000},
    {{I_EQ}, 0},
    {{I_NOT}, 0},
    {{I_IF}, 1},
    {{I_RETURN}, 0}
  };

というVM命令列はそれ自体の処理が非常に軽いため、元々実行時間のうち命令ディスパッチが占める割合が大きかったからこのくらい速くなる、と。あと「ダイレクトスレッデッドコードとかやるならもうJITやればいいじゃんJIT」というのが世の流れかもしれない。

昔やったあたりのことを再確認してるだけ。 http://d.hatena.ne.jp/hogelog/20080706/p2