Node: Optimizing 'unreferenced' timers

[Fishrock123]

tl;dr: Timer#unref() is not very efficient, and is also confusing. This should be fixable.

Timers use pooled handles behind the hood in all normal cases. There is one exception: if a timer has been unreferenced by using Timer#unref(). (But not _unrefActive, which pools the timer but also resets it.)

https://github.com/nodejs/node/pull/8372 Is my pervious attempt at optimizing it. As noted in that PR, that method is very odd and IIRC probably also has some behvaior weirdness in slightly-edge-cases.

A better solution is outlined by @misterdjules in that issue. I am describing it below in clearer detail so that other may better understand it. It assumes basic knowledge of our timers algorithm/implementation, most of which can be found in the extensive comments near the top of lib/timers.js.

From https://github.com/nodejs/node/pull/8372#issuecomment-245117134:

I wanted to experiment with another approach to making unrefed timers use TimerList instances, but _without the inconsistency of having some of them not use TimersList_.

Each TimersList could keep a counting tracker of how many unrefed timers it contains. This would be incremented / decremented whenever Timeout#unref() / Timeout#ref() are called, and also when unref timers call their callbacks. Whenever this counter is adjusted the implementation would check if there are unrefed timers, and then either unref or ref the TimerWrap handle accordingly.

Additionally, it could also cover _unrefActive, and pool our internal unreferenced timers without needed separate pools, even for the same duration.

_The logic behind this revolves around the fact that unrefed handles don't matter if there are still refed handles._

Also, this means we wouldn't need separate _handle properties on unreferenced timers, which is honestly just a confusing behavior as it stands today.

The major consideration here is whether unrefing and re-refing a libuv handle has much overhead. My recollection was that it did not have significant overhead (from @trevnorris, I think), but that would need to be investigated alongside this. (See below.) Keep in mind timers is potentially hot code for any net request and does actually need to be quite efficient.

[bnoordhuis]

Better, all JS timers in node.js could be multiplexed into a single libuv uv_timer_t instance. That timer would then be ref'd or unref'd when necessary.

The major consideration here is whether unrefing and re-refing a libuv handle has much overhead.

uv_ref() and uv_unref() are practically free. The cost in Timeout#unref() is the v8::Persistent handle that new TimerWrap() creates - it adds GC overhead.

[Fishrock123]

Better, all JS timers in node.js could be multiplexed into a single libuv uv_timer_t instance. That timer would then be ref'd or unref'd when necessary.

I am curious how you'd make that more efficient than today? The pooling for regular timers means that handles should be created infrequently - are you seeing something else?

[bnoordhuis]

With the scheme I propose there wouldn't need to be a pool because ref/unref would be as cheap as updating the global ref count. You don't even need to move the timer from one linked list to another, it could all be a single list.

[Fishrock123]

@bnoordhuis then we need to do order sorting though? It's what we already moved away from. 😛

[bnoordhuis]

Total ordering is a net positive, all other things being equal, right?

I have a binary heap implementation in JS that could be used, or it could be done as a timer wheel. A timer wheel is probably best because most timers get cancelled long before they expire and would never make it out of the first bucket.

Apropos timer wheels: the current implementation already resembles one if you don't look closely, but it's more complex than it needs to be. I guesstimate it could be redone in 1/3rd of the current line count.

[Fishrock123]

Total ordering is a net positive, all other things being equal, right?

We already get that cheaper, though. I've taken a look at a binary heap or timers wheel in the past and they really don't work better for our case in my experience.

However, this particular issue is about something more specific that should be independently solvable without changing _absolutely everything_.

[bnoordhuis]

Sorry for hijacking but I was looking into this issue today and I noticed that deletion in random order is 4x slower than sorted or semi-sorted.

'use strict';
const TimerWrap = process.binding('timer_wrap').Timer;
TimerWrap.now = () => 42;  // Remove overhead of time syscall.

const p = (s,t) => {
  t = process.hrtime(t);
  console.log(s, t[0] + '.' + Math.round(t[1] / 1e6));
};

const a = new Array(1<<20);
const f = () => { throw 'boom' };

{
  //const m = 0x48000000;  // 2,147,483,647 period LFSR.
  const m = 0x90000;  // 1,048,577 period LFSR.
  //const m = 0x6000;  // 32,767 period LFSR.
  const t = process.hrtime();
  for (let i = 0, n = 1; i < a.length; ++i) {
    n = (n >>> 1) ^ (m & -(n & 1));
    a[i] = setTimeout(f, n);
  }
  p('insert random', t);
}

{
  const t = process.hrtime();
  for (let i = 0; i < a.length; ++i) clearTimeout(a[i]);
  p('delete random', t);
}

{ 
  const t = process.hrtime();
  for (let i = 0; i < a.length; ++i) a[i] = setTimeout(f, i+1);
  p('insert linear', t);
}

{ 
  const t = process.hrtime();
  for (let i = 0; i < a.length; ++i) clearTimeout(a[i]);
  p('delete linear', t);
}

insert random 5.5
delete random 5.422
insert linear 4.795
delete linear 1.655



md5-9cbd1a4e4bc24899d9107e2a5b8f53f8



insert random 0.280
delete random 0.4
insert linear 0.346
delete linear 0.4

Showing a pretty substantial 5 us to insert or delete.

[apapirovski]

FWIW I have an implementation of this done that makes explicitly .unref() or .ref() timers about 700-800% faster. I'm still not quite happy with it so it might be another week before I open PR. I've assigned to myself so no one accidentally ends up duplicating this work.

Funny enough, I ended up finding this issue after I got about 80% into it and started exploring timer wheels which led me to @bnoordhuis' comment here.

I wish there a was a way to surface interesting issues like this but with 637 of them open, it's more than a little challenging.

[bnoordhuis]

I wish there a was a way to surface interesting issues like this but with 637 of them open, it's more than a little challenging.

I know and feel your pain.