868042 - Dictionary-mode shapes hurt Octane-gameboy

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Jan de Mooij [:jandem]]

Octane-gameboy creates a GameBoyCore object with hundreds of properties (at least 470). This exceeds PropertyTree::MAX_HEIGHT and the object/shape goes into dictionary mode.

If I change PropertyTree::MAX_HEIGHT from 128 to 512 our score improves from 18000 to 31000 points, almost 2x faster.

Comment 1

[Kannan Vijayan [:djvj]]

Re-posting my thoughts from IRC.

If we can devise some heuristics other than number-of-properties that indicate if an object is being used as a struct instead of a hashtable, we can selectively extend MAX_HEIGHT in those situations.

The first thing that came to mind was storing a bit indicating whether or not every property name in ancestor shapes (including the shape containing the bit) have "method-like names" (e.g. matching regex [a-zA-Z_][a-zA-Z0-9]+ or the full regex for JS identifiers to be more complete).

When extending the shape, computing this bit is simple.  If the ancestor is marked as having a non-methodlike property in its chain, then the bit is inherited directly.  Otherwise, the new property name is checked and the bit set based on that.

Looking at gbemu.js, this seems to be the case for GameBoyCore.

Comment 2

[Brian Hackett [Laid off!]]

Another option is to look for element accesses rather than normal property accesses, similar to how we handle despecializing type information for hashtables.

Comment 3

[Kannan Vijayan [:djvj]]

An issue with looking at the access mode (GETELEM vs GETPROP) is that it would break in case of procedural interface generation.  That tends to be a common idiom in js, including in many popular libraries which provide class-construction helpers where you pass in an object with methods to define and they get copied into the constructor prototype.

Comment 4

[Sean Stangl [:sstangl]]

Related to https://bugzilla.mozilla.org/show_bug.cgi?id=831518

Comment 5

[Jan de Mooij [:jandem]]

Attachment: WIP

Bumping the limit from 128 to 512 regresses unpack-code (3 ms). It looks like it uses an object as hashtable to store identifiers, so there's no good way to prevent this based on the property names.

This patch sets a bit on the shape when SETELEM is used. If the bit is not set, we allow a max height of 512.

Comment 6

[Jan de Mooij [:jandem]]

Attachment: Patch

Brian asking you to review since you did the ObjShrink work. Let me know if you can think of a better way to do this.

Comment 7

[Brian Hackett [Laid off!]]

Comment on attachment 746313 [details] [diff] [review]
Patch

Review of attachment 746313 [details] [diff] [review]:
-----------------------------------------------------------------

I think the flag would be better off as a BaseShape::Flag.  These are bits about the object that are automatically preserved by changes made to its shape, so the jspropertytree.cpp change isn't needed.  Doing things this way has a couple problems that hurt robustness:

- Objects that share the initial part of the shape hierarchy with one that is used as a hashmap may still end up with the lower limit, even if they've never seen elements accesses.

- Since the bit is only propagated to children when expanding the property tree, an object which both is used as a hashmap and reuses part of the property tree might not end up with the bit set.

Both of these stem from the fact that the shape is being updated directly, which goes against the general abstraction that shapes are immutable things.  Using the base shape flags for this purpose is how this problem has been handled in the past (e.g. marking objects with uncacheable protos).

Comment 8

[Jan de Mooij [:jandem]]

Attachment: Patch v2

I wasn't sure about adding the bit to Shape or BaseShape, thanks for the explanation. I followed setUncacheableProto, but I don't know if I should use GENERATE_SHAPE or GENERATE_NONE. Does it matter here?

Comment 9

[Brian Hackett [Laid off!]]

Comment on attachment 746353 [details] [diff] [review]
Patch v2

Review of attachment 746353 [details] [diff] [review]:
-----------------------------------------------------------------

GENERATE_NONE would be fine, that argument just controls whether an object that is in dictionary mode needs to be reshaped after the change.  Otherwise the last base shape (which is owned by the object) will be modified directly.

::: js/src/jsinterpinlines.h
@@ +911,5 @@
>          }
>      }
>  
> +    if (obj->isNative())
> +        obj->setHadElementsAccess(cx);

The return value needs to be checked here.

Comment 10

[Jan de Mooij [:jandem]]

Pushed with comment addressed:

https://hg.mozilla.org/integration/mozilla-inbound/rev/0ea128318cc8

Linux64 Try: https://tbpl.mozilla.org/?tree=Try&rev=42d9a0cd75b2

Comment 12

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/0ea128318cc8