MergeSort should directly call QuickSort instead of TypedArraySort

RESOLVED FIXED in Firefox 59

Status

()

defect
RESOLVED FIXED
3 years ago
Last year

People

(Reporter: anba, Assigned: anba)

Tracking

Trunk
mozilla59
Points:
---
Dependency tree / graph

Firefox Tracking Flags

(firefox59 fixed)

Details

Attachments

(1 attachment)

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"
Blocks: 1291005
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.
Assignee: nobody → andrebargull
Status: NEW → ASSIGNED
Attachment #8930053 - Flags: review?(evilpies)
I am not too optimistic about people fixing their code, when it still works ;) What kind of performance difference are we talking about?
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. :-)
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 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.
Attachment #8930053 - Flags: review?(evilpies) → review+
(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.
Pushed by ryanvm@gmail.com:
https://hg.mozilla.org/integration/mozilla-inbound/rev/a132aef55cd0
Remove typed array specialization in Array.prototype.sort. r=evilpie
Keywords: checkin-needed
https://hg.mozilla.org/mozilla-central/rev/a132aef55cd0
Status: ASSIGNED → RESOLVED
Closed: 2 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla59
You need to log in before you can comment on or make changes to this bug.