nodejs
diff --git a/‎lib/timers.js‎
Lines changed: 105 additions & 8 deletions b/‎lib/timers.js‎
Lines changed: 105 additions & 8 deletions
@@ -10,16 +10,90 @@ const kOnTimeout = TimerWrap.kOnTimeout | 0;
 // Timeout values > TIMEOUT_MAX are set to 1.
 const TIMEOUT_MAX = 2147483647; // 2^31-1
 
-// IDLE TIMEOUTS
+
+// HOW and WHY the timers implementation works the way it does.
+//
+// Timers are crucial to Node.js. Internally, any TCP I/O connection creates a
+// timer so that we can time out of connections. Additionally, many user
+// user libraries and applications also use timers. As such there may be a
+// significantly large amount of timeouts scheduled at any given time.
+// Therefore, it is very important that the timers implementation is performant
+// and efficient.
+//
+// Note: It is suggested you first read though the lib/internal/linkedlist.js
+// linked list implementation, since timers depend on it extensively. It can be
+// somewhat counter-intuitive at first, as it is not actually a class. Instead,
+// it is a set of helpers that operate on an existing object.
+//
+// In order to be as performant as possible, the architecture and data
+// structures are designed so that they are optimized to handle the following
+// use cases as efficiently as possible:
+
+// - Adding a new timer. (insert)
+// - Removing an existing timer. (remove)
+// - Handling a timer timing out. (timeout)
+//
+// Whenever possible, the implementation tries to make the complexity of these
+// operations as close to constant-time as possible.
+// (So that performance is not impacted by the number of scheduled timers.)
+//
+// Object maps are kept which contain linked lists keyed by their duration in
+// milliseconds.
+// The linked lists within also have some meta-properties, one of which is a
+// TimerWrap C++ handle, which makes the call after the duration to process the
+// list it is attached to.
+//
+//
+// ╔════ > Object Map
+// ║
+// ╠══
+// ║ refedLists: { '40': { }, '320': { etc } } (keys of millisecond duration)
+// ╚══          ┌─────────┘
+//              │
+// ╔══          │
+// ║ TimersList { _idleNext: { }, _idlePrev: (self), _timer: (TimerWrap) }
+// ║         ┌────────────────┘
+// ║    ╔══  │                              ^
+// ║    ║    { _idleNext: { },  _idlePrev: { }, _onTimeout: (callback) }
+// ║    ║      ┌───────────┘
+// ║    ║      │                                  ^
+// ║    ║      { _idleNext: { etc },  _idlePrev: { }, _onTimeout: (callback) }
+// ╠══  ╠══
+// ║    ║
+// ║    ╚════ >  Actual JavaScript timeouts
+// ║
+// ╚════ > Linked List
+//
+//
+// With this, virtually constant-time insertion (append), removal, and timeout
+// is possible in the JavaScript layer. Any one list of timers is able to be
+// sorted by just appending to it because all timers within share the same
+// duration. Therefore, any timer added later will always have been scheduled to
+// timeout later, thus only needing to be appended.
+// Removal from an object-property linked list is also virtually constant-time
+// as can be seen in the lib/internal/linkedlist.js implementation.
+// Timeouts only need to process any timers due to currently timeout, which will
+// always be at the beginning of the list for reasons stated above. Any timers
+// after the first one encountered that does not yet need to timeout will also
+// always be due to timeout at a later time.
+//
+// Less-than constant time operations are thus contained in two places:
+// TimerWrap's backing libuv timers implementation (a performant heap-based
+// queue), and the object map lookup of a specific list by the duration of
+// timers within (or creation of a new list).
+// However, these operations combined have shown to be trivial in comparison to
+// other alternative timers architectures.
+
+
 // Object maps containing linked lists of timers, keyed and sorted by their
 // duration in milliseconds.
 //
-// Because often many sockets will have the same idle timeout we will not
-// use one timeout watcher per item. It is too much overhead.  Instead
-// we'll use a single watcher for all sockets with the same timeout value
-// and a linked list. This technique is described in the libev manual:
-// http://pod.tst.eu/http://cvs.schmorp.de/libev/ev.pod#Be_smart_about_timeouts
-
+// The difference between these two objects is that the former contains timers
+// that will keep the process open if they are the only thing left, while the
+// latter will not.
+//
+// - key = time in milliseconds
+// - value = linked list
 const refedLists = {};
 const unrefedLists = {};
 
@@ -38,6 +112,10 @@ exports._unrefActive = function(item) {
 
 
 // The underlying logic for scheduling or re-scheduling a timer.
+//
+// Appends a timer onto the end of an existing timers list, or creates a new
+// TimerWrap backed list if one does not already exist for the specified timeout
+// duration.
 function insert(item, unrefed) {
   const msecs = item._idleTimeout;
   if (msecs < 0 || msecs === undefined) return;
@@ -46,9 +124,12 @@ function insert(item, unrefed) {
 
   const lists = unrefed === true ? unrefedLists : refedLists;
 
+  // Use an existing list if there is one, otherwise we need to make a new one.
   var list = lists[msecs];
   if (!list) {
     debug('no %d list was found in insert, creating a new one', msecs);
+    // Make a new linked list of timers, and create a TimerWrap to schedule
+    // processing for the list.
     list = new TimersList(msecs, unrefed);
     L.init(list);
     list._timer._list = list;
@@ -85,12 +166,15 @@ function listOnTimeout() {
   while (timer = L.peek(list)) {
     diff = now - timer._idleStart;
 
+    // Check if this loop iteration is too early for the next timer.
+    // This happens if there are more timers scheduled for later in the list.
     if (diff < msecs) {
       this.start(msecs - diff, 0);
       debug('%d list wait because diff is %d', msecs, diff);
       return;
     }
 
+    // The actual logic for when a timeout happens.
 
     L.remove(timer);
     assert(timer !== L.peek(list));
@@ -117,6 +201,9 @@ function listOnTimeout() {
       domain.exit();
   }
 
+  // If `L.peek(list)` returned nothing, the list was either empty or we have
+  // called all of the timer timeouts.
+  // As such, we can remove the list and clean up the TimerWrap C++ handle.
   debug('%d list empty', msecs);
   assert(L.isEmpty(list));
   this.close();
@@ -144,6 +231,7 @@ function tryOnTimeout(timer, list) {
     // when the timeout threw its exception.
     const domain = process.domain;
     process.domain = null;
+    // If we threw, we need to process the rest of the list in nextTick.
     process.nextTick(listOnTimeoutNT, list);
     process.domain = domain;
   }
@@ -155,6 +243,12 @@ function listOnTimeoutNT(list) {
 }
 
 
+// A convenience function for re-using TimerWrap handles more easily.
+//
+// This mostly exists to fix https://github.com/nodejs/node/issues/1264.
+// Handles in libuv take at least one `uv_run` to be registered as unreferenced.
+// Re-using an existing handle allows us to skip that, so that a second `uv_run`
+// will return no active handles, even when running `setTimeout(fn).unref()`.
 function reuse(item) {
   L.remove(item);
 
@@ -171,6 +265,7 @@ function reuse(item) {
 }
 
 
+// Remove a timer. Cancels the timeout and resets the relevant timer properties.
 const unenroll = exports.unenroll = function(item) {
   var handle = reuse(item);
   if (handle) {
@@ -182,7 +277,9 @@ const unenroll = exports.unenroll = function(item) {
 };
 
 
-// Does not start the time, just sets up the members needed.
+// Make a regular object able to act as a timer by setting some properties.
+// This function does not start the timer, see `active()`.
+// Using existing objects as timers slightly reduces object overhead.
 exports.enroll = function(item, msecs) {
   if (typeof msecs !== 'number') {
     throw new TypeError('"msecs" argument must be a number');