Vjeux

By overriding the toString Object prototype, it is possible to speed up by 5x the sort function. This is an easy to implement trick that gives astonishing results

I wanted to know if there were ways to speed up the Javascript Sort function. I came across an interesting article (Yet another faster Javascript Sorting) that presents a way to boost the builtin sort function. However, the link with the detailed explanation is dead, so i make you a summary here.

To sort some data, you are likely to do something that looks like that:

data.sort(function (a, b) { return b.key - a.key; });

The comparison function is being called n log n times. Since it's a javascript function, it is slow. sort() with no parameters will first convert all elements into strings and then use native (therefore faster) string comparison.

To make this work, we just have to override the toString method of the Object prototype to return the key.

var save = Object.prototype.toString;
Object.prototype.toString = function () { return this.key; };
 
data.sort();
 
Object.prototype.toString = save;

You have to make sure that the key variable is a string. In my application, the key range is [0, 100] so the it is written as String.fromCharCode(key). If you have to deal with larger key range, the best solution is to convert the number into base 256. Make sure the number is padded with 0 because of the string comparison.

I made a little benchmark of the implementation to see how well it performs

*: Script time limit has been exceeded

It gives about a 5x increase of all the browsers I have tested with except in Chrome with a 3x decrease.

Since Chrome is already times faster than all the browsers, it doesn't look slowed by this feature. However it gives a real boost to all other browsers.

Update (24 December 2009): Chrome Array.sort() function is written directly in javascript and calls the ToString function everytime when a comparison is needed. Therefore, it is making 2 function calls (ToString(x), ToString(y) instead of one (compare(x, y)).

In order to check if that optimization will indeed give an actual boost, we can count the number of time the ToString method is being executed for 3 values. 3 times means that it is executed n time and more means that it is executed n log n times.

var need_custom_sort = (function () {
  // Fill the array with 3 values
  var array = new Array(3);
  for (var i = 0; i < 3; ++i) {
    array[i] = new Object();
  }
 
  // Override the toString method that counts how many times it is being called
  var count = 0;
  var save = Object.prototype.toString;
  Object.prototype.toString = function () { count += 1; return ""; };
 
  // Sort
  array.sort();
  Object.prototype.toString = save;
 
  // 3 times is good, more is bad!
  return (count === 3);
}());