乐趣区

关于算法:Bytecode-VM-in-a-nutshell

jiezi

高级编程语言解释器大多采纳了字节码 (Bytecode) 的形式实现，首先把源文件编译为构造简略的虚拟机指令，也就是 Bytecode，而后再应用解释器虚拟机 (VM) 来执行。

上面来模仿一个计算器虚拟机的形成。
计算器虚拟机的指令格局：

struct Code
{Byte code[4];
 Code() {}
 Code(OPCODE op, Byte va0, Byte va1, Byte va2)
 {code[0] = op;
   code[1] = va0;
   code[2] = va1;
   code[3] = va2;
 }
};

计算器虚拟机的命令：

enum OPCODE
{
 OP_LOAD = 0, //LOAD reg,num,0 : reg <- num
 OP_ADD, //ADD dest,src1,src2 : src1 + src2 = dest
 OP_SUB, //SUB dest,src1,src2 : src1 - src2 = dest
 OP_MUL, //MUL dest,src1,src2 : src1 * src2 = dest
 OP_DEC, //DEC dest,src1,src2 : src1 * src2 = dest
 OP_OUT, //OUT
 OP_STOP, //STOP
};

Big Switch 版本的 VM 逻辑如下：

 switch (itr->code[0])
 {
 case OP_LOAD:
 {int pos = itr->code[1];
   int val = itr->code[2];
   stack[pos] = val;
   itr++;
   break;
 }
 case OP_ADD:
 {int dst = itr->code[1];
   int src0 = itr->code[2];
   int src1 = itr->code[3];
   stack[dst] = stack[src0] + stack[src1];
   itr++;
   break;
 }
 case OP_SUB:
 {int dst = itr->code[1];
   int src0 = itr->code[2];
   int src1 = itr->code[3];
   stack[dst] = stack[src0] - stack[src1];
   itr++;
   break;
 }
 case OP_MUL:
 {int dst = itr->code[1];
   int src0 = itr->code[2];
   int src1 = itr->code[3];
   stack[dst] = stack[src0] * stack[src1];
   itr++;
   break;
 }
 case OP_DEC:
 {int dst = itr->code[1];
   int src0 = itr->code[2];
   int src1 = itr->code[3];
   stack[dst] = stack[src0] / stack[src1];
   itr++;
   break;
 }
 case OP_OUT:
 {int dst = itr->code[1];
   printf("%.3fn", stack[dst]);
   itr++;
   break;
 }
 default:
   return;
 }

模仿一下函数指针（Function pointer）列表的实现：

typedef void (*ExecCode)(Byte arg0, Byte arg1, Byte arg2);
HashMap<int,ExecCode> dispatchMap;
….
dispatchMap.find(opcode)(op.code[1],op.code[2],op.code[3]);
….

函数调用要耗费额定的对于栈操作的工夫，尽管在纯 64 位环境，参数数量无限且类型是特地指定的简略类型时，call 能够跟 jmp 差不多快，然而大部分状况下 BigSwitch 的体现要强于函数指令列表。

还有很多晚期语言应用的一种形式，叫做 Threading。BigSwitch 的问题在于，每一条指令的执行须要 jmp 许多次。

GNU GCC 编译器有两个备受诟病的扩大，就是 &&label 和 goto (void)，新版的 LLVM 也反对这个扩大，官网称为 Address of label 和 Indirect Branches。

看上去大略是这个样子：

static const void *labelAddr = &&LABEL
goto *(labelAddr);
...
LABEL:
 //do something

然而很遗憾 Visual C++ 和 Intel C++ 编译器并不反对这个扩大，于是有机智的老外想到了应用内联汇编来模仿，应用宏来做条件编译的话能够这么干：

#ifdef _WIN32
# define STORE_LABEL(index,label) __asm lea eax, label\
 __asm mov edx,_llistd\
 __asm mov [edx][index * TYPE _llistd],eax
# define GOTO_LABEL(addr) __asm jmp addr
#else
# define STORE_LABEL(index,label) _llist[index] = &&label
# define GOTO_LABEL(addr) goto *(addr)
#endif

而后就能够欢快的实现 Indirect Threading 的解释器啦：

MARK_START:
 idx = itr->code[0];
 addr = _llist[idx];
 GOTO_LABEL(addr);
MARK_LOAD:
 pos = itr->code[1];
 val = itr->code[2];
 stack[pos] = val;
 itr++;
 idx = itr->code[0];
 addr = _llist[idx];
 GOTO_LABEL(addr);
MARK_ADD:
 dst = itr->code[1];
 src0 = itr->code[2];
 src1 = itr->code[3];
 stack[dst] = stack[src0] + stack[src1];
 itr++;
 idx = itr->code[0];
 addr = _llist[idx];
 GOTO_LABEL(addr);
MARK_SUB:
 …
MARK_STOP:
 return;
MARK_INIT:
 STORE_LABEL(OP_LOAD, MARK_LOAD);
 STORE_LABEL(OP_ADD, MARK_ADD);
 STORE_LABEL(OP_SUB, MARK_SUB);
 STORE_LABEL(OP_MUL, MARK_MUL);
 STORE_LABEL(OP_DEC, MARK_DEC);
 STORE_LABEL(OP_OUT, MARK_OUT);
 STORE_LABEL(OP_STOP, MARK_STOP);
 goto MARK_START;
}

看上去切实棒棒哒，不过很惋惜有两个大问题：

  1. 在 Windows/VC++ 平台上，汇编版本的 Indirect Threading 居然比 Big Switch 还要慢，并且慢很多！
  2. 在 Windows/VC++ 平台上，X64 编译器不反对内联汇编，要么放弃 64 位，要么就转去用 Intel C++ 编译器。

其实应用 GCC 编译的话，如果不应用 -O2 优化选项，间接生成代码，失去的后果依然是 BigSwitch 要快一些，在优化后，Indirect Threading 的版本要比 BigSwitch 版本快大概 10%。

内联汇编版本和 GCC 未优化版本之所以慢，就在那一个跳转上：

VC++ 最终编译后的汇编指令：

jmp DWORD PTR _addr$[ebp]

GCC 开启优化后的汇编指令：

jmp *%rax

有鉴于此，一些编译器抉择间接应用汇编来实现 Bytecode VM，比方 LuaJIT。

退出移动版