1932138 - JS demo (https://www.fxhash.xyz/generative/slug/box-runner) is slower in Nightly (spends a lot of time in js::PropMapTable::addToCache

Status: NEW

(Core :: JavaScript Engine, task, P3)

Description

[Mayank Bansal]

Go to https://www.fxhash.xyz/generative/slug/box-runner
Click run

Profile: https://share.firefox.dev/4fPWRx0

Comment 1

[Iain Ireland [:iain]]

We're spending a lot of time in GetSparseElementHelper, from code that looks like this:

this.reorder = function(arr3d) {
  let arrtemp = [];
  let x, y, z, k;
  for (let i = 0; i < arr3d.length; i += 1) {
    x = arr3d[i][0];
    y = arr3d[i][1];
    z = arr3d[i][2];
    if (this.ooCanvas.view == 'A') {
      k = (z * this.ooCanvas.w * this.ooCanvas.h) + (y * this.ooCanvas.w) + x
    } else {
      k = (z * this.ooCanvas.w * this.ooCanvas.h) + (y * this.ooCanvas.w) + this.ooCanvas.w - x
    }
    arrtemp[k] = arr3d[i]
  }
  let arr3dout = [];
  let c = 0;
  for (let i = 0; i < arrtemp.length; i += 1) {
    if (arrtemp[i]) {
      arr3dout[c] = arrtemp[i];
      c += 1
    }
  }
  arrtemp = [];
  return arr3dout
};

I think it may be creating a huge array and (at least sometimes) starting to fill it from high indices, which makes us go into sparse elements mode. Here's a microbenchmark that exhibits the issue:

let N = 1001; // Any number > 1000

function foo() {
  var arr = [];
  for (var i = 0; i < N; i++) {
    arr[N-i-1] = 0;
  }
  return arr;
}

for (var i = 0; i < 2000; i++) {
  foo()
}

MIN_SPARSE_INDEX is 1000, so if we start filling an array at index 1000 or higher, then we will use sparse elements until it's at least 1/8th full, which is quite slow.

We've bumped MIN_SPARSE_INDEX in the past, from 256 to 512 (bug 832578), and later from 512 to 1000 (bug 835102). We could consider bumping it again. Digging into V8's code, it looks like their heuristic is a maximum length of 5000 without checking the density (500 for tenured objects), and a maximal gap of 1024.

Comment 2

[Iain Ireland [:iain]]

Debugging the original code on the website, I misdiagnosed this slightly. The problem is that arrtemp is genuinely an extremely sparse array. For example, I'm currently looking at an iteration with 652 defined values in an array of length 769926.

So bumping MAX_SPARSE_INDEX isn't going to do anything here. We could try to make GetSparseElementHelper faster, but I think we'd want more justification than this demo. The root of the problem here is that we represent sparse indices as if they are named properties. I think other engines have a mode where they can use the elements array as a hashtable, which would be faster but also a lot of work to implement for a relatively unimportant pattern.

Comment 3

[Mayank Bansal]

firefox: https://share.firefox.dev/3HwYjsc (29s)
ChromE: https://share.firefox.dev/3Hh6cSw (24s)