timers: greatly improve code comments

Fishrock123 · Fishrock123 · commit 67963c8c6643 · 2016-02-26T18:07:36.000-05:00
Describes the How and Why of the timers implementation, as well as adding comments in spots that should allow for an easier understanding about what is going on. The timers implementation is very efficient, at a cost. That cost is readable understandability, and this aims to improve that. PR-URL: #4007 Reviewed-By: Rod Vagg <rod@vagg.org> Reviewed-By: Trevor Norris <trev.norris@gmail.com> Reviewed-By: Julien Gilli <jgilli@nodejs.org> Reviewed-By: Chris Dickinson <christopher.s.dickinson@gmail.com>
diff --git a/lib/timers.js b/lib/timers.js
@@ -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.
+//
+//
+// &#9556;&#9552;&#9552;&#9552;&#9552; > Object Map
+// &#9553;
+// &#9568;&#9552;&#9552;
+// &#9553; refedLists: { '40': { }, '320': { etc } } (keys of millisecond duration)
+// &#9562;&#9552;&#9552;          &#9484;&#9472;&#9472;&#9472;&#9472;&#9472;&#9472;&#9472;&#9472;&#9472;&#9496;
+//              &#9474;
+// &#9556;&#9552;&#9552;          &#9474;
+// &#9553; TimersList { _idleNext: { }, _idlePrev: (self), _timer: (TimerWrap) }
+// &#9553;         &#9484;&#9472;&#9472;&#9472;&#9472;&#9472;&#9472;&#9472;&#9472;&#9472;&#9472;&#9472;&#9472;&#9472;&#9472;&#9472;&#9472;&#9496;
+// &#9553;    &#9556;&#9552;&#9552;  &#9474;                              ^
+// &#9553;    &#9553;    { _idleNext: { },  _idlePrev: { }, _onTimeout: (callback) }
+// &#9553;    &#9553;      &#9484;&#9472;&#9472;&#9472;&#9472;&#9472;&#9472;&#9472;&#9472;&#9472;&#9472;&#9472;&#9496;
+// &#9553;    &#9553;      &#9474;                                  ^
+// &#9553;    &#9553;      { _idleNext: { etc },  _idlePrev: { }, _onTimeout: (callback) }
+// &#9568;&#9552;&#9552;  &#9568;&#9552;&#9552;
+// &#9553;    &#9553;
+// &#9553;    &#9562;&#9552;&#9552;&#9552;&#9552; >  Actual JavaScript timeouts
+// &#9553;
+// &#9562;&#9552;&#9552;&#9552;&#9552; > 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');
