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

48次阅读

共计 2999 个字符,预计需要花费 8 分钟才能阅读完成。

高级编程语言解释器大多采纳了字节码 (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。

正文完
 0