Closed Bug 610583 Opened 9 years ago Closed 9 years ago

Inlining js_Array_dense_setelem_hole seems to slow down peacekeeper SHA1 testcase

Categories

(Core :: JavaScript Engine, defect, P1)

defect

Tracking

()

RESOLVED FIXED
mozilla2.0b8
Tracking Status
blocking2.0 --- -

People

(Reporter: bzbarsky, Assigned: bzbarsky)

References

Details

(Keywords: regression, Whiteboard: fixed-in-tracemonkey)

Attachments

(1 file, 1 obsolete file)

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...
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
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.  :(
blocking2.0: --- → ?
Let me try comment 1!
Attachment #489107 - Flags: review?(brendan)
Assignee: general → bzbarsky
Priority: -- → P1
Whiteboard: [need review]
Attachment #489107 - Flags: review+
Whiteboard: [need review]
Attachment #489107 - Flags: review?(brendan) → approval2.0?
Whiteboard: [need approval]
(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
How would one guard do the trick here?  What would it be guarding on?  And how would it not fail in this testcase?
(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
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?
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?
(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
We shouldn't need to setOwnShape, since going from not-INDEXED to INDEXED involves a property addition, hence a shape change.
(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
OK, so I filed bug 610697 and bug 610698 on the two issues in comment 2.
Depends on: 610697, 610698
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?
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
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.
(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
Attachment #489107 - Attachment is obsolete: true
Attachment #489107 - Flags: approval2.0?
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.
Attachment #489385 - Flags: review?(brendan)
Attachment #489385 - Flags: approval2.0?
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
Attachment #489385 - Flags: review?(brendan) → review+
This should go into b8.

/be
Status: NEW → ASSIGNED
OS: Mac OS X → All
Hardware: x86 → All
Fixed up the comments, and pushed http://hg.mozilla.org/tracemonkey/rev/2fd60328c2b0
Flags: in-testsuite?
OS: All → Mac OS X
Hardware: All → x86
Whiteboard: [need approval] → fixed-in-tracemonkey
OS: Mac OS X → All
Hardware: x86 → All
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
http://hg.mozilla.org/mozilla-central/rev/2fd60328c2b0
Status: ASSIGNED → RESOLVED
Closed: 9 years ago
Resolution: --- → FIXED
blocking2.0: ? → -
Attachment #489385 - Flags: approval2.0? → approval2.0+
Target Milestone: --- → mozilla2.0b8
You need to log in before you can comment on or make changes to this bug.