Closed Bug 1290554 Opened 3 years ago Closed 8 months ago

Typed array sort with custom comparator is not stable

Categories

(Core :: JavaScript: Standard Library, defect, P3)

defect

Tracking

()

RESOLVED FIXED
mozilla67
Tracking Status
firefox50 --- wontfix
firefox67 --- fixed

People

(Reporter: anba, Assigned: anba)

References

Details

Attachments

(1 file, 1 obsolete file)

It was just brought to my attention that the TypedArraySort function with a custom comparator is not stable. The review thread in bug 1121937 only considers instability for NaN inputs, but an instable sort can be observed without NaNs.

Test case:
---
a = [2,1,0,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4];
ta = new Int8Array(a);
cmpfn = function(a, b){ return (a/4|0) - (b/4|0) };

print([].toString.call(ta.sort(cmpfn).slice(0, 3)));
print(a.sort(cmpfn).slice(0, 3));
---

Expected: Prints "2,1,0" two times.
Actual: Prints "2,0,1" for typed array sort, and "2,1,0" for normal array sort.
Blocks: 1291005
Non-stable sort is also visible when NaN is used to represent same-elements (per spec NaN should be converted to 0). 

---
print(new Int32Array([0, 1]).sort(() => 0));
print(new Int32Array([0, 1]).sort(() => NaN));
---

Expected: Both arrays are sorted in the same order
Actual: Different sort order is applied

We claim handling NaN is not required [1], but since QuickSort calls InsertionSort internally [2], and InsertionSort has a `<= 0` comparison, this claim is false.

[1] http://searchfox.org/mozilla-central/rev/51eae084534f522a502e4b808484cde8591cb502/js/src/builtin/TypedArray.js#1235-1236
[2] http://searchfox.org/mozilla-central/rev/e76c0fee79a34a3612740b33508276f4b37c3ee8/js/src/builtin/Sorting.js#373
[3] http://searchfox.org/mozilla-central/rev/e76c0fee79a34a3612740b33508276f4b37c3ee8/js/src/builtin/Sorting.js#197
Priority: -- → P3
Assignee: nobody → andrebargull
Status: NEW → ASSIGNED
Attached patch bug1290554.patch (obsolete) — Splinter Review

Directly calling the existing MergeSort function will lead to a performance regression, so instead create a new merge-sort implementation optimised for TypedArrays (and also include the performance ideas from bug 1291463).

The specialised TypedArray MergeSort function contains the following changes:

  • The buffer is another TypedArray instance using the same TypedArray element kind.
  • The InsertionSort limit is reduced from 24 to 8, because the preparation steps complete faster compared to the MergeSort function for normal Arrays, since we don't need to collect any dense elements.

bug 1291463 includes the following (standard) MergeSort performance ideas:

  • Use a single buffer and switch the roles of the input and buffer in each turn.
  • Use InsertionSort instead of MergeSort to sort the initial sort windows.
  • And detect already sorted sub-lists in the Merge step.

Drive-by changes:

Here are some rough performance results for the following µ-benchmark to show that having a specialised MergeSort implementation for TypedArrays pays off. (Note: I think there's something wrong when Ion-optimising the current QuickSort with the user comparator wrapper, because after removing these lines, QuickSort is noticeably faster.)

Test QuickSort MergeSort-Array MergeSort-TypedArray
Length=32 (iter=100000) 240ms 530ms 140ms
Length=100 (iter=20000) 200ms 370ms 125ms
Length=1000 (iter=2000) 320ms 530ms 190/260ms
Length=10000 (iter=200) 430ms 690ms 430ms
Length=100000 (iter=20) 530ms 780ms 540ms
function sortAscending(a,b) {
    return a - b;
}

var source = new Int32Array(32);
for (var j = 0; j < source.length; ++j) source[j] = (Math.random() * 0x40000000)|0;

function f() {
    var xs = [new Int32Array(source.length), new Int32Array(source.length)];
    var r = 0, t = 0;
    for (var i = 0; i < 100000; ++i) {
        var ta = xs[i & 1];
        ta.set(source);

        var q = dateNow()
        r += ta.sort(sortAscending).length;
        t += dateNow() - q;
    }
    return [t, r];
}
Attachment #9043913 - Flags: review?(jorendorff)
Comment on attachment 9043913 [details] [diff] [review]
bug1290554.patch

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

Very nice patch. Thanks.

Please consider adding the tests to test262 instead.

::: js/src/builtin/Sorting.js
@@ +318,5 @@
>      return array;
>  }
>  
> +// A helper function for MergeSortTypedArray.
> +function MergeTypedArray(list, buffer, start, mid, end, comparefn) {

// Merge comparefn-sorted slices list[start..<=mid] and list[mid+1..<=end],
// storing the merged sequence in buffer[start..<=end].

Maybe `buffer` could be renamed `out`.

I wonder why we are not already using half-open ranges for everything in this file. Seems weird.
Attachment #9043913 - Flags: review?(jorendorff) → review+

There are test262 tests upstream for sorting stability:

If someone wants to update our test262 pull -- nudge nudge, wink wink -- we could use those. (That would also let me get bug 1519097 reviewed and landed...)

Can this land now?

Flags: needinfo?(andrebargull)
Attached patch bug1290554.patchSplinter Review

Applied review comments, I'll create a follow-up bug for upstreaming our sort tests to test262.

Attachment #9043913 - Attachment is obsolete: true
Flags: needinfo?(andrebargull)
Attachment #9047125 - Flags: review+

Filed bug 1531085 for upstreaming the tests.

Pushed by rmaries@mozilla.com:
https://hg.mozilla.org/integration/mozilla-inbound/rev/603a46a1e921
Use stable sort for TypedArraySort when a user comparator is present. r=anba

Keywords: checkin-needed
Status: ASSIGNED → RESOLVED
Closed: 8 months ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla67
You need to log in before you can comment on or make changes to this bug.