timers: run nextTicks after each immediate and timer

In order to better match the browser behaviour, run nextTicks (and
subsequently the microtask queue) after each individual Timer and
Immediate, rather than after the whole list is processed. The
current behaviour is somewhat of a performance micro-optimization
and also partly dictated by how timer handles were implemented.

PR-URL: https://github.com/nodejs/node/pull/22842
Fixes: https://github.com/nodejs/node/issues/22257
Reviewed-By: Anna Henningsen <anna@addaleax.net>
Reviewed-By: Gus Caplan <me@gus.host>
Reviewed-By: Jeremiah Senkpiel <fishrock123@rocketmail.com>
Reviewed-By: James M Snell <jasnell@gmail.com>
Reviewed-By: Ruben Bridgewater <ruben@bridgewater.de>

13 files changed, 162 insertions, 158 deletions

diff --git a/benchmark/timers/timers-timeout-nexttick.js b/benchmark/timers/timers-timeout-nexttick.js
new file mode 100644
index 0000000000..781e505ae4
--- /dev/null
+++ b/benchmark/timers/timers-timeout-nexttick.js
@@ -0,0 +1,36 @@
+'use strict';
+const common = require('../common.js');
+
+// The following benchmark measures setting up n * 1e6 timeouts,
+// as well as scheduling a next tick from each timeout. Those
+// then get executed on the next uv tick.
+
+const bench = common.createBenchmark(main, {
+  n: [5e4, 5e6],
+});
+
+function main({ n }) {
+  let count = 0;
+
+  // Function tracking on the hidden class in V8 can cause misleading
+  // results in this benchmark if only a single function is used —
+  // alternate between two functions for a fairer benchmark.
+
+  function cb() {
+    process.nextTick(counter);
+  }
+  function cb2() {
+    process.nextTick(counter);
+  }
+  function counter() {
+    count++;
+    if (count === n)
+      bench.end(n);
+  }
+
+  for (var i = 0; i < n; i++) {
+    setTimeout(i % 2 ? cb : cb2, 1);
+  }
+
+  bench.start();
+}
diff --git a/doc/api/process.md b/doc/api/process.md
index 2eac116058..3907271bbf 100644
--- a/doc/api/process.md
+++ b/doc/api/process.md
@@ -1461,13 +1461,11 @@ changes:
 * `callback` {Function}
 * `...args` {any} Additional arguments to pass when invoking the `callback`
 
-The `process.nextTick()` method adds the `callback` to the "next tick queue".
-Once the current turn of the event loop turn runs to completion, all callbacks
-currently in the next tick queue will be called.
-
-This is *not* a simple alias to [`setTimeout(fn, 0)`][]. It is much more
-efficient. It runs before any additional I/O events (including
-timers) fire in subsequent ticks of the event loop.
+`process.nextTick()` adds `callback` to the "next tick queue". This queue is
+fully drained after the current operation on the JavaScript stack runs to
+completion and before the event loop is allowed to continue. As a result, it's
+possible to create an infinite loop if one were to recursively call
+`process.nextTick()`.
 
 ```js
 console.log('start');
@@ -1542,11 +1540,6 @@ function definitelyAsync(arg, cb) {
 }
 ```
 
-The next tick queue is completely drained on each pass of the event loop
-**before** additional I/O is processed. As a result, recursively setting
-`nextTick()` callbacks will block any I/O from happening, just like a
-`while(true);` loop.
-
 ## process.noDeprecation
 <!-- YAML
 added: v0.8.0
@@ -2162,7 +2155,6 @@ cases:
 [`require()`]: globals.html#globals_require
 [`require.main`]: modules.html#modules_accessing_the_main_module
 [`require.resolve()`]: modules.html#modules_require_resolve_request_options
-[`setTimeout(fn, 0)`]: timers.html#timers_settimeout_callback_delay_args
 [`v8.setFlagsFromString()`]: v8.html#v8_v8_setflagsfromstring_flags
 [Android building]: https://github.com/nodejs/node/blob/master/BUILDING.md#androidandroid-based-devices-eg-firefox-os
 [Child Process]: child_process.html
diff --git a/lib/internal/process/next_tick.js b/lib/internal/process/next_tick.js
index df6984aabc..046449d658 100644
--- a/lib/internal/process/next_tick.js
+++ b/lib/internal/process/next_tick.js
@@ -26,7 +26,7 @@ function setupNextTick(_setupNextTick, _setupPromises) {
   const [
     tickInfo,
     runMicrotasks
-  ] = _setupNextTick(_tickCallback);
+  ] = _setupNextTick(internalTickCallback);
 
   // *Must* match Environment::TickInfo::Fields in src/env.h.
   const kHasScheduled = 0;
@@ -39,6 +39,15 @@ function setupNextTick(_setupNextTick, _setupPromises) {
   process._tickCallback = _tickCallback;
 
   function _tickCallback() {
+    if (tickInfo[kHasScheduled] === 0 && tickInfo[kHasPromiseRejections] === 0)
+      runMicrotasks();
+    if (tickInfo[kHasScheduled] === 0 && tickInfo[kHasPromiseRejections] === 0)
+      return;
+
+    internalTickCallback();
+  }
+
+  function internalTickCallback() {
     let tock;
     do {
       while (tock = queue.shift()) {
diff --git a/lib/timers.js b/lib/timers.js
index 9070ade70e..575dcf25f6 100644
--- a/lib/timers.js
+++ b/lib/timers.js
@@ -254,16 +254,17 @@ function processTimers(now) {
   debug('process timer lists %d', now);
   nextExpiry = Infinity;
 
-  let list, ran;
+  let list;
+  let ranAtLeastOneList = false;
   while (list = queue.peek()) {
     if (list.expiry > now) {
       nextExpiry = list.expiry;
       return refCount > 0 ? nextExpiry : -nextExpiry;
     }
-    if (ran)
+    if (ranAtLeastOneList)
       runNextTicks();
     else
-      ran = true;
+      ranAtLeastOneList = true;
     listOnTimeout(list, now);
   }
   return 0;
@@ -275,6 +276,7 @@ function listOnTimeout(list, now) {
   debug('timeout callback %d', msecs);
 
   var diff, timer;
+  let ranAtLeastOneTimer = false;
   while (timer = L.peek(list)) {
     diff = now - timer._idleStart;
 
@@ -288,6 +290,11 @@ function listOnTimeout(list, now) {
       return;
     }
 
+    if (ranAtLeastOneTimer)
+      runNextTicks();
+    else
+      ranAtLeastOneTimer = true;
+
     // The actual logic for when a timeout happens.
     L.remove(timer);
 
@@ -307,7 +314,33 @@ function listOnTimeout(list, now) {
 
     emitBefore(asyncId, timer[trigger_async_id_symbol]);
 
-    tryOnTimeout(timer);
+    let start;
+    if (timer._repeat)
+      start = getLibuvNow();
+
+    try {
+      const args = timer._timerArgs;
+      if (!args)
+        timer._onTimeout();
+      else
+        Reflect.apply(timer._onTimeout, timer, args);
+    } finally {
+      if (timer._repeat && timer._idleTimeout !== -1) {
+        timer._idleTimeout = timer._repeat;
+        if (start === undefined)
+          start = getLibuvNow();
+        insert(timer, timer[kRefed], start);
+      } else {
+        if (timer[kRefed])
+          refCount--;
+        timer[kRefed] = null;
+
+        if (destroyHooksExist() && !timer._destroyed) {
+          emitDestroy(timer[async_id_symbol]);
+          timer._destroyed = true;
+        }
+      }
+    }
 
     emitAfter(asyncId);
   }
@@ -327,30 +360,6 @@ function listOnTimeout(list, now) {
 }
 
 
-// An optimization so that the try/finally only de-optimizes (since at least v8
-// 4.7) what is in this smaller function.
-function tryOnTimeout(timer, start) {
-  if (start === undefined && timer._repeat)
-    start = getLibuvNow();
-  try {
-    ontimeout(timer);
-  } finally {
-    if (timer._repeat) {
-      rearm(timer, start);
-    } else {
-      if (timer[kRefed])
-        refCount--;
-      timer[kRefed] = null;
-
-      if (destroyHooksExist() && !timer._destroyed) {
-        emitDestroy(timer[async_id_symbol]);
-        timer._destroyed = true;
-      }
-    }
-  }
-}
-
-
 // Remove a timer. Cancels the timeout and resets the relevant timer properties.
 function unenroll(item) {
   // Fewer checks may be possible, but these cover everything.
@@ -456,26 +465,6 @@ setTimeout[internalUtil.promisify.custom] = function(after, value) {
 exports.setTimeout = setTimeout;
 
 
-function ontimeout(timer) {
-  const args = timer._timerArgs;
-  if (typeof timer._onTimeout !== 'function')
-    return Promise.resolve(timer._onTimeout, args[0]);
-  if (!args)
-    timer._onTimeout();
-  else
-    Reflect.apply(timer._onTimeout, timer, args);
-}
-
-function rearm(timer, start) {
-  // Do not re-arm unenroll'd or closed timers.
-  if (timer._idleTimeout === -1)
-    return;
-
-  timer._idleTimeout = timer._repeat;
-  insert(timer, timer[kRefed], start);
-}
-
-
 const clearTimeout = exports.clearTimeout = function clearTimeout(timer) {
   if (timer && timer._onTimeout) {
     timer._onTimeout = null;
@@ -601,75 +590,63 @@ function processImmediate() {
   const queue = outstandingQueue.head !== null ?
     outstandingQueue : immediateQueue;
   var immediate = queue.head;
-  const tail = queue.tail;
 
   // Clear the linked list early in case new `setImmediate()` calls occur while
   // immediate callbacks are executed
-  queue.head = queue.tail = null;
-
-  let count = 0;
-  let refCount = 0;
+  if (queue !== outstandingQueue) {
+    queue.head = queue.tail = null;
+    immediateInfo[kHasOutstanding] = 1;
+  }
 
+  let prevImmediate;
+  let ranAtLeastOneImmediate = false;
   while (immediate !== null) {
-    immediate._destroyed = true;
+    if (ranAtLeastOneImmediate)
+      runNextTicks();
+    else
+      ranAtLeastOneImmediate = true;
 
-    const asyncId = immediate[async_id_symbol];
-    emitBefore(asyncId, immediate[trigger_async_id_symbol]);
+    // It's possible for this current Immediate to be cleared while executing
+    // the next tick queue above, which means we need to use the previous
+    // Immediate's _idleNext which is guaranteed to not have been cleared.
+    if (immediate._destroyed) {
+      outstandingQueue.head = immediate = prevImmediate._idleNext;
+      continue;
+    }
 
-    count++;
+    immediate._destroyed = true;
+
+    immediateInfo[kCount]--;
     if (immediate[kRefed])
-      refCount++;
+      immediateInfo[kRefCount]--;
     immediate[kRefed] = null;
 
-    tryOnImmediate(immediate, tail, count, refCount);
+    prevImmediate = immediate;
 
-    emitAfter(asyncId);
+    const asyncId = immediate[async_id_symbol];
+    emitBefore(asyncId, immediate[trigger_async_id_symbol]);
 
-    immediate = immediate._idleNext;
-  }
+    try {
+      const argv = immediate._argv;
+      if (!argv)
+        immediate._onImmediate();
+      else
+        Reflect.apply(immediate._onImmediate, immediate, argv);
+    } finally {
+      immediate._onImmediate = null;
 
-  immediateInfo[kCount] -= count;
-  immediateInfo[kRefCount] -= refCount;
-  immediateInfo[kHasOutstanding] = 0;
-}
+      if (destroyHooksExist())
+        emitDestroy(asyncId);
 
-// An optimization so that the try/finally only de-optimizes (since at least v8
-// 4.7) what is in this smaller function.
-function tryOnImmediate(immediate, oldTail, count, refCount) {
-  var threw = true;
-  try {
-    // make the actual call outside the try/finally to allow it to be optimized
-    runCallback(immediate);
-    threw = false;
-  } finally {
-    immediate._onImmediate = null;
-
-    if (destroyHooksExist()) {
-      emitDestroy(immediate[async_id_symbol]);
+      outstandingQueue.head = immediate = immediate._idleNext;
     }
 
-    if (threw) {
-      immediateInfo[kCount] -= count;
-      immediateInfo[kRefCount] -= refCount;
-
-      if (immediate._idleNext !== null) {
-        // Handle any remaining Immediates after error handling has resolved,
-        // assuming we're still alive to do so.
-        outstandingQueue.head = immediate._idleNext;
-        outstandingQueue.tail = oldTail;
-        immediateInfo[kHasOutstanding] = 1;
-      }
-    }
+    emitAfter(asyncId);
   }
-}
 
-function runCallback(timer) {
-  const argv = timer._argv;
-  if (typeof timer._onImmediate !== 'function')
-    return Promise.resolve(timer._onImmediate, argv[0]);
-  if (!argv)
-    return timer._onImmediate();
-  Reflect.apply(timer._onImmediate, timer, argv);
+  if (queue === outstandingQueue)
+    outstandingQueue.head = null;
+  immediateInfo[kHasOutstanding] = 0;
 }
 
 
diff --git a/test/message/events_unhandled_error_nexttick.out b/test/message/events_unhandled_error_nexttick.out
index e00580ce93..4d0eba3a85 100644
--- a/test/message/events_unhandled_error_nexttick.out
+++ b/test/message/events_unhandled_error_nexttick.out
@@ -14,6 +14,7 @@ Error
     at bootstrapNodeJSCore (internal/bootstrap/node.js:*:*)
 Emitted 'error' event at:
     at process.nextTick (*events_unhandled_error_nexttick.js:*:*)
+    at internalTickCallback (internal/process/next_tick.js:*:*)
     at process._tickCallback (internal/process/next_tick.js:*:*)
     at Function.Module.runMain (internal/modules/cjs/loader.js:*:*)
     at startup (internal/bootstrap/node.js:*:*)
diff --git a/test/message/nexttick_throw.out b/test/message/nexttick_throw.out
index 16e41f6343..09b00de80f 100644
--- a/test/message/nexttick_throw.out
+++ b/test/message/nexttick_throw.out
@@ -4,6 +4,7 @@
         ^
 ReferenceError: undefined_reference_error_maker is not defined
     at *test*message*nexttick_throw.js:*:*
+    at internalTickCallback (internal/process/next_tick.js:*:*)
     at process._tickCallback (internal/process/next_tick.js:*:*)
     at Function.Module.runMain (internal/modules/cjs/loader.js:*:*)
     at startup (internal/bootstrap/node.js:*:*)
diff --git a/test/message/stdin_messages.out b/test/message/stdin_messages.out
index d4498b452a..bbf996bb56 100644
--- a/test/message/stdin_messages.out
+++ b/test/message/stdin_messages.out
@@ -12,7 +12,7 @@ SyntaxError: Strict mode code may not include a with statement
     at Socket.<anonymous> (internal/bootstrap/node.js:*:*)
     at Socket.emit (events.js:*:*)
     at endReadableNT (_stream_readable.js:*:*)
-    at process._tickCallback (internal/process/next_tick.js:*:*)
+    at process.internalTickCallback (internal/process/next_tick.js:*:*)
 42
 42
 [stdin]:1
@@ -29,7 +29,7 @@ Error: hello
     at Socket.<anonymous> (internal/bootstrap/node.js:*:*)
     at Socket.emit (events.js:*:*)
     at endReadableNT (_stream_readable.js:*:*)
-    at process._tickCallback (internal/process/next_tick.js:*:*)
+    at process.internalTickCallback (internal/process/next_tick.js:*:*)
 [stdin]:1
 throw new Error("hello")
 ^
@@ -44,7 +44,7 @@ Error: hello
     at Socket.<anonymous> (internal/bootstrap/node.js:*:*)
     at Socket.emit (events.js:*:*)
     at endReadableNT (_stream_readable.js:*:*)
-    at process._tickCallback (internal/process/next_tick.js:*:*)
+    at process.internalTickCallback (internal/process/next_tick.js:*:*)
 100
 [stdin]:1
 var x = 100; y = x;
@@ -60,7 +60,7 @@ ReferenceError: y is not defined
     at Socket.<anonymous> (internal/bootstrap/node.js:*:*)
     at Socket.emit (events.js:*:*)
     at endReadableNT (_stream_readable.js:*:*)
-    at process._tickCallback (internal/process/next_tick.js:*:*)
+    at process.internalTickCallback (internal/process/next_tick.js:*:*)
 
 [stdin]:1
 var ______________________________________________; throw 10
diff --git a/test/message/timeout_throw.out b/test/message/timeout_throw.out
index 210f2661e2..d97f8b1887 100644
--- a/test/message/timeout_throw.out
+++ b/test/message/timeout_throw.out
@@ -3,7 +3,5 @@
   ^
 ReferenceError: undefined_reference_error_maker is not defined
     at Timeout._onTimeout (*test*message*timeout_throw.js:*:*)
-    at ontimeout (timers.js:*:*)
-    at tryOnTimeout (timers.js:*:*)
     at listOnTimeout (timers.js:*:*)
     at processTimers (timers.js:*:*)
diff --git a/test/message/unhandled_promise_trace_warnings.out b/test/message/unhandled_promise_trace_warnings.out
index d610bb05eb..cf12c647ac 100644
--- a/test/message/unhandled_promise_trace_warnings.out
+++ b/test/message/unhandled_promise_trace_warnings.out
@@ -14,6 +14,7 @@
     at *
     at *
     at *
+    at *
 (node:*) Error: This was rejected
     at * (*test*message*unhandled_promise_trace_warnings.js:*)
     at *
@@ -32,6 +33,7 @@
     at *
     at *
     at *
+    at *
 (node:*) PromiseRejectionHandledWarning: Promise rejection was handled asynchronously (rejection id: 1)
     at handledRejection (internal/process/promises.js:*)
     at handler (internal/process/promises.js:*)
@@ -39,5 +41,3 @@
     at Promise.catch *
     at Immediate.setImmediate (*test*message*unhandled_promise_trace_warnings.js:*)
     at *
-    at *
-    at *
diff --git a/test/parallel/test-process-fatal-exception-tick.js b/test/parallel/test-process-fatal-exception-tick.js
deleted file mode 100644
index f22273e01c..0000000000
--- a/test/parallel/test-process-fatal-exception-tick.js
+++ /dev/null
@@ -1,26 +0,0 @@
-'use strict';
-
-const common = require('../common');
-const assert = require('assert');
-
-if (!common.isMainThread)
-  common.skip('Error handling timing is different in Workers');
-
-// If a process encounters an uncaughtException, it should schedule
-// processing of nextTicks on the next Immediates cycle but not
-// before all Immediates are handled
-
-let stage = 0;
-
-process.once('uncaughtException', common.expectsError({
-  type: Error,
-  message: 'caughtException'
-}));
-
-setImmediate(() => {
-  stage++;
-  process.nextTick(() => assert.strictEqual(stage, 2));
-});
-setTimeout(() => setImmediate(() => stage++), 1);
-common.busyLoop(10);
-throw new Error('caughtException');
diff --git a/test/parallel/test-repl-underscore.js b/test/parallel/test-repl-underscore.js
index dea2ed4370..7e7cabeda7 100644
--- a/test/parallel/test-repl-underscore.js
+++ b/test/parallel/test-repl-underscore.js
@@ -195,8 +195,6 @@ function testError() {
       /setImmediate/,
       /^    at/,
       /^    at/,
-      /^    at/,
-      /^    at/,
     ];
     for (const line of lines) {
       const expected = expectedLines.shift();
diff --git a/test/parallel/test-timers-immediate-queue.js b/test/parallel/test-timers-immediate-queue.js
index ba9ba87c40..dd793eead0 100644
--- a/test/parallel/test-timers-immediate-queue.js
+++ b/test/parallel/test-timers-immediate-queue.js
@@ -33,11 +33,14 @@ const assert = require('assert');
 let ticked = false;
 
 let hit = 0;
-const QUEUE = 1000;
+const QUEUE = 10;
 
 function run() {
-  if (hit === 0)
-    process.nextTick(function() { ticked = true; });
+  if (hit === 0) {
+    setTimeout(() => { ticked = true; }, 1);
+    const now = Date.now();
+    while (Date.now() - now < 2);
+  }
 
   if (ticked) return;
 
diff --git a/test/parallel/test-timers-next-tick.js b/test/parallel/test-timers-next-tick.js
index 1db1d18c3a..89ebf6c8c1 100644
--- a/test/parallel/test-timers-next-tick.js
+++ b/test/parallel/test-timers-next-tick.js
@@ -2,14 +2,29 @@
 
 const common = require('../common');
 
-// This test documents an internal implementation detail of the Timers:
-// since timers of different durations are stored in separate lists,
-// a nextTick queue will clear after each list of timers. While this
-// behaviour is not documented it could be relied on by Node's users.
+// This test verifies that the next tick queue runs after each
+// individual Timeout, as well as each individual Immediate.
 
 setTimeout(common.mustCall(() => {
-  process.nextTick(() => { clearTimeout(t2); });
+  process.nextTick(() => {
+    // Confirm that clearing Timeouts from a next tick doesn't explode.
+    clearTimeout(t2);
+    clearTimeout(t3);
+  });
 }), 1);
-const t2 = setTimeout(common.mustNotCall(), 2);
+const t2 = setTimeout(common.mustNotCall(), 1);
+const t3 = setTimeout(common.mustNotCall(), 1);
+setTimeout(common.mustCall(), 1);
 
 common.busyLoop(5);
+
+setImmediate(common.mustCall(() => {
+  process.nextTick(() => {
+    // Confirm that clearing Immediates from a next tick doesn't explode.
+    clearImmediate(i2);
+    clearImmediate(i3);
+  });
+}));
+const i2 = setImmediate(common.mustNotCall());
+const i3 = setImmediate(common.mustNotCall());
+setImmediate(common.mustCall());