WebAssembly 初探 – Threaded Code

之前写了个 WebAssembly 虚拟机,经过一番折腾,性能(解析执行)终于接近 Intel 的 WAMR 了,这里总结下其中一个重要的优化点:Threaded Code,其主要优化虚拟机执行时的指令分发性能。首先看一下 WebAssembly 虚拟机的运行流程(解析执行):

右上部分是程序输入,主要有函数、内存(堆)和全局变量,可以类比代码编译后产生的 binary 文件加载后的内容,函数体(code)则是一个指令序列,虚拟机运行期维护两个栈:Operand stack 和 Control stack,分别存储操作数(values)和代码结构(labels),每个函数调用都会产生一个函数调用帧(Frame),用于存储函数的局部变量(如参数),当各种数据结构都准备就绪,虚拟机从入口函数开始,顺序地执行函数的指令序列,当执行到 call 指令时,会产生新的 Frame,进入新的函数执行。

指令分发

各种解释型语言(如Java、Lua、WebAssembly) 都会定义自己的一套指令集,代码“编译”之后各函数体的内容就是一个指令列表,指令又分控制指令(如跳转、循环、函数调用等)、数值指令(如加减乘除等)、以及内存操作、变量操作相关的指令等等,而虚拟机在运行的时候,“解析执行”的过程实际上就是遍历指令列表,完成每个指令对应的操作。在经典的计算模型里,会有一个程序计数器(pc)指向指令列表的当前位置,每执行完一条指令,pc++,继续下一条指令,这个过程也可以看作是“指令分发”,“Theaded Code” 就是指这样的指令分发形式。

Switch Threading

使用 switch 做指令分发是最直观的,这里为方便测试,我们先定义 OpCode 如下:

typedef enum {
    ADD,    // *sp += 2
    SUB,    // *sp -= 1
    MUL,    // *sp *= 2
    DIV,    // *sp /= 2
    END
} OpCode;

然后初始化一段 code,总计 20 亿条指令:

#define CODE_LEN (500000000 * 4)

char *code = new char[CODE_LEN + 1];
for (int i = 0; i < CODE_LEN / 4; i++) {
    code[i * 4 + 0] = ADD;
    code[i * 4 + 1] = SUB;
    code[i * 4 + 2] = MUL;
    code[i * 4 + 3] = DIV;
}
code[CODE_LEN] = END;

用 switch 做指令分发的实现如下(sp 模拟栈指针,pc 模拟程序计数器):

long test_switch(char *code) {
    long ret = 0;
    long *sp = &ret;
    char *pc = &code[0];

    while (true) {
        switch (*pc++) {
            case ADD: *sp += 2; break;
            case SUB: *sp -= 1; break;
            case MUL: *sp *= 2; break;
            case DIV: *sp /= 2; break;
            case END: goto END;
            default: break;
        }
    }
END:
    return ret;
}

即在一个大循环里,对指令的 OpCode 进行 switch,在每个 case 里完成对应的栈操作,然后进入下一次循环,pc++,继续 switch 操作。编译器对 switch 有不同的优化实现,可参考:https://zhuanlan.zhihu.com/p/38139553

Call Threading

除了 switch,另一种容易想到的方式是函数调用:

typedef void (*OpFunc)(long *);

void add(long *sp) { *sp += 2; }
void sub(long *sp) { *sp -= 1; }
void mul(long *sp) { *sp *= 2; }
void div(long *sp) { *sp /= 2; }

long test_call(char *code) {
    long ret = 0;
    long *sp = &ret;
    char *pc = &code[0];

    OpFunc funcs[] = { add, sub, mul, div };
    while (*pc != END) {
        funcs[*pc++](sp);
    }

    return ret;
}

即每个指令用一个函数来实现,然后将函数地址存入映射表(数组),运行的时候根据 OpCode 找到对应的函数并调用。使用函数调用来分发指令,有利于代码结构的优化,不需要像 switch 那样所有指令实现都写在一起,但函数的 call 涉及栈帧的创建,参数入栈等一系列操作,性能开销并不会理想。

Indirect Threading

GCC 支持 Labels as Values (LLVM 也支持),即可以拿到 label 的地址,得到 void* 类型的值,然后配合 goto,就能运行期动态跳转到不同 label。基于这个特性,虚拟机的指令分发可以有更高效的形式 indirect threading:

long test_indirect(char *code) {
    long ret = 0;
    long *sp = &ret;
    char *pc = &code[0];

    void *labels[] = { &&ADD, &&SUB, &&MUL, &&DIV, &&END };
    goto *labels[*pc];

ADD:
    *sp += 2; goto *labels[*(++pc)];
SUB:
    *sp -= 1; goto *labels[*(++pc)];
MUL:
    *sp *= 2; goto *labels[*(++pc)];
DIV:
    *sp /= 2; goto *labels[*(++pc)];
END:
    return ret;
}

即不再使用一个大循环来遍历指令列表,而是在每个指令的末尾 goto (同时 pc++) 到下个指令所在 label,直到 END,这里的 indirect 指的是需要根据 pc 的值从数组中找到对应的 label 地址,相应的有 direct threading,pc 的值本身就是 label 地址了,不过实际的项目中,direct threading 可能不方便实现。

尾调用

Indirect threading 方式中,已经不需要大循环来分发指令了,转由指令本身来驱动(pc++), 再看看之前 call threading 的方式,如果在每个函数末尾调用下一个指令的函数,就能省去外面的大循环,转由函数调用来驱动 pc 自增,实现如下:

typedef void (*OpFunc)(long *, char *);

static OpFunc *funcs = nullptr;
#define NEXT pc++; funcs[*pc](sp, pc);

void add(long *sp, char *pc) { *sp += 2; NEXT }
void sub(long *sp, char *pc) { *sp -= 1; NEXT }
void mul(long *sp, char *pc) { *sp *= 2; NEXT }
void div(long *sp, char *pc) { *sp /= 2; NEXT }
void end(long *sp, char *pc) { }

long test_tailcall(char *code) {
    long ret = 0;
    long *sp = &ret;
    char *pc = &code[0];

    funcs = new OpFunc[]{ add, sub, mul, div, end };
    funcs[*pc](sp, pc);

    delete[] funcs;
    return ret;
}

NEXT 宏定义中,我们将 pc++,然后调用下一个指令函数,这样每执行一个指令都会增加一层函数调用栈,指令多了会导致栈溢出,不过由于调用出现在函数最尾部,编译器是可以进行尾调用优化的,即本来应该进行的函数调用相关操作都可以省略(现场已经没用了),直接跳转到新函数入口地址即可,也即“call”指令优化成了“jmp”指令,从而避免了栈溢出。上面程序如果指定 -O0 优化,运行后会栈溢出报错,指定 -O2 则能正常执行,感兴趣的可以 objdump 看一下优化前后函数生成的指令差异。

寄存器

我们知道从数据的访问速度来看,寄存器 > Cache > 内存,因此如何更充分地利用寄存器、Cache 是虚拟机性能优化的重要方向,如栈顶缓存技术(参考这里),将操作数栈的栈顶元素放到寄存器中,必要的时候再同步到内存,从而省去一些内存操作,但 CPU 的寄存器其实是不方便控制的,特别是如 WebAssembly 这样的基于栈设计的字节码,指令本身并没有寄存器相关信息,虽然虚拟机因此结构简单,兼容性好,执行性能却更难优化,这里基于前面的尾调用优化介绍另一种使用寄存器的方式,该方式也是 wasm3 虚拟机的核心优化原理,示例代码如下:

typedef void (*OpFunc)(long *, char *, long);

static OpFunc *funcs = nullptr;
#define NEXT pc++; funcs[*pc](sp, pc, reg);

void add(long *sp, char *pc, long reg) { reg += 2; NEXT }
void sub(long *sp, char *pc, long reg) { reg -= 1; NEXT }
void mul(long *sp, char *pc, long reg) { reg *= 2; NEXT }
void div(long *sp, char *pc, long reg) { reg /= 2; NEXT }
void end(long *sp, char *pc, long reg) { *sp = reg; }

long test_tailcall_reg(char *code) {
    long ret = 0;
    long *sp = &ret;
    char *pc = &code[0];

    funcs = new OpFunc[]{ add, sub, mul, div, end };
    funcs[*pc](sp, pc, *sp);

    delete[] funcs;
    return ret;
}

对比“尾调用”的函数实现,我们的加减乘除指令不再操作 sp 指针,而是操作新增的 reg 参数,并将修改后的 reg 变量作为参数传给下一个指令函数,实际上,函数的参数以及函数的局部变量,最终都是当前函数栈帧(Frame)的 locals,编译器会将一部分 locals 优化分配到寄存器以提升性能,不过寄存器数量有限,具体的分配规则要看不同编译器实现,不过参数较少情况下,大部分都会将参数分配到寄存器,我们对比下添加 reg 前后 add 和 sub 函数的编译结果:

可以看出,函数体的唯一差别是 addq 指令的寻址方式不一样,左边是操作 sp 指针,需要通过寄存器间接访问内存,右边操作 reg 参数,只需要操作寄存器即可,可以从后面的测试数据看到,两者的性能差别巨大。

小结

将以上各种实现进行对比测试,执行前文 Switch Threading 中所述的 20 亿条指令,均开启 -O2 优化,结果如下 (Macbook Pro i7):

switch           2609 ms
indirect         1457 ms
call               2741 ms
tailcall         3184 ms
tailcall_reg 1150 ms

可以看出 indirect 和 tailcall + 寄存器优化这俩种实现的性能比较好,当然这个测试并不完全准确,只能反映个大概的性能差别,实际的虚拟机实现还要考虑指令本身的特点以及虚拟机结构等因素,Intel 的 WAMR 引擎使用了 switch 和 indirect 两种方式(根据编译器特性支持),参看代码:wasm_interp_fast.c#L1037

#if WASM_ENABLE_LABELS_AS_VALUES != 0
  #define HANDLE_OPCODE(op) &&HANDLE_##op
  DEFINE_GOTO_TABLE (const void*, handle_table);
  #undef HANDLE_OPCODE
  if (exec_env == NULL) {
      global_handle_table = (void **)handle_table;
      return;
  }
#endif

#if WASM_ENABLE_LABELS_AS_VALUES == 0
  while (frame_ip < frame_ip_end) {
    opcode = *frame_ip++;
#if WASM_CPU_SUPPORTS_UNALIGNED_ADDR_ACCESS == 0
    frame_ip++;
#endif
    switch (opcode) {
#else
      goto *handle_table[WASM_OP_IMPDEP];
#endif

wasm3 则采用了 tailcall + 寄存器优化,并且前期做了大量的指令优化和寄存器分配工作(m3_compile.c),详见作者自述:How it works,目前 wasm3 仍然是最快的 WASM 解释器,主要还是得益于对寄存器的充分利用。