浅析JavaScript引擎的技术变迁

hechengjin

http://djt.qq.com/article/view/489
本文通过分析开源的浏览器项目中的JavaScript引擎，历数JavaScript引擎的几种实现方式：从原始的遍历语法树，到字节码方式（bytecode interpreter），直到引入了JIT编译方式。每一种新方式的出现都是JavaScript引擎性能的一次飞跃。

遍历语法树（Syntax Tree Walker）

　　和很多脚本语言的解释器一样，JavaScript引擎最先也是采用遍历语法树（syntax tree walker）的方式。执行一条语句的过程就是遍历一次相对应的语法树的过程。举个例子：
一条赋值语句：

i = a + b * c;

　　经过词法分析后，就生成了一堆单词流：

"i", "=", "a", "+", "b", "*", "c";

　　再经过语法分析后，就生成了如下的语法树：

图3 赋值语句的语法树

　　执行这条语句，就是遍历这颗语法树的过程。遍历语法树的过程在程序设计上一般采用访问者模式（vistor pattern）来实现。要遍历这颗语法树，只要将根节点传给visit函数， 然后这个函数递归调用相应子节点的visit函数，如此反复直到叶子节点。例如，在这个例子中根节点是个赋值语句，他知道应该计算出右边表达式的值，然后赋给左边的地址；而在计算右边表达式的时候，发现是一个加法表达式，于是接着递归计算加法表达式的值，如此递归进行直到这颗树的叶子节点，然后一步步回溯，将值传到到根节点，就完成了一次遍历，也即完成了一次执行。

　　这样的方式虽然原始，但是实现起来简单，对于性能要求不高，只是完成小任务的一些脚本语言，也是可以接受的。WebKit的JavaScript引擎在2008年6月（SquirrelFish的推出）之前就是用这种方式。

　　每次执行这条语句，都要进行一次遍历树的过程，这种方式存在着很大的性能缺陷：

　　1. 语法树只是描述语法结构，并不是执行这条语句要进行的操作。例如对于语句：｛x = 1; y = x;｝，根节点是个复合语句“｛...｝”，他的子节点是两个赋值语句，解释器首先访问这个复合语句节点，但实际上没有做任何事情，然后访问第一个赋值语句，接着访问第二个赋值语句。在一个复杂的程序中，这种不是执行单元，但却是语法树不可或缺的节点很多。因此就会导致做很多无用功。

　　2. 访问每个节点的代价太大。遍历语法树一般采用访问者模式，访问每个节点至少需要一次虚函数调用和返回，也即有两个间接跳转，而对于现代CPU而言，这种间接跳转意味着大大增加了分支预测失败的可能行（后文还有关于分支预测的讨论）。

　　因此采用遍历语法树方式的JavaScript引擎是很低效的，而且有很大的提升空间。所以即使WebKit团队对这种syntax tree walker已经优化到了极致，但是由于这个方式中存在着上述提到的固有缺陷，之后他们也跟其它的JavaScript引擎一样引入了字节码（bytecode）。

字节码（bytecode）

　　从上面介绍的遍历语法树方式中可以发现，要执行一棵语法树，实际上是一个后序遍历树的过程。以上面这个例子，要计算赋值语句，先计算加法表达式，那就必须先计算乘法表达式，也就是说只有子结点计算好了之后，父节点才能计算，典型的后序遍历。

　　如果在后序遍历这棵树后，生成对应的后缀记法（逆波兰式）的操作序列，然后在执行时，直接解释执行这个后缀记法的操作序列。那么这时候就把这种树状结构，变换成了一种线性结构。这种操作序列就是字节码（bytecode），这种执行方式就是字节码解释方式（bytecode interpreter）。沿用上面那个遍历语法树的例子，转成相应的字节码，如下图所示：

图4语法树转换成bytecode

　　在JavaScript引擎中直接执行字节码，肯定比每次都遍历一遍语法树高效。

　　字节码，是一种与平台无关的，需要在对应的虚拟机中执行的中间表示。如Java编译器把Java源代码编译成Java字节码，然后在对应平台的Java虚拟机中执行； ActiveScript语言，也是通过转换成字节码，然后在对应的FLASH虚拟机中执行的。Java和ActionScript语言都有标准的字节码格式，但是JavaScript的字节码没有标准的格式，每个JavaScript引擎厂商都有自己的标准。

　　虽然标准不一，但是JavaScript字节码在设计上大体上都可归类为以下两类：基于栈(stack-based)和基于寄存器（register-based）。

　　传统的字节码设计大多是基于栈的，这种方式将所有的操作数和中间表示都保存在一个数据栈中。如语句：c = a + b，转换后的字节码如下：

LOAD a  # 将a推入栈顶
LOAD b  # 将b推入栈顶
ADD     # 从栈顶弹出两个操作数，相加后，将结果推入栈顶
STORE c  #将栈顶数据保存到C中

　　基于寄存器的字节码通过一些槽（slot）或称为寄存器（register）的方式保存操作数。这里的寄存器与汇编代码中的寄存器是两个概念。存在寄存器（或槽）中可以想象成就是存入一个固定数组中了。上面例子要是转换成基于寄存器的代码如下：

ADD c, a, b   # 两个操作数分别存在a和b中，将结果放在c中。

　　这两种字节码设计各有优劣，如栈式字节码每条的指令更短（因为操作树是隐式得存在栈中），但是总的指令条数更多；栈式虚拟机实现起来比寄存器式来得简单。目前这两种方式都有各自的实现：如Flash Player的ActionScript虚拟机Tamarin，Firefox的JagerMonkey，采用的是栈式字节码设计；而webkit，carakan采用基于寄存器方式。

　　采用哪种设计取决于设计者关注的侧重点不同。想详细了解这两种设计的优劣，可参考一些论文（The case for virtual register machines 和Virtual machine showdown: Stack versus registers）。

　　字节码是需要在虚拟机中执行的，而虚拟机的执行过程与CPU过程类似，也是取指，解码，执行的过程。通常情况下，每个操作码对应一段处理函数，然后通过一个无限循环加一个switch的方式进行分派。如:

图5 JavaScript引擎的Switch Loop分派方式

　　这里的vpc是一个指向字节码数组的指针，在虚拟机中作用与PC寄存器在实际机器中的作用类似，所以称作虚拟PC（virtual program counter）。

　　与遍历语法树方式相比，字节码方式就消除了遍历语法树所引起的大部分性能负担。首先字节码序列直接描述了需要执行的动作，去除了多余的语法信息；其次，执行一条字节码语句，只是一次的内存访问（取指令）再加上一次间接跳转（分派到对应的处理函数），这也比访问语法树中一个节点开销来的要小。

　　因此，字节码方式与遍历语法树相比在性能上有很大的提升。虽然从语法树生成字节码也是需要时间的，但是这一小段时间可以从直接执行字节码所获得的性能提升上得到补偿。毕竟在实际的代码中，不会所有的代码都只被执行一次。而且生成了字节码之后，就可以对于这种中间代码进行各种优化，比如常量传播，常量折叠，公共子表达式删除等等。当然这些优化都是有针对性和选择性的，毕竟优化的过程也是需要消耗时间的。而这些优化要想直接在语法树上进行几乎是不可能的。

　　虽然字节码方式相对于遍历语法树已经前进了一大步，但是在分派方式上还可以再改进。在图5中，Switch Loop分派方式每次处理完一条指令后，都要回到循环的开始，处理下一条，并且每次switch操作，可能都是一次线性搜索（现代编译器一般都能对switch语句进行优化， 以消除这种线性搜索开销，但这种优化也是只限于特定条件，如case的数量和值的跨度范围等），这对于一般的函数，只有有限的几个switch case，尚可接受，但是对于虚拟机来说，有上百个switch case并且是频繁地执行，执行一条指令就需要一次线性搜索，那还是太慢了。如果能用查表的方式直接跳转，就可以省去线性搜索的过程了。于是在字节码的分派方式上，有的新的改进，称作Direct Threading。

Direct Threading

　　Direct Threading，这里的threading与我们通常理解的线程没有任何关系，可以理解成是针线中的那个“线”。以这种方式执行时，每执行完一条指令后不是回到循环的开始，而是直接跳到下一条要执行的指令地址。这种方式就比原来的Switch Loop方式有效许多。但是要想有效的实现Direct Threading，需要用到一个gcc的扩展“Labels As Values”，普通的goto语句的标号是在编译时指定的，但是利用“Labels As Values”扩展，goto语句的标号是就可以在运行时计算（这种goto语句也叫Computed Goto），利用这个特性就可以很容易地实现Direct Threading。（想在windows平台用这个特性，也有几个GCC的windows移植版本，如MinGW, Cygwin等）

　　上面的Switch Loop如果用Direct Threading方式，就如下图右边所示：

图6 Direct Threading分派方式

　　右图中的Direct Threading方式已经没有了循环和switch分支，所有的字节码分派就是通过“goto *vpc++”进行的。

　　vpc在这里是指向字节码数组的指针，字节码数组里的元素就是各个标号的地址。例如，如果有个指令序列是：

mov, add, ret

　　那么对应的字节码数组就是：

[&&mov, &&add, &&ret]

　　一开始，vpc指向数组的第一条指令，即vpc = &&mov, 那么goto *vpc，就会跳到标号为“mov”的地方开始执行（普通的goto语句无法完成，这是利用gcc的“labels as values”特性）；在执行“mov”处理函数末尾的“goto *vpc++”之后，就直接跳转到标号“add”的地方开始执行；直到最后。

　　Direct Threading的执行过程如下图所示：

图7 Direct Threading执行过程

　　最左边是生成的字节码序列，中间就是字节码序列对应的数组，右边是对应的虚拟机实现代码。开始执行时，vpc指向字节码数组的开始，即“enter”指令，虚拟机开始执行“enter”指令对应的操作，在“enter”对应的操作的末尾有个“goto *vpc++”，这时的vpc就指向字节码数组的下一条字节码，在图7中即为mov指令，然后进入mov指令对应的操作。如此反复直到执行完这个字节码数组中的指令。每执行完一条指令，就直接跳转到下一条指令的地址处，这就跟一根“线”穿过一条弯曲的隧道，虽然道路是弯曲的，但每次都是前进的，而不是想Switch Loop那样，每次执行完一条字节码后，又回到起点。

　　在引入即时编译（JIT）之前，Direct Threading方式基本上就是采用字节码方式的解释器的最有效和最块的分派方式了。对于一般的JavaScript运算，这种方式也足够用了。但是毕竟解释执行方式肯定比不上直接执行二进制代码。于是接下来即时编译（JIT）技术被引入了JavaScript引擎。

即时编译(Just-In-Time)

　　其实JIT这种技术本身很古老，可以追溯到上世纪60年代的LISP语言；并且现代的大部分运行时环境（runtime environment），如微软的.NET框架和大多数的Java实现都是依赖JIT技术来提高运行性能。在JavaScript引擎中引入JIT技术则是在2008年才开始。

　　JIT编译技术是一种提高程序运行性能的方法。通常一个程序有两种方式执行：静态编译和解释执行。静态编译就是在运行前先将源代码（如c，c++）针对特定平台（如x86,arm，mips）编译成机器代码，在运行时就可以直接在相应的平台上执行；而解释执行则是每次运行的时候，将每条源代码（如python, javascript）翻译成相应的机器码并立刻执行，并不保存翻译后的机器码，周而复始。可以看到解释执行的运行效率很低，因为每次执行都需要逐句地翻译成机器码然后执行；而静态编译在运行前就编译成相应平台的代码。但是静态编译使得平台移植性很差，也无法实施运行时优化，而且对于动态语言（弱类型语言），变量的类型在运行前未知，很难做到静态编译。JIT编译则是这两种方式的混合，在运行时将源代码翻译成机器码（这一点与解释执行类似），但是会保存已翻译的机器代码，下次执行同一代码段时无需再翻译（这又与静态编译类似）。

　　虽然对于一般的运算，Direct Threading方式已经很好了，但是对性能的追求永无之境，没有最好，只有更好。Direct Threading方式曾经是解释器（不仅仅JavaScript引擎）非常有效的分派方式。但是有研究和数据显示在现代体系结构下，这种方式也有很大的局限性（The structure and perfromance of efficient interpreters）。

　　现在的微处理器大量应用流水线构架来达到提高性能的目的。要让流水线总是保持满负荷运转，微处理器有一个专门的硬件设备“分支预测器”来预判分支的目标地址。这样在执行一条指令时，能提前将接下来可能执行的其他指令放入流水线中，上一条指令执行一结束，接下来的指令都已经完成取值和解码阶段，就可以直接执行。所以如果分支预测正确，将会大大提高处理器的性能。但是如果分支预测失败，那么就需要清空整个流水线，重新加载新的指令，而这会导致很严重的性能损耗。

　　分支预测是通过利用PC寄存器和分支目标的相关性来进行预测。而从图7的Direct Threading执行过程，可以看到分支跳转的目标（如goto *vpc++），是与vPC相关，而不是与实际的硬件PC寄存器相关。所以分支预测器没有足够的信息来进行有效的预测，这就导致的大量的分支预测失败。举个例子，图7中，当运行到add处理函数的尾部，在运行"goto *vpc++"之前，“分支预测器”是无法判断实际的跳转目标是在哪里，而只有等到执行完这句的时候才能准确知道要跳转到哪，而这样就会导致分支预测的时候不能把正确的后续指令推入流水线。数据表明30%~40%的执行时间会消耗在这种由于分支预测失败引起的额外处理上。所以要有效地降低分支预测的失败概率，就要给“分支预测器”提供足够的上下文信息。Context threading技术就是以此得名。

图8 Context Threading执行过程

　　可以看到最左边的图还是原来那个字节码数组，Context Threading是在这个表的基础上又增加了一个表Context Threading Table(从这个表中可以看到已经开始有即时编译了)。将字节码数组中的每条指令编译成一条条的本地调用（call指令）。上图与图7相比，除了多一个Context Threading Table外，在每个处理函数的结尾（右图红色标示）是一个与call 指令对应的ret指令。现代CPU对本地调用的返回地址提供一个非常有效的预测机制，从而就能避免大量的分支预测失败。如上图CPU在执行到“call add”时，在进入add的处理函数之前，会将返回地址（在这里就是下一条指令“call sub”指令的地址）保存在栈中，然后进入add的处理函数，当执行到add处理函数末尾ret时，“分支预测器”这时当然可以预测到要跳到哪了，就是刚才进入add处理函数之前保存的返回地址。所以在实际执行ret之前就可以准确的判断到将要执行的指令。而之前的Direct Threading方式无法做到这一点。

　　是否有必要将字节码数组中的每条指令都编译成一条条的本地调用呢？是的，没有必要。在实际的JavaScript引擎实现中，对于简单的指令，如mov，就直接即时编译，inline到机器码中；而对于复杂的指令，如add指令（因为JavaScript是动态语言，是无类型的，所以在运行add指令时需要做一系列的类型判断，如操作数都是数值类型，那么就进行数值加运算；如果操作数都是字符串类型，就进行字符串加运算，还有其他各种类型，所以add指令也算是一个比较复杂的指令），也会对它的常用方式（如操作数都是数值，或都是字符串）直接生成对应的机器码，对于add的其他不常用情况（如一个操作数是数值，另一个是字符串，或者发生溢出了等等情况）则是生成一条call本地调用。

　　在上文中提到从语法树生成字节码会消耗执行时间，而将字节码编译成本地机器码（JIT的过程）也需要消耗执行时间。在生成机器码过程中，实施越多的优化，生成的机器码质量越高，同时延迟时间也越长，所以需要权衡延迟的时间与生成的代码质量。

　　所以一般情况下，JavaScript引擎并不是对所有代码都会生成机器码，而是只对热点（hot spot）片段进行即时编译，同时在运行中会随时跟踪热点的状态，如果热点的程度越高（被执行得越频繁），实施的优化也越激进。

　　以FireFox3.5 JavaScript引擎为例（FireFox的JavaScript引擎叫SpiderMonkey, 在FireFox3.5中，他的JIT编译器叫TraceMonkey），在开始执行时，将源代码生成字节码，然后解释执行字节码，在执行过程中，如果发现一条路径多次执行（比如一个循环体），那么就标记为“HOT”，同时将这条路径上的代码即时编译成机器码，当下次再运行到这条路径时，就直接运行机器码。

　　在FireFox4.0中，引入了新的JIT编译器JaegerMonkey替换原来的TraceMonkey，JaegerMonke实际上是TraceMonkey的加强版，它除了跟踪热点路径外，同时又加入的热点函数的跟踪。

　　如下图：

图9 FireFox4.0的JavaScript引擎执行过程

　　在上图判断热点的虚框中，如果一个路径被执行了超过16次（比如“循环”迭代了超过16次），或一个函数被调用超过16次，那么就进行即时编译；否则解释执行。以这种方式，在JavaScript代码运算强度越大时JavaScript引擎性能提高得越明显，因为对于越频繁执行的代码，不仅是已经被编译成机器码了，同时执行的编译时优化和运行时优化也越充分。目前JIT编译已经是主流浏览器中JavaScript引擎的标配了。

　　随着JavaScript引擎性能显著提升，现在网站开发人员就可以在服务器端或者客户端上，充分利用JavaScript语言来完成一些繁重的运算任务。如果说AJAX让JavaScript焕发了第二春，那么HTML5的普及，则是进一步巩固了JavaScript在Web前端技术中的地位。所以JavaScript引擎的性能，一直会是各个浏览器厂商之间相互较量的重要利器。

　　这篇文章虽然只是关于JavaScript引擎发展的其中一条线索，但是只要抓住一条绳子，应该就能顺势摘到其它想要的桃子。