Sort speed varies greatly

Programming languages Javascript
#1

In my attempts to figure out why my js bot execution speed is all over the place, I’ve found it has to do with sorts…

Here are examples TestA and TestB. TestA uses a pre-built sort function. TestB uses the native sort. You can take this code and throw it into any CG IDE that let’s you view the printErr output:

var Environment = this;

var Sorter = function(a,b){
	return a.val - b.val;
};

function TestA(){

	var s = [];
	var elapsed = 0;
	var biggest = 0;
	var iterations = 0;
	while( elapsed < 250000 ) {
		var start = Environment.elapsed();
		s.sort(Sorter);
		var end = Environment.elapsed();
		end -= start;
		if( end > biggest ) {
			biggest = end;
		}
		iterations++;
	   	elapsed += end;
    }

    printErr("TESTA: Elapsed time: " + elapsed + " Biggest: " + biggest + " iterations: " + iterations);
}

function TestB(){

	var s = [];
	var elapsed = 0;
	var biggest = 0;
	var iterations = 0;
	while( elapsed < 250000 ) {
		var start = Environment.elapsed();
		s.sort();
		var end = Environment.elapsed();
		end -= start;
		if( end > biggest ) {
			biggest = end;
		}
		iterations++;
		elapsed += end;
	}

	printErr("TestB: Elapsed time: " + elapsed + " Biggest: " + biggest + " iterations: " + iterations);
}

TestA();
TestB();

The native sort appears to be (on-average) 3x faster at initializing than the function-based sort. This is so bothersome! Typically, the native sort initializes and sorts an empty array in 30 microseconds or less. Whereas the function-based sort initializes in anywhere from 90 microseconds to 2500 microseconds.

So if you’re ever wondering why a random function took 10 milliseconds to run when it normally takes 140 microseconds… it’s because you’re using custom sorts.

Has anyone seen a way to get around this limitation? I assume it’s something to do with Spidermonkey’s way of implementing sorts.

1 Like
#2

Don’t use javascript if you want performances.

It’s weird because the custom sorter has all reasons in the world to be slower that the native sort. I believe the native sort is implemented in a native C or C++ function. And it’s just comparing values. Your custom sort read values in 2 objects to compare them.

So the Spidermonkey behavior don’t disturb me.

But Firefox is disturbing according to this test : https://jsperf.com/native-sort-vs-custom-sort (try it yourself). On my Firefox, the native sorter is 2 times slower than your custom sorter.

It’s disturbing since Spidermonkey is the Mozilla javascript engine :smiley: