From 56199ec6af319d2da71a685808caf54d1a49623d Mon Sep 17 00:00:00 2001 From: Jeremiah Senkpiel Date: Mon, 18 Mar 2019 16:17:45 -0700 Subject: 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 Reviewed-By: Anatoli Papirovski Reviewed-By: Joyee Cheung --- lib/internal/timers.js | 72 ++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 72 insertions(+) (limited to 'lib/internal/timers.js') 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, -- cgit v1.2.3