Thursday, August 22, 2013

Building a better _________: debounce

I'm going to do a series of posts on taking functions and patterns that we all know and love and having a look to see if there are any ways we can improve them either through a faster implementation or by adding features. First up is the debounce function.

Debounce

The debounce function is an extremely useful tool that can help throttle requests. It is different to throttle though as throttle will allow only one request per time period, debounce will not fire immediately and wait the specified time period before firing the request. If there is another request made before the end of the time period then we restart the count. This can be extremely useful for calling functions that often get called and are only needed to run once after all the changes have been made.

An example could be a sort function that is automatically fired every time an element is added. If you add 100 items in succession then the sort function will be run 100 times, but really you only want it run once after everything has been added. Debounce that sort function and your problem is solved (though keep in mind debounce works in a different event loop so if you have code requiring your data to be sorted you may want to rethink how to structure it). Another good example is a function based on scroll position, we really want to wait for the scrolling to be done and listening to scroll events will hit a function multiple time.

An implementation


var debounce = function(func, wait) {
 var timeout;

 // the debounced function
 return function() {

  var context = this, args = arguments;

  // nulls out timer and calls original function
  var later = function() {
   timeout = null;
   func.apply(context, args);
  };

  // restart the timer to call last function
  clearTimeout(timeout);
  timeout = setTimeout(later, wait);
 };
}

Above is a simplified version of the underscore.js debounce. It's fairly simple and works well, but can we improve it?

An improvement


If we do add 100 items to a list then we will be clearing and setting a new timer 100 times, yet if these are all added before the end of the event cycle then there isn't much point resetting a setTimeout 100 times, one should be sufficient.

So now we need to update the debounce so that a timeout is not cleared. What we can do instead is save a timestamp every time we call debounce and only re-initialize a timeout if the last call has a timestamp less than our period in the past.

var debounce = function(func, wait) {
 // we need to save these in the closure
 var timeout, args, context, timestamp;

 return function() {

  // save details of latest call
  context = this;
  args = [].slice.call(arguments, 0);
  timestamp = new Date();

  // this is where the magic happens
  var later = function() {

   // how long ago was the last call
   var last = (new Date()) - timestamp;

   // if the latest call was less that the wait period ago
   // then we reset the timeout to wait for the difference
   if (last < wait) {
    timeout = setTimeout(later, wait - last);

   // or if not we can null out the timer and run the latest
   } else {
    timeout = null;
    func.apply(context, args);
   }
  };

  // we only need to set the timer now if one isn't already running
  if (!timeout) {
   timeout = setTimeout(later, wait);
  }
 }
};


Results

So I decided to just run a simple loop that called a function 100 times using the underscore.js debounce and we get a timeline something like this:



Then tried our new and improved debounce:


A huge improvement.

*edit* I have created a jsperf calling debounce 100 times here: http://jsperf.com/debounce

You can see it outperforms lodash and underscore mostly due to the fact it only has to install 1 timer rather than remove and install 100 timers. Also the debounce I used for the jsperf is slightly different to the one in the article - it was modified to have the same functionality as underscore and lodash (the ability to execute immediately) to make it a fair test. I have also made a pull request to underscore to change to this implementation and you can see the progress here: https://github.com/jashkenas/underscore/pull/1269

*edit 2*

Looks like lodash has now updated it's debounce in the edge version (see comments) based on this post! Check out the JSPerf - it's now VERY fast.

You can get the code for debounce on my github at https://github.com/rhysbrettbowen/debounce



15 comments:

  1. BUT DID YOU JSPERF IT

    ReplyDelete
  2. How does it compare to the lodash' version of debounce? https://github.com/lodash/lodash/blob/1.3.1/dist/lodash.js#L4481:L4561

    ReplyDelete
    Replies
    1. It's definitely faster - see the perf I added

      Delete
    2. Check again, I've patched the edge after reading your post :)

      Delete
    3. Nice one. we're actually using lodash at work (and debounce a lot) so it'll be great when it gets in to the production release (though we use the underscore build).

      Delete
    4. Awesome! The underscore build will get this benefit too :D

      Delete
    5. Lovely, thanks for taking time to make amendments to your code and benchamark this! Really love the concept of one timer!

      Delete
  3. shouldn't it be [].slice.call(arguments, 1) in line 9? since it should slice away the 0'th element, starting with the first?

    ReplyDelete
    Replies
    1. that line is in the inner function - the one that gets returned. Which means it's the function you're going to call and you want all arguments to be passed through. So you want to slice from the 0th element (the start) to the end to get all arguments

      Delete
  4. This comment has been removed by the author.

    ReplyDelete
  5. This is really cool, thanks. Sometimes incremental improvements can be really simple while the current solution is just accepted as 'good enough'. It's nice to be reminded to revise things now and then.

    ReplyDelete
  6. Hey there, thanks a lot this is very nice. I needed to improve this function for my need which were that I had to fire immediately to make the UI as responsive as possible but also on when the timeout runs out so the latest change is also reflected in the UI here is my modified function:

    /**
    * Fire once immediately and then when the last change was done once again
    * but take care that we do not fire twice on the first time we fired
    * http://modernjavascript.blogspot.de/2013/08/building-better-debounce.html
    * @param {function} func founction to debounce
    * @param {number} wait number of milliseconds to wait
    * @return {function} debounced function
    */
    function customDebounce(func, wait) {
    // we need to save these in the closure
    var timeout, args, context, timestamp, call_count = 0;
    return function() {
    // save details of latest call
    context = this;
    args = [].slice.call(arguments, 0);
    timestamp = new Date();
    // immediately fire on the first call
    if (call_count == 0) {
    func.apply(context, args);
    }
    ++call_count;
    // this is where the magic happens
    var later = function() {
    // how long ago was the last call
    var last = (new Date()) - timestamp;
    // if the latest call was less that the wait period ago
    // then we reset the timeout to wait for the difference
    if (last < wait) {
    timeout = setTimeout(later, wait - last);
    // or if not we can null out the timer and run the latest
    } else {
    timeout = null;
    if (call_count > 1) { // only fire if this was not the first call, first call aready fired
    func.apply(context, args);
    }
    call_count = 0; // time is over reset the counter
    }
    };
    // we only need to set the timer now if one isn't already running
    if (!timeout) {
    timeout = setTimeout(later, wait);
    }
    }
    };

    ReplyDelete
  7. Great tip. I think you could improve the performance further by replacing new Date() with Date.now(), see http://jsperf.com/date-instance-vs-timestamp

    ReplyDelete
  8. would it be possible to move `later` up one scope level to not recreate the function on each call to the debounced function? `later` would still have access to all necessary locals if i'm not mistaken.

    @John `window.performance.now` might be another even faster option!?

    ReplyDelete