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)

defect

Tracking

()

Performance Impact low
Tracking Status
firefox57 --- affected

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.
Priority: -- → P3
Whiteboard: [qf:p3]
Keywords: perf
Assignee: andrebargull → nobody
Status: ASSIGNED → NEW
Performance Impact: --- → P3
Whiteboard: [qf:p3]
Severity: normal → S3

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

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.)

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.