timers: improve setImmediate() performance

This commit avoids re-creating a new immediate queue object every
time the immediate queue is processed. Additionally, a few functions
are tweaked to make them inlineable.

These changes give ~6-7% boost in setImmediate() performance in the
existing setImmediate() benchmarks.

PR-URL: https://github.com/nodejs/node/pull/8655
Reviewed-By: James M Snell <jasnell@gmail.com>
Reviewed-By: Ilkka Myller <ilkka.myller@nodefield.com>
Reviewed-By: Jeremiah Senkpiel <fishrock123@rocketmail.com>

1 files changed, 72 insertions, 22 deletions

diff --git a/lib/timers.js b/lib/timers.js
index f49227f020..d247c4001c 100644
--- a/lib/timers.js
+++ b/lib/timers.js
@@ -514,17 +514,58 @@ Timeout.prototype.close = function() {
 };
 
 
-var immediateQueue = L.create();
+// A linked list for storing `setImmediate()` requests
+function ImmediateList() {
+  this.head = null;
+  this.tail = null;
+}
+
+// Appends an item to the end of the linked list, adjusting the current tail's
+// previous and next pointers where applicable
+ImmediateList.prototype.append = function(item) {
+  if (this.tail) {
+    this.tail._idleNext = item;
+    item._idlePrev = this.tail;
+  } else {
+    this.head = item;
+  }
+  this.tail = item;
+};
+
+// Removes an item from the linked list, adjusting the pointers of adjacent
+// items and the linked list's head or tail pointers as necessary
+ImmediateList.prototype.remove = function(item) {
+  if (item._idleNext) {
+    item._idleNext._idlePrev = item._idlePrev;
+  }
+
+  if (item._idlePrev) {
+    item._idlePrev._idleNext = item._idleNext;
+  }
+
+  if (item === this.head)
+    this.head = item._idleNext;
+  if (item === this.tail)
+    this.tail = item._idlePrev;
+
+  item._idleNext = null;
+  item._idlePrev = null;
+};
+
+// Create a single linked list instance only once at startup
+var immediateQueue = new ImmediateList();
 
 
 function processImmediate() {
-  const queue = immediateQueue;
-  var domain, immediate;
+  var immediate = immediateQueue.head;
+  var tail = immediateQueue.tail;
+  var domain;
 
-  immediateQueue = L.create();
+  // Clear the linked list early in case new `setImmediate()` calls occur while
+  // immediate callbacks are executed
+  immediateQueue.head = immediateQueue.tail = null;
 
-  while (L.isEmpty(queue) === false) {
-    immediate = L.shift(queue);
+  while (immediate) {
     domain = immediate.domain;
 
     if (!immediate._onImmediate)
@@ -534,16 +575,18 @@ function processImmediate() {
       domain.enter();
 
     immediate._callback = immediate._onImmediate;
-    tryOnImmediate(immediate, queue);
+    tryOnImmediate(immediate, tail);
 
     if (domain)
       domain.exit();
+
+    immediate = immediate._idleNext;
   }
 
   // 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)) {
+  if (!immediateQueue.head) {
     process._needImmediateCallback = false;
   }
 }
@@ -551,19 +594,26 @@ function processImmediate() {
 
 // 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, queue) {
+function tryOnImmediate(immediate, oldTail) {
   var threw = true;
   try {
     // make the actual call outside the try/catch to allow it to be optimized
     runCallback(immediate);
     threw = false;
   } finally {
-    if (threw && !L.isEmpty(queue)) {
+    if (threw && immediate._idleNext) {
       // Handle any remaining on next tick, assuming we're still alive to do so.
-      while (!L.isEmpty(immediateQueue)) {
-        L.append(queue, L.shift(immediateQueue));
+      const curHead = immediateQueue.head;
+      const next = immediate._idleNext;
+      if (curHead) {
+        curHead._idlePrev = oldTail;
+        oldTail._idleNext = curHead;
+        next._idlePrev = null;
+        immediateQueue.head = next;
+      } else {
+        immediateQueue.head = next;
+        immediateQueue.tail = oldTail;
       }
-      immediateQueue = queue;
       process.nextTick(processImmediate);
     }
   }
@@ -617,10 +667,6 @@ exports.setImmediate = function(callback, arg1, arg2, arg3) {
     case 3:
       args = [arg1, arg2];
       break;
-    case 4:
-      args = [arg1, arg2, arg3];
-      break;
-    // slow case
     default:
       args = [arg1, arg2, arg3];
       for (i = 4; i < arguments.length; i++)
@@ -628,6 +674,10 @@ exports.setImmediate = function(callback, arg1, arg2, arg3) {
         args[i - 1] = arguments[i];
       break;
   }
+  return createImmediate(args, callback);
+};
+
+function createImmediate(args, callback) {
   // declaring it `const immediate` causes v6.0.0 to deoptimize this function
   var immediate = new Immediate();
   immediate._callback = callback;
@@ -639,20 +689,20 @@ exports.setImmediate = function(callback, arg1, arg2, arg3) {
     process._immediateCallback = processImmediate;
   }
 
-  L.append(immediateQueue, immediate);
+  immediateQueue.append(immediate);
 
   return immediate;
-};
+}
 
 
 exports.clearImmediate = function(immediate) {
   if (!immediate) return;
 
-  immediate._onImmediate = undefined;
+  immediate._onImmediate = null;
 
-  L.remove(immediate);
+  immediateQueue.remove(immediate);
 
-  if (L.isEmpty(immediateQueue)) {
+  if (!immediateQueue.head) {
     process._needImmediateCallback = false;
   }
 };