Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP

Loading…

setImmediate is not always very immediate #5798

Closed
bnoordhuis opened this Issue · 44 comments

9 participants

@bnoordhuis

Apply this patch:

diff --git a/src/node.cc b/src/node.cc
index a9c11e0..4192a82 100644
--- a/src/node.cc
+++ b/src/node.cc
@@ -181,6 +181,7 @@ Isolate* node_isolate = NULL;


 static void CheckImmediate(uv_check_t* handle, int status) {
+  puts(__func__);
   assert(handle == &check_immediate_watcher);
   assert(status == 0);

Then run this:

$ out/Release/node -e \
  'function f() { console.log("tick"); } for (var i = 0; i < 3; i++) setImmediate(f);'

Which prints this:

CheckImmediate
tick
CheckImmediate
tick
CheckImmediate
tick

Suggesting that the callbacks are spread out over multiple ticks, i.e. one per tick.

/cc @tjfontaine

@bnoordhuis

Mailing list link: https://groups.google.com/forum/#!topic/nodejs/A_uo0Mfmk5o (message ID 063a4318-5317-45b3-814d-b05b3c9382f7@googlegroups.com.)

@tjfontaine

That is certainly how it was designed, to avoid starving the loop we decided to only run one callback per tick.

Prior to 0.11 nextTick checks to see how "deep" you are and warns that you may essentially be starving the loop, in 0.11 that check is no longer there and nextTick will soldier on and do what you told it to do and fire every cb you scheduled.

The differentiating factor for setImmediate is that we're always yielding to the loop to let it do IO. Yes, that means that cb queued with setImmediate will fire more slowly than nextTick.

@trevnorris
Owner
@tjfontaine

The difference is that we could move the list out of the way, such that anything that would schedule a new setImmediate (while we're currently processing immediates) would indeed happen on the next tick

This avoids the recursive starvation that could happen with nextTick but not the general starvation problem for your application -- the question is if we care

@sam-github
Collaborator

Fwiw, the observed behaviour is what I would expect from reading the docs: "Immediates are queued in the order created, and are popped off the queue once per loop iteration.".

Its unfortunate that process.nextTick and the timers global setImmediate are in different modules despite being very similar, and that the behaviour is reversed from what I might guess from the name:

  • nextTick: runs during this loop iteration, afaict (modulo max tick depth, which is going away)
  • setImmediate: defers callback until later (the opposite of immediate?), one per iteration
@bnoordhuis

the question is if we care

I think we should. It hurts throughput and doesn't behave like I would expect it to. (YMMV, of course. Sam is a counterpoint to my second argument.)

@tjfontaine

The question is if we should care that the change would potentially let the user starve his application, we obviously care that what we're doing may be the exact opposite and slowing down an application and having unintended consequences.

On the plus side, it is working exactly like I documented :)

@trevnorris
Owner

A change like this would put setImmediate back into the same situation process.nextTick was in. Either the user is allowed to starve their application, which setImmediate was supposed to get around, or we have to set an arbitrary time in which to break the loop and allow I/O to flow.

@othiym23

I think that if we swapped the names of nextTick and setImmediate, most of the confusion would go away.

It seems pretty clear to me that both functions are useful: nextTick allows you to ensure that a function is "always asynchronous" without incurring a penalty in terms of overhead, and setImmediate allows you to distribute computation over many turns of the event loop while ensuring that I/O doesn't get starved. If setImmediate worked through the entire queue of callbacks on the next turn of the event loop, that reintroduces the possibility of starvation. The current behavior is more expensive, but (IMO) more useful as a counterpart to nextTick. I also think it's more intuitive, but that's a matter of opinion.

What this suggests is that the docs need to be clearer in terms of explaining when you'd want to use one instead of the other (and also maybe gently guiding people away from using setTimeout(fn, 0), although maybe we could modify setTimeout(fn, 0) to process the entire callback queue on a further turn of the event loop, because setTimeout(0)'s semantics are sufficiently vague and magic is great!).

@othiym23

Also, for purely documentary purposes, putting nextTick() on global instead of process or cross-referencing it from the timers page would be very useful.

@bnoordhuis

Starvation doesn't have to be an issue, we could do something like this:

var queue = immediateQueue;
immediateQueue = {};
while (!L.isEmpty(queue)) {
  var obj = L.shift(queue);
  obj.cb();
}

IOW, operate on a copy of the 'pending callbacks' list and clear the original. If a callback calls setImmediate(), that callback won't get invoked until the next tick. Problem solved, right?

@othiym23

I think conceptually it makes sense to handle one setImmediate per turn of the event loop -- it's simpler and more consistent, even if performance suffers. nextTick is there if you want something with minimal overhead.

@trevnorris
Owner

I still don't fully understand how this would work w/ multiple callbacks and multiple levels. example:

function log(n) { console.log(n); }

setImmediate(function() {
  setImmediate(function() {
    log(1);
    setImmediate(function() { log(2); });
    setImmediate(function() { log(3); });
  });
  setImmediate(function() {
    log(4);
    setImmediate(function() { log(5); });
    setImmediate(function() { log(6); });
  });
});

// output: 1 4 2 3 5 6

To achieve this you'd need to maintain multiple lists.

@tjfontaine

Only two lists are needed

  • Currently being processed list of queued immediates
  • List of immediates to be processed next round

There's no difference in order of execution because every created immediate always goes on the end, there's only a difference in which tick they happen on

@trevnorris
Owner

@tjfontaine that still means I could essentially starve I/O. Not indefinitely because v8 would eventually crash from filling up an object beyond bounds, but would change the following doc:

setImmediate will yield to the event loop after firing a queued callback to make sure I/O is not being starved.

@tjfontaine

Yes, as I pointed out above, it can starve your application, but not in quite the same pathological way a recursive nextTick would. This is because as you queue new immediates (while immediates are being processed) they won't happen until the next tick.

@trevnorris
Owner

Guess my thought was that setImmediate would/should always be safe from begin able to starve I/O. Surprised @isaacs hasn't chimed in on this.

@othiym23

Repurposing a conversation I had about this with @domenic...

Given how messy the situation is when dealing with the event loop across multiple JS runtimes, and the absence of standards here, does it make sense to try to reuse names from the browser to mimic semantically similar behaviors in Node, or should we give these functions names that accurately reflect their behavior? Cross-environment consistency has merit, but right now nextTick and setImmediate describe what they do poorly, especially in relation to each other.

I'm not devoted to the idea of swapping the names of nextTick and setImmediate, but I do feel that it would be in Node's best interests to unify the timer API. In fact, I'd like to see Node completely divorce itself from the browser context altogether and do all this via a module rather than via globals. It would be polyfillable in libraries like Q, and would allow us to handle all these cases, depending on how much the community cared about them:

  • run functions asynchronously and as soon as possible (process.nextTick)
  • run an entire queue of functions on the next turn of the event loop (doesn't exist today)
  • run through a queue of functions on subsequent turns of the event loop, one at a time (setImmediate)
  • run a function a specified number of turns of the event loop in the future (doesn't exist)
  • run a function at an arbitrary time in the future (setTimeout)
  • run a function at a specified interval (setInterval)
  • run a function every x turns of the event loop (doesn't exist)

I can see games and other latency-sensitive applications caring about some of those nonexistent functions, but my larger point is that right now this very important class of functions are scattered across the API surface of the runtime in a scattershot way due to the desire to provide a more browser-like interface, when it makes more sense (to me, at least) to centralize them in a module that can be used and documented as a single unit.

@tjfontaine

There are two basic ideas then that core should formalize and export

  • turn - happens once per iteration
    • currently implemented via uv_check that drives setImmediate
  • schedule - happens some time in the future
    • essentially the internal Timeout class that setTimeout and setInterval use

Everything else can be built on those.

Removing those globals would certainly cause some upheaval, but if we're going to do it we need to agree to start the deprecation procedure for v0.12.

@Mithgol

The backwards compatibility of nextTick was once broken (around 2012.07.20, for Node 0.9.0), and setImmediate introduced to act as an equivalent of (and instead of) the previous version of nextTick (around 2012.08.28, for Node 0.9.1). That was the right time to notice that nextTick is going to become not so “next” and the introduced setImmediate is not very “immediate”.

But that time passed, the dust settled, and the applications relying on the current meanings of both of those functions started to appear gradually. Now (almost a year later) should the backwards compatibility be broken once again? Could it be that both functions just need to be documented slightly better?

For example, process.nextTick() is documented at http://nodejs.org/docs/latest/api/process.html#process_process_nexttick_callback currently. Could setImmediate() be also mentioned there (with differences explained thoroughly)? Would it be enough to prevent misunderstandings and solve the issue without harming the current usus of functions?

@trevnorris
Owner

Would just like to clarify a couple things that @tjfontaine and i discussed on IRC.

First is that developers should not think about process.nextTick() in terms of the uv_run() event loop. Instead think of it in terms of the function passing the callback. This is because the nextTickQueue[] will be drained whenever MakeCallback() runs. Which can happen several times during the event queue.

Tthe functionality of process.nextTick() as it works now is absolutely necessary, and it works exactly as it should. Does it have an incorrect name? Maybe. It'd probably be better as process.runImmediatelyAfterThisCallbackBeforeOtherIO() or some such, but i'm not really concerned about that. What I'm getting after with this is just to solidify that the functionality it provides doesn't change.

So again, don't think of process.nextTick as a timer. Because it's not. It's a completely different type of functionality. Put most basically, a promise that callbacks passed will run after the current function but before any other I/O. Though that promise is broken if a callback throws. In which case it will resume on the following tick.

Again just to make it really really clear. process.nextTick should not be part of any discussion about timers.

@othiym23 You're point on "run an entire queue of functions on the next turn of the event loop (doesn't exist today)". It does. Not pretty, but it does.

setImmediate(function() {
  process.nextTick(cb1);
  process.nextTick(cb2);
  process.nextTick(cb3);
});

Here it will schedule a single function to run on the next tick, after which the entire queue of callbacks will also run. Of course this does have the caveat that if there are multiple setImmediate callbacks queued that it may not happen for several loops, but you get the general idea.

@bnoordhuis

Before the topic derails further, here is what I had in mind:

diff --git a/lib/timers.js b/lib/timers.js
index f4a6069..d5dc787 100644
--- a/lib/timers.js
+++ b/lib/timers.js
@@ -313,19 +313,24 @@ L.init(immediateQueue);


 function processImmediate() {
-  var immediate = L.shift(immediateQueue);
+  var queue = immediateQueue;
+  immediateQueue = {};
+  L.init(immediateQueue);
+
+  while (L.isEmpty(queue) === false) {
+    var immediate = L.shift(queue);
+    var domain = immediate.domain;
+    if (domain) domain.enter();
+    immediate._onImmediate();
+    if (domain) domain.exit();
+  }

+  // Only round-trip to C++ land if we have to. Calling clearImmediate() on an
+  // immediate that's in |queue| is okay. Worst case is we make a superfluous
+  // call to NeedImmediateCallbackSetter().
   if (L.isEmpty(immediateQueue)) {
     process._needImmediateCallback = false;
   }
-
-  if (immediate._onImmediate) {
-    if (immediate.domain) immediate.domain.enter();
-
-    immediate._onImmediate();
-
-    if (immediate.domain) immediate.domain.exit();
-  }
 }

The numbers:

# before
$ /usr/bin/time out/Release/node -e 'function f() {} for (var i = 0; i < 1e6; ++i) setImmediate(f)'
0.18user 8.79system 0:08.97elapsed 100%CPU (0avgtext+0avgdata 102544maxresident)k
0inputs+0outputs (0major+25960minor)pagefaults 0swaps

# after
$ /usr/bin/time out/Release/node -e 'function f() {} for (var i = 0; i < 1e6; ++i) setImmediate(f)'
0.38user 0.23system 0:00.61elapsed 100%CPU (0avgtext+0avgdata 102560maxresident)k
0inputs+0outputs (0major+25972minor)pagefaults 0swaps

tl;dr 1,400% speedup.

@domenic

So again, don't think of process.nextTick as a timer. Because it's not. It's a completely different type of functionality. Put most basically, a promise that callbacks passed will run after the current function but before any other I/O. Though that promise is broken if a callback throws. In which case it will resume on the following tick.

Woah! This is bad. Did not realize it worked this way. Allowing plan interference attacks via throwing handlers is the opposite of what any asynchronous scheduling mechanism should be about. (See e.g. slides 44 onward of Mark Miller's presentation.)

Have you considered using finally to allow the queue to continue unrolling? E.g. as in https://github.com/montagejs/montage/blob/601f849e86150f427ebe49bef8317b3fcf4488f2/core/next-tick.js#L76-L96

@trevnorris
Owner

@bnoordhuis you can check if domains are being used before checking if there's a domain by require('events').usingDomains.

@domenic we already do (https://github.com/joyent/node/blob/master/src/node.js#L372-L377). Problem w/ the approach of marching blindly on in the case of an error is that an error callback can also throw. If you hit that, and you're using domains, you're now in an infinite loop.

@domenic

and you're using domains

Oh dear :(. I'll have to give this some thought; there must be a way to avoid plan interference attacks while preserving domain functionality (and not hurting performance of course).

@sam-github
Collaborator

@trevnorris I completely agree with

Again just to make it really really clear. process.nextTick should not be part of any discussion about timers.

Its equally as true that setImmediate should not be part of any discussion about timers, for all the same reasons. Its hard to understand why it got put in the timers section.

I agree with @Mithgol, despite the confusing names, a good first step would be to accurately document the current behaviour (a 1,400% speed improvement would be nice, too), starting with rewriting "On the next loop around the event loop call this callback. "

If you call nextTick from inside nextTick, won't it happen right away? And aren't there multiple points in a uv_run loop where the nextTick queue is processed? When the first sentence of the docs are so wrong, its hard to recover.

@Mithgol

A good starting step would be editing http://nodejs.org/docs/latest/api/process.html#process_process_nexttick_callback to put a hyperlink leading to http://nodejs.org/docs/latest/api/timers.html from there (in order for any human reader to be able to compare them and make an informed choice).

The description of setImmediate() already references process.nextTick() (without any hyperlinking, unfortunately) and explains some differences. I suppose the description of process.nextTick() should do at least the same.

@tjfontaine tjfontaine referenced this issue from a commit
Commit has since been removed from the repository and is no longer available.
@tjfontaine tjfontaine referenced this issue from a commit in tjfontaine/node
@bnoordhuis bnoordhuis timers: setImmediate process full queue each turn
Previously only one cb per turn of the event loop was processed at a
time, which is not exactly what is meant by immediate

fixes #5798
9126f3c
@tjfontaine tjfontaine referenced this issue from a commit in tjfontaine/node
@tjfontaine tjfontaine test: regression test for #5798 setImmediate af3263d
@bnoordhuis bnoordhuis closed this issue from a commit
@bnoordhuis bnoordhuis timers: setImmediate process full queue each turn
Previously only one cb per turn of the event loop was processed at a
time, which is not exactly what is meant by immediate

fixes #5798
fa46483
@trevnorris
Owner

The updated changes the execution order, which now seems incorrect:

setImmediate(function() {
  console.log('0');
  process.nextTick(function() {
    console.log('2');
    process.nextTick(function() {
      console.log('3');
    });
  });
});

setImmediate(function() {
  console.log('4');
  process.nextTick(function() {
    console.log('5');
  });
});

// before: 0 2 3 4 5
// now:   0 4 2 5 3

I expect that callbacks passed to process.nextTick to run immediately after the running callback, before any other callback. Now that is not the case.

@tjfontaine

change setImmediate to setTimeout(..., 0) you'll observe that we don't make that promise in a lot of other places.

almost nearly solidifying my belief that nextTick should not be consumed by external users

@OrangeDog

So nextTick, which was originally an efficient version of setTimeout(..., 0), was changed and setImmediate was added to keep an efficient version of setTimeout(..., 0), and now that's been changed and we're back to setTimeout(..., 0) again?

@Mithgol

How is setImmediate() different from process.nextTck() after #5835 / fa46483?

@tjfontaine

The setImmediate queue is processed exactly once per event loop, and any immediates scheduled while processing that queue won't happen until the next turn of the event loop.

nextTick queue is processed on every MakeCallback boundary jump from cc to js, and any nextTick scheduled while processing that queue will be appended and happen in the same sequence.

@Mithgol

Very good.

@bjouhier

nextTick is nothing more than a trampoline helper.

It is important to document the fairness issue. Besides nextTick which is handled in a special way, are all the other callbacks handled in a fair way (first in, first out), or are they dequeued from several queues, in which case some queues have higher priority and could even starve the other queues?

From what I understand each turn of event loop resets the queues and processes all the callbacks that had been queued. The callbacks are on separate queues so they are not processed exactly in a first-in first-out fashion. But there is no risk of starvation as all the queues are emptied at every turn of the event loop.

But I'm not sure I'm getting it right. Can someone comment?

@tjfontaine
@bjouhier

Thanks TJ.

I just have one more question: what are the categories, and in which order are they processed?

@tjfontaine
  • nextTick
  • setImmediate
  • setTimeout-N (where N indicates the time to wait before calling)
@bjouhier

What about the callbacks from I/O operations? Are they on a separate queue, processed after the setTimeout queue?

@tjfontaine

ordering of IO is outside the scope of this issue, but you can feel free to discuss it on the mailing list, I'll drop here the image of ordering that's slightly out of date, but still mostly true

ordering

@bjouhier

OK but the diagram does not show if only one I/O callback is dequeued at each turn of the loop or if all the queued I/O callbacks are processed. I ran a little test and it looks like several I/O callbacks are processed.

@trevnorris
Owner
@othiym23

@trevnorris @tjfontaine I've been working on a blog post off and on for weeks now with a bunch of this stuff in there. Here's my current draft: https://gist.github.com/othiym23/6102710

Feel free to suggest revisions, or fork and edit. Big blocker right now is doing enough of a crawl through the C++ to accurately describe how the event loop is actually run. I have the JS side down, but the interaction between node.js, MakeCallback, ReqWrap, and the various bits of libuv still eludes me a little. Also it's late and I'm tired, so I'll have to pick this up again this week.

@bnoordhuis

Here's a quick run down of what a tick of the libuv event loop looks like. Dispatch in chronological order:

  • timer handles (drives setTimeout / setInterval)
  • idle handles (these are pretty much irrelevant to node.js code)
  • prepare handles (ditto)
  • I/O callbacks (includes polling for new events, may block if no work is queued)
  • check handles (drives setImmediate)
  • handle close callbacks

process.nextTick() callbacks weave through pretty much all of the above, just about everything that calls into JS land can set off a dispatch of pending nextTick callbacks...

... which is pretty fscking stupid IMO, it should be more like setImmediate() and dispatch only once per tick. The downside is that callbacks may sit in the queue longer which can affect latency and/or throughput.

The whole current "call into JS land" scheme is pretty deranged right now. A call to MakeCallback() potentially does four C++ to JS calls: to enter the callback's domain, to invoke the callback, to exit the domain again and to dispatch pending nextTick callbacks. That's a lot of potential overhead. :-(

Anyway, hope that helps.

(EDIT: That comment about the four calls into JS land is only applicable when you use domains. If you don't, there's just the callback and the nextTick dispatch.)

@trevnorris
Owner
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.