Building a Promise Chain Recursively in JavaScript - Memory Considerations

Building a promise chain recursively in javascript - memory considerations

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.

<sub>[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</sub>

Recursive promise chain

Is this a good practice?

If you just want it to repeat whenever it finishes and make sure the next iteration doesn't start before the previous one finishes, this is a perfectly fine practice (much better than setInterval()). Your looping stops if there's a rejection anywhere so you may want to code what should happen with a .catch().

Are there any memory problems with calling the "refresh" method recursively in the last '.then' statement?

No. There are not. Since .then() is always called asynchronously, the stack always gets to unwind and since you presumably have async operations in your chain, there should be time for normal garbage collection.

See Building a promise chain recursively in javascript - memory considerations for more discussion of memory consumption during the looping.

---

FYI, this must be pseudo-code because a function defined as a property refresh: function() {} won't be directly callable with .then(refresh). So, I'm assuming you did that properly in your real code.

JavaScript Promises: Recursively Building Promise Chain With Breadth-First Traversal

Promise chains can be extended dynamically, with new links inserted at any point in a chain, simply by returning a promise from any .then fulfillment handler.

Say each Task resolves with an array of its children. If children can be processed in parallel, then:

promiseParent
.then(children => Promise.all(children.map(child => loadChild(child))))
.then(grandchildren => Promise.all(grandchildren.map(child => loadChild(child))))

should do. If children must be processed sequentially, then:

let sequence = (a, f) => a.reduce((p, c) => p.then(() => f(c)), Promise.resolve());

promiseParent
.then(kids => sequence(kids, kid => loadChild(kid)).then(() => nextGen())
.then(gkds => sequence(gkds, kid => loadChild(kid)).then(() => nextGen())

will do that (I'm simplifying by assuming nextGen knows to return the next generation).

If the number of children must be discovered recursively, then:

let loadChildrenRecursively = child => loadChild(child)
  .then(nextChild => nextChild && loadChildrenRecursively(nextChild));

promiseParent
.then(firstChild => loadChildrenRecursively(firstChild)).then(() => nextGen())
.then(firstGchild => loadChildrenRecursively(firstGchild)).then(() => nextGen())

should do that.

To generalize this to N levels, pick any approach above, say in parallel, and recurse on it:

let doGeneration = generation =>
  Promise.all(generation.map(child => loadChild(child))))
  .then(offsprings => offsprings && doGeneration(offsprings))

promiseParent.then(children => doGeneration(children));

So you can always extend as long as there is more to do, by resolving a promise with another promise (which is what you implicitly do by returning a new promise from a .then fulfillment handler).

How can I chain many sequential promises while limiting stack depth?

Promises are asynchronous, which means it's not actually recursive calls; it's more like a loop. A simple example of this is the following, which isn't recursive either.

function send(buffers){
    buffers.shift();
    if (buffers.length) {
        setTimeout(send.bind(null, buffers), 10);
    }
}

send(buffers);

When we call send, it shifts a buffer, and then maybe registers a timeout, and then returns. Because it returns without calling itself, it's not recursive.

_{side note: With ES6, there's proper tail call optimization; which means recursion limits won't be a problem as often.}

Recursion with Promises means registered callbacks get called many times

If the recursion is synchronous, you can simply recurse within the .then's function

new Promise(res => {
    res(); // dummy initial promise
}).then(() => {
    function recurse(x) { // recursion inside then
        console.log('x', x);
        if (x < 10) return recurse(++x);
        return x;
    }
    return recurse(1); // begin recursion
}).then(y => { // this only fires once recursion above is resolved
    console.log('y', y);
    return 5;
}).then(z => console.log('z', z));
// x 1
// ... (synchronous)
// x 10
// y 10 (value passed from resolving inner promise)
// z 5 (value returned from previous then)

Or if our recursive function is asynchronous, we can have it return a promise too, so you end up with a recursion which looks like this

function doWork() {
    function addOne(x) {
        return new Promise((res, rej) => {
            // async bit here
            res(x + 1);
        });
    }
    function recurse(x) {
        if (x < 10) return addOne(x).then(recurse);
        return x;
    }
    return recurse(1);
}

And in a promise chain, would look like this

new Promise(res => {
    res(); // dummy initial promise
}).then(() => {
    return doWork();
}).then(y => {
    console.log(y);
});

Recursive thenables?

You can't get away with truly endless recursion. You'll get a stack overflow at some point.

function runMyRoutine() {
  runMyRoutine();  // call stack overflows here at some point
}

However, you don't actually have endless recursion in your case. If doThis() is set up correctly, the last runMyRoutine() is effectively on its own call stack (the same stack with whatever ends up calling the function wrapping it). It's disconnected from the original context.

Javascript promises and recursion: is this a stack bomb?

There's nothing wrong with writing recursive asynchronous functions. But let's take a step back and ask two important questions:

1. How do you know when it's safe to read the global localData?
2. How does backend.getMoredata know to fetch the "next" data? Ie, what's stopping it from repeating the first query?

To answer 1, we must wait until the last data is fetched and then finally resolve the last Promise – it's at that exact point we know we have all of the data.

To answer 2, you're probably using another global variable that you didn't include in your code paste. But in general, you'll want to avoid introducing new globals into your code. Instead ...

Use function parameters! We solve both problems by adding an optional parameter and defining a default value. Now, localData is actually local data, and it's obvious how backend.getMoreData queries the "next" data chunk

const fetchAll = (page = 0, localData = []) =>
  backend.getMoreData(page).then(data =>
    data.page === data.pageCount
       ? localData
       : fetchAll(page + 1, localData.concat(data.results)))

Here's a complete demo. I stubbed out backend and a DB constant so we can see it working in both the success and error scenarios

const DB =   { 0: { results: [ 'a', 'b', 'c' ], page: 1, pageCount: 3 }  , 1: { results: [ 'd', 'e', 'f' ], page: 2, pageCount: 3 }  , 2: { results: [ 'g' ], page: 3, pageCount: 3 }  }
const backend =  { getMoreData: page =>      DB[page] === undefined        ? Promise.reject(Error(`Data not found`))        : Promise.resolve(DB[page])  }  const fetchAll = (page = 0, localData = []) =>  backend.getMoreData(page).then(data =>    data.page === data.pageCount       ? localData       : fetchAll(page + 1, localData.concat(data.results)))       // query all data starting on page 0fetchAll().then(console.log, console.error)// [ 'a', 'b', 'c', 'd', 'e', 'f' ]
// query all data starting on page 5 (out of bounds)fetchAll(5).then(console.log, console.error)// Error: Data not found

---

Related Topics