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/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.
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.
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.
Look, this submission states "WebKit sorts JS arrays using Selection Sort". In fact, WebKit will sort things that are not JS arrays using selection sort (the first check); and, as of 7 months ago, will sort JS arrays that are "in sparse mode" as if they were not JS arrays ("non-standard" being the terminology).
I am not arguing selection sort is a good sort for the reason chosen, but I will maintain that the real (yes: "real", that is the correct term to use here) sorting algorithm used by WebKit for "JS arrays" (remember: I was complaining about "how incorrect this submission is") is actually a choice between mergesort, quicksort, and an AVL tree.
Now, if the submission title had been "WebKit sorts sparse JS arrays using selection sort" or even "WebKit sorts non-standard JS arrays using selection sort" (to evoke the wording of the commit message 7 months ago), that would be different: that would not be a linkbait title. I could even maybe get behind "WebKit uses four different sorting algorithms, and one of them is selection sort?!".
However, when one sees the title "WebKit sorts JS arrays using Selection Sort", I think many, if not most, reasonable developers go "oh, wow, maybe I should be avoiding the WebKit sort algorithm, given that my arrays are reasonably sized... I wonder if they'll get that fixed"; but, when you click through to the actual code and read it you realize this would be wrong.
So, from my perspective, you are now arguing a strawman, and are doing so fairly abrasively :(. To be clear: I certainly am not defending the existence of selection sort in the codebase, even for non-standard arrays. That does not make this submission correct, or even reasonable: it is looking at the wrong code and making it out to be something it is not (even quite generally, "important").
Regardless, I got curious, and decided to look more into that sorting code. It is apparently sufficiently old that it predates WebKit being called "WebKit", so I went back through kdelibs and found the original commit that added it, from January 2001. At this time, most of the array implementation was still "does nothing, needs to be implemented" or "does the wrong thing, needs to be fixed".
It was in March of 2003, during a commit-spree of merging from Safari back to kjs, that the quick sort implementation and code to use it for JS arrays was added. This means that this submission's title was correct for two years, incorrect for almost 9 years, and then maybe-sort-of-almost-correct for 7 months.
I guess the response is symmetric: I'm not defending the title of the post. I'm saying that this is an example of code review discovering a real problem in code, and that it needs to be fixed. You apparently agree, so yay. :)
Empirically, when I tested sort algorithms, Safari makes fewer calls to the comparison function than either Firefox or Chrome, and all of the sorts are definitely O(n log n) in the average case. http://trac.webkit.org/browser/trunk/Source/JavaScriptCore/r... seems to be the real algorithm. Since Safari's sort is stable, I'm guessing that merge sort is being used.
As a side note, Firefox's sort implementation slows down drastically when you use a custom comparison function because it has to call from C++ back out to JS (https://bugzilla.mozilla.org/show_bug.cgi?id=715181). Chrome's sort is presumably implemented in JS for this reason.
The AVL tree is used for sorting when there is a custom comparison function because we cannot guarantee that the user-provided comparison function conforms to the requirements of the underlying standard library sort functions. Websites have a habit of providing nonsense comparison functions (e.g., using function() { return 0.5 - Math.random(); } to "shuffle" via sorting) and we need to ensure that these sorts will give terminate.
EDIT: Sparse mode is when JSC::JSArray switches from storing the array data as a vector to storing it in a map. You can see from the code at http://trac.webkit.org/browser/trunk/Source/JavaScriptCore/r... that a vector will be used for sufficiently small arrays (< 10,000 elements) and for larger arrays that are at least 12.5% full.
Performance is generally fine only because this is a ridiculously obscure feature that no one sane would ever trip over. Frankly I had no idea "sparse arrays" existed, nor would I have ever used them if I did (that's what a hash table is for). No doubt they're there because some browser did it once, some important site relied on it, and now we're all stuck with performance constraints (don't explode for huge unassigned array sizes) that don't make any sense.
No, O(N^2) sorting algorithms are just dumb in library/runtime[1] code. No one expects that, it will eventually bite anyone who uses the code. And this code is a booby trap, no one even knows if they're using it!
[1] In application code, where you might know a priori that they'll never sort more than "one screen worth" of data, I can see it being a reasonable hack. But never as part of a standard feature called "sort".
Except that every sort algorithm in every library on earth falls back to selection sort (or similar) for small problems (e.g. N < 10), because that's more efficient than drilling a merge sort all the way down.
How is that relevant? Is your contention that the code in question will never see performance problems because there's a constant factor that outweighs the runtime? That's not my read at all. It looks to me like sorting 40k items that happen to be packed in a sparse array is going to take on the order of a billion operations. No?
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/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.