2039524 - Testcase searching for integers in arrays is 17x slower in Firefox

Status: RESOLVED FIXED

(Core :: JavaScript Engine, task)

Description

[Mayank Bansal]

Attachment: Packed array.html

I gave the code of bug 2012239 to gemini and asked it to create a simplifed version. After some iterations, i got this testcase.

Open testcasea and click run

Chrome: https://share.firefox.dev/438J28w (5s)
Firefox: https://share.firefox.dev/4eLKTr0 (85s)

Comment 1

[Jan de Mooij [:jandem]]

We're spending all of our time under array_includes searching for a dense element, and a lot of time in Value::toNumber.

We can't use our SIMD code path because for numbers we have to check for both int32 values and the int32 value stored as double. If I change this code to enable the SIMD code for int32 values too we're 5-6x faster and a bit less than 2x of V8, but that's not a valid optimization. For this to work we'd need to know the elements are all Int32Value; this is an optimization we're considering implementing at some point.

As an alternative, I wonder if we could change this loop so that if val is an int32, we pre-compute the matching DoubleValue and then compare each element against both? That avoids floating point operations for each element. Need to watch out for 0/-0 though...

Comment 2

[Tom S. (please needinfo tschuster)]

I will give this a shot.

Comment 3

[Tom S. (please needinfo tschuster)]

Attachment: Bug 2039524 - Optimize Array.prototype.{indexOf, lastIndexOf, includes} for number searches. r?jandem

Comment 4

[Jan de Mooij [:jandem]]

I forgot to post the shell version...

function executeIntegerStress() {
  const matrixSize = parseInt("600");
  const linearBuffer = [];
  for (let row = 0; row < matrixSize; row++) {
    for (let col = 0; col < matrixSize; col++) {
      const numericTarget = (row * matrixSize) + col;
      let targetExists = false;
      if (linearBuffer.includes(numericTarget)) {
        targetExists = true;
      }
      if (!targetExists) {
        linearBuffer.push(numericTarget);
      }
    }
  }
}
executeIntegerStress();

Comment 5

[Pulsebot]

Pushed by [e-mail]:
https://github.com/mozilla-firefox/firefox/commit/f92d2f9fbc79
https://hg.mozilla.org/integration/autoland/rev/16928d21fc7b
Optimize Array.prototype.{indexOf, lastIndexOf, includes} for number searches. r=jandem

Comment 6

[Serban Stanca [:SerbanS]]

https://hg.mozilla.org/mozilla-central/rev/16928d21fc7b

Comment 7

[Mayank Bansal]

Nightly: https://share.firefox.dev/4diickm (39s)
So we improved 85s-->39s, which is 2.1x faster.

I will open a new bug for the remaining slowness.