js中非死循环引起的栈调用溢出问题

时间:2023-03-09 08:33:38
js中非死循环引起的栈调用溢出问题

一般情况下,仅从代码上看只要不出现死循环,是不会出现堆栈调用溢出的。但是某些情况下列外,比如下面这段代码:

 var a = 99;
function b (){
a --;
if (a > 0){
b();
} else {
console.info(a);
}
}
b();
=> 0

这并不是死循环,当变量 a逐渐减少到0时,递归就终止了。乍一看是不会出现任何问题的,但是如果我们把 a增加到一个较大的数值,就会出现问题:

js中非死循环引起的栈调用溢出问题

如图所示,一个范围错误的异常抛了出来,我们被告知"超过了最大栈调用大小",哈哈,如果业务代码里出现了针对大量数据的递归,后果可想而知。所有我们有必要知道js调用栈的一些特点。

针对示例中 b函数来说,它的内部应用了外部作用域中的 a变量,形成了闭包,只要符合条件,它会一直被递归调用。而当b函数每一次被调用都会有新的闭包产生,为了记录对外部作用域中的变量引用,上一次因函数调用产生的栈帧不会从栈顶出去,导致栈中的栈帧超过了允许的数量而抛出栈调用溢出的异常。我们在函数内部能从arguments获取调用时的入参以及函数体本身(callee),以及调用者(caller),都是建立在该次函数调用产生的栈帧被记录的基础上的。而js引擎(或者是其他计算机语言的解释器)设计这种限制的目的就是在于要控制程序对内存资源的使用量,如果无此限制,一个错误的代码就足以让计算机奔溃。在较为新版的Chrom中,调用栈深度在13000次左右,FireFox在60000次左右,Node.js在10000次左右。因版本不同可能限制不同,这个可以自行测试。

针对js递归中容易出现栈调用溢出问题,是有解决办法的。

利用js事件循环机制来处理该问题

js最初就是被作为浏览器端语言而开发的,它能够和处理DOM的引擎进行交互,它处于和处理HTML、CSS、layout等事务的线程中也就是主线程中。以chrome浏览器多进程架构为例,一个web页面实际就是由主线程和排版线程(或者叫合成线程)相互协作来完成一个页面的渲染和更新的,这两个线程处于渲染进程内部,由渲染进程进行调度。当然对于整个浏览器来说,还存在有其他的进程,多个进程之间的协作完成整个浏览器的所有工作,包括多tab展示多个页面。简单的说来就是主线程解析和处理上层语言的代码,解析出最终的位图(像素阵列图像)并交给排版线程,排版线程根据主线程输出的结果,调用操作系统底层图形接口来计算和绘制页面到显示器上(主要是涉及到与GPU有关的事务)。但为了表现的一致性,在主线程内部,JS和DOM引擎的交互不是并行工作的。如果它们之间的操作是非阻塞的话,需要非常复杂的锁机制来避免同时对一个元素进行操作而导致出错,所以同时多个对DOM的修改之间必须是互斥的。主线程与排版线程之间是并行工作的,排版线程不会一直等待主线程的位图反馈,无反馈就直接渲染空白,会出现掉帧、白屏等现象。主线程的特点确保了页面的表现一致性,但却带来了另外一个问题:阻塞。

试想如果我在做一个xhr请求,在请求没回来之前,按照单线程阻塞的特点,页面是没有任何反应的,所有浏览器内部事务和用户操作都阻塞了,动画全部停止,用户的点击事件也没法响应,这简直就是噩梦。为了避免这个问题,js在设计之初就拥有一个 Event Loop 事件轮询(循环)机制来支持异步回调,特备是I/O有关的异步回调。

js中非死循环引起的栈调用溢出问题

由上图可以看出在主线程之外其实还维护了一个队列,整个过程由上到下。我们使用setTimeout等异步定时器操作的函数都被推入了任务队列中,而不是在主线程里直接被运行了。当主线程的C过程中的同步任务被执行完后,在此刻主线程中的任务都被执行完,事件轮询会在任务队列中去查看是有任务需要执行的事件。这个事件的产生就是由任务队列中的任务执行完成后生成出的一个标记。如果任务队列中有需要执行的事件,那么将这个事件所对应的任务推回主线程中进行执行,如上图 A函数,A函数执行完成后或者在执行的过程中,主线程执行栈中又被压入了一个D过程的同步任务,在A函数执行后就开始执行D任务。当然数值都只是打个比方,不可能经过100毫秒、200毫秒就正好可以见缝插针。总之事件轮询机制就是不停地定时查看主线程是否空闲,如果空闲,就去队列中找事情到主线中去做。也就是说异步的函数调用是不会阻塞的,除非是主线程同步任务自己阻塞了,比如:

js中非死循环引起的栈调用溢出问题

在浏览器中弹出alert,如果不点击确定,console的内容是永远不会出现的。因为alert(1)是在主线程中调用的,如果用户没有在浏览器上有任何点击弹出框确定按钮的动作,该同步任务一直在执行栈中处于挂起状态,主线程是一直阻塞着的,且无法进行下一个同步任务的执行。即便事件轮询机制发现了事件队列中有任务到了需要执行的时间点,该任务的执行也会排在主线程阻塞完成之后。

以上只是一个对异步循环机制队列的简单描述,其实队列还细分为宏任务(macro task)微任务(micro task)队列,微任务队列的优先级高于宏任务,低于主线程执行栈的任务。类似于setTimeout、setInterval等都归属于宏任务类型,而传入promise对象的then方法的函数归属于微任务类型,当同时存在时,调用then时传入的回调函数的执行优先级高于调用setTimeout等方法是传入的回调函数。

以上算是对js事件轮询机制有个初步的描述,那么利用这一机制怎么来解决递归中可能会出现的调用栈溢出情况呢?

通过上面的函数调用栈我们已经知道每次函数的调用如果有对外层内容的引用或依赖,本次函数调用时在调用栈中创建调用帧都会被保留。如果达到的最大调用大小还没有被清除,那么就会抛出异常。但是我们可以在每次调用的时候将对函数的递归调用放到异步方法中去,比如通过setTimeout方法,强行将函数的同步调用放到主线程以外的任务队列中,把主线程对函数调用的控制权交由更上一层的事件轮询机制来处理。之前代码片段可以修改为:

 var a = 9999;
function b (){
a --;
if (a > 0){
setTimeout(b, 4);
} else {
console.info(a);
}
}
b();

大概等了一会儿,控制台输出了0;实际测试中即便将a修改为99999,只要时间等的足够久也是能看到控制台打出东西的。

通过setTimeout异步函数来调用b时,上一次当b函数被调用完成后,主线程的执行栈会清除掉该次调用栈帧,因为到setTimeout这里的时候,主线程执行栈已经知道b在主线的调用已经结束了,不需要为它保存任何记录,它被推入了主线程外的队列中去了,控制权由主线程交到了事件轮询机制手里。既然调用栈帧每一次都会被清除,自然也不会出现调用栈达到最大值的异常了。当定时器到点时,就会在任务队列中产生一个事件,事件轮询机制下一次轮询的时候,会在任务队列中发现这个事件,就会知道b函数现在可以被拿回到主线程中执行了。

同时这也解释了为什么setTimeout和setIntervel异步调用的函数内容的this指向的是window对象,因为即便他们是处于某个对象的方法中,他们的调用也就是事件轮询机制决定的,并不是主线程一手操控,和他们在被书写时候处于哪个对象内部并没有直接的关系。其实是js引擎(对于页面作用域来说也就是window对象)调用了它们,而不是代码上的a对象调用的,所有this也自然不会指向a对象:

js中非死循环引起的栈调用溢出问题

除了这个方法可以处理递归调用可能存在的调用栈溢出问题,还有尾调用优化也能解决,在支持ES6的现代浏览器,只要函数是尾调用并开启 "use strict" 严格模式,就会在执行的时候被优化成循环方式来替换函数递归调用进行优化,避免巨量的调用帧出现且不能被清空的情况发生。但是,ES标准中最初有针对编译器提出过尾调用优化的要求,但后来这个标准被废弃了。

在babel6以下版本,一代源代码符合尾调用,会被转译成while循环来避免因递归的深层级而引起的爆栈,但在后续babel6版本中被取消了,可能是因为while性能不佳也不被严格模式支持的原因,或这是ES标准变动上的原因,后续可能会有更优方案提供。

Node.js中的事件循环机制

在Node.js中有一套基于服务端应用用途的事件循环机制,对于JavaScript语言来说,setInterval、setTimeout作为语言标准是一定支持的外,setImmediate和process.nextTick是Node.js独有的,而Promise的异步回调是ES2015标准加入的,在现代浏览器中也都支持。这些方法或新标准在较为新的Node.js版本中都能完全支持。Node.js引入libuv库作为内部事件循环机制的管理器。先抛开I/O操作,看一下Node.js中的回调函数是怎么被处理的:

// a.js

setTimeout(() => console.log(1));
setImmediate(() => console.log(2));
process.nextTick(() => console.log(3));
Promise.resolve().then(() => console.log(4)); $ node a.js
4
3
1
2

这三句话都是以异步回调的模式运行,不是直接在主线程中执行的。可以看到3和4先被打印出来,1和2跟随其后,为啥后执行的反而先出来呢?在Node.js中异步任务可以分成两种:追加在本轮事件循环的异步任务和追加在次轮事件循环的异步任务。使用过Vue.js的同学一定对nextTick这个东西不陌生,它可以传入一个下一次渲染时再调用的函数,这个函数在下一次渲染的时候再执行。但在Node.js中,通过上面代码的执行nextTick其实追加到本轮循环执行后的,是所有异步任务里面最快执行的,哈哈,它的名称似乎产生了误解。对于Promise来说,根据ES2015的语言标准,会进入异步队列中的microTask队列,并追加在nextTick之后,也属于本轮事件循环的异步任务。所有的微任务队列在nextTick队列执行完成后执行,nextTick队列在同步任务执行完成后执行。
js中非死循环引起的栈调用溢出问题

加入I/O操作后,事件循环机制有6个阶段:

1. timers 对setTimeout和setInterval的处理
2. I/O callbacks 除timers和nextTick等以外的回调函数
3. idle, prepare libuv库内部执行
4. poll 轮询还未返回的I/O操作事件
5. check 执行nextTick也就是setImmediate回调函数
6. close callbacks 执行关闭请求的回调函数,比如socket.on('close', xxx)

每个阶段都有一个先进先出的回调函数队列。只有一个阶段的回调函数队列清空了,该执行的回调函数都执行了,事件循环才会进入下一个阶段。

Node.js的官方事件轮询的介绍说明,libuv官方介绍以供参考。