// generate an array of 1000 elements
var a = new Array(1000).join(",.").split(","),
calls = 0;
// call sort method incrementing the conter
a.sort(function(a, b){
++calls;
// return zero, nothing should change
return 0;
});
// discover the monster
alert(calls);
Guess how many times Internet Explorer compare results? 17583 times, against a.length - 1 in other browsers.
Nice stuff guys, I guess for big arrays a manual reimplementation could perform better, am I wrong?
Another big IE FAIL. Geez, that's 1st-2nd year stuff in most Computer Science departments!
ReplyDeleteopera 9.63 - 499485
ReplyDeletechrome 2.0.174.0 - 1 (999 if array filled with random values)
0 does not mean "nothing should change". Per spec, it can either leave them as they are, or most importantly, *swap them around* (which will then cause many more comparisons). Each approach could have other benefits in real world cases. Since a real world Web page rarely-if-ever sorts such a pointless identical array, this corner case is almost never encountered. Optimising for this case is a pointless optimisation for a pointless benchmark. It will almost never yield any useful effect on the real Web.
ReplyDeleteAnonymous so you point is about array values, right?
ReplyDeletefor(var a = [], i = 0, calls = 0; i < 1000; ++i)
a[i] = Math.random();exactly the same result, that array creation was to make things more simple to understand ... that's it.
P.S. for nothing should change I meant the array does not change (no indexes operations in the array itself)
ReplyDeleteP.S.2 ... pelase Anonymous, bring me a world case where Internet Explroer performs a sort faster than other browser ...
ReplyDelete> for(var a = [], i = 0, calls = 0; i < 1000; ++i)
ReplyDelete> a[i] = Math.random();exactly the same result
Of course it is, since your sort function always returns 0. It doesn't matter what you put in the cells initially if the sort function always returns the same thing. Use a proper *sort* function that actually sorts something.
> P.S. for nothing should change I meant the array does not change (no indexes operations in the array itself)
And that's where you're wrong. The items in the cells are allowed to swap around (and swap back again on a later sort) if the sort function returns 0. Array sorting is unstable per spec when the sort function declares two cells as identical in sort order. The indexes for the individual cell contents can change.
> P.S.2 ... pelase Anonymous, bring me a world case where Internet Explroer performs a sort faster than other browser ...
I never said it was. All I am saying is that your benchmark is fairly pointless in real world cases, so you can't be surprised that a browser does not optimise for it. IE is slow in any case, even when it is optimised, but it's hardly appropriate to point at something like this as an example of how or why it is slow. You have to point at actual common use cases that will be encountered on a regular basis, not just on benchmarks.
a pointless identical array, that's why I showed you that it does not matter if the array is identical or not.
ReplyDeleteAbout swapping keys, it is about sort implementation, you are right, but not about the used Array, it is internal, the Array does not change:
var a = [1,2,3];
a.sort(function(x,y){
alert([x,y,"-"].concat(a));
return 0;
});Nothing should happen is about the Array, the sort is useless but IE performs length * 2 - N operations against 999.
Whatever argument you can bring here, IE is not faster during sort and it sorts with a not optimal algorithm since the function is called too many times.
What I mean, useless or not, IE is already slow and best of all, it has a bad sort implementation (not clever enough).
For example, returning -1 allows us to know how many times the callback will be called.
If the array has 10 elements, for instances, the callback will be called at least 3x - 6 times, which is better than return 0, the one that should not change anything, but in this case the most expensive.
Accordingly, to demonstrate that IE sort is bad in any case, if you want to call a function for an Array with length 21, you retrieve the lower length for 21 calls in sort via Math.floor((21 + 6) / 3) and it will perform slower than a for or while loop.
So, however we put things, IE is slow and this is yet another case where it shows how slow it is.
P.S. the reason I tested these performances and calls is an unsuccessful try to create a faster:
ReplyDeleteArray.prototype.forEach = function(callback, self){
var $this = this,
length = this.length,
i = 0,
a = this.slice(0, Math.floor((length + 6) / 3))
;
a.sort(function(){
callback.call(self, $this[i], i++, $this);
return -1;
});
while(i < length)
callback.call(self, $this[i], i++, $this);
};
No Way, An optimized for is ways faster:
forEach = function(callback, self){
var i = 0,
length = this.length;
while(i < length)
callback.call(self, this[i], i++, this);
};
And that's all folks :D
P.S. [1,2,3,4,5] in sort 4 and 1, for example, are compared twice in IE ... are we still talking about not that bad algorithm? Just to underline that the problem is not what "we do not see" but how they do it!
ReplyDeleteThe average number of comparisons for a sort should be o(n * log2(n)). n * log2(n) is approximately 1000 * 10 = 10000. So 17583 comparisons isn't bad. I wouldn't necessarily expect a sort to be optimized for when all the values are equal.
ReplyDeleteTrying IE out with random numbers seems to result in about twice the number of comparisons that safari or firefox uses, so you could probably do better if you either have an expensive comparison or you know enough about your data to optimize for it (e.g. if your data is almost sorted already). Otherwise I'd expect a javascript implementation to be slower on IE.
It's worth pointing out that a naively implemented quicksort will always choose the first element to partition the array. Resulting in 999 comparisons on the first pass, then 998, 997 down to 1:
999 + 998 + ... + 2 + 1
= 1/2 * 1000 * 999
= 499500
Opera is five less than that. So I guess that once it has a partition of length 5 it switches to a simple sort that in this case uses 5 comparisons instead of the 10 comparisons (4+3+2+1) it'd take with their quicksort.
did you measure actual time in profiler? why care about number of calls to comparing function when the overal time is good - and in my case (sorting 500 lines table) is very good (1ms, definitely not bottleneck); do you know the difference between comparing two values and actually switching them? the first is cheap, latter can be problem
ReplyDeleteCan anyone tell what sorting algo IE uses by looking at how the comparison is done?
ReplyDeletehttp://www.smallapple.net/blog/art/how_does_your_browser_sort.html