V8引擎支持WebAssembly尾调用,提高递归函数执行性能

由Google开发的开源JavaScript引擎V8,将会在V8 11.2版本加入WebAssembly尾调用(Tail Calls)支持,避免递归调用消耗大量内存导致堆栈溢出,进一步提高递归函数执行效率。

尾调用是一种程序开发技巧,主要在函数程序语言中使用,借此提高递归函数的效率,尾调用是指在函数最后一个操作调用另一个函数,但在调用完成之后不做任何额外的操作。而尾调用优化则是一种程序编译器或是解释器中的功能,可以避免尾调用导致额外的堆栈框。

由于每次函数调用时,编译器便会创建一个称为堆栈框(Stack Frame)的数据结构,来存储区域变量和回传地址,在递归中,这可能会累计大量堆栈框累计,因此消耗大量内存导致堆栈溢出,而编译器可以通过丢弃堆栈框,以跳转替换调用来优化调用。

一般递归函数调用会消耗O(n)的堆栈空间,而采用尾调用优化后,可以将递归函数简化仅使用O(1)堆栈空间。也就是说,原本在计算过程,堆栈空间的需求会与问题规模成正比,当连接串行(Linked list)中的每个元素都要在调用堆栈上增加一个新的资料框,因此在列表太长时便会溢出堆栈,通过跳转代替调用,便能够使消耗的堆栈空间与问题规模无关。Google解释,这种优化对函数程序语言很重要,因为函数语言严重依赖递归函数。

但因为侦测尾部位置的调用并非引擎的责任,而是由上游的工具链完成,因此V8的优化编译器TurboFan的工作,便是根据调用类型和目标函数声明,发出适当的指令串行。同时,V8中的WebAssembly基准编译器(Baseline Compiler)Liftoff也支持尾调用,以避免基准程序代码耗尽堆栈空间,但是在这一层并没有尾调用优化,会以一般调用运行方式处理。