Stop memory leaks with recursive promises

Question

How do I create a recursive chain of JavaScript Promises with the Q library? The following code fails to complete in Chrome:

<html>
    <script src="q.js" type="text/javascript"></script>
    <script type="text/javascript">
        //Don't keep track of a promises stack for debugging
        //Reduces memory usage when recursing promises
        Q.longStackJumpLimit = 0;

        function do_stuff(count) {
            if (count==1000000) {
                return;
            }

            if (count%10000 == 0){
                console.log( count );
            }

            return Q.delay(1).then(function() {
                return do_stuff(count+1);
            });
        }

        do_stuff(0)
        .then(function() {
            console.log("Done");
        });
    </script>
</html>

The promises library lines up functions to be called from a setTimeout(0) handler so there's no traditional stack exhaustion to worry about. It's just eating the heap with references to parent promises! — engie, Feb 22 '13 at 15:23
It doesn't complete because `do_stuff` doesn't return a promise when `count==1000000`, that doesn't help you though :P — peterjwest, Feb 22 '13 at 16:32
Closely related: [Building a promise chain recursively in javascript - memory considerations](http://stackoverflow.com/q/29925948/1048572) — Bergi, Mar 24 '16 at 13:50

ForbesLindesay · Answer 1 · 2016-03-24T13:47:57.367

This won't stack overflow because promises break the stack, but it will leak memory. If you run this same code in node.js you'll get an error that reads:

FATAL ERROR: CALL_AND_RETRY_2 Allocation failed - process out of memory

What is happening here is that a really long chain of nested promises is being created, each waiting for the next. What you need to do is find a way to flatten that chain so that there is just one top level promise that gets returned, waiting on the inner most promise that is currently representing some real work.

breaking the chain

The easiest solution is to construct a new promise at the top level and use it to break the recursion:

var Promise = require('promise');

function delay(timeout) {
    return new Promise(function (resolve) {
        setTimeout(resolve, timeout);
    });
}

function do_stuff(count) {
    return new Promise(function (resolve, reject) {
        function doStuffRecursion(count) {
            if (count==1000000) {
                return resolve();
            }

            if (count%10000 == 0){
                console.log( count );
            }

            delay(1).then(function() {
                doStuffRecursion(count+1);
            }).done(null, reject);
        }
        doStuffRecursion(count);
    });
}

do_stuff(0).then(function() {
    console.log("Done");
});

Although this solution is somewhat inelegant, you can be sure it will work in all promise implementations.

then/promise now supports tail recursion

Some promise implementations (for example promise from npm, which you can download as a standalone library from https://www.promisejs.org/) correctly detect this case and collapse the chain of promises into a single promise. This works providing you don't keep a reference to the promise returned by the top level function (i.e. call .then on it immediately, don't keep it around).

Good:

var Promise = require('promise');

function delay(timeout) {
    return new Promise(function (resolve) {
        setTimeout(resolve, timeout);
    });
}

function do_stuff(count) {
    if (count==1000000) {
        return;
    }

    if (count%10000 == 0){
        console.log( count );
    }

    return delay(1).then(function() {
        return do_stuff(count+1);
    });
}

do_stuff(0).then(function() {
    console.log("Done");
});

Bad:

var Promise = require('promise');

function delay(timeout) {
    return new Promise(function (resolve) {
        setTimeout(resolve, timeout);
    });
}

function do_stuff(count) {
    if (count==1000000) {
        return;
    }

    if (count%10000 == 0){
        console.log( count );
    }

    return delay(1).then(function() {
        return do_stuff(count+1);
    });
}

var thisReferenceWillPreventGarbageCollection = do_stuff(0);

thisReferenceWillPreventGarbageCollection.then(function() {
    console.log("Done");
});

Unfortunately, none of the built in promise implementations have this optimisation, and none have any plans to implement it.

Excellent. I had an identical recursive code structure as engie running in node and had a memory leak that I couldn't explain. The retention of return value solved it, thanks for the heads up. — Tim, Jan 19 '14 at 02:04
@kgram thanks for the edit suggestion, that line was left in by accident. I disagree with the editors who rejected the edit. — ForbesLindesay, Mar 24 '16 at 13:52
I was playing with these examples and if you change the timeout value (for example, using a `delay(1000)` instead of `delay(1)`), the JS Heap (at least in Chrome v62.0.3202.94) goes up and up. Does anyone know what could be the reason? — Christian Martinez, Dec 26 '17 at 19:39

score 2 · Answer 2 · answered Feb 22 '13 at 17:08

Below is the most simple implementation of what you're trying to do, if this works then there's a problem with the q library, otherwise there's some deep javascript troubles:

<html>
    <script type="text/javascript">
        function do_stuff(count) {
            if (count==1000000) {
                return done();
            }

            if (count%1000 == 0){
                console.log( count );
            }

            return setTimeout(function() { do_stuff(count+1); }, 0);
        }

        do_stuff(0);

        function done() {
            console.log("Done");
        };
    </script>
</html>

Stop memory leaks with recursive promises

2 Answers2

breaking the chain

then/promise now supports tail recursion

Linked