Repository navigation
[Converge] timers: Avoid linear scan in _unrefActive. #23
Description
Activity
_unrefActive()hasn't been touched, this could probably be ported to io.js.. I had been meaning to look into doing it simpler but hadn't yet.Edit: hmm, more git conflicts than I had expected.
Also:
- timers: don't close interval timers when unrefd nodejs/node-v0.x-archive@78db74d
- timers: don't mutate unref list while iterating it nodejs/node-v0.x-archive@fd2cb7c
This patch was deliberately left out of io.js, because I felt that Timer.unref() should be really be O(1) - which it always had been prior to nodejs/node@f46ad01
@piscisaureus But isn't
_unrefActive()for internal timeouts that are explicitly unrefed on creation? What is the point ofunref()-ing those? I admit it is a little hacky to effectively have two types of timers..@Fishrock123
timers._unrefActive()executes an O(n) operation (a linear scan of the active internal timers) and is normally called repeatedly. For example, a timer that is associated with anet.Socketcalls it every time data is sent or received.@bnoordhuis understood. I don't really get what's so bad about the patch(es) in question though, although I am quite sure they are not perfect. Running O(n) at the timeout phase is a bit weird and usually undesired, but it does make some sense for timeouts that usually shouldn't timeout.
What's the other option, making it a sorted list again and using an (average) O(n log n) ((I think?)) search? Won't a timing wheel still be somewhat O(n log n) at best too?
Btw, how far did you get on that timers re-write? Even if it's not done I may be interested in seeing how things could be changed. :)
Running O(n) at the timeout phase is a bit weird and usually undesired, but it does make some sense for timeouts that usually shouldn't timeout.
It's not O(n) on expiry, it's O(n) every time something happens that resets (moves back) the timeout. A socket can generate hundreds or thousands of
timers._unrefActive()calls during its lifetime. Multiply that by the number of active sockets (thousands, usually) and you can see why that is a problem.I've repeatedly had
timers._unrefActive()show up as the biggest cost center in some of our (StrongLoop's) customers' applications. I reported that as nodejs/node-v0.x-archive#8160 and that is what eventually led up to nodejs/node-v0.x-archive@934bfe2. See the discussion in the issue for pros and cons on the current fix.What's the other option, making it a sorted list again and using an (average) O(n log n) ((I think?)) search? Won't a timing wheel still be somewhat O(n log n) at best too?
A timer wheel has the benefit that insertion and deletion (by far most common operations) are O(1). Even a logarithmic data structure is still an improvement over the current O(n^2) approach.
Btw, how far did you get on that timers re-write? Even if it's not done I may be interested in seeing how things could be changed. :)
I had a working prototype based on a binary heap but I scrapped it because it didn't preserve insertion order. (I probably could have worked around that with a monotonic counter but I didn't want to go there.)
It should be in a branch in my fork but I'm not sure which. https://github.com/bnoordhuis/io.js/commits/timer-heap contains just the heap implementation.
It's not O(n) on expiry, it's O(n) every time something happens that resets (moves back) the timeout.
Do you mean the current state in io.js, or with nodejs/node-v0.x-archive@934bfe2? (I think I understood that was currently the case in io.js, but not with Julien's patch.)
Oh, I think I understand your 'Running O(n) at the timeout phase is a bit weird' comment now.
Yes, you're right: io.js is O(n) reset + O(1) expiry whereas joyent/node is the other way around, O(1) reset + O(n) expiry. Both approaches are terrible, only under different workloads.
Ok, so in that case we need to come to a decision: which approach is less terrible and should we port this particular set of patches or not?
TSC discussion today: hold off landing these. timers need new impl. Leaving this open for now but tagging as
do-not-land
@misterdjules ... please weigh in here if you have specific concerns.we may need to consider a backup plan for this, timers has the potential to be a deep rabbit hole and it'd be nice if a "rewrite" doesn't end up deferring a release
17 remaining items
@Fishrock123 what's the status of this? Can it go on the 4.0.0 milestone or is it too much work for now?
- added 2 commits that reference this issue
on Sep 2, 2015 - added a commit that references this issue
on Sep 2, 2015 - added 2 commits that reference this issue
on Sep 3, 2015
See: nodejs/node-v0.x-archive@934bfe2
/cc @misterdjules
Summary of original commit message:
We need to reconcile this against recent io.js changes within timers.js. Is the original sorted unrefList still there. This patch will be need to be ported if so.