1951338 - Demo at https://www.elmismopancho.cl/demos/github/everythingformula/index.html is 1.2x slower in Nightly

Status: RESOLVED FIXED

(Core :: JavaScript Engine, task, P3)

Description

[Mayank Bansal]

Attachment: sample number

Go to https://www.elmismopancho.cl/demos/github/everythingformula/index.html
Enter the sample number and press enter.

Nightly: https://share.firefox.dev/41C7yix (5m10s)
Chrome: https://share.firefox.dev/3EXL4jg (4m)

Comment 1

[Iain Ireland [:iain]]

I see very little GC time in this profile.

We spend ~25% of our time in t.times, whereas V8 spends ~1.5%. Most of that time is in AddOrUpdateSparseElementHelper and SetElementMegamorphic. I think this is a case where our existing sparse element code is not good enough.

Here's the code for t.times. The minification doesn't make it particularly easy to figure out what's going on:

  t.mul = t.times = function(n) {
    var t, s = this,
      h = s.constructor,
      f = s.c,
      e = (n = new h(n))
      .c,
      o = f.length,
      i = e.length,
      u = s.e,
      r = n.e;
    if (n.s = s.s == n.s ? 1 : -1, !f[0] || !e[0]) return new h(n.s * 0);
    for (n.e = u + r, o < i && (t = f, f = e, e = t, r = o, o = i, i = r), t = new Array(r = o +
      i); r--; t[r] = 0);
    for (u = i; u--;) {
      for (i = 0, r = o + u; r > u;) i = t[r] + e[u] * f[r - u - 1] + i, t[r--] = i % 10, i = i / 10 | 0;
      t[r] = (t[r] + i) % 10
    }
    for (i && ++n.e, t[0] || t.shift(), u = t.length; !t[--u]; t.pop());
    return n.c = t, n
  };

Comment 2

[Iain Ireland [:iain]]

Ah, the non-minified version is here: https://github.com/MikeMcl/big.js/blob/master/big.js

I think the culprit is this line of code:

 for (c = new Array(j = a + b); j--;) c[j] = 0;

This initializes a new array and then iterates through it in reverse order, setting its elements to 0. Pretty quickly, the creation of an array with only one element exceeds our thresholds for dense storage: if the array length is >1000 and less than 1/8 of indices are filled in, then we go sparse. By starting at the highest element, we hit that case as quickly as possible. It's possible that we redensify as we fill things in, but the damage is already done. (I don't see any redensification in the profile, so maybe it doesn't kick in for some reason).

As the input gets longer, the effect of this problem gets worse, so a 26K digit input is slow.

I looked a little bit at the V8 sparse array heuristics in this comment. Revisiting that, one thing I notice is that they only enforce those heuristics when adding elements to an existing array. It turns out that V8 imposes basically no restrictions on how large an array they are willing to allocate for new Array(n). They have a limit around 16K, but it turns out that's just the limit for how large an array they are willing to allocate from jitcode. Testing in rr, it looks like they're willing to immediately allocate a dense array of any length up to the maximum length of a dense array (kMaxFastArrayLength, which is 0x2000000, or roughly 33M elements, pretty close to our MAX_DENSE_ELEMENTS_COUNT).

In comparison, our limit for eager allocation is 2046, which AFAICT hasn't been changed in 11 years. There's a lot of room between 2k and 33M for us to relax this restriction, which might help this code.

Comment 3

[Iain Ireland [:iain]]

It's slightly more complicated than just bumping EagerAllocationMaxLength. The problem is that new Array(N) creates an array with length and capacity equal to N, but initLength of 0: we've allocated enough space for N elements, but they are not yet initialized. We could initialize them eagerly, but then we'd have to set the non-packed flag on the elements, which would make things worse in the common case where the array is initialized from index 0 to index N.

To make this work, I think we'd have to modify the existing StoreDenseElementHole IC to handle the case where initLength < index < capacity by a) looping from initLength to index and writing the magic hole value, b) updating initLength, and c) setting the non-packed flag. As I write this, I'm realizing that it sounds familiar: we already have bug 1804104 to track doing that.

Comment 4

[Mayank Bansal]

With the try build from here, this is the profile : https://share.firefox.dev/43I6yL1 (3m47s)
So a 27% improvement (5m10s -> 3m47s)

Comment 5

[Iain Ireland [:iain]]

Attachment: Bug 1951338: Bump EagerAllocationMaxLength r=jandem

This seemed like a reasonable place to draw the line. Combined with the previous patch, code like this:

let arr = new Array(50000);
for (let i = arr.length - 1; i >= 0; i--) {
  arr[i] = 0;
}

is 9-10x faster.

Comment 6

[Iain Ireland [:iain]]

Attachment: Bug 1951338: Add fast path for packed elements in willBeSparseElements r=jandem

I originally intended to reset the NON_PACKED flag in this code if there were no holes, but after a closer look, I realized that we exit early from the loop once we've seen enough non-holes, but resetting the flag would require us to examine every element.

Comment 7

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/9fee213591f6
Bump EagerAllocationMaxLength r=jandem
https://hg.mozilla.org/integration/autoland/rev/28d7ac36c32b
Add fast path for packed elements in willBeSparseElements r=jandem

Comment 8

[Serban Stanca [:SerbanS]]

https://hg.mozilla.org/mozilla-central/rev/9fee213591f6
https://hg.mozilla.org/mozilla-central/rev/28d7ac36c32b

Comment 9

[Mayank Bansal]

Either this bug or Bug 1804104 lead to some improvements:

SP3:
Windows: 2.8% on SP3-perf-Dashboard-Total , which was driven by 7.2% improvement on SP3-perf-Dashboard-SelectingPoints-total
Android: 4.8% on Android SP3-perf-Dashboard-SelectingPoints-total

Sunspider
54% on Sunspider-access-nsieve (Probably due to bug 1804104)

Jetstream2
7.6% on Segmentation
3% on Jetstream2-Lebab-wtb

Comment 10

[Markus Stange [:mstange]]

It was bug 1804104.

Perf-Dashboard profiles before/after:
Before: https://share.firefox.dev/4c1XCCr (SetElem ICs in findOptimalSegmentationInternal and in costBetween)
After: https://share.firefox.dev/3RjJo6g (no SetElem ICs)

Comment 11

[Acasandrei Beatrice (needinfo me)]

(In reply to Pulsebot from comment #7)

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/9fee213591f6
Bump EagerAllocationMaxLength r=jandem
https://hg.mozilla.org/integration/autoland/rev/28d7ac36c32b
Add fast path for packed elements in willBeSparseElements r=jandem

Hi! Do you think this changeset or Bug 1804104 (changeset dbeb07f4be696ee197f2c651238f02f5484376e5) could have caused the performance regression reported below ?
Thanks!

Perfherder has detected a mozperftest performance change from push 1e8104bb5f08f6dd47bd9f323a971a58e3db8ee9.

Regressions:

Ratio	Test	Platform	Options	Absolute values (old vs new)
8%	browser_ml_smart_tab_perf.js SMART-TAB-EMBEDDING-total-memory-usage	linux1804-64-shippable		221.73 -> 239.17
7%	browser_ml_smart_tab_perf.js SMART-TAB-EMBEDDING-total-memory-usage	linux1804-64-shippable		221.79 -> 236.54

As author of one of the patches included in that push, we need your help to address this regression.
Details of the alert can be found in the alert summary, including links to graphs and comparisons for each of the affected tests. Please follow our guide to handling regression bugs and let us know your plans within 3 business days, or the patch(es) may be backed out in accordance with our regression policy.

If you need the profiling jobs you can trigger them yourself from treeherder job view or ask a sheriff to do that for you.

You can run these tests on try with ./mach try perf --alert 44431

For more information on performance sheriffing please see our FAQ.

Comment 12

[Ted Campbell [:tcampbell]]

I pushed a try run to revert the EagerAllocationMaxLength changes and do see an improvement in numbers: https://perf.compare/compare-results?baseRev=a01b30eb1058cc8c6d4e27a0e2f393bcee8f4c72&baseRepo=try&newRev=7194c012ea145c3832cd7a078d9b56406858b576&newRepo=try&framework=15&search=mem

The benchmark is multi-modal, but this patch does seem to change the distribution.

Comment 13

[Iain Ireland [:iain]]

The "Bump EagerAllocationMaxLength" patch could increase memory usage in cases where code allocates an array using new Array(size), but doesn't touch all the elements. By eagerly allocating the backing storage, we avoid taking the sparse elements path, which is generally pretty bad for performance. V8 will densely allocate any array up to 33M elements. We previously only allocated up to 2K; this patch moves us to 64K, which is still conservative compared to V8.

Given the significant improvements we've seen from these patches, we should just accept the memory increase. In practice, I expect most code that explicitly allocates large arrays intends to use them in a way that will benefit from remaining dense.