MergeSort should directly call QuickSort instead of TypedArraySort

RESOLVED FIXED in Firefox 59

Status

()

defect
RESOLVED FIXED
3 years ago
10 months ago

People

(Reporter: anba, Assigned: anba)

Tracking

Trunk
mozilla59
Points:
---

Firefox Tracking Flags

(firefox59 fixed)

Details

Attachments

(1 attachment)

(Assignee)

Description

3 years ago
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
(Assignee)

Comment 1

a year ago
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?
(Assignee)

Comment 3

a year ago
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. :-)
(Assignee)

Comment 4

a year ago
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+
(Assignee)

Comment 7

a year ago
(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

a year ago
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

Comment 9

a year ago
bugherder
https://hg.mozilla.org/mozilla-central/rev/a132aef55cd0
Status: ASSIGNED → RESOLVED
Last Resolved: a year ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla59
You need to log in before you can comment on or make changes to this bug.