recursion - Building a promise chain recursively in javascript - memory considerations

Question

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?

Answer 1

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}