1121937 - Implement %TypedArray%.prototype.sort

Status: RESOLVED FIXED

(Core :: JavaScript: Standard Library, defect)

Comment 1

[Morgan Phillips [:mrrrgn]]

Attachment: typedarraysort.diff

A working implementation as self-hosted JS. In tests with a randomized Float64Array (length 1000000), when the simple comparator (x, y) => x-y is passed in faster than v8's default implementation by ~500ms however, the spec's default comparator is slower than v8's implementation by ~600ms.

Because std_Array_sort is not self-hosted I'm going to try writing the comparator in c++ to see if that improves our performance enough to make the implementation worthwhile.

Comment 2

[Morgan Phillips [:mrrrgn]]

Update, I'm testing out three approaches here:

 1.) Just calling std_Array_sort with a new default comparator. 

This is very easy, but performs a little worse than other engines in my testing.
 
 1.a) Interestingly, we have code to detect and optimize numeric comparators. When I trigger this (by using the comparator (x, y) => x-y the std_Array_sort is very very fast. It would be good to see if it's possible to construct the spec's required comparator so that this optimization is triggered. It would yield the simplest implementation and perform well.

2.) Self-hosted Radix sorts. 

This is a little tricky since they don't take a comparator, but I believe I can just add separate stacks for -0 +0 and NaN to achieve the same behavior as the spec's suggested comparator. This is the fastest way to sort TypedArrays by far.

3.) Self-hosted in place quicksort. This is nearly as fast as Radix and uses less memory. It's also very straightforward.

I've tried 1 and 2 so far, with 1.a and 3 coming today. This should make it possible to make a "real" patch soon.

Comment 3

[Morgan Phillips [:mrrrgn]]

Attachment: typedarrayquicksort.diff

This implementation adds a self-hosted in place quicksort which gives very good results. Notably, at least one other engine (v8) uses quicksort for TypedArrays but we manage to outperform them by quite a lot in the performance tests I've run so far using: https://pastebin.mozilla.org/8854613

SM:
Morgans-MacBook-Pro:_OPT.OBJ mrrrgn$ dist/bin/js ../../../../test-scripts/typedarraysort.js
SORTING f64 WITH 500000 ITEMS 0.06 s
SORTING f32 WITH 500000 ITEMS 0.167 s
SORTING u8 WITH 500000 ITEMS 0.144 s
SORTING i8 WITH 500000 ITEMS 0.145 s
SORTING u16 WITH 500000 ITEMS 0.162 s
SORTING i16 WITH 500000 ITEMS 0.166 s
SORTING u32 WITH 500000 ITEMS 0.177 s
SORTING i32 WITH 500000 ITEMS 0.177 s

V8:
Morgans-MacBook-Pro:v8 mrrrgn$ out/x64.release/shell ~/projects/inbound-clean/test-scripts/typedarraysort.js
SORTING f64 WITH 500000 ITEMS 0.427 s
SORTING f32 WITH 500000 ITEMS 0.586 s
SORTING u8 WITH 500000 ITEMS 0.204 s
SORTING i8 WITH 500000 ITEMS 1.342 s
SORTING u16 WITH 500000 ITEMS 2.843 s
SORTING i16 WITH 500000 ITEMS 2.87 s
SORTING u32 WITH 500000 ITEMS 3.629 s
SORTING i32 WITH 500000 ITEMS 3.527 s

This implementation also outperforms Array.sort(...) by an order of magnitude.

Comment 4

[Morgan Phillips [:mrrrgn]]

Attachment: typedarrayquicksort.diff

Comment 5

[Morgan Phillips [:mrrrgn]]

Plans if this looks good: 1.) rewrite the sort using a MedianOfMedians algorithm for pivot selection. 2.) Add tests and ask for final review. 3.) ???? 4.) profit.

Comment 6

[Jason Orendorff [:jorendorff]]

Comment on attachment 8698687 [details] [diff] [review]
typedarrayquicksort.diff

Review of attachment 8698687 [details] [diff] [review]:
-----------------------------------------------------------------

Yep, this looks good. One or two correctness issues:

*   `new Array()` is probably off-limits in self-hosted code. Change to `[]` or maybe `new List()`.

*   I don't think we can use `std_Array_push` to push to `stack` if it's an actual Array.
    It will misbehave if someone has defined a setter on Array.prototype[0] or something.
    You can do this with
        Object.defineProperty(Array.prototype, 0, {set: function () { throw "FAIL"; }});
    Calling TypedArray.prototype.sort should not cause the setter to be called.

----

If all we cared about was performance, there would be plenty more possible work to do. :)

1.  We could test the no-comparator case against hand-rolled C++. This is what C++ is for;
    just to pick some random thing, you get to skip bounds checks that I don't expect our
    jits to optimize away (we do have an integer range analysis, for eliminating bounds
    checks, but I don't expect it to be able to follow the thread through `stack`).

2.  We could implement a counting-sort for 8-bit array types.

3.  We could use a different implementation of the default comparator for integer types
    vs. floating-point types.

4.  We could probably speed up TypedArrayComparator even for floating-point types.
    Just for starters, if we move the common cases to the top, it should be much
    faster except when we're comparing thousands of NaNs and -0s, which should be rare:

        var diff = x - y;
        if (diff)
            return diff;
        if (x === y) {
            return ...; // TODO, watch out for -0
        }
        return ...;  // TODO, at least one argument is NaN

But all of this is fodder for later bugs.

Comment 7

[Till Schneidereit [:till]]

I don't think we should use QuickSort for this. People really like stable sorting, and I think there *might* be a chance to eventually standardize that. (I think v8 might be the only engine not having a stable sort right now, but that might very well be outdated.) Obviously, introducing a non-stable sort in our engine would be counterproductive for that.

Comment 8

[Jeff Walden [:Waldo]]

The only way unstable sorting is observable here is if people are manually punning distinct NaN-patterns into their typed arrays, unless I'm missing something.  I'm not sure we should worry about that.

Comment 9

[Morgan Phillips [:mrrrgn]]

(In reply to Till Schneidereit [:till] from comment #7)
> I don't think we should use QuickSort for this. People really like stable
> sorting, and I think there *might* be a chance to eventually standardize
> that. (I think v8 might be the only engine not having a stable sort right
> now, but that might very well be outdated.) Obviously, introducing a
> non-stable sort in our engine would be counterproductive for that.

Considering that we're only using this for TypedArrays, where we expect to see numbers in almost all cases, it seems like it wouldn't create a huge problem, nevertheless, it can't hurt to try out a merge sort implementation. 

Mostly I'm wanting to try self-hosting this since it makes future improvements (based on the type) easier to add, and using a js comparator with the std_Array_sort is dog slow.

Comment 10

[Morgan Phillips [:mrrrgn]]

* I mention std_Array_sort since I believe it's already a merge sort.

Comment 11

[Morgan Phillips [:mrrrgn]]

Attachment: typedarraymergesort.diff

Just finished implementing this, and it's still very fast ( faster than v8 ;] ) and fixes up concerns around stability. I am a little sad that we need to increase memory usage, but it's definitely worthwhile if stability is important.

Morgans-MacBook-Pro:_OPT.OBJ mrrrgn$ dist/bin/js ../../../../test-scripts/typedarraysort.js
SORTING f64 WITH 500000 ITEMS 0.16 s
SORTING f32 WITH 500000 ITEMS 0.274 s
SORTING u8 WITH 500000 ITEMS 0.289 s
SORTING i8 WITH 500000 ITEMS 0.277 s
SORTING u16 WITH 500000 ITEMS 0.374 s
SORTING i16 WITH 500000 ITEMS 0.296 s
SORTING u32 WITH 500000 ITEMS 0.301 s
SORTING i32 WITH 500000 ITEMS 0.269 s

Comment 12

[Morgan Phillips [:mrrrgn]]

Attachment: typedarraymergesort.diff

Ha, oops. Derped the last patch upload.

Comment 13

[Morgan Phillips [:mrrrgn]]

To recap, MergeSort is half the performance of QuickSort and uses more memory, but is stable. They both outperform v8, and std_Array_sort very handily.

By self-hosting hour TypedArray sort we open the door for future improvements like the ones Jason mentioned in comment 6. I feel like Merge + Insertion sort is a good middle way forward here. We can improve with Radix in the future (also a stable sort).

Working on tests now.

Comment 14

[Morgan Phillips [:mrrrgn]]

Attachment: typedarraymergesortcomplete.diff

This is a merge sort implementation of the sort, which is half the speed of QuickSort (but still quite fast), but is stable. One thing I'm curious about is whether or not stability _really_ matters here. If not, it will be very easy to drop QuickSort back in.

MergeSort SpiderMonkey:

Morgans-MacBook-Pro:_OPT.OBJ mrrrgn$ dist/bin/js ../../../../test-scripts/typedarraysort.js
SORTING f64 WITH 500000 ITEMS 0.157 s
SORTING f32 WITH 500000 ITEMS 0.281 s
SORTING u8 WITH 500000 ITEMS 0.288 s
SORTING i8 WITH 500000 ITEMS 0.285 s
SORTING u16 WITH 500000 ITEMS 0.369 s
SORTING i16 WITH 500000 ITEMS 0.302 s
SORTING u32 WITH 500000 ITEMS 0.293 s
SORTING i32 WITH 500000 ITEMS 0.254 s

QuickSort SpiderMonkey:

Morgans-MacBook-Pro:_OPT.OBJ mrrrgn$ dist/bin/js ../../../../test-scripts/typedarraysort.js
SORTING f64 WITH 500000 ITEMS 0.06 s
SORTING f32 WITH 500000 ITEMS 0.167 s
SORTING u8 WITH 500000 ITEMS 0.144 s
SORTING i8 WITH 500000 ITEMS 0.145 s
SORTING u16 WITH 500000 ITEMS 0.162 s
SORTING i16 WITH 500000 ITEMS 0.166 s
SORTING u32 WITH 500000 ITEMS 0.177 s
SORTING i32 WITH 500000 ITEMS 0.177 s

callFunction(std_Array_sort, ...) SpiderMonkey:

Morgans-MacBook-Pro:_OPT.OBJ mrrrgn$ dist/bin/js ../../../../test-scripts/typedarraysort.js
SORTING f64 WITH 500000 ITEMS 0.693 s
SORTING f32 WITH 500000 ITEMS 0.704 s
SORTING u8 WITH 500000 ITEMS 0.75 s
SORTING i8 WITH 500000 ITEMS 0.744 s
SORTING u16 WITH 500000 ITEMS 0.718 s
SORTING i16 WITH 500000 ITEMS 0.719 s
SORTING u32 WITH 500000 ITEMS 0.716 s
SORTING i32 WITH 500000 ITEMS 0.667 s

V8 (QuickSort):

Morgans-MacBook-Pro:v8 mrrrgn$ out/x64.release/shell ~/projects/inbound-clean/test-scripts/typedarraysort.js
SORTING f64 WITH 500000 ITEMS 0.397 s
SORTING f32 WITH 500000 ITEMS 0.541 s
SORTING u8 WITH 500000 ITEMS 0.183 s
SORTING i8 WITH 500000 ITEMS 1.241 s
SORTING u16 WITH 500000 ITEMS 2.814 s
SORTING i16 WITH 500000 ITEMS 2.674 s
SORTING u32 WITH 500000 ITEMS 3.39 s
SORTING i32 WITH 500000 ITEMS 3.203 s

Comment 15

[Morgan Phillips [:mrrrgn]]

> This is a merge sort implementation of the sort, which is half the speed of
> QuickSort (but still quite fast), but is stable. One thing I'm curious about
> is whether or not stability _really_ matters here. If not, it will be very
> easy to drop QuickSort back in.

/meta
Holy cow, I've forgotten how to English. ^.^

Comment 16

[Alex Art]

(In reply to Morgan Phillips [:mrrrgn] from comment #14)
> Created attachment 8698825 [details] [diff] [review]
> typedarraymergesortcomplete.diff
> 
> This is a merge sort implementation of the sort, which is half the speed of
> QuickSort (but still quite fast), but is stable. One thing I'm curious about
> is whether or not stability _really_ matters here. If not, it will be very
> easy to drop QuickSort back in.

IMHO for typed array stability does not matter.

Comment 17

[Morgan Phillips [:mrrrgn]]

(In reply to Alex Art from comment #16)
> (In reply to Morgan Phillips [:mrrrgn] from comment #14)
> > Created attachment 8698825 [details] [diff] [review]
> > typedarraymergesortcomplete.diff
> > 
> > This is a merge sort implementation of the sort, which is half the speed of
> > QuickSort (but still quite fast), but is stable. One thing I'm curious about
> > is whether or not stability _really_ matters here. If not, it will be very
> > easy to drop QuickSort back in.
> 
> IMHO for typed array stability does not matter.

I'm inclined to agree, I can't think of a case where someone would need it, and that 2x speedup would be nice....

Comment 18

[Lars T Hansen [:lth]]

(In reply to Morgan Phillips [:mrrrgn] from comment #17)
> (In reply to Alex Art from comment #16)
> > (In reply to Morgan Phillips [:mrrrgn] from comment #14)
> > > Created attachment 8698825 [details] [diff] [review]
> > > typedarraymergesortcomplete.diff
> > > 
> > > This is a merge sort implementation of the sort, which is half the speed of
> > > QuickSort (but still quite fast), but is stable. One thing I'm curious about
> > > is whether or not stability _really_ matters here. If not, it will be very
> > > easy to drop QuickSort back in.
> > 
> > IMHO for typed array stability does not matter.
> 
> I'm inclined to agree, I can't think of a case where someone would need it,
> and that 2x speedup would be nice....

Even more so, sort is specified in terms of [[Get]] and [[Set]] and [[Get]] always canonicalizes; it is arguably incorrect (by the spec) not to canonicalize a NaN whose position changes in the array, and always correct to canonicalize NaNs, on the assumption they were moved at least once as part of the sorting algorithm.  And with self-hosting all this will just happen anyway.

(Piling on: canonicalization probably has to happen since the user can sneak signaling NaNs into the buffer and trip up the comparison if they are not canonicalized.)

+1 for quicksort for the general case.

Comment 19

[Till Schneidereit [:till]]

(In reply to Lars T Hansen [:lth] from comment #18)
> +1 for quicksort for the general case.

And another +1. Canonicalization was what I was concerned about, but is lth right in that it shouldn't be a problem at all. What's more, in the light of day my concerns seem awfully overblown even if it did matter.

However, the mergesort implementation should transfer very nicely to generic arrays, so there's that, at least.

Finally, it'd probably make sense to use something like the dispatch-to-self-hosted helper from attachment 770750 [details] [diff] [review] to only call the self-hosted version if a (non-pattern-matched) comparison function is provided. At least until we get loop unrolling (bug 1039458), the native version is bound to be faster than the self-hosted one in the common case.

Comment 20

[Morgan Phillips [:mrrrgn]]

(In reply to Till Schneidereit [:till] from comment #19)
> (In reply to Lars T Hansen [:lth] from comment #18)
> > +1 for quicksort for the general case.
> 
> And another +1. Canonicalization was what I was concerned about, but is lth
> right in that it shouldn't be a problem at all. What's more, in the light of
> day my concerns seem awfully overblown even if it did matter.
> 
> However, the mergesort implementation should transfer very nicely to generic
> arrays, so there's that, at least.
> 
> Finally, it'd probably make sense to use something like the
> dispatch-to-self-hosted helper from attachment 770750 [details] [diff] [review]
> [review] to only call the self-hosted version if a (non-pattern-matched)
> comparison function is provided. At least until we get loop unrolling (bug
> 1039458), the native version is bound to be faster than the self-hosted one
> in the common case.

Nice, thanks for the dispatch-to-self-hosted suggestion. I'll drop QS back in and save this merge sort for Bug 715181. ;)

Comment 21

[Morgan Phillips [:mrrrgn]]

Comment on attachment 8698825 [details] [diff] [review]
typedarraymergesortcomplete.diff

Keeping the tests/comparator and dropping QS back in due to progress in the discussion. Will consider using this merge sort to tackle bug 715181.

Comment 22

[Morgan Phillips [:mrrrgn]]

Attachment: typedarrayquicksortcomplete.diff

I spent today breaking this apart into functions and trying to sqeeze more performance from it. The biggest improvement came from managing the stack without using push/pop. Strangely enough, 23 elements does seem to be the ideal insertion sort cutoff on my machine.

Comment 23

[Morgan Phillips [:mrrrgn]]

Attachment: typedarrayquicksortcomplete.diff

More bugmail, heh. I was working on bug 1101256 and found that I could indeed implement IsDetachedBuffer checks, so now the spec should be fully satisfied here.

Comment 24

[Jason Orendorff [:jorendorff]]

Comment on attachment 8699642 [details] [diff] [review]
typedarrayquicksortcomplete.diff

Review of attachment 8699642 [details] [diff] [review]:
-----------------------------------------------------------------

Clearing review for now.

These tests are not evil enough. It tests sensible cases. But we need to test stuff like:

* it works if the size of the array is 0
* or 1 or 2 or 3 --- in general, small sizes reveal bugs in sorting algorithms, and you can exhaustively test the sort against every permutation of a small array
* it correctly throws if you pass it a this-value that's not a TypedArray, like a plain Array, or Int32Array.prototype, or an ArrayBuffer with no view, or a DataView, or `Object.create(some typed array)`, or `new Proxy(some typed array, {})`
* it works correctly if you pass it a TypedArray from another global:
        let g2 = newGlobal(); Int32Array.prototype.sort(new g2.Int32Array(4))
* it correctly throws if this TypedArray is detached
* sorting a Float64 or Float32Array containing a variety of NaN bit-patterns produces all-NaN output
* if the comparator function throws, the exception is propagated out as expected
* if the buffer becomes detached in the middle of the sort, due to an evil comparator function, we throw a TypeError (as required by the SortCompare algorithm in the spec)
    ^^^^ I think this particular test would not patch, as the patch stands.
* if the comparator function writes array elements in the middle of a sort, we finish the sort (though the results are not guaranteed to be anything in particular)
* or if the comparator function calls sort() on the array again, recursively, same deal

::: js/src/builtin/TypedArray.js
@@ +909,5 @@
> +    for (var i = from; i <= to; i++) {
> +        item = array[i];
> +        for (var j = i - 1; j >= from; j--) {
> +            swap = array[j];
> +            if (comparefn(swap, item) <= 0) break

Style nit: put `break;` on its own indented line, with a semicolon (we avoid relying on ASI.)

@@ +924,5 @@
> +}
> +
> +// A QuickSort partition helper, returns final index positions (i, j)
> +// used for swapping values around the pivot
> +function Partition(array, from, to, comparefn) {

Document the preconditions with a comment: 0 <= from < to < array.length

@@ +936,5 @@
> +    // Median of three pivot selection
> +    if (comparefn(array[from], array[to]) > 0)
> +        SwapArrayElements(array, from, to);
> +
> +    if(comparefn(array[i], array[to]) > 0)

Style int: Please add a space between `if` and `(` and generally between a keyword and a parenthesis (there are several cases of `while(` and `for(` in this code).

@@ +947,5 @@
> +
> +    while(true) {
> +        do i++; while(comparefn(array[i], array[pivot_i]) < 0);
> +        do j--; while(comparefn(array[j], array[pivot_i]) > 0);
> +        if (i > j) break;

Nit: break; on its own line

@@ +952,5 @@
> +        SwapArrayElements(array, i, j);
> +    }
> +
> +    SwapArrayElements(array, pivot_i, j);
> +    return [i, j];

I would return only one of the two indices. The benefit (in the special case where many elements are equal) isn't worth the allocation. (If we were going to start tuning for special cases, we would have a merge sort, right?)

@@ +958,5 @@
> +
> +// In-place QuickSort
> +function QuickSort(array, len, comparefn) {
> +    // Managing the stack ourselves seems to provide a small performance boost
> +    var stack = new List(len);

The List constructor doesn't take an argument.

@@ +962,5 @@
> +    var stack = new List(len);
> +    var top = 0;
> +
> +    var start = 0;
> +    var end = len - 1;

Sort algorithms are a lot easier to read if the stop index variables are "fenceposts" (i.e. one past the end of the range in question, like in Python). I suppose it's OK like this, though.

@@ +970,5 @@
> +        // Insertion sort for the first N elements where N is some value
> +        // determined by performance testing.
> +        if (end - start <= 23) {
> +            InsertionSort(array, start, end, comparefn);
> +            if (top <= 0) break;

Style nit: `break;` on its own line.

@@ +972,5 @@
> +        if (end - start <= 23) {
> +            InsertionSort(array, start, end, comparefn);
> +            if (top <= 0) break;
> +            end   = stack[top - 1]; top--;
> +            start = stack[top - 1]; top--;

It's ok to write `stack[--top];`. It preserves the symmetry between push and pop statements:

    stack[top++] = v;
    v = stack[--top];

@@ +980,5 @@
> +            i = indices[0];
> +            j = indices[1];
> +
> +            // Continue sorting around the indices
> +            if (end - i + 1 >= j - start) {

Comment that pushing the longer range and leaving the shorter one in [start, end] limits the maximum number of `stack` entries we allocate to ceil(log2(len)). Otherwise it could get big.

@@ +1044,5 @@
> +    var len = TypedArrayLength(obj);
> +
> +    // Steps 2a, 2c, and 2d from TypedArray SortCompare described in 22.2.3.26.
> +    if (comparefn === undefined)
> +      comparefn = TypedArrayCompare

Nit: semicolon

::: js/src/tests/ecma_6/TypedArray/sort.js
@@ +1,3 @@
> +function *genRandomInt(to, power) {
> +    for (var i = 0; i < to; i++)
> +        yield Math.round((Math.pow(2, power) * Math.random()) - 1);

Nit: Symptomless bug, but please use Math.floor() rather than Math.round(), and drop the `- 1` at the end. As it stands, this can yield -1, which turns out to be OK but it sure is weird.

More importantly: please paste in a short random number generator, initially seeded from Math.random(), and have the test print() the initial seed. That way, on failure, we can get the seed out of the log and recreate the data that triggered the bug. (Otherwise, there is no way to investigate failures and the test is therefore useless!)

A random number generator for something like this shouldn't be longer than 10 lines of code. See <https://en.wikipedia.org/wiki/Xorshift#Example_implementation> for a nice one that doesn't require 64-bit ints.

@@ +4,5 @@
> +}
> +
> +function *genRandomFloat(to, power) {
> +    for (var i = 0; i < to; i++)
> +        yield (Math.pow(2, power) * Math.random()) - 1;

This doesn't cover anything like the whole range of floats. Which is fine; maybe we don't need to - but it reads like a bug.

You could say:

    let sign = Math.random() > .5 ? 1 : -1;
    let mant = 1 + Math.random();
    let exp = Math.floor(2046 * Math.random()) - 1022;
    yield sign * mant * 2**exp;

and get a uniform-ish distribution over most of the finite float64s. Bute you'd be missing 0, -0, NaNs, infinities, and the denormalized range (very small numbers).

Better, you can create a Uint32Array pointing at the same ArrayBuffer as the Float64Array or Float32Array, and use it to fill the underlying buffer with random bits. That can (of course) produce every possible value.

This brings up an interesting quirk, though. I think you can use the same machine code to sort a Float32Array as an Int32Array, because the bits of an IEEE floating-point number are arranged just so...

@@ +9,5 @@
> +}
> +
> +function hasEqualElements(arrayOne, arrayTwo) {
> +  assertEq(arrayOne.length, arrayTwo.length);
> +  for (let i in arrayOne)

correct, but makes me queasy because here `i` is a string. :)  I would use a for(let i = 0; ...; i++) loop but it's up to you.

@@ +28,5 @@
> +float64NaN.sort();
> +float32NaN.sort();
> +
> +hasEqualElements(float64NaN, new Float64Array(NaNsAndZeros.sorted));
> +hasEqualElements(float32NaN, new Float32Array(NaNsAndZeros.sorted));

The stuff regarding NaNsAndZeros is logically a completely separate test. Please put it in a separate file.

@@ +54,5 @@
> +        typedArray = Int32Array.from(
> +            testData.generator(dataSize, testData.power));
> +    if (dataType == "u32")
> +        typedArray = Uint32Array.from(
> +            testData.generator(dataSize, testData.power));

I would write it like this (having had the benefit of seeing your code with a fresh eye):

    function RunTests(size) {
        SortTest(Int32Array, genRandomInt(size, 32));
        SortTest(Uint32Array, genRandomInt(size, 32));
        SortTest(Int16Array, genRandomInt(size, 16));
        ...
        SortTest(Float64Array, genRandomFloat(size));
    }

    RunTests(9);
    RunTests(5000);

replacing both TestData and the if-statements.

@@ +81,5 @@
> +    let largest = typedArray[0];
> +    for (let i=1; i < typedArray.length; i++) {
> +        assertEq(typedArray[i] >= largest, true, "The array is not properly sorted!")
> +        largest = typedArray[i];
> +    }

I found this awkward; consider instead:

   for (let i = 0; i < typedArray.length - 1; i++)
       assertEq(typedArray[i] <= typedArray[i + 1], "The array is not properly sorted!");

For the reversed sort, the only thing that needs to change is <= to >=.

@@ +95,5 @@
> +    }
> +}
> +
> +for (let t of Object.getOwnPropertyNames(TestData))
> +    SortTest(t, 5*Math.pow(10, 3));

This number should be written 5e3 or just 5000.

Comment 25

[Jason Orendorff [:jorendorff]]

> Document the preconditions with a comment: 0 <= from < to < array.length

This isn't the correct precondition; comment the correct one of course ;-)

Partition()'s comment should be quite formal. Like:

// Rearranges the elements in array[from:to] and returns a pair [i, j] such that:
//     from < i < j < to
//     each element in array[from:i] is less than each element in array[i:j]
//     each element in array[i:j] is equal to each other element in array[i:j]
//     each element in array[j:to] is greater than each element in array[i:j]

Comment 26

[Morgan Phillips [:mrrrgn]]

Attachment: typedarrayquicksortcomplete.diff

Comment 27

[Morgan Phillips [:mrrrgn]]

(In reply to Jason Orendorff [:jorendorff] from comment #24)

Thank you for the awesomely thorough review, I've fixed up most of the issues you pointed out, however, I'm not sure if this one needs doing:

> ++ * if the buffer becomes detached in the middle of the sort, due to an evil
> comparator function, we throw a TypeError (as required by the SortCompare
> algorithm in the spec)
>     ^^^^ I think this particular test would not patch, as the patch stands.

In the spec it seems to only call for a detached buffer check if the default comparator is being used:

"""
2.) If the argument comparefn is not undefined, then

    a. Let v be ? Call(comparefn, undefined, « x, y »).
    b. If IsDetachedBuffer(buffer) is true, throw a TypeError exception.
    c. If v is NaN, return +0.
    d. Return v.
"""

So this test may be unnecessary. Please let me know if I'm misreading the spec.

Comment 28

[Morgan Phillips [:mrrrgn]]

Attachment: typedarraymergesortcomplete.diff

Hopefully moving closer to our target.

Comment 29

[Morgan Phillips [:mrrrgn]]

Attachment: typedarrayquicksortcomplete.diff

/me uploads wrong patch

Comment 30

[Morgan Phillips [:mrrrgn]]

Comment on attachment 8701246 [details] [diff] [review]
typedarrayquicksortcomplete.diff

Reworking this, tests are no longer working after the holiday since one of them depended on ArrayBuffer.transfer: see https://bugzilla.mozilla.org/show_bug.cgi?id=1235631#c3 for an explanation.

Comment 31

[Jason Orendorff [:jorendorff]]

(In reply to Morgan Phillips [:mrrrgn] from comment #27)
> In the spec it seems to only call for a detached buffer check if the default
> comparator is being used:
> 
> """
> 2.) If the argument comparefn is not undefined, then
> 
>     a. Let v be ? Call(comparefn, undefined, « x, y »).
>     b. If IsDetachedBuffer(buffer) is true, throw a TypeError exception.
> """

It's the other way around: "If the argument comparefn is **not** undefined" i.e. the default comparator is **not** being used.

Comment 32

[Morgan Phillips [:mrrrgn]]

(In reply to Jason Orendorff [:jorendorff] from comment #31)
> (In reply to Morgan Phillips [:mrrrgn] from comment #27)
> > In the spec it seems to only call for a detached buffer check if the default
> > comparator is being used:
> > 
> > """
> > 2.) If the argument comparefn is not undefined, then
> > 
> >     a. Let v be ? Call(comparefn, undefined, « x, y »).
> >     b. If IsDetachedBuffer(buffer) is true, throw a TypeError exception.
> > """
> 
> It's the other way around: "If the argument comparefn is **not** undefined"
> i.e. the default comparator is **not** being used.

https://stopdrinkingmyfrigginmilk.files.wordpress.com/2012/02/i-am-so-smrt-80stees1.jpg

Comment 33

[Steve Fink [:sfink] [:s:]]

(In reply to Morgan Phillips [:mrrrgn] from comment #30)
> Comment on attachment 8701246 [details] [diff] [review]
> typedarrayquicksortcomplete.diff
> 
> Reworking this, tests are no longer working after the holiday since one of
> them depended on ArrayBuffer.transfer: see
> https://bugzilla.mozilla.org/show_bug.cgi?id=1235631#c3 for an explanation.

The effect of ArrayBuffer.transfer should still be possible. In the shell, you can use serialize with a Transferable parameter to detach a buffer. In the browser, you can use postMessage. Detaching is still a thing; the bug you pointed to is only talking about removing its usage for asm.js's "heap resizing" (and the attendant unspecced helper function that was just a convenience anyway.)

Comment 34

[Morgan Phillips [:mrrrgn]]

Attachment: typedarrayquicksort.diff

More tests and a proper implementation of Step 2. from the TypedArray comparator spec.

Comment 35

[Morgan Phillips [:mrrrgn]]

Attachment: typedarrayquicksortcomplete.diff

Comment 36

[Jason Orendorff [:jorendorff]]

Comment on attachment 8704014 [details] [diff] [review]
typedarrayquicksortcomplete.diff

Review of attachment 8704014 [details] [diff] [review]:
-----------------------------------------------------------------

OK!

::: js/src/builtin/TypedArray.js
@@ +905,5 @@
>  
> +// For sorting small arrays
> +function InsertionSort(array, from, to, comparefn) {
> +    var item, swap;
> +    for (var i = from; i <= to; i++) {

`i` could start at `from + 1`, right?

@@ +923,5 @@
> +    array[i] = array[j];
> +    array[j] = swap;
> +}
> +
> +// Rearranges the elements in array[from:to] and returns an index j such that:

`array[from:to+1]`, right?

@@ +926,5 @@
> +
> +// Rearranges the elements in array[from:to] and returns an index j such that:
> +// - from < j < to
> +// - each element in array[from:j] is less than or equal to array[j]
> +// - each element in array[j:to] greater than or equal to array[j].

And `array[j+1:to+1]`.

@@ +928,5 @@
> +// - from < j < to
> +// - each element in array[from:j] is less than or equal to array[j]
> +// - each element in array[j:to] greater than or equal to array[j].
> +function Partition(array, from, to, comparefn) {
> +    var median_i = (from + to) >> 1;

This whole function is rather intricate. Would it break down if `to - from` was, say, 3? What if it was 2?

Figure out some number that's definitely safe, and add `assert(to - from >= safeNumber);` please.

@@ +945,5 @@
> +
> +    if (comparefn(array[from], array[i]) > 0)
> +        SwapArrayElements(array, from, i);
> +
> +    var pivot_i = i;

I don't even want to admit how long it took me to figure out this code. :-|

@@ +947,5 @@
> +        SwapArrayElements(array, from, i);
> +
> +    var pivot_i = i;
> +
> +    while(true) {

Style nit: space after keyword

@@ +1010,5 @@
> +// as opposed to the ordering in the spec.
> +function TypedArrayCompare(x, y) {
> +    // Step 1.
> +    assert(typeof x === "number" && typeof y === "number",
> +           "x and y are not numbers.")

Nit: missing semicolon.

@@ +1066,5 @@
> +            if (IsDetachedBuffer(buffer))
> +                ThrowTypeError(JSMSG_TYPED_ARRAY_DETACHED);
> +            // Step c.
> +            if (Number_isNaN(v))
> +                return 0;

Step c is redundant, since every where this function is used, it's used in one of these ways:

    comparefn(a, b) < 0
    comparefn(a, b) > 0

and these are always false if the function returns NaN, just as if it returned 0.

::: js/src/tests/ecma_6/TypedArray/sort_basics.js
@@ +41,5 @@
> +    if (a === -Infinity && b === Infinity)
> +        return true;
> +    if (a === Infinity && b === -Infinity)
> +        return false;
> +    return a <= b;

<= works as expected on infinities - the four lines before `return a <= b;` here are redundant.

@@ +57,5 @@
> +    typedArray.sort();
> +
> +    for (let i=0; i < typedArray.length - 1; i++)
> +        assertEq(lte(typedArray[i], typedArray[i + 1]), true,
> +                 `The array is not properly sorted! ${typedArray[i]} > ${typedArray[i + 1]}, seed: ${SEED}`)

This tests that the "after" data is in order, but not that it is a permutation of the "before" data.

The surest way I can think of to check the latter property is:

    var originalValues = Array.from(typedArray);
    typedArray.sort();
    assertDeepEq(Array.from(typedArray), Array.from(originalValues).sort(cmp));

where

    function cmp(a, b) {
        return lte(a, b) ? gte(a, b) ? 0 : -1 : 1;
    }

@@ +72,5 @@
> +            return 1;
> +        if (y === -Infinity && x === Infinity)
> +            return -1;
> +        return y - x;
> +    });

With the above definition of cmp, I think this could have been something like:

    typedArray.sort((x, y) => cmp(y, x));

::: js/src/tests/ecma_6/TypedArray/sort_comparators.js
@@ +12,5 @@
> +
> +assertThrows(() => {
> +    let array = new Uint8Array([1, 99, 2, 99]);
> +    array.sort(badComparator);
> +}, TypeError);

These tests are redundant with some in sort_errors.js, right?

@@ +26,5 @@
> +    return x - y;
> +}
> +outsideArray.sort(addingComparator)
> +assertEq(outsideArray[0], 101);
> +assertEq(outsideArray[outsideArray.length - 1], 102);

I'm sure the standard doesn't guarantee that these last two assertions will pass. Maybe it's not worth asserting these things; it's enough that the sort finishes (we'll get a test failure if it doesn't).

The standard does seem to require that outsideArray.every(x => [1, 2, 99, 101, 102].includes(x)) is true.

@@ +36,5 @@
> +    outsideArray.sort();
> +    return x - y;
> +}
> +outsideArray.sort(recursiveComparator);
> +assertDeepEq(outsideArray, new Int32Array([1, 99, 99]));

Same comment here.

@@ +46,5 @@
> +    let array = new Uint8Array(buffer);
> +    array[0] = 21;
> +    array[1] = 12;
> +    array.sort((x, y) => {
> +        neuter(buffer, "change-data");

This test is also the same as one in sort_errors.js.

@@ +56,5 @@
> +// to +0s.
> +let nanComparatorData  = [2112, 42, 1111, 34];
> +let nanComparatorArray = new Int32Array(nanComparatorData);
> +nanComparatorArray.sort((x, y) => NaN);
> +assertDeepEq(nanComparatorArray, new Int32Array(nanComparatorData));

Again, the spec doesn't require this assertion to pass. Any permutation of the input would be fine; when the comparator returns +0 (or NaN) it means the sort routine is allowed to do whatever it wants.

Better, then, to assert that every element of nanComparatorData is still in the array after sorting:

    assertEq(nanComparatorData.every(x => nanComparatorArray.includes(x)), true);

::: js/src/tests/ecma_6/TypedArray/sort_errors.js
@@ +9,5 @@
> +// Ensure that TypedArray.prototype.sort will not sort non-TypedArrays
> +assertThrows(() => {
> +    let array = [4, 3, 2, 1];
> +    Int32Array.prototype.sort.call(array);
> +}, TypeError);

assertThrows() only takes one argument. You want assertThrowsInstanceOf().

@@ +27,5 @@
> +
> +// Ensure that comparator errors are propagataed
> +function badComparator(x, y) {
> +    if (x == 99 && y == 99)
> +        throw TypeError;

`throw new TypeError`

::: js/src/tests/ecma_6/TypedArray/sort_small.js
@@ +4,5 @@
> +    arr[j] = swap;
> +}
> +
> +// Yield every combination of the elements in some iterable.
> +function *combinations(items) {

Nit: These are permutations, not combinations.

@@ +17,5 @@
> +    }
> +}
> +
> +// Pre-sorted test data, it's important that these arrays remain in ascending order.
> +let i32  = [-2147483647, -320000, -244000, 0, 4, 777000, 2147483647]

If you want to test the minimum value of these types, it's -2147483648 here, not 7, and likewise -32768 and -128 below.

@@ +22,5 @@
> +let u32  = [0, 1, 42, 5000, 987632, 1013000, 4294967295]
> +let i16  = [-32767, -999, -1, 0, 2, 1942, 32767]
> +let u16  = [0, 2, 1942, 8147, 32767, 65535, 65535]
> +let i8   = [-127, -99, 0, 0, 1, 2, 127]
> +let u8   = [0, 1, 2, 44, 89, 255]

If the runtime of this test is not instantaneous, it'd be fine to make some of the arrays shorter. Slow tests are a drag forever.

Maybe it's fine though - 7! is 5040, and we have 7 arrays of length 7, so this is about 35,000 trials sorting arrays of length 7? Should be pretty snappy, I hope.

...In fact, make sure that we test at least one array each of length 1, 2, and 3, all permutations. (sort_basics already covers empty arrays.)

::: js/src/tests/ecma_6/TypedArray/sort_snans.js
@@ +4,5 @@
> +    let a = [];
> +    for (let i = 0; i < length; i++)
> +        a.push(NaN);
> +    return a;
> +};

Style nit: unnecessary semicolon after function declaration

Comment 37

[Morgan Phillips [:mrrrgn]]

Try run: https://treeherder.mozilla.org/#/jobs?repo=try&revision=3b1b163d8edb

Comment 38

[Pulsebot]

https://hg.mozilla.org/integration/mozilla-inbound/rev/509a6dd8d1c5

Comment 39

[Nigel Babu [:nigelb]]

Backing out for jsreftest bustage that looks like https://treeherder.mozilla.org/logviewer.html#?job_id=19417362&repo=mozilla-inbound

Comment 40

[Nigel Babu [:nigelb]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/2f6e12a6f04f8e676c357bd50ec88e81f2037306
Backed out changeset 509a6dd8d1c5 (bug 1121937) for jsreftest bustage

Comment 41

[Morgan Phillips [:mrrrgn]]

I'd omitted "// |reftest| skip-if(!xulRuntime.shell)" from a test that required neuter(...) -- fixing it up.

Comment 42

[Pulsebot]

https://hg.mozilla.org/integration/mozilla-inbound/rev/21b1103b8b11

Comment 43

[Jeff Walden [:Waldo]]

(In reply to Morgan Phillips [:mrrrgn] from comment #41)
> I'd omitted "// |reftest| skip-if(!xulRuntime.shell)" from a test that
> required neuter(...) -- fixing it up.

Congratulations on, for the first time, making the same mistake the rest of us regularly make even years into hacking SpiderMonkey!  :-D

(It would be nice not to have this footgun, but the browser will never do everything the shell does, nor vice versa, and it's hard to see a way to distinguish failure by using an unprovided capability, from failure by dint of real bug.  I guess we could do a top-level splitup of tests that are browser-only, tests that are shell-only, and tests that run in both.  But I would expect people would still regularly write tests in the wrong locations if that were done, so wouldn't solve much.)

Comment 44

[Morgan Phillips [:mrrrgn]]

(In reply to Jeff Walden [:Waldo] (remove +bmo to email) from comment #43)
> (In reply to Morgan Phillips [:mrrrgn] from comment #41)
> > I'd omitted "// |reftest| skip-if(!xulRuntime.shell)" from a test that
> > required neuter(...) -- fixing it up.
> 
> Congratulations on, for the first time, making the same mistake the rest of
> us regularly make even years into hacking SpiderMonkey!  :-D
> 
> (It would be nice not to have this footgun, but the browser will never do
> everything the shell does, nor vice versa, and it's hard to see a way to
> distinguish failure by using an unprovided capability, from failure by dint
> of real bug.  I guess we could do a top-level splitup of tests that are
> browser-only, tests that are shell-only, and tests that run in both.  But I
> would expect people would still regularly write tests in the wrong locations
> if that were done, so wouldn't solve much.)

Muahahaha, thank you. I feel somewhat better about it now. ^.^

Comment 45

[Carsten Book [:Tomcat]]

https://hg.mozilla.org/mozilla-central/rev/21b1103b8b11

Comment 46

[Florian Scholz (Open Web Docs)]

https://developer.mozilla.org/en-US/Firefox/Releases/46#JavaScript
https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/TypedArray/sort