1290543 - MergeSort should directly call QuickSort instead of TypedArraySort

Status: RESOLVED FIXED

(Core :: JavaScript: Standard Library, defect)

Description

[André Bargull [:anba]]

Test case:
---
ta = new Int8Array([3,2,1]);
Object.defineProperty(ta, "length", {value: 2});
[].sort.call(ta, function(a, b){ return a - b; });
print([].toString.call(ta));


ta = new Int8Array([3,2,1]);
Object.defineProperty(ta, "length", {value: 2});
[].sort.call(ta, function(a, b){ var d = a - b; return d; });
print([].toString.call(ta));
---

Expected: Prints "2,3,1" two times
Actual: Prints "2,3,1" followed by "1,2,3"

Comment 1

[André Bargull [:anba]]

Attachment: bug1290543.patch

I think it's no longer necessary to special-case typed arrays in Array.p.sort(). Web-pages which are concerned about the performance of sorting typed arrays hopefully have been updated in the last 1.5 years (or almost two years when considering the release date for Fx59 and bug 1259600, which added this code) to use TypedArray.p.sort() directly.

Comment 2

[Tom S [:evilpie]]

I am not too optimistic about people fixing their code, when it still works ;) What kind of performance difference are we talking about?

Comment 3

[André Bargull [:anba]]

Hmm, it depends on the typed array element type, size, and element values (random elements, fully or partially sorted in ascending/descending order, all elements are the same value, etc.). Plus taking into account that our Mergesort implementation lacks a few optimizations (bug 1291463), performance regressions between 0-100% are possible. ¯\_(ツ)_/¯ 

(Yes, I know this is probably not a super helpful answer. :-)

Comment 4

[André Bargull [:anba]]

And it looks like the in-operator isn't optimized for typed arrays, so this check also costs a bit (on top of the other missing MergeSort optimizations): https://searchfox.org/mozilla-central/rev/919dce54f43356c22d6ff6b81c07ef412b1bf933/js/src/builtin/Sorting.js#279

Comment 5

[Tom S [:evilpie]]

Comment on attachment 8930053 [details] [diff] [review]
bug1290543.patch

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

Please file a follow-up for "in" on typed arrays. That shouldn't be too hard to fix.

Comment 6

[André Bargull [:anba]]

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

Comment 7

[André Bargull [:anba]]

(In reply to Tom Schuster [:evilpie] from comment #5)
> Comment on attachment 8930053 [details] [diff] [review]
> bug1290543.patch
> 
> Review of attachment 8930053 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> Please file a follow-up for "in" on typed arrays. That shouldn't be too hard
> to fix.

Filed bug 1419372 to optimize the in-operator on typed arrays.

Comment 8

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/mozilla-inbound/rev/a132aef55cd0
Remove typed array specialization in Array.prototype.sort. r=evilpie

Comment 9

[Stefan Hindli [:stefan_hindli]]

https://hg.mozilla.org/mozilla-central/rev/a132aef55cd0