在 javascript 中递归构建承诺链 - 内存注意事项 [英] Building a promise chain recursively in javascript - memory considerations

问题描述

在这个答案中，一个promise链是递归构建的.

稍微简化一下，我们有:

function foo() {函数 doo() {//总是返回一个承诺if (/* 还有更多事情要做 */) {返回 doSomethingAsync().then(doo);} 别的 {返回 Promise.resolve();}}返回 doo();//返回一个承诺}

大概这会产生一个调用栈和一个承诺链——即深"和宽".

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

• 是这样吗?
• 有没有人考虑过以这种方式构建链的内存问题?
• promise 库之间的内存消耗会有所不同吗?

解决方案

一个调用栈和一个承诺链——即深"和宽".

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

我们在这里面对的是一个解析链¹——最终会发生什么，当满足递归的基本情况时，就像Promise.resolve(Promise.resolve(Promise.resolve(…))).如果你想这样称呼它，这只是深"，而不是宽".

<块引用>

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

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

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

[…].reduce(function(prev, val) {//对数组中的所有 val 连续执行 fnreturn prev.then(() => fn(val));}, Promise.resolve())

会显示一个尖峰，同时分配n个promise对象，然后一个一个慢慢解析，垃圾回收前面的，直到只有已解决的endpromise活着.>

内存^ 解决 promise "then" (tail)|链链递归|/|||/|||/|||___/|___ ___|\___ ___________|+---------------------------------------------->时间

<块引用>

是这样吗?

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

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

<块引用>

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

是的.例如，这是在 promises/aplus 中讨论过的，但还没有结果.

许多承诺库确实支持迭代助手以避免承诺then链的峰值，例如Bluebird的each和map方法.

我自己的 promise 库^3,4 在不引入内存或运行时开销的情况下具有解析链的功能.当一个承诺采用另一个承诺时(即使仍处于未决状态)，它们将变得不可区分，并且中间承诺不再在任何地方被引用.

<块引用>

promise 库之间的内存消耗会有所不同吗?

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

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

_{[1]:没有官方术语
[2]:嗯，他们是相互解决的.但是我们希望用相同的值解析它们，我们期望
[3]:无证操场，通行证aplus.自行阅读代码:https://github.com/bergus/F-Promise
[4]:也在这个拉取请求}

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 and a 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?

解决方案

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.each or Promise.reduce might do to sequentially execute handlers if it was written this way).

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.

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.

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 n promise 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.

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 loops with a dynamic condition (no fixed number of steps), you cannot really avoid it. In Haskell, where this is used all the time for the IO monad, 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.

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

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

Many promise libraries do support iteration helpers to avoid the spike of promise then chains, like Bluebird's each and map methods.

My own promise library^3,4 does 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.

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 resolve call, 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 esdiscuss but remains unresolved.

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

_{[1]: no official terminology
[2]: well, they are resolved with each other. But we want to resolve them with the same value, we expect that
[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}

这篇关于在 javascript 中递归构建承诺链 - 内存注意事项的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！