610583 - Inlining js_Array_dense_setelem_hole seems to slow down peacekeeper SHA1 testcase

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect, P1)

Description

[Boris Zbarsky [:bzbarsky]]

The patch for bug 607242 makes the testcase in bug 609212 about 4x slower (2800ms instead of 600ms).

In particular, this added line is causing all the slowdown:

 CHECK_STATUS_A(guardPrototypeHasNoIndexedProperties(obj, obj_ins, mismatchExit));

as a result we have way more aborts (though they all seem to be about lacking compatible inner trees) and lot and lots more trace enters/exits.  If I comment that one line out, things are fine.

It looks like we're getting a lot (hundreds of thousands, over a partial run of the testcase) of setelem mismatch exits when actually running...

Comment 1

[David Anderson [:dvander] - inactive, e-mail if emergency]

guardPrototypeHasNoIndexedProperties looks fairly old - it generates:

  obj = obj.prototype
  guard obj != null
  guard obj.shape == <shape>
  obj = obj.prototype
  guard obj != null
  guard obj.shape == <shape>
  guard obj.prototype == null

If it turns out these shape guards are failing we can change that function to do this instead:

  bake in Array.prototype
  guard that Array.prototype.flags doesn't have INDEXED
  guard that Array.prototype.prototype is Object.prototype
  guard that Object.prototype.flags doesn't have INDEXED

Comment 2

[Boris Zbarsky [:bzbarsky]]

So after we compile that guard, I see the following shape changes:

1)  For Object.prototype, via js_InitNumberClass calling
    js_DefineNativeProperty, which calls js_PurgeScopeChain on
    Number.prototype, which calls PurgeProtoChain, which does shadowing shape
    changes.

2)  For Array.prototype, via js::TraceRecorder::record_JSOP_CALLPROP caling
    test_property_cache, which calls PropertyCache::fill, which calls brand().
    This happens when the testcase calls array_push.

It's really unfortunate that these things end up changing shapes on the proto chain of all arrays, but the upshot is that guardPrototypeHasNoIndexedProperties is really fragile.  :(  It didn't use to be an issue, since we only used it when reading a hole and reading out of bounds on arrays, which are both somewhat rare to have early in a script. But writing on top of a hole is very common early on, I'd think: it happens any time you first put stuff in an array.  :(

Comment 3

[Boris Zbarsky [:bzbarsky]]

Let me try comment 1!

Comment 4

[Boris Zbarsky [:bzbarsky]]

Attachment: Guarding on shapes to ensure we have no indexed props on our proto chain is brittle and unnecessary.

Comment 5

[Brendan Eich [:brendan]]

(In reply to comment #4)
> Created attachment 489107 [details] [diff] [review]
> Guarding on shapes to ensure we have no indexed props on our proto chain is
> brittle and unnecessary.

Two guard for what could be one seems strictly worse, on the other paw.

The brittleness in real-world JS is not an issue. The brittleness due to our C++ code making builtin methods' parent the class proto is a bug. If we fix that then we can avoid twice as many guards. That seems to me the bug to fix here.

/be

Comment 6

[Boris Zbarsky [:bzbarsky]]

How would one guard do the trick here?  What would it be guarding on?  And how would it not fail in this testcase?

Comment 7

[Brendan Eich [:brendan]]

(In reply to comment #6)
> How would one guard do the trick here?

The comparison is one guard instead of two, not one guard for the entire proto chain -- one guard per proto level instead of the two guards per proto level in the patch.

This handles the proto-setting case, which is non-standard and fairly freakish testsuite fodder (not done in real-world JS), because you can't change an object's proto without reshaping it, and initial object shape depends on proto identity.

For the indexed case, which is completely freakish testsuite fodder (not done in real-world JS), we just need JSObject::updateFlags, in the case of an indexed property, to call setOwnShape in addition to calling setIndexed.

/be

Comment 8

[Boris Zbarsky [:bzbarsky]]

So what are you proposing to guard on, exactly?  Right now we basically guard that the proto exists (or not) and if it exists we guard that it has no indexed props.  What's the proposed guard on?

Comment 9

[Boris Zbarsky [:bzbarsky]]

I suppose we could have one guard per proto, just guarding on the indexed flag, if we also had explicit branches on trace to check for non-null proto.  It's the same number of branch instructions, same number of side exits.... more complicated jstracer.cpp code.  In what way is it better?

Comment 10

[Brendan Eich [:brendan]]

(In reply to comment #8)
> So what are you proposing to guard on, exactly?  Right now we basically guard
> that the proto exists (or not) and if it exists we guard that it has no indexed
> props.  What's the proposed guard on?

Shape. See comment 4's "Guarding on shapes ..." and my rebuttal :-/.

You guard on the shape of a proto to protect both the lack of INDEXED (at recording time; with the proposed fix to setOwnShape when updateFlags calls setIndexed), *and* to guard on the proto-identity (not just non-nullness).

You still need to guard each proto's shape, since changing Object.prototype's proto member later will reshape only Object.prototype, not the myriad delegating objects.

/be

Comment 11

[Boris Zbarsky [:bzbarsky]]

We shouldn't need to setOwnShape, since going from not-INDEXED to INDEXED involves a property addition, hence a shape change.

Comment 12

[Brendan Eich [:brendan]]

(In reply to comment #11)
> We shouldn't need to setOwnShape, since going from not-INDEXED to INDEXED
> involves a property addition, hence a shape change.

Great -- good point.

On the lazy branding causes a branch exit, we should probably pre-brand standard class prototypes to cover al their built-in methods' identities with their shape.

/be

Comment 13

[Boris Zbarsky [:bzbarsky]]

OK, so I filed bug 610697 and bug 610698 on the two issues in comment 2.

Comment 14

[Boris Zbarsky [:bzbarsky]]

I just tested brendan's suggestion: made the indexed guard use branchExit instead of mismatchExit, and changed guardPrototypeHasNoIndexedProperties to use a single shape guard per proto instead of the null and INDEXED guards.

The resulting runtime for the testcase is about 630ms (it was 640ms with just the change to use branchExit instead of mismatchExit and not changing the guards).

The runtime for the attached patch is 600ms.  The difference is that it doesn't have to deal with multiple branches in the trace tree due to bug 610697 and bug 610698.

For reference, v8 shell is at 680ms.

So I would propose that we use the attached patch for now, then switch to shape guards once bug 610697 and bug 610698 are fixed (and file a followup to track that).  Brendan, thoughts?

Comment 15

[Brendan Eich [:brendan]]

Counterproposal, fewer hops along the path toward the desired target: I fix bug 610697 adn bug 610698 today (they are easy) and we fix this bug with shape guards.

We have had other standard-proto reshaping issues. They tend to cause more traces but not always with bz-like good analysis. We need to fix those bugs and see how the tracer does on popular benchmarks.

More by lunchtime, in the blocking bugs.

/be

Comment 16

[Boris Zbarsky [:bzbarsky]]

Counterproposal accepted; will remeasure once we have patches in the dependent bugs.

I do agree that the shape-guard approach looks nice if it works; it gets us down to two shape guards and one load for the entire guardPrototypeHasNoIndexedProperties thing.

Comment 17

[Brendan Eich [:brendan]]

(In reply to comment #16)
> Counterproposal accepted; will remeasure once we have patches in the dependent
> bugs.

Those patches have landed on tm now.

/be

Comment 18

[Boris Zbarsky [:bzbarsky]]

Attachment: When guarding on no indexed properties on our proto chain, use a branch exit, and reduce the number of guards involved.

Comment 19

[Boris Zbarsky [:bzbarsky]]

Comment on attachment 489385 [details] [diff] [review]
When guarding on no indexed properties on our proto chain, use a branch exit, and reduce the number of guards involved.

Per discussion.

Comment 20

[Brendan Eich [:brendan]]

Comment on attachment 489385 [details] [diff] [review]
When guarding on no indexed properties on our proto chain, use a branch exit, and reduce the number of guards involved.

>+    JS_ASSERT(obj->isDenseArray());
>+
>+    /*
>+     * Changing __proto__ on a dense array makes it slow, so we can
>+     * just bake in the current prototype as the first prototype to
>+     * test.  This avoids an extra load when running the trace.
..12345678901234567890123456789012345678901234567890123456789012345678901234567890

Nit: rewrap to column 79 maybe? Also we use French spacing (or try to -- uber-nit, for sure).

Want to comment how changing __proto__ on any native object regenerates its shape, and note that adding indexed properties changes shape too? Maybe just a few words condensing my poor attempts in this bug.

Looks great otherwise, r=me with these.

/be

Comment 21

[Brendan Eich [:brendan]]

This should go into b8.

/be

Comment 22

[Boris Zbarsky [:bzbarsky]]

Fixed up the comments, and pushed http://hg.mozilla.org/tracemonkey/rev/2fd60328c2b0

Comment 23

[Nicholas Nethercote [inactive]]

This helped Kraken a bit:

---------------------------------------------------------------
| millions of instructions executed                           |
| total                        | on-trace (may overestimate)  |
---------------------------------------------------------------
|  4433.097  4433.097 (------) |  4142.906  4142.906 (------) | ai-astar
|  2934.580  2910.514 (1.008x) |  1391.178  1365.531 (1.019x) | audio-beat-det
|  1307.400  1298.413 (1.007x) |  1140.652  1131.745 (1.008x) | audio-dft
|  2683.524  2657.573 (1.010x) |  1347.583  1321.941 (1.019x) | audio-fft
|  2665.113  2632.229 (1.012x) |  1856.255  1823.421 (1.018x) | audio-oscillat
|  6950.825  6950.748 (------) |  4784.012  4784.010 (------) | imaging-gaussi
|  3315.591  3315.106 (------) |   748.440   748.428 (------) | imaging-darkro
|  5995.455  5995.367 (------) |  3836.520  3836.518 (------) | imaging-desatu
|   681.309   681.309 (------) |    10.073    10.073 (------) | json-parse-fin
|   497.739   497.739 (------) |     5.954     5.954 (------) | json-stringify
|  1272.720  1272.500 (------) |   748.719   748.688 (------) | stanford-crypt
|   710.550   708.678 (1.003x) |   362.991   362.883 (------) | stanford-crypt
|  1152.121  1151.339 (1.001x) |   585.029   585.006 (------) | stanford-crypt
|   503.629   502.360 (1.003x) |   199.421   199.389 (------) | stanford-crypt
-------
| 35103.659 35006.978 (1.003x) | 21159.740 21066.498 (1.004x) | all

Comment 24

[Robert Sayre]

http://hg.mozilla.org/mozilla-central/rev/2fd60328c2b0