javascript - 在 JavaScript 中异步迭代大量数组而不触发堆栈大小超出

Question

我的环境是 NodeJS，尽管这也可能是与 Web 相关的问题。我有来自数据库的大量数据，我正在尝试枚举它们。然而，为了便于论证，假设我有一个包含 20,000 个字符串的数组:

var y = 'strstrstrstrstrstrstrstrstrstr';
var x = [];
for(var i = 0; i < 20000; i++)
  x.push(y);

我想异步枚举这个列表，假设使用 async library ，并且可以说，因为我非常谨慎，所以我什至将枚举限制为一次 5 次迭代:

var allDone = function() { console.log('done!') };
require('async').eachLimit(x, 5, function(item, cb){
  ...
  someAsyncCall(.., cb);
}, allDone);

预期 x 的 5 个项目将在上面同时迭代，最终所有 20,000 个项目将被迭代，并且控制台将打印“完成!”。实际发生的情况是:

Uncaught exception: [RangeError: Maximum call stack size exceeded]

此时我认为这一定是异步库的某种错误，因此我编写了自己的eachLimit 版本，如下所示:

function eachLimit(data, limit, iterator, cb) {
    var consumed = 0;
    var consume;
    var finished = false;
    consume = function() {
        if(!finished && consumed >= data.length) {
            finished = true;
            cb();
        }else if(!finished) {
            return iterator(data[consumed++], consume);
        }
    };
    var concurrent = limit > data.length ? data.length : limit;
    for(var i = 0; i < concurrent; i++)
        consume();
}

有趣的是，这解决了我的问题。但是当我将实验从 nodeJS 转移到 Chrome 时，即使使用上面的解决方案，我仍然收到超出堆栈大小的消息。

显然，我的方法不会增加与 async 中包含的eachLimit 方法一样大的堆栈。但是，我仍然认为我的方法很糟糕，因为可能不适用于 20k 项，但对于某些大小的数组，我仍然可以使用我的方法超过堆栈大小。我觉得我需要使用尾递归设计某种解决方案来解决这个问题，但我不确定 v8 是否会针对这种情况进行优化，或者考虑到这个问题是否可能。

Answer 1

I feel like I need to design some sort of solution to this problem using tail recursion, but I'm not sure if v8 will even optimize for this case, or if it's possible given the problem.

您使用的连续传递风格已经是尾递归(或接近)。问题是大多数 JS 引擎确实倾向于在这种情况下发生 stackoverflows。

解决此问题的主要方法有两种:

1) 使用 setTimeout 强制代码异步。

您的代码发生的情况是您在原始函数返回之前调用返回回调。在某些异步库中，这最终会导致堆栈溢出。一个简单的解决方法是通过将回调包装在 setTimeout 中来强制回调仅在事件处理循环的下一次迭代中运行。翻译

//Turns out this was actually "someSyncCall"...
someAsyncCall(.., cb);

进入

someAsyncCall(..., function(){
    setTimeout(cb, 0)
});

这里的主要优点是这非常简单。缺点是这会给循环增加一些延迟，因为 setTimeout 的实现使得回调总会有一些非零延迟(即使您将其设置为零)。在服务器上，您也可以使用 nextTick (或类似的东西，忘记确切的名称)来执行类似的操作。

也就是说，有一个大循环的顺序异步操作已经有点奇怪了。如果您的操作实际上都是异步的，那么由于网络延迟，它将需要数年时间才能完成。

2) 使用蹦床来处理同步代码。

100% 避免堆栈溢出的唯一方法是使用真正的 while 循环。有了 Promise，编写伪代码会更容易一些:

//vastly incomplete pseudocode
function loopStartingFrom(array, i){
    for(;i<array.length; i++){
        var x = run_next_item(i);
        if(is_promise(x)){
            return x.then(function(){
                loopStartingFrom(array, i+1)
            });
        }
    }
}

基本上，您在实际循环中运行循环，并通过某种方式来检测其中一次迭代是立即返回还是推迟到异步计算。当事情立即返回时，您将保持循环运行，当您最终获得真正的异步结果时，您将停止循环并在异步迭代结果完成时恢复循环。

使用蹦床的缺点是它有点复杂。也就是说，有一些异步库可以保证不会发生 stackoverflow(通过使用我在幕后提到的两个技巧之一)。