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: https://github.com/joyent/node/issues/8160

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

Conflicts:
	lib/timers.js

Fixes: https://github.com/nodejs/node-convergence-archive/issues/23
Ref: https://github.com/nodejs/node/issues/268
PR-URL: https://github.com/nodejs/node/pull/2540
Reviewed-By: bnoordhuis - Ben Noordhuis <info@bnoordhuis.nl>

1 files changed, 51 insertions, 0 deletions

diff --git a/test/parallel/test-timers-unref-active.js b/test/parallel/test-timers-unref-active.js
new file mode 100644
index 0000000000..08f28b0153
--- /dev/null
+++ b/test/parallel/test-timers-unref-active.js
@@ -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);