4 ms·
Interesting. Perhaps a quicksort/heapsort/mergesort should be written in JS instead and used by webkit for large collections. It'd be a lot less code than in C+
by lucian1900 14y ago
Interesting. Perhaps a quicksort/heapsort/mergesort should be written in JS instead and used by webkit for large collections. It'd be a lot less code than in C++, that's for sure.
- Robin_Message 14y agoThat would make performance worse, since webkit already uses what looks like standard library quicksort or mergesort, which I'd count at 0 lines of code. (Although they also use an AVL tree for sorting some things, I'm not sure why, or why the AVL tree code lives in the "wtf" source directory. It's all in http://trac.webkit.org/browser/trunk/Source/JavaScriptCore/runtime/JSArray.cpp http://trac.webkit.org/browser/trunk/Source/JavaScriptCore/r... from line 1409 onwards)
- rodneyrehm 14y agoWhile I doubt a javascript-space sorting implementation runs any faster than a C++ implementation could, there are some implementations around, http://millermedeiros.github.com/amd-utils/array.html#sort http://millermedeiros.github.com/amd-utils/array.html#sort for example.
- simonster 14y agoJavaScript sorting algorithms can definitely be faster if you are passing a comparator function to Array.prototype.sort, depending on the JS engine. See https://groups.google.com/forum/#!msg/mozilla.dev.tech.js-engine/Ct6JsfJEjdI/1Vz5LJxnkXYJ https://groups.google.com/forum/#!msg/mozilla.dev.tech.js-en..., where Boris Zbarsky shows that translating quick sort into JavaScript produces an algorithm that runs 7X faster than Array.prototype.sort(function(a, b) { return a-b; }) in SpiderMonkey (which uses an insertion + merge sort in C++ for Array.prototype.sort) because of the expense of making calls from C++ to JS. Chrome's sort algorithm is written in JavaScript so it doesn't suffer from this.