Faster Javascript – Part 2

In Faster Javascript Part 1 we compared a three methods for evaluating a string of alien DNA. With Switch, Boolean & Conditional going head to head, Switch was the clear winner with Conditional (Ternary) trailing way behind.

Testing methods is one thing, but there’s more to writing fast code than just testing. For example: order and probability.

var dna = 'GGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGG';

var times = 100000,
    len = dna.length;

// Fast
var inc = 0;
var time = new Date().getTime();
for( var j = 0 ; j < times; j++ ){
  for( var i = 0 ; i < len; i++ ){
    switch( dna[ i ] ){
      case 'G': inc += 1; break;
      case '_00': inc += 1; break;
      case '_01': inc += 1; break;
      case '_02': inc += 1; break;
      case '_03': inc += 1; break;
      case '_04': inc += 1; break;
      case '_05': inc += 1; break;
      case '_06': inc += 1; break;
      case '_07': inc += 1; break;
      case '_08': inc += 1; break;
      case '_09': inc += 1; break;
      case '_10': inc += 1; break;
      case '_20': inc += 1; break;
      case '_21': inc += 1; break;
      case '_22': inc += 1; break;
      case '_23': inc += 1; break;
      case '_24': inc += 1; break;
      case '_25': inc += 1; break;
      case '_26': inc += 1; break;
      case '_27': inc += 1; break;
      case '_28': inc += 1; break;
      case '_29': inc += 1; break;
      case '_30': inc += 1; break;
    }
  }
}
console.log( 'Fast: ', [ new Date().getTime() - time,  ( inc == times * len ) ] );

// Slow
var inc = 0;
var time = new Date().getTime();
for( var j = 0 ; j < times; j++ ){
  for( var i = 0 ; i < len; i++ ){
    switch( dna[ i ] ){
      case '_00': inc += 1; break;
      case '_01': inc += 1; break;
      case '_02': inc += 1; break;
      case '_03': inc += 1; break;
      case '_04': inc += 1; break;
      case '_05': inc += 1; break;
      case '_06': inc += 1; break;
      case '_07': inc += 1; break;
      case '_08': inc += 1; break;
      case '_09': inc += 1; break;
      case '_10': inc += 1; break;
      case '_20': inc += 1; break;
      case '_21': inc += 1; break;
      case '_22': inc += 1; break;
      case '_23': inc += 1; break;
      case '_24': inc += 1; break;
      case '_25': inc += 1; break;
      case '_26': inc += 1; break;
      case '_27': inc += 1; break;
      case '_28': inc += 1; break;
      case '_29': inc += 1; break;
      case '_30': inc += 1; break;
      case 'G': inc += 1; break;
    }
  }
}
console.log( 'Slow: ', [ new Date().getTime() - time,  ( inc == times * len ) ] );

I get the following results:

Fast: [1322, true]
Slow: [3109, true]

If you didn’t catch the trick.. look closely at the order of the the switch. In the first switch, the check for the string “G” is at the top of the block. In the second switch, the “G” is checked after 30 other string cases have already been checked.

Lets say you were walking down the corridor of a library, and the books were all stored in alphabetical order. If you were at the ‘A’ end of the corridor… and I asked you to fetch any book beginning with ‘Z’, how long would it take you? Answer: longer than it would take if I asked for a book beginning with ‘A’.

So Simple

When we check for the letter ‘G’ 64 times, and we start at ‘_00’ it takes longer than if we flip the corridor to start at ‘G’. To compensate for this corridor effect, we should weight code to deal with specific shapes, patterns and probability in our data.

Thinking Rocks

Another way to think of this idea comes from gardening. Imagine you loaded a sieve with different size rocks, ready to separate the small rocks from the large. If you were to stack the large rocks on the bottom and the fine grains on the top… you would expend more energy in the process than if you stacked them the other way around.

If you are processing text, weight your switch to deal with the most common letters in the English language first. If you’re processing HTML, XML, you will want <div>’s to be closer to the top than <blockquote>’s. If you are processing natural data and you know the probability law that your data set is following, stack it in favor of your CPU.

Switching to Literals

When you switch the method to calling functions from a literal object, something really cool happens.

var dna = 'GGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGG';

var times = 1000000,
    len = dna.length;

var obj1 = {
  G   : function(){ return 1 },
  _00 : function(){ return 1 },
  _01 : function(){ return 1 },
  _02 : function(){ return 1 },
  _03 : function(){ return 1 },
  _04 : function(){ return 1 },
  _05 : function(){ return 1 },
  _06 : function(){ return 1 },
  _07 : function(){ return 1 },
  _08 : function(){ return 1 },
  _09 : function(){ return 1 },
  _10 : function(){ return 1 },
  _11 : function(){ return 1 },
  _12 : function(){ return 1 },
  _13 : function(){ return 1 },
  _14 : function(){ return 1 },
  _15 : function(){ return 1 },
  _16 : function(){ return 1 },
  _17 : function(){ return 1 },
  _18 : function(){ return 1 },
  _19 : function(){ return 1 },
  _20 : function(){ return 1 },
  _21 : function(){ return 1 },
  _22 : function(){ return 1 },
  _23 : function(){ return 1 },
  _24 : function(){ return 1 },
  _25 : function(){ return 1 },
  _26 : function(){ return 1 },
  _27 : function(){ return 1 },
  _28 : function(){ return 1 },
  _29 : function(){ return 1 },
  _30 : function(){ return 1 }
};

var obj2 = {
  _00 : function(){ return 1 },
  _01 : function(){ return 1 },
  _02 : function(){ return 1 },
  _03 : function(){ return 1 },
  _04 : function(){ return 1 },
  _05 : function(){ return 1 },
  _06 : function(){ return 1 },
  _07 : function(){ return 1 },
  _08 : function(){ return 1 },
  _09 : function(){ return 1 },
  _10 : function(){ return 1 },
  _11 : function(){ return 1 },
  _12 : function(){ return 1 },
  _13 : function(){ return 1 },
  _14 : function(){ return 1 },
  _15 : function(){ return 1 },
  _16 : function(){ return 1 },
  _17 : function(){ return 1 },
  _18 : function(){ return 1 },
  _19 : function(){ return 1 },
  _20 : function(){ return 1 },
  _21 : function(){ return 1 },
  _22 : function(){ return 1 },
  _23 : function(){ return 1 },
  _24 : function(){ return 1 },
  _25 : function(){ return 1 },
  _26 : function(){ return 1 },
  _27 : function(){ return 1 },
  _28 : function(){ return 1 },
  _29 : function(){ return 1 },
  _30 : function(){ return 1 },
  G   : function(){ return 1 }
};

// Faster Processing
var inc = 0;
var time = new Date().getTime();
for( var j = 0 ; j < times; j++ ){
  for( var i = 0 ; i < len; i++ ){
    inc += obj1[ dna[i] ]();
  }
}
console.log( 'Fast: ', [ new Date().getTime() - time,  ( inc == times * len ) ] );

// Slower Processing
var inc = 0;
var time = new Date().getTime();
for( var j = 0 ; j < times; j++ ){
  for( var i = 0 ; i < len; i++ ){
    inc += obj2[ dna[i] ]();
  }
}
console.log( 'Slow: ', [ new Date().getTime() - time,  ( inc == times * len ) ] );

Results:

/* 1st Run */
Fast: [36369, true]
Slow: [41355, true]

/* 2nd Run */
Fast: [39752, true]
Slow: [42457, true]

/* 3rd Run */
Fast: [40697, true]
Slow: [42928, true]
```

Consider now that I am running this test 1 million times, compared to the 100 thousand times in the switch array. That means the literal-object test is iterating 10 times as much as the switch, but the results are not proportional. This really demonstrates the some of the awesome power that can be unleashed using objects instead of switch statements.

The same is true of objects in general. For example: 

~~~js
  var obj1 = function(){};
  obj1.prototype.G = function(){ return 1 };
  obj1.prototype._00 = function(){ return 1 };
  obj1.prototype._01 = function(){ return 1 };
  obj1.prototype._02 = function(){ return 1 };

Yields the following, similar results

Fast:  [39753, true]
Slow: [43426, true]

Conclusion:

If you are going to make any kind of program that processes a significant amount of data, and you have a way of learning the inherent probability within your data set… time is of the essence, so stack wisely.