1889685 - Reimplement TypedArraySort with a JIT trampoline

Status: RESOLVED FIXED

(Core :: JavaScript Engine, task, P3)

Description

[Jan de Mooij [:jandem]]

We can optimize %TypedArray%.prototype.sort now similar to the Array.prototype.sort changes in bug 1884360. The typed array version shows up in one of the Charts tests on Speedometer 3.

The self-hosted code is especially inefficient when sorting typed arrays of different types because the code becomes polymorphic.

Comment 1

[Jan de Mooij [:jandem]]

An initial patch for this improves Charts-observable-plot/Stacked by 6/Sync by about 2.8%.

https://treeherder.mozilla.org/perfherder/comparesubtest?originalProject=try&newProject=try&newRevision=ca805ef00505ebbd7722ae9a6e17982de947f361&originalSignature=4586009&newSignature=4586009&framework=13&application=firefox&originalRevision=e720ecdda3af3ad33c2b758402e31d20c789736c&page=1

Comment 2

[Jan de Mooij [:jandem]]

I got back to this and ran some micro-benchmarks. For the Int32Array micro-benchmark below I get:

normal:         567 => 464 ms
--no-ion:      2909 => 794 ms
--no-blinterp: 21.5 => 7.1 seconds

For a version that uses BigInt64Array (BigInt GC thing values are allocated for values read from the typed array):

normal:        1533 => 1138 ms
--no-ion:      4571 => 2159 ms
--no-blinterp: 28.2 => 10.7 seconds

The new code also doesn't have a perf cliff when sorting arrays of different types, for example sorting both an Int32Array and Int16Array now takes twice as long (as expected) instead of 3-4x or so (due to polymorphic ICs).

normal:        2331 => 910 ms
--no-ion:      6261 => 1570 ms
--no-blinterp: 43.5 => 14.2 seconds

function f() {
  var len = 100;
  var c = 0;
  var fun = (x, y) => {
    c++;
    if (i & 1) {
      return x - y;
    }
    return y - x;
  };
  var arr = new Int32Array(len);
  for (var j = 0; j < len; j++) {
    arr[j] = (j / 3)|0;
  }  
  var t = new Date;
  for (var i = 0; i < 100_000; i++) {
    arr.sort(fun);
  }
  print(new Date - t);
  print(c);
  return arr;
}
f();

Comment 3

[Jan de Mooij [:jandem]]

Attachment: Bug 1889685 part 1 - Move parts of array sorting code to Sorting.h/Sorting-inl.h. r?iain!

This lets us reuse code for typed array sorting.

Comment 4

[Jan de Mooij [:jandem]]

Attachment: Bug 1889685 part 2 - Port TypedArray sort/toSorted to C++ with a JIT trampoline. r?iain!,anba!

The implementation is very similar to Array.prototype.sort and uses a lot of the
same code.

This version is a lot faster than the self-hosted code when sorting typed arrays
with a JS comparator function, because we no longer have to warm up self-hosted code.
This improves one of the Charts tests in Speedometer 3.

Comment 5

[Jan de Mooij [:jandem]]

Attachment: Bug 1889685 part 3 - Remove empty builtin/Sorting.js file. r?iain!

Comment 6

[Worcester12345]

"PERF" keyword?

Comment 7

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/f8228eda6525
part 1 - Move parts of array sorting code to Sorting.h/Sorting-inl.h. r=iain
https://hg.mozilla.org/integration/autoland/rev/a5fbfba95f9a
part 2 - Port TypedArray sort/toSorted to C++ with a JIT trampoline. r=iain,anba
https://hg.mozilla.org/integration/autoland/rev/70dea500e928
part 3 - Remove empty builtin/Sorting.js file. r=iain

Comment 8

[Cristian Tuns]

https://hg.mozilla.org/mozilla-central/rev/f8228eda6525
https://hg.mozilla.org/mozilla-central/rev/a5fbfba95f9a
https://hg.mozilla.org/mozilla-central/rev/70dea500e928