Free Mind

The Free Mind of pluskid

Introduction to direct threading, or computed goto

Develop
exec现在许多语言都是先把源代码编译成跨平台的字节码，然后通过解释字节码（或是对字节码进行 JIT）的方式执行程序。这比直接遍历 AST 的方式要高效许多。而现在许多虚拟机的字节码其实已经不是以字节 (byte) 为单位，而是以机器字 (word) 为单位（比如 Rubinius 和 Ruby 1.9 的虚拟机 YARV 都是如此），只是仍然沿用“字节码”这一称呼而已，这个原因我稍后会讲。

除此之外，虚拟机一般会分为两种：基于栈和基于寄存器的。虽然在现实的 CPU 上基于寄存器是理所当然的，但是在实现虚拟机的时候却不一样，基于栈的指令集能够让字节码跟紧凑，这样也可以提高 Cache 的利用率，而且实现起来也比基于寄存器的机器要简单。虽然有不少 paper （例如 The case for virtual register machines 和 Virtual machine showdown: Stack versus registers 等）对比了性能之后都得出基于寄存器的虚拟机“虽然代码大小有所增加，但是带来的性能提升更值”的结论，然而实际上除了 Perl 6 的虚拟机 Parrot 之外其他大部分虚拟机都是基于栈的。

扯了这么多，才要说到今天的正题。虚拟机的实现其实和一个真正的 CPU 差不多，大致有如下几个步骤：

  1. 取指令。在这里是字节码。
  2. 解码，在真实的 CPU 里这个过程会比较复杂，例如 x86 的指令集就是出奇的复杂。而在虚拟机里则不一样，一般 opcode 和 operand 是可以很简单地分开的。
  3. 执行。
如果学过体系结构相关的课程的话，应该了解一个简单的 CPU 大致是如何执行一条指令的，而在虚拟机中，则通常是针对每一个 opcode 会有一段代码完成相应的功能。

最简单的情况：每一个 opcode 对应一个函数：


void do_plus()
{
    VALUE a = stack_pop();
    VALUE b = stack_pop();
    stack_push(a+b);
}

void do_minus()
{
    /* ... */
}


...

然后通过 switch 进行分派：


switch (opcode)
{
...
case OP_PLUS:
    do_plus();
    break;
case OP_MINUS:
    do_minus();
    break;
...
}

然而函数调用在这个时候开销可以算非常大了，并且通常指令的实现代码都是比较短的，所以一个优化就是直接把代码放到一起变成一个大 switch （不禁让我想起了 Windows 的消息循环 :p ）：


switch (opcode)
{
...
case OP_PLUS:
    a = stack_pop();
    b = stack_pop();
    stack_push(a+b);
    break;
case OP_MINUS:
    /* ... */
    break;
...
}

然而这样看起来还是有些慢，一般情况下，switch 是一个平凡的线性搜索，如果对于每一条要执行的指令，都执行一次线性搜索的话，问题就出来了。如果能使用类似于查表的方法直接跳转的话，就可以省去线性搜索的过程了。到这里，终于说到了今天的主角：每条指令执行完之后直接跳转到下一条指令的代码的地方，就称作 direct threading 。

然而 direct threading 并不能很方便地在 ANSI C 里实现。一个办法就是通过函数指针，还是把每个 opcode 对应的操作写在单独的函数中，然后把每个 opcode 替换成对应的函数指针，这样指令的执行就从 


while (1)
{
    switch (*ip)
    {
    /* ... */
    }
}
变成了： 

while (1)
{
    (*ip)();
    NEXT_INSN;
}
看起来确实省去了 switch 查找，但是函数指针的方式实在是比较重量级：调用函数的开销在这种场合显得有些大，而使用函数指针进行间接函数调用甚至让编译器无法进行内联优化。

除去函数指针，（臭名昭著的）goto 似乎是一个选择，然而 goto 的标号又必须是编译时指定的。好在 GCC 提供了称作 “computed goto” 的扩展，顾名思义就是 goto 的标号是在运行时计算出来的，正好用来实现 direct threading 。

computed goto 的用法很简单，首先还是要按照普通的 goto 的做法设置标号，然后通过 && 运算符取得标号的“地址”，把这个“地址”存放在一个变量中，就可以使用这个变量来进行 goto 了，通过给这个变量赋不同的“地址”，就可以实现跳转到不同的地方。

下面用一个简单的程序来演示一下吧。来实现一个简单的虚拟机：

  • 数据类型是无符号整形。
  • 指令定长，2 个字，一个 opcode 和一个 operand 。
  • 使用基于栈的指令集。
  • 支持如下 opcode:
    • 0: push
    • 1: +
    • 2: -
    • 3: print
    • 4: read
    • 5: return
例如，下面一段字节码，会读入 3 个数字（例如 10, 20, 40），再打印出计算结果（5+40+20-10）： 

VALUE progn[] = {
    4, 0,                   /* read a number a */
    4, 0,                   /* read a number b */
    4, 0,                   /* read a number c */
    0, 5,                   /* push number 5 */
    1, 0,                   /* top = c+5 */
    1, 0,                   /* top = top+b */
    2, 0,                   /* top = top-a */
    3, 0,                   /* print result: 5+c+b-a */
    5, 0                    /* return */
};

首先按照常规的办法，写出实现各个 opcode 对应的代码： 


insn_0:
    /* push a value to the stack */
    *stack++ = iseq[1];
    NEXT_INSN;
insn_1:
    /* + */
    t1 = *(--stack);
    t2 = *(--stack);
    *stack++ = t1+t2;
    NEXT_INSN;
insn_2:
    /* - */
    t1 = *(--stack);
    t2 = *(--stack);
    *stack++ = t1-t2;
    NEXT_INSN;
insn_3:
    /* display the number on top of the stack */
    t1 = *(--stack);
    printf("DISP: %d\n", t1);
    NEXT_INSN;
insn_4:
    /* read a number and push on top of the stack */
    printf("Input a number: ");
    scanf("%d", &t1);
    *stack++ = t1;
    NEXT_INSN;
insn_5:
    /* return */
    return;
其中 NEXT_INSN 的定义如下： 

#define NEXT_INSN iseq += INSN_LEN; goto **iseq
其中 goto **iseq 就是采用了 direct threading 的方法直接跳转到下一条指令对应的代码所在的地址。但是原来的字节码里存放的是 opcode ，因此还要经过一个“预处理”，把 opcode 替换成相应的地址： 

void setup_dt(VALUE *iseq, int len)
{
    while (len > 0)
    {
        *iseq = _dt_address[*iseq];
        iseq += INSN_LEN;
        len -= INSN_LEN;
    }
}
这也是为什么现在不少虚拟机的实现里字节码实际上都是以 word 为单位了，这样在进行 direct threading 转换的时候就可以直接把 opcode 用地址替换了（一个 word 刚好是一个平台上的指针的长度）。

还有一点需要做的就是把各个 opcode 对应的代码地址存放在 _dt_address 中，有一点需要注意的是，即使是 computed goto ，goto 的目的也必须是在当前函数中，所以初始化地址和实际执行字节码都用同一个函数来做了，并且用一个参数来指明是初始化还是实际执行：


void run(VALUE *stack, VALUE *iseq, int init)
{
    VALUE t1, t2;
    if (init)
    {
        _dt_address[0] = &&insn_0;
        _dt_address[1] = &&insn_1;
        _dt_address[2] = &&insn_2;
        _dt_address[3] = &&insn_3;
        _dt_address[4] = &&insn_4;
        _dt_address[5] = &&insn_5;

return;
    }


/* else, run the instruction sequence */

如上所示，标号的地址通过 && 运算符取得，存放在 _dt_address 表中，并通过 dt_setup 函数将字节码进行转换，就可以实现 direct threading 了。下面是完整的代码：


#include 

typedef unsigned int VALUE;


/**
 * if init != 0, do initialization.
 * otherwise, run iseq on stack.
 */
void run(VALUE *stack, VALUE *iseq, int init);


void setup_dt(VALUE *iseq, int len);


int main(int argc, char *argv[])
{
    VALUE stack[512];
    VALUE progn[] = {
        4, 0,                   /* read a number a */
        4, 0,                   /* read a number b */
        4, 0,                   /* read a number c */
        0, 5,                   /* push number 5 */
        1, 0,                   /* top = c+5 */
        1, 0,                   /* top = top+b */
        2, 0,                   /* top = top-a */
        3, 0,                   /* print result: 5+c+b-a */
        5, 0                    /* return */
    };


/* init */
    run(0, 0, 1);


setup_dt(progn, sizeof(progn)/sizeof(progn[0]));
    run(stack, progn, 0);


return 0;
}


#define INSN_LEN 2
#define NEXT_INSN iseq += INSN_LEN; goto **iseq
#define INSN_NUM 6
static void *_dt_address[INSN_NUM];


void run(VALUE *stack, VALUE *iseq, int init)
{
    VALUE t1, t2;
    if (init)
    {
        _dt_address[0] = &&insn_0;
        _dt_address[1] = &&insn_1;
        _dt_address[2] = &&insn_2;
        _dt_address[3] = &&insn_3;
        _dt_address[4] = &&insn_4;
        _dt_address[5] = &&insn_5;


return;
    }


goto **iseq;


insn_0:
    /* push a value to the stack */
    *stack++ = iseq[1];
    NEXT_INSN;
insn_1:
    /* + */
    t1 = *(--stack);
    t2 = *(--stack);
    *stack++ = t1+t2;
    NEXT_INSN;
insn_2:
    /* - */
    t1 = *(--stack);
    t2 = *(--stack);
    *stack++ = t1-t2;
    NEXT_INSN;
insn_3:
    /* display the number on top of the stack */
    t1 = *(--stack);
    printf("DISP: %d\n", t1);
    NEXT_INSN;
insn_4:
    /* read a number and push on top of the stack */
    printf("Input a number: ");
    scanf("%d", &t1);
    *stack++ = t1;
    NEXT_INSN;
insn_5:
    /* return */
    return;
}


void setup_dt(VALUE *iseq, int len)
{
    while (len > 0)
    {
        *iseq = _dt_address[*iseq];
        iseq += INSN_LEN;
        len -= INSN_LEN;
    }
}

虽然看起来初始化 _dt_address 表的代码很冗余，而且还有不少重复的代码，但是实际的虚拟机中通常都是有一个指令集的定义，并通过定义自动生成相应的代码，所以重复代码在这里并不是问题。 :) 其实 goto 虽然臭名昭著，但是在许多实际的代码中还是会经常见到，Dijkstra 批评的其实应该是 goto 的滥用，而不是 goto 语句本身了。 :)

本来还可以对比一下 switch 分派、函数指针和 computed goto 三种方式的性能差异，但是由于这个指令集实在太 trivial 了，得不出什么有价值的结果来，所以还是算了。 :p

Comments (12)

Aaron June 14, 2008
额 狂晕
居然还有computed goto这回事
一直以为label只能跳函数的scope呢
pluskid June 14, 2008
@Aaron,
computed goto 也是有函数的 scope 这个限制的。
roy_hu June 14, 2008
switch-case 未必是线性搜索，编译器也可能会优化成查找表。在这种情况下，computed goto 还有优势吗？楼主是否做过比较？
pluskid June 14, 2008

@roy_hu, 呵呵！你说得对，这也是我正在看的问题。我发现在取值连续的情况下，对于较小的 switch 编译器一般都会做转换为查找表的优化。例如这样一段代码：

  switch(n) {
    case 0:
      a = 1;
      break;
    case 1:
      a = 2;
      break;
    case 2:
      a = 3;
      break;
    case 3:
      a = 4;
      break;
    case 4:
      a = 5;
      break;
    case 5:
      a = 6;
      break;
    case 6:
      a = 7;
      break;
  }

在 gcc 下被编译成这样子：

;; 
        cmpl    $6, -12(%ebp)
        ja      .L2
        movl    -12(%ebp), %eax
        jmp     *.L10(,%eax,4)
        .section        .rodata
        .align 4
        .align 4
.L10:
        .long   .L3
        .long   .L4
        .long   .L5
        .long   .L6
        .long   .L7
        .long   .L8
        .long   .L9
        .text
.L9:
        movl    $7, %ebx
        .p2align 4,,7
.L2:
;; 
        ret
.L3:
        movl    $1, %ebx
        jmp     .L2
.L4:
        movl    $2, %ebx
        jmp     .L2
;;

在 Microsoft 的 Visual Studio 编译器下也会编译出类似的代码：

; 6    :   switch(n) {
mov	eax, DWORD PTR _n$[ebp]
	mov	DWORD PTR tv64[ebp], eax
	cmp	DWORD PTR tv64[ebp], 6
	ja	SHORT $LN8@main
	mov	ecx, DWORD PTR tv64[ebp]
	jmp	DWORD PTR $LN17@main[ecx*4]
$LN7@main:
; 7    :     case 0:
; 8    :       a = 1;
mov	BYTE PTR $T3869[ebp], 1
	mov	DWORD PTR _a$[ebp], 1
; 9    :       break;
jmp	SHORT $LN8@main
$LN6@main:
; 10   :     case 1:
; 11   :       a = 2;
mov	BYTE PTR $T3869[ebp], 1
	mov	DWORD PTR _a$[ebp], 2
; 12   :       break;
jmp	SHORT $LN8@main
;;

而这些都是在默认参数下编译的结果，可见这种 switch 优化是一种很 common 的优化技术，而且即使存在少许不连续的情况，编译器也可以很简单地用“填补”的技术绕过。这种时候似乎没有必要使用 computed goto “手工地”进行查找表优化了。 :)

Aaron June 14, 2008

不好意思，当时写了个代码运行了一下，又看了-S结果 确实是用jmp的，太激动了 仔细一想，如果打破函数scope jmp过去，现场就很混乱了，例如跳入的那个函数的参数和原来函数的对像销毁，可能会取决于编译器的实现和寄存器的状态使得跳函数变得很无意义和混乱 但是确实可以执行的 

#include 
static void *_dt;
int main()
{
    func(1);
    goto *_dt;
}
int func(int init)
{
    _dt = &&mylabel;
    if (!init)
    {
mylabel:
            printf("Hello, mylabel!\n");
    }
}

roy_hu June 14, 2008
想要打破函数scope jmp的话，c有setjmp/longjmp，裸跳肯定是不行。
Rhythm June 14, 2008
基于寄存器的虚拟机还有一个 Erlang
pluskid June 14, 2008
@Rhythm,
哦，Erlang 的虚拟机我倒是确实不了解。你最近在研究 Erlang ?感觉如何？
maninred June 14, 2008
代码好像Rubinius里的shortgun的代码。
pluskid June 14, 2008
@maninred,
bingo! :D
roy_hu June 17, 2008
呵呵，一个相关的帖子：
http://blog.mozilla.com/dmandelin/2008/06/03/squirrelfish/
pluskid June 17, 2008
@roy_hu,
嗯，那篇文章下面的评论里提到的两篇 paper 也很不错的样子。 :)

Blog Archive — Originally hosted with WordPress (2007–2009)