Optimize timer._unrefActive

[piscisaureus]

@misterdjules pointed out that node had become significantly faster after optimizing timer._unrefActive(). To get the idea: https://github.com/joyent/node/commits/v0.10/lib/timers.js.

It turns out that timer._unrefActive() was added somewhere in 2013 to fix an issue related to unref()ing http requests; when an http request object is unref'ed, it's associated timeout timer also needs to be unref'ed or it'll keep the loop open. But it's really a performance bottleneck; _unrefActive() performs what is basically a linear scan of a linked list.

What seems more reasonable is to make timers that are stored in the linked list (through Timer.active()) always be unref'ed, and just use a separate TimerWrap object for all user timers that are scheduled through setTimeout/setInterval.

[bnoordhuis]

I don't think that splitting it into two lists is going to help much, unless you want to create a timer handle per tcp/udp/pipe handle.

There is currently a lot of low hanging fruit in the timers module, it just needs someone that wants to work on it for a few days. For example, .unref() always creates a new timer handle but that's not strictly necessary; the module can just as easily maintain a global refcount and ref/unref the main timer handle.

Another probable win is the introduction of a timer wheel. In most applications, the majority of timers are short-lived and never expire because the predominant use case is to time out network I/O after a good amount of time has elapsed. Most I/O however completes in milliseconds and afterwards the timer is deleted or reset.

A reset is when the timeout is extended for (for example) another 30 seconds after a read or write. With the current implementation, resetting consists of a O(1) deletion and O(n) insertion, where n is normally at least the number of open connections, so it's easily in the low thousands. With a timer wheel, that's reduced to O(1) deletion and O(1) insertion.

As an intermediate step, switching to binary search would lower the overhead to O(log n) for insertion and deletion. It's probably just as much work to implement binary search as it is to switch to a timer wheel, however.

The one (albeit minor) downside to a timer wheel is that you have to rehash timers every now and then. However, the beauty of it is that most timers are repeatedly reset and those always stay in the highest bucket, they are never rehashed.

Yet another optimization path is to try reduce the number of calls to Date.now() / Timer.now(). Obtaining the current system time is often outrageously expensive in virtual machines because the RDTSC instruction or HPET access or whatever the time source is, is intercepted and emulated by the host. It's not uncommon to see upwards of 20% wall clock time being wasted in clock_gettime() and gettimeofday() system calls.

A harebrained idea I had is to start a thread that consists of a loop that wakes up every millisecond, calls clock_gettime() and writes the result to an atomic variable. The main thread then has cheap but accurate time; the penalty is offloaded to the other thread.

[Fishrock123]

Trying to take a look at this, did some reading on timer wheels. [1] [2] (that being said, our implementation with handles means i'm still a bit confused. :))

@bnoordhuis

I don't think that splitting it into two lists is going to help much

Don't we already have two? unrefList and lists?

With a timer wheel, that's reduced to O(1) deletion and O(1) insertion.

Not strictly, unless the timer wheel is very large & more than one timers never fire on the same tick.

Also, I'm not really sure how this would get rid of the aforementioned unrefList?

As an intermediate step, switching to binary search would lower the overhead to O(log n) for insertion and deletion

How would this effect deletion? This does seem like an obvious win for setting timers though. But, we still have the two lists.

[Fishrock123]

See nodejs/node-convergence-archive#23

[Fishrock123]

https://gist.github.com/Fishrock123/23950d26346dc8077a08

@bnoordhuis Even in cases that should be horrible (to my best understanding) for O(n) on timeout (Tests 3 & 4), it still performs over 2x as well as a sorted array. At minimum, I move we accept the joyent/node patches for it.

The heap impl (primarly made by Ben) is probably usable even in this state without severe optimizations, it seems generally better for the common case, and consistent even to the uncommon case (lots of timeouts).

[Fishrock123]

Closing while keeping in mind that I can try to optimize it further. When I have some time.