在 javascript 中递归构建承诺链 - 内存注意事项

Building a promise chain recursively in javascript - memory considerations

提问by Roamer-1888

In this answer, a promise chain is built recursively.

在这个答案中，一个承诺链是递归构建的。

Simplified slightly, we have :

稍微简化一下，我们有：

function foo() {
    function doo() {
        // always return a promise
        if (/* more to do */) {
            return doSomethingAsync().then(doo);
        } else {
            return Promise.resolve();
        }
    }
    return doo(); // returns a promise
}

Presumably this would give rise to a call stack anda promise chain - ie "deep" and "wide".

大概这会产生一个调用堆栈和一个承诺链——即“深”和“宽”。

I would anticipate a memory spike larger than either performing a recursion or building a promise chain alone.

我预计内存峰值会比单独执行递归或构建承诺链要大。

• Is this so?
• Has anyone considered the memory issues of building a chain in this way?
• Would memory consumption differ between promise libs?

• 是这样吗？
• 有没有人考虑过这样建链的内存问题？
• 承诺库之间的内存消耗会有所不同吗？

采纳答案by Bergi

a call stack and a promise chain - ie "deep" and "wide".

一个调用栈和一个承诺链——即“深”和“宽”。

Actually, no. There is no promise chain here as we know it from doSomeThingAsynchronous.then(doSomethingAsynchronous).then(doSomethingAsynchronous).…(which is what Promise.eachor Promise.reducemight do to sequentially execute handlers if it was written this way).

实际上，没有。正如我们所知道的那样，这里没有承诺链doSomeThingAsynchronous.then(doSomethingAsynchronous).then(doSomethingAsynchronous).…（如果以这种方式编写，这就是Promise.each或Promise.reduce可能会顺序执行处理程序）。

What we are facing here is a resolve chain¹- what happens in the end, when the base case of the recursion is met, is something like Promise.resolve(Promise.resolve(Promise.resolve(…))). This is only "deep", not "wide", if you want to call it that.

我们在这里面临的是一个解析链¹- 最终会发生什么，当满足递归的基本情况时，类似于Promise.resolve(Promise.resolve(Promise.resolve(…))). 如果你想这样称呼它，这只是“深”，而不是“宽”。

I would anticipate a memory spike larger than either performing a recursion or building a promise chain alone.

我预计内存峰值会比单独执行递归或构建承诺链要大。

Not a spike actually. You'd slowly, over time, build a bulk of promises that are resolved with the innermost one, all representing the same result. When, at the end of your task, the condition is fulfilled and the innermost promise resolved with an actual value, all of these promises should be resolved with the same value. That would end up with O(n)cost for walking up the resolve chain (if implemented naively, this might even be done recursively and cause a stack overflow). After that, all the promises except for the outermost can become garbage collected.

实际上不是尖峰。随着时间的推移，你会慢慢地构建大量的承诺，并用最里面的承诺解决，所有承诺都代表相同的结果。当在你的任务结束时，条件得到满足并且最内层的承诺用实际值解决时，所有这些承诺都应该用相同的值解决。这最终会O(n)导致遍历解析链的成本（如果天真地实现，这甚至可能以递归方式完成并导致堆栈溢出）。之后，除了最外层的所有承诺都可以成为垃圾收集。

In contrast, a promise chain that is built by something like

相比之下，由类似的东西构建的承诺链

[…].reduce(function(prev, val) {
    // successive execution of fn for all vals in array
    return prev.then(() => fn(val));
}, Promise.resolve())

would show a spike, allocating npromise objects at the same time, and then slowly resolve them one by one, garbage-collecting the previous ones until only the settled end promise is alive.

会显示一个尖峰，同时分配npromise 对象，然后一个一个慢慢地解决它们，垃圾收集之前的那些，直到只有已解决的 end promise 还活着。

memory
  ^     resolve      promise "then"    (tail)
  |      chain          chain         recursion
  |        /|           |\
  |       / |           | \
  |      /  |           |  \
  |  ___/   |___     ___|   \___     ___________
  |
  +----------------------------------------------> time

Is this so?

是这样吗？

Not necessarily. As said above, all the promises in that bulk are in the end resolved with the same value², so all we would need is to store the outermost and the innermost promise at one time. All intermediate promises may become garbage-collected as soon as possible, and we want to run this recursion in constant space and time.

不必要。如上所述，该批量中的所有承诺最终都以相同的值²解析，因此我们需要的只是一次存储最外层和最内层的承诺。所有中间承诺可能会尽快被垃圾收集，我们希望在恒定的空间和时间中运行这个递归。

In fact, this recursive construct is totally necessary for asynchronous loopswith a dynamic condition (no fixed number of steps), you cannot really avoid it. In Haskell, where this is used all the time for the IOmonad, an optimisation for it is implemented just because of this case. It is very similar to tail call recursion, which is routinely eliminated by compilers.

事实上，这种递归结构对于具有动态条件（没有固定步数）的异步循环是完全必要的，你无法真正避免它。在 Haskell 中，它一直用于IOmonad，因此对其进行了优化。它与尾调用递归非常相似，后者通常被编译器消除。

Has anyone considered the memory issues of building a chain in this way?

有没有人考虑过这样建链的内存问题？

Yes. This was discussed at promises/aplusfor example, though with no outcome yet.

是的。例如，这已在 promises/aplus 上讨论过，但还没有结果。

Many promise libraries do support iteration helpers to avoid the spike of promise thenchains, like Bluebird's eachand mapmethods.

许多承诺库确实支持迭代助手来避免承诺then链的峰值，例如 Bluebirdeach和map方法。

My own promise library^3,4does feature resolve chains without introducing memory or runtime overhead. When one promise adopts another (even if still pending), they become indistinguishable, and intermediate promises are no longer referenced anywhere.

我自己的承诺库^3,4没有引入内存或运行时开销的特性解析链。当一个承诺采用另一个承诺时（即使仍然未决），它们变得不可区分，并且中间承诺不再在任何地方被引用。

Would memory consumption differ between promise libs?

承诺库之间的内存消耗会有所不同吗？

Yes. While this case can be optimised, it seldom is. Specifically, the ES6 spec does require Promises to inspect the value at every resolvecall, so collapsing the chain is not possible. The promises in the chain might even be resolved with different values (by constructing an example object that abuses getters, not in real life). The issue was raised on esdiscussbut remains unresolved.

是的。虽然这种情况可以优化，但很少。具体来说，ES6 规范确实要求 Promise 在每次resolve调用时检查值，因此不可能折叠链。链中的承诺甚至可以用不同的值来解决（通过构造一个滥用 getter 的示例对象，而不是在现实生活中）。该问题已在 esdiscuss 上提出，但仍未解决。

So if you use a leaking implementation, but need asynchronous recursion, then you better switch back to callbacks and use the deferred antipatternto propagate the innermost promise result to a single result promise.

因此，如果您使用泄漏实现，但需要异步递归，那么您最好切换回回调并使用延迟反模式将最内层的承诺结果传播到单个结果承诺。

_{[1]: no official terminology
[2]: well, they are resolved with each other. But we wantto resolve them with the same value, we expectthat
[3]: undocumented playground, passes aplus. Read the code at your own peril: https://github.com/bergus/F-Promise
[4]: also implemented for Creed in this pull request}

_{[1]：没有官方术语
[2]：好吧，它们是相互解决的。但是，我们希望用相同的值来解决这些问题，我们期待的是
[3]：无证操场，通过Aplus的。阅读代码请自担风险：https: //github.com/bergus/F-Promise
[4]：也在此拉取请求中为 Creed 实现}

回答by Benjamin Gruenbaum

Disclaimer:premature optimization is bad, the real way to find out about performance differences is to benchmark your code, and you shouldn't worry about this (I've only had to once and I've used promises for at least 100 projects).

免责声明：过早优化是不好的，找出性能差异的真正方法是对您的代码进行基准测试，您不必担心这一点（我只需要一次，并且我已经为至少 100 个项目使用了 promise） .

Is this so?

是这样吗？

Yes, the promises would have to "remember" what they're following, if you do this for 10000 promises you'd have a 10000 long promise chain, if you don't then you won't (for example, with recursion) - this is true for any queueing flow control.

是的，承诺必须“记住”他们所遵循的内容，如果您为 10000 个承诺执行此操作，您将拥有 10000 个长的承诺链，如果您不这样做，那么您将不会（例如，使用递归） - 对于任何排队流控制都是如此。

If you have to keep track of 10000 extra things (the operations) then you need to keep memory for it and that takes time, if that number is a million it might not be viable. This varies among libraries.

如果您必须跟踪 10000 个额外的事情（操作），那么您需要为它保留内存，这需要时间，如果这个数字是一百万，它可能不可行。这因图书馆而异。

Has anyone considered the memory issues of building a chain in this way?

有没有人考虑过这样建链的内存问题？

Of course, this is a big issue, and a use case for using something like Promise.eachin libraries like bluebird over thenable chaining.

当然，这是一个大问题，并且是Promise.each在诸如 bluebird 之类的库中使用类似then链接的用例。

I've personally had in my code to avoid this style for a quick app that traverses all the files in a VM once - but in the vast majority of cases it's a non issue.

我个人在我的代码中避免了这种风格，用于一次遍历 VM 中所有文件的快速应用程序 - 但在绝大多数情况下，这不是问题。

Would memory consumption differ between promise libs?

承诺库之间的内存消耗会有所不同吗？

Yes, greatly.For example bluebird 3.0 will not allocate an extra queue if it detects a promise operation is already asynchronous (for example if it starts with a Promise.delay) and will just execute things synchronously (because the async guarantees are already preserved).

是的，大大。例如，如果 bluebird 3.0 检测到 promise 操作已经是异步的（例如，如果它以 Promise.delay 开头），则不会分配额外的队列，并且只会同步执行（因为已经保留了异步保证）。

This means that what I claimed in my answer to the first question isn't always true (but is true in the regular use case) :) Native promises will never be able to do this unless internal support is provided.

这意味着我在第一个问题的回答中所声称的并不总是正确的（但在常规用例中是正确的）:) 除非提供内部支持，否则本机承诺将永远无法做到这一点。

Then again - it's no surprise since promise libraries differ by orders of magnitude from one another.

再说一遍 - 这并不奇怪，因为 Promise 库彼此之间存在数量级的不同。

回答by dotslashlu

I just came out a hack that may help solving the problem: don't do recursion in the last then, rather, do it in the last catch, since catchis out of the resolve chain. Using your example, it would be like this:

我刚刚提出了一个可能有助于解决问题的 hack：不要在 last 中进行递归then，而是在 last 中进行catch，因为catch它超出了解析链。使用您的示例，它会是这样的：

function foo() {
    function doo() {
        // always return a promise
        if (/* more to do */) {
            return doSomethingAsync().then(function(){
                        throw "next";
                    }).catch(function(err) {
                        if (err == "next") doo();
                    })
        } else {
            return Promise.resolve();
        }
    }
    return doo(); // returns a promise
}

回答by dotslashlu

To complement the awesome existing answers I'd like to illustrate the expression, which is the result of such an asynchronous recursion. For the sake of simplicity I use a simple function that computes the power of a given base and exponent. The recursive and base case are equivalent to those of the OP's example:

为了补充令人敬畏的现有答案，我想说明表达式，这是这种异步递归的结果。为简单起见，我使用一个简单的函数来计算给定底数和指数的幂。递归和基本情况等效于 OP 示例中的那些：

const powerp = (base, exp) => exp === 0 
 ? Promise.resolve(1)
 : new Promise(res => setTimeout(res, 0, exp)).then(
   exp => power(base, exp - 1).then(x => x * base)
 );

powerp(2, 8); // Promise {...[[PromiseValue]]: 256}

With the help of some substitution steps the recursive portion can be replaced. Please note that this expression can be evaluated in your browser:

在一些替换步骤的帮助下，递归部分可以被替换。请注意，可以在您的浏览器中评估此表达式：

// apply powerp with 2 and 8 and substitute the recursive case:

8 === 0 ? Promise.resolve(1) : new Promise(res => setTimeout(res, 0, 8)).then(
  res => 7 === 0 ? Promise.resolve(1) : new Promise(res => setTimeout(res, 0, 7)).then(
    res => 6 === 0 ? Promise.resolve(1) : new Promise(res => setTimeout(res, 0, 6)).then(
      res => 5 === 0 ? Promise.resolve(1) : new Promise(res => setTimeout(res, 0, 5)).then(
        res => 4 === 0 ? Promise.resolve(1) : new Promise(res => setTimeout(res, 0, 4)).then(
          res => 3 === 0 ? Promise.resolve(1) : new Promise(res => setTimeout(res, 0, 3)).then(
            res => 2 === 0 ? Promise.resolve(1) : new Promise(res => setTimeout(res, 0, 2)).then(
              res => 1 === 0 ? Promise.resolve(1) : new Promise(res => setTimeout(res, 0, 1)).then(
                res => Promise.resolve(1)
              ).then(x => x * 2)
            ).then(x => x * 2)
          ).then(x => x * 2)
        ).then(x => x * 2)
      ).then(x => x * 2)
    ).then(x => x * 2)
  ).then(x => x * 2)
).then(x => x * 2); // Promise {...[[PromiseValue]]: 256}

Interpretation:

解释：

1. With new Promise(res => setTimeout(res, 0, 8))the executor is invoked immediately and executes a non-bllocking computation (mimicked with setTimeout). Then an unsettled Promiseis returned. This is equivalent with doSomethingAsync()of the OP's example.
2. A resolve callback is associated with this Promisevia .then(.... Note: The body of this callback was substituted with the body of powerp.
3. Point 2) is repeated and a nested thenhandler structure is build up until the base case of the recursion is reached. The base case returns a Promiseresolved with 1.
4. The nested thenhandler structure is "unwound" by calling the associated callback correspondingly.

1. 与new Promise(res => setTimeout(res, 0, 8))所述执行器被立即调用并执行非bllocking计算（模仿带setTimeout）。然后一个未解决Promise的返回。这等效doSomethingAsync()于 OP 的示例。
2. 解析回调Promise通过与此相关联.then(...。注意：此回调的主体已替换为powerp.
3. 重复第 2) 点并then构建嵌套处理程序结构，直到达到递归的基本情况。基本情况返回一个已Promise解决的1。
4. 嵌套的then处理程序结构通过相应地调用关联的回调来“展开”。

Why is the generated structure nested and not chained? Because the recursive case within the thenhandlers prevents them from returning a value until the base case is reached.

为什么生成的结构是嵌套的而不是链接的？因为then处理程序中的递归情况会阻止它们在达到基本情况之前返回值。

How can this work without a stack? The associated callbacks form a "chain", which bridges the successive microtasks of the main event loop.

没有堆栈如何工作？关联的回调形成了一个“链”，它连接了主事件循环的连续微任务。

回答by neatsu

This promise pattern will generate a recursive chain. So, each resolve() will create a new stack frame (with its own data), utilizing some memory. This means that large number of chained functions using this promise pattern can produce stack overflow errors.

这种承诺模式将生成一个递归链。因此，每个 resolve() 都会创建一个新的堆栈帧（带有自己的数据），使用一些内存。这意味着使用这种承诺模式的大量链式函数会产生堆栈溢出错误。

To illustrate this, I'll use a tiny promise library called Sequence, which I've written. It relies on recursion to achieve sequential execution for chained functions:

为了说明这一点，我将使用我编写的一个名为 Sequence的小型Promise 库。它依靠递归来实现链式函数的顺序执行：

var funcA = function() { 
    setTimeout(function() {console.log("funcA")}, 2000);
};
var funcB = function() { 
    setTimeout(function() {console.log("funcB")}, 1000);
};
sequence().chain(funcA).chain(funcB).execute();

Sequence works great for small/medium sized chains, in the range of 0-500 functions. However, at about 600 chains Sequence starts degradating and generating often stack overflow errors.

Sequence 适用于 0-500 函数范围内的中小型链。然而，在大约 600 个链时，序列开始退化并经常产生堆栈溢出错误。

The bottom line is: currently, recursion-based promise libraries are more suitable for smaller/medium sized function chains, while reduce-based promise implementations are ok for all cases, including larger chains.

底线是：目前，基于递归的 promise 库更适合中小型函数链，而基于 reduce 的 promise 实现适用于所有情况，包括更大的链。

This of course doesn't mean that recursion-based promises are bad. We just need to use them with their limitations in mind. Also, it's rare that you'll need to chain that many calls (>=500) via promises. I typically find myself using them for async configurations which utilize heavily ajax. But even if the most complex cases I haven't seen a situation with more than 15 chains.

这当然并不意味着基于递归的承诺是不好的。我们只需要在使用它们时考虑到它们的局限性。此外，您很少需要通过 promise 链接这么多调用 (>=500)。我通常发现自己将它们用于大量使用 ajax 的异步配置。但即使是最复杂的情​​况，我也没有看到超过 15 个链的情况。

On a side note...

在旁注...

These statistics were retrieved from tests performed with another of my libraries - provisnr- which captures the achieved number of function calls within a given interval of time.

这些统计数据是从我的另一个库 - provisnr执行的测试中检索到的，它捕获了给定时间间隔内实现的函数调用次数。