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

toString Sort Benchmark Firefox
3.5.2
IE
8
Safari
4.528
Chrome
3.0.197
Normal - 10 000 135ms 188ms 45ms 16ms
Fast - 10 000 10ms 31ms 14ms 68ms
Improvement - 10 000 x13.5 x6.1 x3.2 /4.3
Normal - 100 000 695ms 2125ms 200ms 128ms
Fast - 100 000 101ms 437ms 46ms 326ms
Improvement - 100 000 x6.9 x4.9 x4.3 /2.5
Normal - 1 000 000 10102ms * 2736ms 970ms
Fast - 1 000 000 1158ms 6828ms 482ms 2593ms
Improvement - 1 000 000 x8.7 x5.7 /2.7

*: 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);
}());
If you liked this article, you might be interested in my Twitter feed as well.
 
 

Related Posts

  • January 8, 2010 Javascript – Sorting Table (18)
    For my new project on World of Raids I have to implement a table sorting. The browser not stable sorting and the faster sorting trick add difficulty to the task. String Comparison As mentionned in the Speed Up Javascript Sort() article, using a string as a key to represent each […]
  • October 30, 2009 Javascript – Dynamic Query Throttling (4)
    Working on the World of Raids Recruitment Tool we wanted automatic saving while editing. There are basically two ways of handling the problem. Send update everytime something changes. The main advantage of this technique is that you are always up to date. However, it is spamming the […]
  • December 24, 2009 Guild Recruitement – Search Optimizations (1)
    In World of Raids Guild Recruitment Tool, we wanted the search to be instant! We achieved this goal by not having a single page refresh or ajax call while updating the settings. Since it runs in the browser, performance was a real concern. We will see in this article what were the tricks […]
  • September 25, 2011 Javascript Object Difference (6)
    This article is about a difference algorithm. It extracts changes from one version of an object to another. It helps storing a smaller amount of information. Template In a project, I have a template object with all the default settings for a widget. var template = { […]
  • January 3, 2010 Bistromathique – Optimized Arbitrary Precision Calculator (3)
    The Bistromathique is an Arbitrary Precision Calculator EPITA project where the main focus is optimization. The input can be in any base (up to 250) and the following operations have to be performed: Addition, Subtraction, Multiplication, Division, Modulo. Base Representation Going […]