Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Why does native browser sort function work slower than quicksort?

I implemented quicksort and found that it work faster than native .sort() method, here is the Performance test

Why and how is this happening?

like image 571
iKBAHT Avatar asked Dec 18 '13 04:12

iKBAHT


1 Answers

The reason is that even though the .sort() method is native, it WAY more general than quick sort.

The sort method takes a comparison function. While in the case of quick sort the kind of comparisons are already limited.

The native sort() method is slower to account for more unconventional comparison functions.

Also of note: You should read about underscore.js vs lowdash.

Lowdash is full of methods where a for loop is used instead of a native function for speed.

Update: I read the comment below and realised my mistake. After some digging, I found the real reason for the slower native performance. The native code is obviously in a lower level language such as C which less "safe" than javascript.

The native function has many checks to ensure there are no errors and things don't break. Javascript code doesn't need as many checks as Javascript as a language tends save you from many such errors anyway.

The answer is still not quite convincing, but .each from lowdash compared to Array.forEach also has a similar result with the low dash implementation being faster. This is because the low dash implementation skips a if (... in ....) check. Little differences such as this can help javascript become faster due to the way Javascript is compiled these days. All function are essentially turned to native code before they run. So the native advantage is minimal.

like image 183
Naman Goel Avatar answered Oct 22 '22 16:10

Naman Goel