Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Optimizing 'unreferenced' timers #16105

Closed
Fishrock123 opened this issue Oct 9, 2017 · 9 comments
Closed

Optimizing 'unreferenced' timers #16105

Fishrock123 opened this issue Oct 9, 2017 · 9 comments
Assignees
Labels
help wanted Issues that need assistance from volunteers or PRs that need help to proceed. performance Issues and PRs related to the performance of Node.js. timers Issues and PRs related to the timers subsystem / setImmediate, setInterval, setTimeout.

Comments

@Fishrock123
Copy link
Contributor

Fishrock123 commented Oct 9, 2017

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.)

#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 #8372 (comment):

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.

@Fishrock123 Fishrock123 added the timers Issues and PRs related to the timers subsystem / setImmediate, setInterval, setTimeout. label Oct 9, 2017
@gibfahn gibfahn added the help wanted Issues that need assistance from volunteers or PRs that need help to proceed. label Oct 9, 2017
@bnoordhuis
Copy link
Member

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
Copy link
Contributor Author

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
Copy link
Member

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.

@mscdex mscdex added the performance Issues and PRs related to the performance of Node.js. label Oct 10, 2017
@Fishrock123
Copy link
Contributor Author

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

@bnoordhuis
Copy link
Member

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
Copy link
Contributor Author

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
Copy link
Member

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

With setTimeout and clearTimeout stubs to measure the overhead:

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 apapirovski self-assigned this Feb 12, 2018
@apapirovski
Copy link
Member

apapirovski commented Feb 12, 2018

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
Copy link
Member

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.

apapirovski added a commit that referenced this issue May 22, 2018
Hang all timer lists off a single TimerWrap and use the PriorityQueue
to manage expiration priorities. This makes the Timers code clearer,
consumes significantly less resources and improves performance.

PR-URL: #20555
Fixes: #16105
Reviewed-By: Ben Noordhuis <info@bnoordhuis.nl>
Reviewed-By: Jeremiah Senkpiel <fishrock123@rocketmail.com>
Reviewed-By: Matteo Collina <matteo.collina@gmail.com>
Reviewed-By: James M Snell <jasnell@gmail.com>
Reviewed-By: Ruben Bridgewater <ruben@bridgewater.de>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
help wanted Issues that need assistance from volunteers or PRs that need help to proceed. performance Issues and PRs related to the performance of Node.js. timers Issues and PRs related to the timers subsystem / setImmediate, setInterval, setTimeout.
Projects
None yet
Development

Successfully merging a pull request may close this issue.

5 participants