Open
Bug 1384900
Opened 7 years ago
Updated 1 year ago
Array.prototype.sort is slow on very sparse arrays
Categories
(Core :: JavaScript: Standard Library, defect, P3)
Core
JavaScript: Standard Library
Tracking
()
People
(Reporter: anba, Unassigned)
References
(Blocks 1 open bug)
Details
(Keywords: perf)
bug 1368978 adds a new helper function to delete element ranges more quickly. With some additional changes, we should be apply to make this test case much faster: var array = new Array(2**25); var t = dateNow(); array.sort(); print(dateNow() - t); This is mostly an issue for the native sort() implementation: Needs 9500ms for me with the native sort implementation, but only 300ms when the self-hosted sort implementation is called.
Updated•7 years ago
|
Reporter | ||
Updated•5 years ago
|
Assignee: andrebargull → nobody
Status: ASSIGNED → NEW
Updated•2 years ago
|
Performance Impact: --- → P3
Whiteboard: [qf:p3]
Updated•2 years ago
|
Severity: normal → S3
Comment 1•1 year ago
|
||
Found this while searching, is this still true? The followings don't really have a significant difference on my Surface Pro 7:
// native sort
var array = new Array(2**25);
var t = Date.now();
array.sort();
Date.now() - t // around 1500
// self hosted
var array = new Array(2**25);
var t = Date.now();
array.sort((x, y) => x - y);
Date.now() - t // around 1500 too
Reporter | ||
Comment 2•1 year ago
•
|
||
The comparator (x, y) => x - y
also uses the native implementation. Try this version instead:
var array = new Array(2**25);
var t = performance.now();
array.sort((x, y) => { let r = x-y; return r; });
console.log(performance.now() - t);
(The byte code for (x, y) => x - y
is pattern matched to call the native implementation: https://searchfox.org/mozilla-central/rev/028c68d5f32df54bca4cf96376f79e48dfafdf08/js/src/builtin/Array.cpp#1818-1871.)
Comment 3•1 year ago
|
||
Thanks, the difference is extreme with multiple magnitude, it's 40 vs 1500!
You need to log in
before you can comment on or make changes to this bug.
Description
•