6 ms·

WebKit sorts JS arrays using Selection Sort

53 points by lars 14y ago

jere 14y ago
> // "Min" sort. Not the fastest, but definitely less code than heapsort // or quicksort, and much less swapping than bubblesort/insertionsort. Oh, OK. Glad you could save yourself some time/LOC.
- calinet6 14y ago
  While you're correct to criticize to a degree, there is also something to be said for reducing complexity and preventing bugs by avoiding unnecessarily long algorithms.
damian2000 14y ago
I don't know much JS but shouldn't there be a quicksort library function for that?
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 ago
  That 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 ago
  While 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 ago
    JavaScript 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.
Robin_Message 14y ago
It appears to me from the line: 631 if (thisObj->classInfo() == &JSArray::s_info && !asArray(thisObj)->inSparseMode()) { that only non-arrays, or arrays in some kind of "sparse" mode are sorted inefficiently. I'm not sure what sparse mode is, but let's try my Raymond Chen inspired psychic powers: if you assign a[0]=1 and a[1000000]=2, you don't want a 1 to 999999 to be stored, so an array like that will end up in a sparse mode which functions more like a hash table keyed by integers. The same applies to non-arrays: since they aren't true arrays, they won't be stored in the blessed, contiguous way that the sort routine is expecting, so a slower access method has to be used. Now, fast sorting is presumably written assuming the array is in a contiguous array. Since in sparse mode the array isn't like that, we aren't on the fast path, so it doesn't matter if we are slow, and correctness and special cases are more important, hence the simple selection sort algorithm. Note also that line 633, 635 and 637 further specialise the fast path into three cases: a default sort with no user-defined comparator, a sort based on a built-in numerical comparator, and a more general sort using a user-defined comparator. (EDIT: The functions called on 633, 635 and 637 are defined 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, and use quicksort or mergesort, except in the general case which uses an AVL tree, which feels odd but I'm sure there was a reason.) TL;DR: This only applies to certain arrays; the performance is generally fine else someone would have noticed by now; if you are sorting array-like things or sparse arrays regularly, profile to discover if this is a problem for you.
- saurik 14y ago
  Yeah... to demonstrate how painfully incorrect this submission is, I think this comment from the real sorting code (which switches between mergesort and quicksort for different workloads) does quite well: // For numeric comparison, which is fast, qsort is faster than mergesort. We // also don't require mergesort's stability, since there's no user visible // side-effect from swapping the order of equal primitive values.
  - ajross 14y ago
    If this is not the "real" sorting code, why is it there? If it's not real, it should be gone. If it's real, it's wrong. The proper response to a code review that finds broken code is to fix it, not excuse it.
mda 14y ago
V8 sort algorithm (Quicksort + Insertion Sort): http://code.google.com/p/v8/source/browse/trunk/src/array.js#741 http://code.google.com/p/v8/source/browse/trunk/src/array.js...
- maxpow4h 14y ago
  It's known as Introsort
  - mda 14y ago
    No, Introsort is (Quicksort + Heapsort) designed to prevent algorithm to degenerate O(n^2) for particular input sets. Afaik v8 (and Java's pre Java 7 versions) quicksort algorithms are based on Jon Bentley's work.
js2 14y ago
FWIW, this code's over a decade old. Presumably if it had any negative performance implications, someone would have noticed by now: author kocienda <kocienda@> Fri, 24 Aug 2001 10:24:45 -0400 (14:24 +0000) Imported sources from kde-2.2 distribution http://git.chromium.org/gitweb/?p=external/Webkit.git;a=blob;f=JavaScriptCore/kjs/array_object.cpp;hb=66a6d360850d1643dc51807f9c6c0e0029ce3459#l292 http://git.chromium.org/gitweb/?p=external/Webkit.git;a=blob...
- trebor 14y ago
  This is a big assumption. See this animated example that danso posted: http://www.sorting-algorithms.com/ http://www.sorting-algorithms.com/ Yes, a difference of maybe 5ms won't be noticed... unless you're going a lot of sorting. Selection Sort is basically the slowest sort of all.
  - calinet6 14y ago
    One thing I learned when optimizing code is to never trust my intuition. That piece of code you think must be slow and must be impacting the application speed? It might not be consequential at all. Spending 4 hours optimizing it might get you exactly 0% improvement. And that one line you think is benign and would take 5 minutes to opt might end up being the key to speeding up your entire algorithm tenfold. It's important to understand speed and complexity when architecting software, but it's just as important to know how it really performs in the real world, on the CPU, with real memory constraints and real data. I'm not saying this is true at all for this particular algorithm, but it's been uncannily true for me in the past and I still fool myself to this day trying to optimise prematurely based on my primitive human computer.
- sesqu 14y ago
  I ran a simple test with Chrome 20: var a=new Array(4e9); for (var i=1; i<a.length; i=Math.ceil(i*1.0001)) a[i]=new Number(i).toString(); a.sort(); The speed suggest that this sparse string array is not sorted with a quadratic algorithm (today).
  - deleted 14y ago
danso 14y ago
FWIW, this animated demo of the comparative sorting efficiencies http://www.sorting-algorithms.com/ http://www.sorting-algorithms.com/
rodneyrehm 14y ago
http://blog.rodneyrehm.de/archives/14-Sorting-Were-Doing-It-Wrong.html#stability http://blog.rodneyrehm.de/archives/14-Sorting-Were-Doing-It-... may be of [some] interest here, too.
EchoAbstract 14y ago
Does any browser actually rely on WebKit's JS Core? I know Safari has Nitro and Chrome has v8, so I'm not sure what would use this code except maybe konqueror.
- bla2 14y ago
  nitro == jscore
  - EchoAbstract 14y ago
    If that's the case, then why does UIWebView under-perform Mobile Safari? (I know Mobile Safari uses nitro, but I have no idea what UIWebView uses under the covers). Also, Apple's known for being a bit slow to contribute some things back to WebKit. I wouldn't be surprised to see them not contributing nitro back.
    - illamint 14y ago
      I think they're both using Nitro (depending on who you ask: http://ariya.ofilabs.com/2012/06/nitro-javascriptcore-and-jit.html http://ariya.ofilabs.com/2012/06/nitro-javascriptcore-and-ji...), but UIWebViews don't have JIT compilation turned on (no executable memory pages allowed in iOS apps), so they're slower.
    - bdash 14y ago
      Apple engineers contributed "Nitro" to the WebKit SVN repository before it even gained that name.
    - bla2 14y ago
      JavaScriptCore (like other js engines) has an interpreter and a JIT. The JIT requires memory that's both writable and executable. iOS doesn't allow memory that's both writable and executable for security reasons, so normal apps can't use the JIT parts of jsc. Safari gets an exception from the "no writable and executable memory" rule. (That's the technical reason; if you're wearing a tinfoil hat, you could argue that Apple wants to make sure native apps work a lot better than thin UIWebView shims, for lock-in and whatnot.)
mbostock 14y ago
This is part of the reason why I ported Vladimir Yaroslavskiy's dual-pivot quicksort to JavaScript (https://github.com/square/crossfilter/blob/master/src/quicksort.js https://github.com/square/crossfilter/blob/master/src/quicks...) for Crossfilter (http://square.github.com/crossfilter http://square.github.com/crossfilter). It is much, much faster than the native sort. I would guess that WebKit uses this slower algorithm because it's an easy way to implement stable sort. If I recall, Chrome was one of the earlier browsers to implement a non-stable sorting algorithm for JavaScript and it broke various pages that assumed stable sort (such as tables that let you sort by multiple columns). Fun side-note: you can use a matrix diagram to visualize how your browser sorts, letting you determine your browser's sort algorithm visually. For example, Chrome uses median-of-3 quicksort, and Firefox uses mergesort. See for yourself! http://bost.ocks.org/mike/shuffle/compare.html http://bost.ocks.org/mike/shuffle/compare.html http://www.flickr.com/photos/mbostock/sets/72157628971703067/detail/ http://www.flickr.com/photos/mbostock/sets/72157628971703067...
- bdash 14y ago
  Can you point me at some code comparing the performance of your JavaScript quicksort implementation to the browser's native sort? I threw together a quick comparison myself and couldn't see any cases where the JavaScript implementation was significantly faster than JavaScriptCore's Array.prototype.sort, and there were a few cases where Array.prototype.sort was significantly faster than the JS implementation. EDIT: One interesting case is that of sparse arrays (e.g., the arrays which trigger JavaScriptCore to fall down the slow path that prompted this discussion). It seems that your JavaScript quicksort implementation doesn't handle these correctly: it gives different results from Array.prototype.sort and is dramatically slower as well. I'm guessing the performance impact comes from the fact that from JavaScript's point of view the holes in the array are identical undefined values. I'm not sure why correctness would be affected though.

53 points by lars 14y ago

jere 14y ago

> // "Min" sort. Not the fastest, but definitely less code than heapsort // or quicksort, and much less swapping than bubblesort/insertionsort. Oh, OK. Glad you could save yourself some time/LOC.

calinet6 14y ago
While you're correct to criticize to a degree, there is also something to be said for reducing complexity and preventing bugs by avoiding unnecessarily long algorithms.

damian2000 14y ago

I don't know much JS but shouldn't there be a quicksort library function for that?

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 ago
That 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 ago
While 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 ago
  JavaScript 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.

Robin_Message 14y ago

It appears to me from the line: 631 if (thisObj->classInfo() == &JSArray::s_info && !asArray(thisObj)->inSparseMode()) { that only non-arrays, or arrays in some kind of "sparse" mode are sorted inefficiently. I'm not sure what sparse mode is, but let's try my Raymond Chen inspired psychic powers: if you assign a[0]=1 and a[1000000]=2, you don't want a 1 to 999999 to be stored, so an array like that will end up in a sparse mode which functions more like a hash table keyed by integers. The same applies to non-arrays: since they aren't true arrays, they won't be stored in the blessed, contiguous way that the sort routine is expecting, so a slower access method has to be used. Now, fast sorting is presumably written assuming the array is in a contiguous array. Since in sparse mode the array isn't like that, we aren't on the fast path, so it doesn't matter if we are slow, and correctness and special cases are more important, hence the simple selection sort algorithm. Note also that line 633, 635 and 637 further specialise the fast path into three cases: a default sort with no user-defined comparator, a sort based on a built-in numerical comparator, and a more general sort using a user-defined comparator. (EDIT: The functions called on 633, 635 and 637 are defined 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, and use quicksort or mergesort, except in the general case which uses an AVL tree, which feels odd but I'm sure there was a reason.) TL;DR: This only applies to certain arrays; the performance is generally fine else someone would have noticed by now; if you are sorting array-like things or sparse arrays regularly, profile to discover if this is a problem for you.

saurik 14y ago
Yeah... to demonstrate how painfully incorrect this submission is, I think this comment from the real sorting code (which switches between mergesort and quicksort for different workloads) does quite well: // For numeric comparison, which is fast, qsort is faster than mergesort. We // also don't require mergesort's stability, since there's no user visible // side-effect from swapping the order of equal primitive values.
- ajross 14y ago
  If this is not the "real" sorting code, why is it there? If it's not real, it should be gone. If it's real, it's wrong. The proper response to a code review that finds broken code is to fix it, not excuse it.

mda 14y ago

V8 sort algorithm (Quicksort + Insertion Sort): http://code.google.com/p/v8/source/browse/trunk/src/array.js#741 http://code.google.com/p/v8/source/browse/trunk/src/array.js...

maxpow4h 14y ago
It's known as Introsort
- mda 14y ago
  No, Introsort is (Quicksort + Heapsort) designed to prevent algorithm to degenerate O(n^2) for particular input sets. Afaik v8 (and Java's pre Java 7 versions) quicksort algorithms are based on Jon Bentley's work.

js2 14y ago

FWIW, this code's over a decade old. Presumably if it had any negative performance implications, someone would have noticed by now: author kocienda <kocienda@> Fri, 24 Aug 2001 10:24:45 -0400 (14:24 +0000) Imported sources from kde-2.2 distribution http://git.chromium.org/gitweb/?p=external/Webkit.git;a=blob;f=JavaScriptCore/kjs/array_object.cpp;hb=66a6d360850d1643dc51807f9c6c0e0029ce3459#l292 http://git.chromium.org/gitweb/?p=external/Webkit.git;a=blob...

trebor 14y ago
This is a big assumption. See this animated example that danso posted: http://www.sorting-algorithms.com/ http://www.sorting-algorithms.com/ Yes, a difference of maybe 5ms won't be noticed... unless you're going a lot of sorting. Selection Sort is basically the slowest sort of all.
- calinet6 14y ago
  One thing I learned when optimizing code is to never trust my intuition. That piece of code you think must be slow and must be impacting the application speed? It might not be consequential at all. Spending 4 hours optimizing it might get you exactly 0% improvement. And that one line you think is benign and would take 5 minutes to opt might end up being the key to speeding up your entire algorithm tenfold. It's important to understand speed and complexity when architecting software, but it's just as important to know how it really performs in the real world, on the CPU, with real memory constraints and real data. I'm not saying this is true at all for this particular algorithm, but it's been uncannily true for me in the past and I still fool myself to this day trying to optimise prematurely based on my primitive human computer.
sesqu 14y ago
I ran a simple test with Chrome 20: var a=new Array(4e9); for (var i=1; i<a.length; i=Math.ceil(i*1.0001)) a[i]=new Number(i).toString(); a.sort(); The speed suggest that this sparse string array is not sorted with a quadratic algorithm (today).
- deleted 14y ago

danso 14y ago

FWIW, this animated demo of the comparative sorting efficiencies http://www.sorting-algorithms.com/ http://www.sorting-algorithms.com/

rodneyrehm 14y ago

http://blog.rodneyrehm.de/archives/14-Sorting-Were-Doing-It-Wrong.html#stability http://blog.rodneyrehm.de/archives/14-Sorting-Were-Doing-It-... may be of [some] interest here, too.

EchoAbstract 14y ago

Does any browser actually rely on WebKit's JS Core? I know Safari has Nitro and Chrome has v8, so I'm not sure what would use this code except maybe konqueror.

bla2 14y ago
nitro == jscore
- EchoAbstract 14y ago
  If that's the case, then why does UIWebView under-perform Mobile Safari? (I know Mobile Safari uses nitro, but I have no idea what UIWebView uses under the covers). Also, Apple's known for being a bit slow to contribute some things back to WebKit. I wouldn't be surprised to see them not contributing nitro back.
  - illamint 14y ago
    I think they're both using Nitro (depending on who you ask: http://ariya.ofilabs.com/2012/06/nitro-javascriptcore-and-jit.html http://ariya.ofilabs.com/2012/06/nitro-javascriptcore-and-ji...), but UIWebViews don't have JIT compilation turned on (no executable memory pages allowed in iOS apps), so they're slower.
  - bdash 14y ago
    Apple engineers contributed "Nitro" to the WebKit SVN repository before it even gained that name.
  - bla2 14y ago
    JavaScriptCore (like other js engines) has an interpreter and a JIT. The JIT requires memory that's both writable and executable. iOS doesn't allow memory that's both writable and executable for security reasons, so normal apps can't use the JIT parts of jsc. Safari gets an exception from the "no writable and executable memory" rule. (That's the technical reason; if you're wearing a tinfoil hat, you could argue that Apple wants to make sure native apps work a lot better than thin UIWebView shims, for lock-in and whatnot.)

mbostock 14y ago

This is part of the reason why I ported Vladimir Yaroslavskiy's dual-pivot quicksort to JavaScript (https://github.com/square/crossfilter/blob/master/src/quicksort.js https://github.com/square/crossfilter/blob/master/src/quicks...) for Crossfilter (http://square.github.com/crossfilter http://square.github.com/crossfilter). It is much, much faster than the native sort. I would guess that WebKit uses this slower algorithm because it's an easy way to implement stable sort. If I recall, Chrome was one of the earlier browsers to implement a non-stable sorting algorithm for JavaScript and it broke various pages that assumed stable sort (such as tables that let you sort by multiple columns). Fun side-note: you can use a matrix diagram to visualize how your browser sorts, letting you determine your browser's sort algorithm visually. For example, Chrome uses median-of-3 quicksort, and Firefox uses mergesort. See for yourself! http://bost.ocks.org/mike/shuffle/compare.html http://bost.ocks.org/mike/shuffle/compare.html http://www.flickr.com/photos/mbostock/sets/72157628971703067/detail/ http://www.flickr.com/photos/mbostock/sets/72157628971703067...

bdash 14y ago
Can you point me at some code comparing the performance of your JavaScript quicksort implementation to the browser's native sort? I threw together a quick comparison myself and couldn't see any cases where the JavaScript implementation was significantly faster than JavaScriptCore's Array.prototype.sort, and there were a few cases where Array.prototype.sort was significantly faster than the JS implementation. EDIT: One interesting case is that of sparse arrays (e.g., the arrays which trigger JavaScriptCore to fall down the slow path that prompted this discussion). It seems that your JavaScript quicksort implementation doesn't handle these correctly: it gives different results from Array.prototype.sort and is dramatically slower as well. I'm guessing the performance impact comes from the fact that from JavaScript's point of view the holes in the array are identical undefined values. I'm not sure why correctness would be affected though.