Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Already on GitHub? Sign in to your account

Consumes O(n) memory when evaluating long promise chains #111

Closed
ef4 opened this Issue Sep 9, 2012 · 9 comments

Comments

Projects
None yet
2 participants
Collaborator

ef4 commented Sep 9, 2012

The following example consumes a surprisingly large amount of memory.

    function test(i){ 
        if (i <= 0){ 
           return Q.when('done')
       } else { 
           return Q.when(i-1).then(test) 
       }
    }
    test(10000).then(function(output){ alert(output) });

This isn't a permanent memory leak. The memory gets freed once the last promise is fulfilled. But until then, every intermediate promise seems to be staying in the heap and is not eligible for garbage collection.

While the above is a simplified example, this memory issue is causing real problems in my application.

Collaborator

ef4 commented Sep 10, 2012

I found a worse case. Here, the promises aren't chained together at all. Simply initiating one promise in the then handler of another seems to link them together (via closure references somewhere down inside Q).

function test(i){
    if (i <=0){
       console.log("Done"); 
    } else { 
       Q.when(i-1).then(test);
    }
}

The above keeps all the intermediate values in memory until the last one finishes. But if we insert a delay like this the problem goes away:

function fixed(i){
    if (i <=0){
       console.log("Done"); 
    } else { 
       Q.nextTick(function(){
         Q.when(i-1).then(fixed);
       });
    }
}

This fixed function run in constant memory, whereas the test function runs in linear memory.

Collaborator

ef4 commented Sep 10, 2012

PS: I realized my use of when above for coercing a value into a promise may be less correct than using resolve, but you get the same problem behavior either way.

Collaborator

ef4 commented Sep 10, 2012

I think I found the root cause. If I comment out this line in defer, we get nice constant memory usage:

        Error.captureStackTrace(promise, defer);

And this makes sense. If your current stack contains a bunch of closures, you're going to grab references to them here and they can't get GCed until you let go of the stack reference. Those closures in turn have many things in scope that can't get GCed, including other promises with their own stack references, and so on.

I don't know what the fix is here, other than to enable a mode that disables these nice stack traces in favor of better memory performance.

Collaborator

domenic commented Sep 10, 2012

Nice detective work. As for the fix, we should probably either respect Error.stackTraceLimit or implement a counterpart to it for Q stack traces (e.g. longStackJumpLimit).

Collaborator

ef4 commented Sep 10, 2012

A workaround that doesn't require altering Q is to set Error.stackTraceLimit = 0.

EDITED TO ADD:

I posted the above before seeing domenic's reply. Yes, agreed, I think Error.stackTraceLimit is probably sufficient. I'm don't think any Q-specific limit is needed.

Collaborator

domenic commented Sep 10, 2012

Well, but the point of Error.stackTraceLimit is somewhat different.

If you write non-Q code, even with long callstacks, you wouldn't run into this. With, say, Error.stackTraceLimit === 10, it would cap at 10 levels of stack traces, and memory usage would stay constant. That is, memory usage is O(Error.stackTraceLimit) = O(1).

But we capture multiple stack traces, one for each "jump" between short stack traces, so memory grows linearly. That is, memory is O(n * Error.stackTraceLimit) = O(n).

We could use Error.stackTraceLimit as an indication that you don't want memory to grow any further than that. I'm not sure we could do that accurately without triggering the getter---that is, to determine the actual length of each component stack trace, I think we'd need to look at the stack trace. But we could limit the number of stack jumps to Error.stackTraceLimit, giving a total possible memory consumption proportional to Error.stackTraceLimit * Error.stackTraceLimit. Or we could introduce longStackJumpLimit or similar, giving memory consumption proportional to longStackJumpLimit * Error.stackTraceLimit.

Collaborator

ef4 commented Sep 10, 2012

Ah right, got it. I was only considering the limit==0 case, which mitigates my immediate problem.

A constant-but-nonzero amount of stack frames would be even better. :-)

Collaborator

domenic commented Nov 22, 2012

OK, this is harder than I initially thought. I think it will require a redo of the long stack trace logic. Jotting down some notes here, both for myself and for anyone to comment on.


The current approach is to attach a stack property to every promise, essentially recording the stack at the time of its creation. (This is done in defer, where all pending promises come from. NB why don't we capture fulfilled and rejected stacks??)

We actually do not support more than one level deep of long stack traces. That is,

Q.resolve(5)
.then(function () { return 10; })
.then(function () { return 20; })
.then(function () { throw new Error("boo!"); })
.done();

only generates

C:\Users\Domenic\Dropbox\Programming\GitHub\q\q.js:1436
                throw error;
                      ^
Error: boo!
    at C:\Users\Domenic\Dropbox\Programming\GitHub\q\test.js:8:27
From previous event:
    at Object.<anonymous> (C:\Users\Domenic\Dropbox\Programming\GitHub\q\test.js:8:2)

This can clearly be seen by looking at the implementation of done: it just concatenates the error's stack trace with the promise's stack trace. It has no way of looking back in the history to find previous promises in the chain.

I'd like to fix this.


But, why is the current approach "leaking"?

It doesn't really make sense, if we only use the last stack trace, for us to keep around memory for every stack trace. Why is this happening? If @ef4 is right and commenting out Error.captureStackTrace keeps the memory constant, why is that? I'd expect it to still grow linearly, just with the increment being the size of a promise, not size of a promise + stack trace.

The key question: is the test function preventing the GC of 1000 promises inherently, or is it due to the stack traces?

Is it possible that by using these not-yet-serialized stack traces we're keeping references to closures and scope that keep the promise alive, even though we've since chained off it and moved on? Test this by serializing the stack trace.


Regardless, this needs a rewrite. The current architecture leaks and doesn't give you anything useful for your leaks; i.e. it only gives you one jump.

New strategy: each promise gets a chain of serialized stack traces, probably pre-concatenated. This can be capped using Q.stackJumpLimit.

Getting access to the existing chain is the tricky part. Currently we hook into defer, but that won't really suffice, since a deferred has no knowledge that it's being created in order to react to a previous promise in a chain. We'll probably need to hook in to a few places, with when being the primary candidate. That is, var promise2 = when(promise1) can transfer promise1's stack chain to promise2 for promise2 to build upon, and chop off the beginning if we're starting to exceed stackJumpLimit.

Collaborator

domenic commented Nov 22, 2012

WOW. It is indeed preventing GC because of the unserialized stack traces. That is, if I change

Error.captureStackTrace(promise, defer);

to

Error.captureStackTrace(promise, defer);
promise.stack;

the memory usage stays low. That means by doing #117 this bug should be fixed. We remain with the fact that there's only one stack jump level, but that's actually pretty orthogonal.

@domenic domenic closed this Nov 22, 2012

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment