972601 - Convert nsTreeStyleCache::mTransitionTable and ::mCache to more modern hashtables

Status: RESOLVED FIXED

(Core :: XUL, defect)

Description

[Andrew McCreight [:mccr8]]

This is somewhat odd.  There are two hash tables, one representing a finite state machine, and one representing some kind of cache of results for the finite state machine.

This involves two custom hashtable key classes, nsDFAState and nsTransitionKey.  The first one is odd because the things it can hold are from a linearly allocated set of integers, and the hash function is just the identity.  I guess because it is used for the cache, they wanted the lookup to be fast?  But I'm guessing it is okay to just replace it with a regular integer hash class.  nsTransitionKey is a pair, of an int and a COMPtr.  I'm not sure if there's a newer hashtable key class that allows pairs, or if one will have to be created.

This code is old, and landed as part of a big refactoring, so digging around in the history for it didn't clarify anything for me.

Comment 1

[Neil Deakin]

I think it's ok to replace the custom hash code. But this code needs to be performant -- it will be called many times during painting.

Comment 2

[Andrew McCreight [:mccr8]]

https://tbpl.mozilla.org/?tree=Try&rev=8797b19a1ecd

Comment 3

[Andrew McCreight [:mccr8]]

Attachment: part 1 - Get rid of pointless start state in nsTreeStyleCache::GetStyleContext.

L64 debug try run: https://tbpl.mozilla.org/?tree=Try&rev=8797b19a1ecd

Comment 4

[Andrew McCreight [:mccr8]]

Attachment: part 2 - Delete trailing whitespace from nsXULTreeStyleCache.

Comment 5

[Andrew McCreight [:mccr8]]

Attachment: part 3 - Make nsTreeStyleCache use auto pointers for its hashtables.

Comment 6

[Andrew McCreight [:mccr8]]

Attachment: part 4 - Convert nsTreeStyleCache::mCache to nsRefPtrHashtable.

Comment 7

[Andrew McCreight [:mccr8]]

Attachment: part 5 - Convert nsTreeStyleCache::mTransitionTable to nsClassHashtable.

This also turns nsTransitionKey into an inner class of nsStyleContext, and changes it from an nsHashKey to a class to be used with nsGenericHashKey.

It also changes the intermediate values of the hash computation to uints, instead of signed ints, as that seems more right.

Comment 8

[Andrew McCreight [:mccr8]]

Attachment: part 6 - Replace nsDFAState with uint32_t in nsXULTreeStyleCache.

It is now a pointless wrapper around uint32_t.

Comment 9

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Comment on attachment 8411092 [details] [diff] [review]
part 5 - Convert nsTreeStyleCache::mTransitionTable to nsClassHashtable.

>Bug 972601, part 5 - Convert nsTreeStyleCache::mTransitionTable to nsClassHashtable. r=dbaron
>
>This also turns nsTransitionKey into an inner class of nsStyleContext, and changes it from an nsHashKey to a class to be used with nsGenericHashKey.

of nsTreeStyleCache, not nsStyleContext

>+bool nsTreeStyleCache::Transition::operator==(const Transition& aOther) const

newline after bool

>+{
>+  return aOther.mState == mState && aOther.mInputSymbol == mInputSymbol;
>+}
>+
>+uint32_t nsTreeStyleCache::Transition::Hash() const

newline after uint32_t


I spent a bit of time checking that what both APIs expected from their Hash()/HashCode() function was the same, but it should have been obvious since they both use pldhash.  (i.e., no need to use the MFBT AddToHash functions)

r=dbaron



But please test that trees still paint reasonably after your patch, since we have almost no test coverage for it.  Look at, say, the bookmarks sidebar, about:config, and some of the things in the preferences UI.

(Also, it would probably be good to double-check that you're still hitting the cache at similar rates.)

Comment 10

[Andrew McCreight [:mccr8]]

Thanks for the reviews.

(In reply to David Baron [:dbaron] (needinfo? me) (UTC-7) from comment #9)
> of nsTreeStyleCache, not nsStyleContext
> newline after bool
> newline after uint32_t
Done.

> But please test that trees still paint reasonably after your patch, since we
> have almost no test coverage for it.  Look at, say, the bookmarks sidebar,
> about:config, and some of the things in the preferences UI.
>
> (Also, it would probably be good to double-check that you're still hitting
> the cache at similar rates.)

I looked around at those things you mentioned (I wasn't really sure what this code was for), and they look okay.  The cache rate looks more or less the same, too.

I'll land after the trees open.

Comment 11

[Andrew McCreight [:mccr8]]

remote:   https://hg.mozilla.org/integration/mozilla-inbound/rev/3389cea57d49
remote:   https://hg.mozilla.org/integration/mozilla-inbound/rev/5d1f1d5ff06c
remote:   https://hg.mozilla.org/integration/mozilla-inbound/rev/4cfc79c744f8
remote:   https://hg.mozilla.org/integration/mozilla-inbound/rev/838156914c6d
remote:   https://hg.mozilla.org/integration/mozilla-inbound/rev/4a54846d5ad6
remote:   https://hg.mozilla.org/integration/mozilla-inbound/rev/40532c120293

Comment 12

[Carsten Book [:Tomcat]]

https://hg.mozilla.org/mozilla-central/rev/3389cea57d49
https://hg.mozilla.org/mozilla-central/rev/5d1f1d5ff06c
https://hg.mozilla.org/mozilla-central/rev/4cfc79c744f8
https://hg.mozilla.org/mozilla-central/rev/838156914c6d
https://hg.mozilla.org/mozilla-central/rev/4a54846d5ad6
https://hg.mozilla.org/mozilla-central/rev/40532c120293