2031153 - 8s of hang when switching folders on Gdrive (~3x slower than Chrome)

Status: ASSIGNED

(Core :: JavaScript Engine, task, P3)

Description

[Mayank Bansal]

I had a folder on GDrive with lots of images. I then moved one directory up and noticed a hang.
I then repeated the steps and captured a profile.

https://share.firefox.dev/4tLtBPa

Maybe something obvious to improve?

Comment 1

[Iain Ireland [:iain]]

It looks to me like we are spending most of our time in Array.join because we called toString on an array. The most interesting part of the profile is the time we spend in GetProperty under GetArrayElement, which implies that we aren't looking at a dense array. I suspect that part of this is just the website doing something inefficient.

It might be interesting to see an equivalent profile in Chrome. They have slightly better support for sparse arrays. I don't think we have any easy wins in that area, though.

Comment 2

[Mayank Bansal]

Here is another profile where i cut 350 photos from a folder and paste them into another
https://share.firefox.dev/4dLYDBA

Comment 3

[Mayank Bansal]

(In reply to Iain Ireland [:iain] from comment #1)

It looks to me like we are spending most of our time in Array.join because we called toString on an array. The most interesting part of the profile is the time we spend in GetProperty under GetArrayElement, which implies that we aren't looking at a dense array. I suspect that part of this is just the website doing something inefficient.

It might be interesting to see an equivalent profile in Chrome. They have slightly better support for sparse arrays. I don't think we have any easy wins in that area, though.

Firefox: https://share.firefox.dev/4tFLlv1 (8.5s)
Chrome: https://share.firefox.dev/3QlplqV (3.s)

Comment 4

[Iain Ireland [:iain]]

Yeah, looks like they're just faster on Array.join on sparse arrays (which makes sense, because they have a nicer data representation: see bug 1339265).

Here's a microbenchmark that reproduces the time we spend on GetArrayElement:

let arr = [];
for (var i = 0; i < 1000; i++) {
  arr[i * 4000] = 1;
}

function foo(arr) {
  return arr.join("");
}

let start = performance.now()
for (var i = 0; i < 5; i++) {
  foo(arr);
}
print(performance.now() - start);

There's also time in the profile spent in ValueToStringBuilder, which I can't immediately explain. V8 is probably also a bit faster there, but it's hard to tell because most of that logic is inlined into ArrayJoin.

Comment 5

[Mayank Bansal]

Attachment: WIP: Bug 2031153 - Walk sparse elements instead of every index in Array builtins. r?#spidermonkey-reviewers

Adds ForEachOwnIndexedProperty and CollectOwnIndexedKeysInRange, replacing the
hand-rolled shape scans in ArraySetLength, maybeDensifySparseElements and for-in
enumeration.

Array.prototype.join already skipped the trailing holes of an array with no
indexed properties (bug 1964988), but went back to a generic lookup for every
index as soon as the array had any. It now walks only the indexes that exist.

Bug 1939342's delete fast path is generalized to "remove every element at index

= N" and reused by sort and by splice's tail deletion, which ran the same
per-index loop.

Comment 6

[Mayank Bansal]

Attachment: Bug 2031153 - Part 1: Add helpers for walking an object's sparse elements. r?#spidermonkey-reviewers

ForEachOwnIndexedProperty and CollectOwnIndexedKeysInRange replace the
hand-rolled shape scans in ArraySetLength, maybeDensifySparseElements and for-in
enumeration, and SortIndexedKeys absorbs the sort those keys need.

The delete fast path is renamed to TryFastDeleteElementsAbove, since it removes
every element above an index and leaves .length to its caller.

No behavior change.

Comment 7

[Mayank Bansal]

Attachment: Bug 2031153 - Part 2: Reuse the sparse-element delete fast path in sort and splice. r?#spidermonkey-reviewers

Removing every element above an index is what Array.prototype.sort does when it
re-creates the holes that sorted to the end, and what splice does when it
deletes its tail. Both ran a per-index DeletePropertyOrThrow loop over the whole
range, so an array with sparse elements paid for every index in between.

Comment 8

[Mayank Bansal]

Attachment: Bug 2031153 - Part 3: Walk sparse elements in Array.prototype.join. r?#spidermonkey-reviewers

join already skipped the trailing holes of an array with no indexed properties
(bug 1964988), but went back to a generic lookup for every index as soon as the
array had any. It now walks only the indexes that exist.

Comment 9

[Mayank Bansal]

Attachment: WIP: Bug 2031153 - Part 4: Append a run of join separators in one step. r?#spidermonkey-reviewers

array_join walked every index of a hole run to append one separator each, so
joining an array that is mostly holes did work proportional to its length even
when the separator was empty and the run produced nothing at all.

The separator becomes a small type that knows how to append itself n times, so
the run is emitted in one call: nothing for an empty separator, one appendN for
a single Latin-1 character. Two-byte and multi-character separators still repeat
one at a time, since StringBuilder::appendN only takes a Latin1Char.

Comment 10

[Mayank Bansal]

the try run looks green: https://treeherder.mozilla.org/jobs?repo=try&revision=599b2373f4870777a2c34fc8d758509b8c42d269

Comment 11

[Mayank Bansal]

sp3 and js3 perfcompare: https://perf.compare/compare-results?baseRev=af0bbfff5716e41a229235041dcd570bf37ff80a&baseRepo=try&newRev=8bb08db2872bed81824653ca9f300a35afb31121&newRepo=try&framework=13&filter_significance=significant&filter_status=improvement%2Cregression
Seems neutral to me.

Comment 12

[Mayank Bansal]

These patches are created by Claude. I cannot defend the patch line-by-line. Therefore, per Moz AI policy, I cannot be the author.
So the reviewer would need to find an author for these patches (and a co-author by me).

Comment 13

[Mayank Bansal]

I did not test with Gdocs, but here are the results with a modified version of the microbenchamark that Iain posted in comment 4:

Nightly: https://share.firefox.dev/4cj2QuQ (11s)
Patched with 1000x loopcount: https://share.firefox.dev/4hPyZ0J (190ms)

Comment 14

[Mayank Bansal]

Attachment: Testcase from comment 4.html

Comment 15

[Mayank Bansal]

And these are the profiles on gdrive on image heavy folders (but not necessarily the one from comment 0) : https://share.firefox.dev/4fT6KvK, https://share.firefox.dev/4z5hcZR, https://share.firefox.dev/4wa9kn7

Comment 16

[Mayank Bansal]

What else shows up in the GDrive profiles?

Comment 17

[Jan de Mooij [:jandem]]

We discussed this a bit on Matrix. We should check the patches help on Google Drive because we still spend a lot of time under ArrayJoin looking up properties, so it's possible the fast path doesn't apply there for some reason.

Comment 18

[Mayank Bansal]

(In reply to Jan de Mooij [:jandem] from comment #17)

We discussed this a bit on Matrix. We should check the patches help on Google Drive because we still spend a lot of time under ArrayJoin looking up properties, so it's possible the fast path doesn't apply there for some reason.

In the Google Drive workload, the arrays being joined have holes in their dense elements. Consequently, the denseElementsArePacked() check fails, HasOnlyDenseAndSparseElements() returns false, and SpiderMonkey falls completely back to the unoptimized ArrayJoinKernel slow path

Comment 19

[Mayank Bansal]

Attachment: sparse array test.html

Nightly: All the three methods are slow
With current patches: Methods 1 and 3 are fast. Method 2 is slow. This is the reduced testcase for the GDrive profile.

Comment 20

[Mayank Bansal]

(In reply to Jan de Mooij [:jandem] from comment #17)

We discussed this a bit on Matrix. We should check the patches help on Google Drive because we still spend a lot of time under ArrayJoin looking up properties, so it's possible the fast path doesn't apply there for some reason.

Proposed change:

We will eliminate the denseElementsArePacked() guard. To preserve correctness without writing a complex interleaved loop or slowing down the common case, we will simply widen the sparse key collection to cover the entire array[0, length)and conditionally bail out only if a sparse key overlaps with the dense range

Modify ArrayJoinSparseKernel:
Reorder the logic to collect and sort sparse keys before executing the dense loop. Widen the search range from [initLength, length) to [0, length). If the smallest sorted sparse key is less than initLength, we safely bail out to the slow generic loop (which is an incredibly rare edge case). Otherwise, we proceed with the fast path exactly as before, since we are guaranteed that all dense holes are truly empty.

  RootedIdVector keys(cx);
  // CHANGE: collect from 0 instead of initLength
  switch (CollectOwnIndexedKeysInRange(
      obj, 0, uint32_t(length),
      [](<PropertyInfoWithKey prop>) { return prop.isDataProperty(); }, &keys)) {
    case IndexedKeysResult::Ok:
      break;
    case IndexedKeysResult::Unsupported:
      return true;
    case IndexedKeysResult::Failure:
      return false;
  }

  if (!SortIndexedKeys(cx, &keys)) {
    return false;
  }

  uint32_t initLength = ClampedDenseInitializedLength(obj, length);

  // NEW: If there is a sparse property hiding in the dense range, fall back
  // to the generic loop to ensure it isn't incorrectly treated as a hole.
  if (keys.length() > 0) {
    uint32_t firstSparse;
    MOZ_ALWAYS_TRUE(IdIsIndex(keys[0], &firstSparse));
    if (firstSparse < initLength) {
      return true; // Leaves numProcessed at 0, falling back to Step 7.
    }
  }

  // Now safely run the dense loop
  if (!ArrayJoinDenseElements(cx, sepOp, obj, initLength, length, sb,
                              numProcessed)) {
    return false;
  }
  if (*numProcessed != initLength) {
    return true;
  }

  // ... rest of the function remains the same

Jan, do these suggested changes from Antigravity loo OK?

Comment 21

[Mayank Bansal]

removing the needinfo. As usual, Gemini gives bad designs.

Comment 22

[Mayank Bansal]

Attachment: Bug 2031153 - Part 5: Walk sparse elements of an array whose dense elements have holes. r?#spidermonkey-reviewers

Adding a sparse element below the dense initialized length turns the dense
element there into a hole, so packed dense elements imply the dense and sparse
ranges are disjoint. The reverse does not hold: deleting a dense element marks
the elements non-packed without adding anything to the shape, and join then
gave up on an array whose ranges never overlapped.

Check for the overlap itself instead of requiring packed elements.

Comment 23

[Mayank Bansal]

Attachment: Bug 2031153 - Part 6: Resume Array.prototype.join's dense walk after an object element. r?#spidermonkey-reviewers

The dense walk stops at the first element it can't stringify without running
script, and everything after it went through the generic loop, which looks up
every index. That is much worse than it sounds for an array with holes:
GetArrayElement's dense fast path falls through on a hole, so each one costs a
full prototype chain lookup that the dense walk did for free.

Run the walk again once the generic loop has handled the element that stopped
it, re-checking the fast path guard first since stringifying can run script.

Comment 24

[Mayank Bansal]

Attachment: Bug 2031153 - Part 4: Append a run of join separators in one step. r?#spidermonkey-reviewers

array_join walked every index of a hole run to append one separator each, so
joining an array that is mostly holes did work proportional to its length even
when the separator was empty and the run produced nothing at all.

The separator becomes a small type that knows how to append itself n times, so
the run is emitted in one call: nothing for an empty separator, one appendN for
a single Latin-1 character. Two-byte and multi-character separators still repeat
one at a time, since StringBuilder::appendN only takes a Latin1Char, and they
keep checking for interrupts as they go; a run that no longer has anywhere to
check is checked once before it starts.

The run stopped at lengths below UINT32_MAX, so the one length an array can't
exceed missed it by one. Nothing needs the stricter bound: the run counts in a
uint32_t and an index never reaches UINT32_MAX. Checking the premise of the
skipped range in debug builds walked all of it, which is the work the run exists
to avoid, so check each end of it instead.

Comment 25

[Mayank Bansal]

Attachment: Bug 2031153 - Part 7: Sort an array by walking its sparse elements. r?#spidermonkey-reviewers

Sorting without a comparator reserved room for two Values per index and then
asked for every index, so an array holding a handful of elements at a large
length needed gigabytes and minutes rather than work proportional to what it
holds. Everything after the collection was already proportional to the element
count, and Part 2 made the trailing deletion so too.

Walk the sparse elements instead when the array has no other way to hold an
index, and size the sort buffer from what the walk finds. The dense and sparse
ranges are disjoint there, so appending one after the other keeps the elements
in index order, which sort has to be stable over.

Comment 26

[Mayank Bansal]

• SP3/JS3 perfcompare: https://perf.compare/compare-results?baseRev=1d1ff7e80efee61337eb23c8d64972e2c6a0cee2&baseRepo=try&newRev=a8c516639c9ce965bfa26427f3cc3c13a259dda9&newRepo=try&framework=13&filter_significance=significant&filter_status=improvement%2Cregression (Perf neutral)

GDrive STR:

• Patched : https://share.firefox.dev/3S09nnj (2.9s)
• Chrome: https://share.firefox.dev/4hmQfKB (3s)

testcase from comment4 (100x loopcount): https://share.firefox.dev/4bDG80j (85ms)
sparse array test (100x loopcount): https://share.firefox.dev/4q6Agmg (120ms-150ms)