timers: move big impl comment to /internal/

To be paired with the commits from
https://github.com/nodejs/node/pull/26583

Specifically:
1a6fb71f71faf37e0b213cfc69021a5a27faea1f

PR-URL: https://github.com/nodejs/node/pull/26761
Reviewed-By: Ruben Bridgewater <ruben@bridgewater.de>
Reviewed-By: Anatoli Papirovski <apapirovski@mac.com>
Reviewed-By: Joyee Cheung <joyeec9h3@gmail.com>

1 files changed, 72 insertions, 0 deletions

diff --git a/lib/internal/timers.js b/lib/internal/timers.js
index b44952cafe..c8d8e5a6c3 100644
--- a/lib/internal/timers.js
+++ b/lib/internal/timers.js
@@ -1,5 +1,77 @@
 'use strict';
 
+// 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
+// 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 through 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.
+//
+/* eslint-disable node-core/non-ascii-character */
+//
+// ╔════ > Object Map
+// ║
+// ╠══
+// ║ lists: { '40': { }, '320': { etc } } (keys of millisecond duration)
+// ╚══          ┌────┘
+//              │
+// ╔══          │
+// ║ TimersList { _idleNext: { }, _idlePrev: (self) }
+// ║         ┌────────────────┘
+// ║    ╔══  │                              ^
+// ║    ║    { _idleNext: { },  _idlePrev: { }, _onTimeout: (callback) }
+// ║    ║      ┌───────────┘
+// ║    ║      │                                  ^
+// ║    ║      { _idleNext: { etc },  _idlePrev: { }, _onTimeout: (callback) }
+// ╠══  ╠══
+// ║    ║
+// ║    ╚════ >  Actual JavaScript timeouts
+// ║
+// ╚════ > Linked List
+//
+/* eslint-enable node-core/non-ascii-character */
+//
+// 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 currently due to expire, 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:
+// The PriorityQueue — an efficient binary heap implementation that does all
+// operations in worst-case O(log n) time — which manages the order of expiring
+// Timeout lists 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 timers architectures.
+
 const {
   scheduleTimer,
   toggleTimerRef,