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



Tuesday, August 20, 2013

Promises/A+ - understanding the spec through implementation

NB: This is for promises/A+ v1. The spec has since moved to v1.1. The below is still a good introduction. There are now slides available with an implementation of v1.1.


What we're going to do is create a promises/A+ implementation based on http://promises-aplus.github.io/promises-spec/. By doing this hopefully we'll get a deeper understanding of just how promises work. I'll call this Aplus and put it up on github under https://github.com/rhysbrettbowen/Aplus

First some boilerplate. Let's make Aplus an object:

Aplus = {};

Promise States

from http://promises-aplus.github.io/promises-spec/#promise_states there are three states: pending, fulfilled and rejected. It does not state the value of these states, so let's enumerate them:

var State = {
 PENDING: 0,
 FULFILLED: 1,
 REJECTED: 2
};

var Aplus = {
 state: State.PENDING
};

you will see that I've also put in the default state for our promise as pending.

now we need to be able to transition from a state. There are some rules around what transitions are allowed - mostly that when we transition from pending to any other state we can't transition again. Also when transitioning to a fulfilled state we need a value, and a reason for rejected.

according to the terminology http://promises-aplus.github.io/promises-spec/#terminology a value can be anything including undefined and a reason is any value that indicates why a promise was rejected. That last definition is a little blurry - can "undefined" indicate why something was rejected? I'm going to say no and only accept non-null values. If anything doesn't work then I'll throw an error. So let's create a "chageState" method that handles the checking for us:

var State = {
 PENDING: 0,
 FULFILLED: 1,
 REJECTED: 2
};

var Aplus = {
 state: State.PENDING,
 changeState: function(state, value) {

  // catch changing to same state (perhaps trying to change the value)
  if ( this.state == state ) {
   throw new Error("can't transition to same state: " + state);
  }

  // trying to change out of fulfilled or rejected
  if ( this.state == State.FULFILLED ||
    this.state == State.REJECTED ) {
   throw new Error("can't transition from current state: " + state);
  }

  // if second argument isn't given at all (passing undefined allowed)
  if ( state == State.FULFILLED &&
    arguments.length < 2 ) {
   throw new Error("transition to fulfilled must have a non null value");
  }

  // if a null reason is passed in
  if ( state == State.REJECTED &&
    value == null ) {
   throw new Error("transition to rejected must have a non null reason");
  }

  //change state
  this.state = state;
  this.value = value;
  return this.state;
 }
};

Now we're on to the fun stuff.

Then


This is where the usefulness of the promise comes in. The method handles all it's chaining and is the way we add new functions on to the list. First up let's get a basic then function that will check if the fulfilled and rejected are functions and then store them in an array. This is important as 3.2.4 says that it must return before invoking the functions so we need to store them somewhere to execute later. Also we need to return a promise so let's create the promise and store that with the functions in an array:

then: function( onFulfilled, onRejected ) {

 // initialize array
 this.cache = this.cache || [];

 var promise = Object.create(Aplus);

 this.cache.push({
  fulfill: onFulfilled,
  reject: onRejected,
  promise: promise
 });

 return promise;
}

Resolving

Next let's concentrate on what happens when we actually resolve the promise. Let's again try and take the simple case and we'll add on the other logic as we go. First off we either run the onFulfilled or onRejected based on the promise state and we must do this in order. We then change the status of their associated promise based on the return values. We also need to pass in the value (or reason) that we got when the state changed. Here is a first pass:

resolve: function() {
 // check if pending
 if ( this.state == State.PENDING ) {
  return false;
 }

 // for each 'then'
 while ( this.cache && this.cache.length ) {
  var obj = this.cache.shift();

  // get the function based on state
  var fn = this.state == State.FULFILLED ? obj.fulfill : obj.reject;
  if ( typeof fn != 'function' ) {
   fn = function() {};
  }

  // fulfill promise with value or reject with error
  try {
   obj.promise.changeState( State.FULFILLED, fn(this.value) );
  } catch (error) {
   obj.promise.changeState( State.REJECTED, error );
  }
 }
}


This is a good first pass. It handles the base case for normal functions. The two other cases we need to handle though are when we're missing a function (at the moment we're using a blank function but we really need to pass along the value or the reason with the correct state) and when they return a promise. Let's first tackle the problem of passing along an error or value when we're missing a function:


resolve: function() {
 // check if pending
 if ( this.state == State.PENDING ) {
  return false;
 }

 // for each 'then'
 while ( this.cache && this.cache.length ) {
  var obj = this.cache.shift();

  var fn = this.state == State.FULFILLED ? obj.fulfill : obj.reject;


  if ( typeof fn != 'function' ) {

   obj.promise.changeState( this.state, this.value );

  } else {

   // fulfill promise with value or reject with error
   try {
    obj.promise.changeState( State.FULFILLED, fn(this.value) );
   } catch (error) {
    obj.promise.changeState( State.REJECTED, error );
   }

  }

 }
}

If the function doesn't exist we're essentially passing along the state and the value. One thing that hit me when reading through this is that if you are using a onRejected function and you want to pass along the error state to the next promise is you'll have to throw another error, otherwise the promise will resolve with the returned value. I guess that this is a good thing as you can essentially use onRejected to "fix" errors by doing things like returning a default value.

There is only one thing left in resolving and that's to handle what happens when a promise is returned. The spec gives an example of how to do this at: http://promises-aplus.github.io/promises-spec/#point-65 so let's put it in

resolve: function() {
 // check if pending
 if ( this.state == State.PENDING ) {
  return false;
 }

 // for each 'then'
 while ( this.cache && this.cache.length ) {
  var obj = this.cache.shift();

  var fn = this.state == State.FULFILLED ? obj.fulfill : obj.reject;


  if ( typeof fn != 'function' ) {

   obj.promise.changeState( this.state, this.value );

  } else {

   // fulfill promise with value or reject with error
   try {

    var value = fn( this.value );

    // deal with promise returned
    if ( value && typeof value.then == 'function' ) {

     value.then( function( value ) {
      obj.promise.changeState( State.FULFILLED, value );
     }, function( reason ) {
      obj.promise.changeState( State.REJECTED, error );
     });
    // deal with other value returned
    } else {
     obj.promise.changeState( State.FULFILLED, value );
    }
   // deal with error thrown
   } catch (error) {
    obj.promise.changeState( State.REJECTED, error );
   }
  }
 }
}

Asynchronous

So far so good, but there are two bits we haven't dealt with. The first is that the onFulfilled and onRejected functions should not be called in the same turn of the event loop. To fix this we should only add our "then" functions to the array after the event loop. We can do this through things like setTimeout or process.nextTick. To make this easier we'll put on a method that will run a given function asynchronously so it can be overridden with whatever implementation you use. For now though we'll use setTimeout though you can use nextTick or requestAnimationFrame

async: function(fn) {
 setTimeout(fn, 5);
}

The last step is putting in when to resolve. There should be two cases when we need to check, the first is when we add in the 'then' functions as the state might already be set. This gives us a then method looking like:


then: function( onFulfilled, onRejected ) {

 // initialize array
 this.cache = this.cache || [];

 var promise = Object.create(Aplus);
 var that = this;
 this.async( function() {
  that.cache.push({
   fulfill: onFulfilled,
   reject: onRejected,
   promise: promise
  });
  that.resolve();
 });

 return promise;
}

and the second should be when the state is changed so add a this.resolve() to the end of the changeState function. Wrap it all in a function that will use Object.create to get you a promise and the final code will look like this:

Final


var Aplus = function() {

 var State = {
  PENDING: 0,
  FULFILLED: 1,
  REJECTED: 2
 };

 var Aplus = {
  state: State.PENDING,
  changeState: function( state, value ) {

   // catch changing to same state (perhaps trying to change the value)
   if ( this.state == state ) {
    throw new Error("can't transition to same state: " + state);
   }

   // trying to change out of fulfilled or rejected
   if ( this.state == State.FULFILLED ||
     this.state == State.REJECTED ) {
    throw new Error("can't transition from current state: " + state);
   }

   // if second argument isn't given at all (passing undefined allowed)
   if ( state == State.FULFILLED &&
     arguments.length < 2 ) {
    throw new Error("transition to fulfilled must have a non null value");
   }

   // if a null reason is passed in
   if ( state == State.REJECTED &&
     value == null ) {
    throw new Error("transition to rejected must have a non null reason");
   }

   //change state
   this.state = state;
   this.value = value;
   this.resolve();
   return this.state;
  },
  fulfill: function( value ) {
   this.changeState( State.FULFILLED, value );
  },
  reject: function( reason ) {
   this.changeState( State.REJECTED, reason );
  },
  then: function( onFulfilled, onRejected ) {

   // initialize array
   this.cache = this.cache || [];

   var promise = Object.create(Aplus);

   var that = this;

   this.async( function() {
    that.cache.push({
     fulfill: onFulfilled,
     reject: onRejected,
     promise: promise
    });
    that.resolve();
   });

   return promise;
  },
  resolve: function() {
   // check if pending
   if ( this.state == State.PENDING ) {
    return false;
   }

   // for each 'then'
   while ( this.cache && this.cache.length ) {
    var obj = this.cache.shift();

    var fn = this.state == State.FULFILLED ?
     obj.fulfill :
     obj.reject;


    if ( typeof fn != 'function' ) {

     obj.promise.changeState( this.state, this.value );

    } else {

     // fulfill promise with value or reject with error
     try {

      var value = fn( this.value );

      // deal with promise returned
      if ( value && typeof value.then == 'function' ) {
       value.then( function( value ) {
        obj.promise.changeState( State.FULFILLED, value );
       }, function( error ) {
        obj.promise.changeState( State.REJECTED, error );
       });
      // deal with other value returned
      } else {
       obj.promise.changeState( State.FULFILLED, value );
      }
     // deal with error thrown
     } catch (error) {
      obj.promise.changeState( State.REJECTED, error );
     }
    }
   }
  },
  async: function(fn) {
   setTimeout(fn, 5);
  }
 };

 return Object.create(Aplus);

};

you might have noticed I also put in functions "fulfill" and "reject". The spec doesn't say anything about how to manually change the state of a promise. Other names may be used like "fail", "resolve" or "done" but I'm using "fulfill" and "reject" to keep in line with the specs and what they call their two functions.

Next time

In future I'll write a bit more about some patterns you can use promises for, like passing around data, making requests in parallel and caching. Promises are really powerful but they also come at a cost so I'll outline all the pros and cons and what their alternatives are in different situations, but for now hopefully this sheds some light on the internals of how a promise works.

*edit* Looks like the tests https://github.com/promises-aplus/promises-tests don't like errors thrown so I've changed the changeState to instead return the errors, not throw and the tests allow null reasons for errors so I've changed that and uploaded to github