528291 - Tamarin needs a faster subtype-test primitive

Status: RESOLVED FIXED

(Tamarin Graveyard :: Virtual Machine, defect)

Description

[Edwin Smith]

downcasting and instanceof-testing (OP_istype/istypelate) are frequent enough that this primitive needs to be more highly optimized.

currently, Traits::containsInterface(T) involves:
  * self-check which usually fails
  * weak-ref access to load the interfaces table (load+branch)
  * quadradic probe to search for T in the interface set, which
    usually succeeds on the first probe  (at least two more loads, at least one more compare)

there are two special cases that are important to optimize:

* if T is a shallowly-inherited class (not interface), the subtype check can be O(1) with as few as two loads and one branch

* if T is a known constant, the whole test can be speciailized

* if self is left out of the interface set, then many common sets can be shared between types.  (many leaf types have the same sets of base classes and interfaces).

Additionally, preliminary data shows that at least a one-entry positive cache and a one-entry negative cache would be a more effective short-circuit than the existing self-test.

Comment 1

[Edwin Smith]

Attachment: encapsulates access to the Traits::isInterface flag (the flag may eventually go away)

Comment 2

[Edwin Smith]

Comment on attachment 412231 [details] [diff] [review]
encapsulates access to the Traits::isInterface flag (the flag may eventually go away)

pushed http://hg.mozilla.org/tamarin-redux/rev/68449f7ee5f4

Comment 3

[Edwin Smith]

Attachment: renames containsInterface to subtypeof, fixups in AbcParser

1. Renames containsInterface to subtypeof mainly for clarity.
2. small code cleanup in AbcParser.cpp

Comment 4

[Steven Johnson]

Comment on attachment 412636 [details] [diff] [review]
renames containsInterface to subtypeof, fixups in AbcParser

unrelated, but why don't we check for subtypeof(Array) in LIR, like we do for Vector? (Granted, people don't subclass Array very often...)

Comment 5

[Edwin Smith]

Good question, probably a useful enhancement.

Comment 6

[Edwin Smith]

Comment on attachment 412636 [details] [diff] [review]
renames containsInterface to subtypeof, fixups in AbcParser

pushed
http://hg.mozilla.org/tamarin-redux/rev/17686f7b8cce

Comment 7

[Edwin Smith]

Attachment: Encapsulate interface iteration in a helper class

Upcoming change to supertype data structures will mean iteration changes.  This patch factors iteration code into a helper so upcoming changes will be targeted to the iterator.

also:
 - s/uint32/uint32_t
 - make TraitsBindings.subtypeof() private

Comment 8

[Steven Johnson]

Comment on attachment 412848 [details] [diff] [review]
Encapsulate interface iteration in a helper class

nice.

Comment 9

[Edwin Smith]

Comment on attachment 412848 [details] [diff] [review]
Encapsulate interface iteration in a helper class

http://hg.mozilla.org/tamarin-redux/rev/4680c1e2a7ce

Comment 10

[Edwin Smith]

Attachment: add new postype for interfaces, remove m_isInterface flag

Remove Traits.m_isInterface flag and use a postype value instead.  (all behind encapsulated api's).

The material part of this change ensures we know whether a Traits is an interface or not in the Traits constructor, instead of being set after construction by AbcParser.  This will let us internally build supertype information in the constructor.

other:  drop the _FROM_ABC verbage in enum TraitsPosType enums, to make them shorter.  comments added.

Comment 11

[Edwin Smith]

Comment on attachment 412915 [details] [diff] [review]
add new postype for interfaces, remove m_isInterface flag

pushed http://hg.mozilla.org/tamarin-redux/rev/eb68108d689b

Comment 12

[Edwin Smith]

Attachment: Implements new subtypeof algorithm

New, faster subtypeof algorithm.

See implementation comments in Traits.h

This patch is a drop in replacement for the old subtypeof().
Subsequent patches will:

* correct unbounded recursion in Traits::countInterfaces and resolveSignatures
* provide inlineable fast specialized variants of subtypeof for primary types, final types, known interfaces, etc.

Comment 13

[Steven Johnson]

did you want a review for this patch? or comments? or...?

Comment 14

[Steven Johnson]

Comment on attachment 413373 [details] [diff] [review]
Implements new subtypeof algorithm

nicely documented!

two nits:

-- using naked 'int' in new code 
-- new private members should generally be prepended with 'm_' or '_'

Comment 15

[Steven Johnson]

More comments I should have added in my review+:

-- TB::subtypeof looks like it can be eliminated in favor of directly calling owner->subtypeof

-- Traits::countInterfaces() calls resolveTypeName with Toplevel=NULL... this is only safe to do if you *know* that the resolve is going to succeed (generally, if we know we have already called it on this at least once). Not sure if this is the case here, since we're calling it at Traits-construction time...

-- It's worth adding a comment to Traits::countInterfaces that it only adds interfaces that are not implemented by the baseclass (ie, "new" interfaces)

-- should Traits::allocSupertypeList allocate pre-zeroed memory, just in case? Seems like cheap insurance.

-- Traits::secondary_subtypeof smells like it would benefit from FASTCALL.

-- nit: max_primary_supertype is a constant, so really should be ALL_CAPS

Comment 16

[Edwin Smith]

(In reply to comment #15)
> More comments I should have added in my review+:
> 
> -- TB::subtypeof looks like it can be eliminated in favor of directly calling
> owner->subtypeof

done

> -- Traits::countInterfaces() calls resolveTypeName with Toplevel=NULL... this
> is only safe to do if you *know* that the resolve is going to succeed
> (generally, if we know we have already called it on this at least once). Not
> sure if this is the case here, since we're calling it at Traits-construction
> time...

in AbcParser, every interface is resolved before we construct the class Traits.  any failures would happen earlier. I didn't see much gain in a new assert since deeper down we'd require toplevel != NULL anyway.  thoughts?

> -- It's worth adding a comment to Traits::countInterfaces that it only adds
> interfaces that are not implemented by the baseclass (ie, "new" interfaces)

renamed to countNewInterfaces and expanded the comment.

> -- should Traits::allocSupertypeList allocate pre-zeroed memory, just in case?
> Seems like cheap insurance.

agreed, done.

> -- Traits::secondary_subtypeof smells like it would benefit from FASTCALL.

done

> -- nit: max_primary_supertype is a constant, so really should be ALL_CAPS

done

Comment 17

[Steven Johnson]

(In reply to comment #16)

> in AbcParser, every interface is resolved before we construct the class Traits.
>  any failures would happen earlier. I didn't see much gain in a new assert
> since deeper down we'd require toplevel != NULL anyway.  thoughts?

if we know every interface is resolved (and thus parsable) then we should be safe. (probably worth adding a comment to this effect)

Comment 18

[Edwin Smith]

pushed http://hg.mozilla.org/tamarin-redux/rev/b0c67bf77d3e

Comment 19

[Edwin Smith]

this assert sometimes fires:

  AvmAssert(!secondary_subtypeof(seen[i]));

implying we are adding duplicate entries to the secondary_supertypes array, incorrectly.

Comment 20

[Edwin Smith]

Comment on attachment 413373 [details] [diff] [review]
Implements new subtypeof algorithm

Comments from kpalacz:

* an inline-cache for the istype check could obviate the need for the negative cache.

* maybe do (S==T) check earlier, since it's cheap.

Comment 21

[Edwin Smith]

(In reply to comment #19)

> implying we are adding duplicate entries to the secondary_supertypes array,
> incorrectly.

Fixed, pushed
http://hg.mozilla.org/tamarin-redux/rev/584908b66c82

Comment 22

[Edwin Smith]

(In reply to comment #20)
> (From update of attachment 413373 [details] [diff] [review])
> Comments from kpalacz:
> 
> * an inline-cache for the istype check could obviate the need for the negative
> cache.
> 
> * maybe do (S==T) check earlier, since it's cheap.

Did some spot-checking of several apps including Flex apps, Traits (and thus instances of the negative cache) outnumber istype call sites by 10:1 or more.  Memory wise, the inline cache would win, and would avoid the need for GCHiddenPtr.

todo: test hit rates.  if an inline negative cache hits at least as much as the per-traits negative cache, we should make the change.

(this assumes that subtypeof negative-cache hits are mainly for istype, and not downcasting.  still need to test the assumption).