Octane/gbemu regresses by 20% if we don't GC at exactly the right time

• Component: JavaScriptCore
• Status: NEW ---

[Filip Pizlo]

One way to trigger this is to comment out the try/catch block in fromTypedArray. The result is that we compile this function with DFG and then we take a slightly different allocation path that causes us to GC at a slightly different time.  Not always, but sometimes.  Consequently, on my MBP, we usually nudge the GC to happen at the "wrong" time.  That is, we fail to observe that the bad structure for the GameBoy state (the one with secondaryBuffer) doesn't get blown away by GC.  This postpones our ability to realize that this structure is bogus.

The underlying issue is that we're trying to monomorphise this object too aggressively.  In truth, the object sometimes has secondaryBuffer and sometimes not.  And none of our accesses to the object care.  Also, the presence (or lack) of this property doesn't change the property offsets of any of the properties that we care about.  But, we still try to check the type of the object by enumerating over "both" of its types: one type that has secondaryBuffer and one that doesn't.

I suspect that the correct long-term solution is to not use structures in these checks, since structures can (and should) go away.  For example, we could observe the everyone who checks for a particular structure is really interested in the presence of some set of fields along with their offsets.  We can turn this into a Protocol object that describes the concept of a structure having certain fields at certain offsets.  Protocols can be always strongly referenced.  Then:

- If the structure goes away, we can turn all checks for that structure into checks for the Protocol.
- If any accesses cache on the structure see a different structure but that other structure follows the same Protocol, then turn the structure check into a Protocol check.

Protocol checks could be implemented using type displays.  We could arrange each Structure to have an inline display with 8 byte-sized entries, along with an overflow pointer.  Or, we could just disallow association of structures with protocols if it blows the limit.

Note that there are probably different variants of how to associate structures with protocols.  The turning of structures into protocols during GC might be optional.

- One approach is to say that anytime a CodeBlock emits a check for a structure, we account for the reason for that check.  All of those reasons put together constitute a protocol.  This could lead to some protocol explosion.
- Another approach is to say that we always maximize what a protocol encompasses.  If any access goes bimorphic despite the offset of the accessed property staying the same, we can derive a protocol that has the intersection of the two structures.  If such a protocol already exists, we can use it.

I like the latter approach best.  We could take this further:

- If an access on property F with offset O goes bimorphic over structures S and T and neither S nor T have any protocols, create a protocol P that:
    - Strictly requires F to be at O
    - Cites S and T as belonging to the protocol
    - S and T will claim to subtype P
- If an access on property F with offset O goes bimorphic over structures S and T and S and T have protocols already, then we should have some smarts to try to merge the protocols.
    - Need to think about this more.
- If an access on property F with offset O on protocol P sees structure T such that T has F at O then:
    - Include T in P

[Filip Pizlo]

- If an access on property F with offset O goes bimorphic over structures S and T and S and T have any protocols that they share, then find the largest shared protocol whose membership is happy with F at O.

[Filip Pizlo]

- If an access on property F with offset O goes bimorphic over structures S and T and S and T have any protocols that they share, then find the largest shared protocol whose membership is happy with F at O.

- If an access on property F with offset O goes bimorphic over structures S and T and there are no shared protocols or none of them agree on F at O, find the largest protocol of either structure that would be happy with F at O and add the other structure to that protocol.

- Create a new protocol if none of the protocols already associated with S or T are happy with F at O.

Protocol happiness is defined as all of the member structures agreeing with a proposition like "F is at O".  It's OK to a member structure to a protocol if that structure agrees with all of the propositions the protocol makes.  It's OK to add a proposition to a protocol if all of the memory structures agree to the proposition.

[Filip Pizlo]

A protocol being OK with a structure being added to it also means that the structure has room in its type display for that protocol.  We could have an incremental protocol/display moving thingy for changing the slot that the display appears in.  Alternatively, we could randomize the bucket that a protocol uses and just reject structure-protocol membership if there is a collision.

We might have an access go bimorphic such that S, T have protocols P, Q where both protocols already have F at O.  In that case, attempt to merge the protocols.  If the protocols can't be merged, attempt to make S a member of Q or T a member of P, whichever leads to the larger protocol.  If that doesn't work out, just create a new protocol.

Protocol size is determined by the number of propositions it makes.

Note that protocol merging means that each protocol needs to know about:
- All of the structures that use it, so that if we change the protocol's bucket and TID, we can update the structures' displays.
- All of the places that check for the protocol, so that if we change the bucket/TID, we can patch the code.