How is setTimeout implemented in node.js

Question

I was wondering if anybody knows how setTimeout is implemented in node.js. I believe I have read somewhere that this is not part of V8. I quickly tried to find the implementation, but could not find it in the source(BIG).I for example found this timers.js file, which then for example links to timer_wrap.cc. But these file do not completely answer all of my questions.

• Does V8 have setTimeout implementation? I guess also from the source the answer is no.

• How is setTimeout implemented? javascript or native or combination of both? From timers.js I assume something along the line of both:

  var Timer = process.binding('timer_wrap').Timer;`
  

• When adding multiple timers(setTimeout) how does node.js know which to execute first? Does it add all the timers to a collection(sorted)? If it is sorted then finding the timeout which needs to be executed is O(1) and O(log n) for insertion? But then again in timers.js I see them use a linkedlist?

• But then again adding a lot of timers is not a problem at all?

• When executing this script:

  var x = new Array(1000),
      len = x.length;
  
  /**
   * Returns a random integer between min and max
   * Using Math.round() will give you a non-uniform distribution!
   */
  function getRandomInt (min, max) {
      return Math.floor(Math.random() * (max - min + 1)) + min;
  }
  
  var y = 0;
  
  for (var i = 0; i < len; i++) {
      var randomTimeout = getRandomInt(1000, 10000);
  
      console.log(i + ', ' + randomTimeout + ', ' + ++y);
      setTimeout(function () {
          console.log(arguments);
      }, randomTimeout, randomTimeout, y);
  }
  

  you get a little bit of CPU usage but not that much?

• I am wondering if I implement all these callbacks one by one in a sorted list if I will get better performance?

Answer 1

You've done most of the work already. V8 doesn't provides an implementation for setTimeout because it's not part of ECMAScript. The function you use is implemented in timers.js, which creates an instance of a Timeout object which is a wrapper around a C class.

There is a comment in the source describing how they are managing the timers.

// Because often many sockets will have the same idle timeout we will not
// use one timeout watcher per item. It is too much overhead.  Instead
// we'll use a single watcher for all sockets with the same timeout value
// and a linked list. This technique is described in the libev manual:
// http://pod.tst.eu/http://cvs.schmorp.de/libev/ev.pod#Be_smart_about_timeouts

Which indicates it's using a double linked list which is #4 in the linked article.

If there is not one request, but many thousands (millions...), all employing some kind of timeout with the same timeout value, then one can do even better:

When starting the timeout, calculate the timeout value and put the timeout at the end of the list.

Then use an ev_timer to fire when the timeout at the beginning of the list is expected to fire (for example, using the technique #3).

When there is some activity, remove the timer from the list, recalculate the timeout, append it to the end of the list again, and make sure to update the ev_timer if it was taken from the beginning of the list.

This way, one can manage an unlimited number of timeouts in O(1) time for starting, stopping and updating the timers, at the expense of a major complication, and having to use a constant timeout. The constant timeout ensures that the list stays sorted.

Node.js is designed around async operations and setTimeout is an important part of that. I wouldn't try to get tricky, just use what they provide. Trust that it's fast enough until you've proven that in your specific case it's a bottleneck. Don't get stuck on premature optimization.

UPDATE

What happens is you've got essentially a dictionary of timeouts at the top level, so all 100ms timeouts are grouped together. Whenever a new timeout is added, or the oldest timeout triggers, it is appended to the list. This means that the oldest timeout, the one which will trigger the soonest, is at the beginning of the list. There is a single timer for this list, and it's set based on the time until the first item in the list is set to expire.

If you call setTimeout 1000 times each with the same timeout value, they will be appended to the list in the order you called setTimeout and no sorting is necessary. It's a very efficient setup.

Answer 2

No problem with many timers! When uv loop call poll, it pass timeout argument to it with closest timer of all timers.

[closest timer of all timers]
https://github.com/joyent/node/blob/master/deps/uv/src/unix/timer.c #120

RB_MIN(uv__timers, &loop->timer_handles)  

[pass timeout argument to poll api]
https://github.com/joyent/node/blob/master/deps/uv/src/unix/core.c #276

timeout = 0;  
if ((mode & UV_RUN_NOWAIT) == 0)  
    timeout = uv_backend_timeout(loop);  

uv__io_poll(loop, timeout); 

Note: on Windows OS, it's almost same logic