Closed
Bug 1291463
Opened 8 years ago
Closed 5 years ago
Array.prototype.sort performance improvements
Categories
(Core :: JavaScript: Standard Library, defect, P3)
Core
JavaScript: Standard Library
Tracking
()
RESOLVED
FIXED
mozilla70
People
(Reporter: anba, Assigned: anba)
References
(Blocks 1 open bug)
Details
Attachments
(3 files, 3 obsolete files)
Possible performance improvements for Array.prototype.sort: - Move "ArraySort" to vm/CommonPropertyNames.h instead of calling Atomize repeatedly - Directly return in ArraySort() if the length less than 2 - Handle partially sorted sublists in Merge - Reduce stores in Merge() by using a single additional buffer - Use std_Array instead of List (also avoids a JIT bug [1] when there's only one element) - Handle packed arrays when storing from the array to the denseList - Use InsertionSort() instead of Merge() for windowSize=1 and windowSize=2 [1]: --- function t(array) { function c(a, b) { var d = a - b; return d; } var t = 0; for (var i = 0; i < 100000; ++i) { var arrays = []; for (var j = 0; j < 10; ++j) arrays[j] = array(); var d = dateNow(); for (var j = 0; j < 10; ++j) arrays[j].sort(c); t += (dateNow() - d); } print(t); } // Slow t(() => [1,,,,,,,,,,]); // Faster // t(() => [,,,,,,,,,,]); // t(() => [1,2,,,,,,,,,]); ---
Assignee | ||
Comment 1•8 years ago
|
||
Patch which implements the suggestions mentioned in comment #0
Assignee | ||
Comment 2•8 years ago
|
||
Results when running the attached benchmark, including comparisons to JavaScriptCore and V8.
Assignee | ||
Comment 3•8 years ago
|
||
SpiderMonkey version: m-c ffac2798999c JSC version: trunk rev204022 V8 version: master 8552e6822317c48638eb25d71c902cffebee21f1
Comment 4•8 years ago
|
||
I have difficulty thinking of pretty much any situation where it makes sense to have Atomize(cx, "...", ...) in regularly executed, non-test code. Things like ArraySort and similar should always be in CommonPropertyNames.h, IMO.
Assignee | ||
Comment 5•8 years ago
|
||
Attachment #8777104 -
Attachment is obsolete: true
Assignee | ||
Comment 6•8 years ago
|
||
Attachment #8777107 -
Attachment is obsolete: true
Updated•6 years ago
|
Priority: -- → P3
Assignee | ||
Comment 8•5 years ago
|
||
Also change the temporary buffer to a normal Array to ensure the Merge
helper
is called with the same object class.
Assignee | ||
Updated•5 years ago
|
Attachment #8777105 -
Attachment is obsolete: true
Assignee | ||
Comment 9•5 years ago
|
||
With bug 1538692 also applied, this improves µ-benchmark from bug 1502882 when the str_cmp_full
comparator function is used from 6.2ms (when only bug 1538692 is applied) to 5.5ms for me.
Blocks: 1502882
Assignee | ||
Updated•5 years ago
|
Assignee: nobody → andrebargull
Status: NEW → ASSIGNED
Assignee | ||
Comment 11•5 years ago
|
||
Flags: needinfo?(andrebargull)
Keywords: checkin-needed
Comment 12•5 years ago
|
||
Pushed by nbeleuzu@mozilla.com:
https://hg.mozilla.org/integration/autoland/rev/a869bc3e91a4
Apply TypedArray sort optimisations to normal Array sort. r=jorendorff
Keywords: checkin-needed
Comment 13•5 years ago
|
||
bugherder |
Status: ASSIGNED → RESOLVED
Closed: 5 years ago
status-firefox70:
--- → fixed
Resolution: --- → FIXED
Target Milestone: --- → mozilla70
You need to log in
before you can comment on or make changes to this bug.
Description
•