Skip to content

use unsorted array in Timers._unrefActive() #2540

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.

Sign up for GitHub

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

Closed
Fishrock123 wants to merge 3 commits into from
Closed

use unsorted array in Timers._unrefActive() #2540

Show file tree
Hide file tree
Changes from 1 commit
Commits
Show all changes
3 commits
Select commit Hold shift + click to select a range
8ae5292
timers: Avoid linear scan in _unrefActive.
Aug 20, 2014
27b5b0e
timers: don't mutate unref list while iterating it
Dec 18, 2014
8104759
timers: minor _unrefActive fixes and improvements
Fishrock123 Aug 27, 2015
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
Next Next commit
timers: Avoid linear scan in _unrefActive. 
Before this change, _unrefActive would keep the unrefList sorted when
adding a new timer.

Because _unrefActive is called extremely frequently, this linear scan
(O(n) at worse) would make _unrefActive show high in the list of
contributors when profiling CPU usage.

This commit changes _unrefActive so that it doesn't try to keep the
unrefList sorted. The insertion thus happens in constant time.

However, when a timer expires, unrefTimeout has to go through the whole
unrefList because it's not ordered anymore.

It is usually not large enough to have a significant impact on
performance because:
- Most of the time, the timers will be removed before unrefTimeout is
  called because their users (sockets mainly) cancel them when an I/O
  operation takes place.
- If they're not, it means that some I/O took a long time to happen, and
  the initiator of subsequents I/O operations that would add more timers
  has to wait for them to complete.

With this change, _unrefActive does not show as a significant
contributor in CPU profiling reports anymore.

Fixes: nodejs/node-v0.x-archive#8160
PR-URL: nodejs/node-v0.x-archive#8751

Signed-off-by: Timothy J Fontaine <tjfontaine@gmail.com>

Conflicts:
	lib/timers.js
  • Loading branch information
@Fishrock123
Julien Gilli authored and Fishrock123 committed Aug 31, 2015
commit 8ae52923dee615fd6fb0b9db791b425129402428
119 changes: 72 additions & 47 deletions lib/timers.js
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -483,41 +483,90 @@ function unrefTimeout() {

debug('unrefTimer fired');

var diff, domain, first, threw;
while (first = L.peek(unrefList)) {
diff = now - first._idleStart;
var timeSinceLastActive;
var nextTimeoutTime;
var nextTimeoutDuration;
var minNextTimeoutTime;
var itemToDelete;

// The actual timer fired and has not yet been rearmed,
// let's consider its next firing time is invalid for now.
// It may be set to a relevant time in the future once
// we scanned through the whole list of timeouts and if
// we find a timeout that needs to expire.
unrefTimer.when = -1;

if (diff < first._idleTimeout) {
diff = first._idleTimeout - diff;
unrefTimer.start(diff, 0);
unrefTimer.when = now + diff;
debug('unrefTimer rescheudling for later');
return;
// Iterate over the list of timeouts,
// call the onTimeout callback for those expired,
// and rearm the actual timer if the next timeout to expire
// will expire before the current actual timer.
var cur = unrefList._idlePrev;
while (cur != unrefList) {
timeSinceLastActive = now - cur._idleStart;

if (timeSinceLastActive < cur._idleTimeout) {
// This timer hasn't expired yet, but check if its expiring time is
// earlier than the actual timer's expiring time

nextTimeoutDuration = cur._idleTimeout - timeSinceLastActive;
nextTimeoutTime = now + nextTimeoutDuration;
if (minNextTimeoutTime == null ||
(nextTimeoutTime < minNextTimeoutTime)) {
// We found a timeout that will expire earlier,
// store its next timeout time now so that we
// can rearm the actual timer accordingly when
// we scanned through the whole list.
minNextTimeoutTime = nextTimeoutTime;
}

// This timer hasn't expired yet, skipping
cur = cur._idlePrev;
continue;
}

L.remove(first);
// We found a timer that expired
var domain = cur.domain;

domain = first.domain;
if (!cur._onTimeout) continue;

if (!first._onTimeout) continue;
if (domain && domain._disposed) continue;
if (domain && domain._disposed)
continue;

try {
var threw = true;

if (domain) domain.enter();
threw = true;

itemToDelete = cur;
// Move to the previous item before calling the _onTimeout callback,
// as it can mutate the list.
cur = cur._idlePrev;

// Remove the timeout from the list because it expired.
L.remove(itemToDelete);

debug('unreftimer firing timeout');
first._called = true;
first._onTimeout();
itemToDelete._called = true;
itemToDelete._onTimeout();

threw = false;

if (domain)
domain.exit();
} finally {
if (threw) process.nextTick(unrefTimeout);
}
}

debug('unrefList is empty');
unrefTimer.when = -1;
// Rearm the actual timer with the timeout delay
// of the earliest timeout found.
if (minNextTimeoutTime != null) {
unrefTimer.start(minNextTimeoutTime - now, 0);
unrefTimer.when = minNextTimeoutTime;
debug('unrefTimer rescheduled');
} else if (L.isEmpty(unrefList)) {
debug('unrefList is empty');
}
}


Expand All @@ -543,38 +592,14 @@ exports._unrefActive = function(item) {
var now = Timer.now();
item._idleStart = now;

if (L.isEmpty(unrefList)) {
debug('unrefList empty');
L.append(unrefList, item);
var when = now + msecs;

// If the actual timer is set to fire too late, or not set to fire at all,
// we need to make it fire earlier
if (unrefTimer.when === -1 || unrefTimer.when > when) {
unrefTimer.start(msecs, 0);
unrefTimer.when = now + msecs;
unrefTimer.when = when;
debug('unrefTimer scheduled');
return;
}

var when = now + msecs;

debug('unrefList find where we can insert');

var cur, them;

for (cur = unrefList._idlePrev; cur != unrefList; cur = cur._idlePrev) {
them = cur._idleStart + cur._idleTimeout;

if (when < them) {
debug('unrefList inserting into middle of list');

L.append(cur, item);

if (unrefTimer.when > when) {
debug('unrefTimer is scheduled to fire too late, reschedule');
unrefTimer.start(msecs, 0);
unrefTimer.when = when;
}

return;
}
}

debug('unrefList append to end');
Expand Down
51 changes: 51 additions & 0 deletions test/parallel/test-timers-unref-active.js
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -0,0 +1,51 @@
'use strict';

/*
* This test is aimed at making sure that unref timers queued with
* timers._unrefActive work correctly.
*
* Basically, it queues one timer in the unref queue, and then queues
* it again each time its timeout callback is fired until the callback
* has been called ten times.
*
* At that point, it unenrolls the unref timer so that its timeout callback
* is not fired ever again.
*
* Finally, a ref timeout is used with a delay large enough to make sure that
* all 10 timeouts had the time to expire.
*/

const common = require('../common');
const timers = require('timers');
const assert = require('assert');

var someObject = {};
var nbTimeouts = 0;

/*
* libuv 0.10.x uses GetTickCount on Windows to implement timers, which uses
* system's timers whose resolution is between 10 and 16ms. See
* http://msdn.microsoft.com/en-us/library/windows/desktop/ms724408.aspx
* for more information. That's the lowest resolution for timers across all
* supported platforms. We're using it as the lowest common denominator,
* and thus expect 5 timers to be able to fire in under 100 ms.
*/
const N = 5;
const TEST_DURATION = 100;

timers.unenroll(someObject);
timers.enroll(someObject, 1);

someObject._onTimeout = function _onTimeout() {
++nbTimeouts;

if (nbTimeouts === N) timers.unenroll(someObject);

timers._unrefActive(someObject);
};

timers._unrefActive(someObject);

setTimeout(function() {
assert.equal(nbTimeouts, N);
}, TEST_DURATION);