525608 - [FIX]Speed up pseudo-style probing

Status: RESOLVED FIXED

(Core :: CSS Parsing and Computation, defect)

Description

[Boris Zbarsky [:bzbarsky]]

Basic idea is to be smarter about storing our pseudo-style selectors in the rule cascade, instead of just using a flat list.  See the mozilla.dev.tech.layout thread about "Optimizing pseudo-style probing".

Comment 1

[Boris Zbarsky [:bzbarsky]]

Attachment: Part 1. Introduce an enum for pseudo-elements

I'm not a huge fan of the actual names in this enum, so if you have better suggestions, please let me know!

Comment 2

[Boris Zbarsky [:bzbarsky]]

Attachment: Part 2. CSS parser changes

Comment 3

[Boris Zbarsky [:bzbarsky]]

Attachment: Part 3. Make consumers ask for different pseudo styles differently

Comment 4

[Boris Zbarsky [:bzbarsky]]

Attachment: Part 4. The actual change to how pseudo-elements work

Two things worth checking here:

1)  I removed the null-checks of the return value of PresContext() in the style
    set.  I think that's ok, but if not please let me know?
2)  Should EnumerateAllRules get the tag/id/etc from aData itself, now that it
    can?

Comment 5

[Boris Zbarsky [:bzbarsky]]

Attachment: Part 5. Make anonymous boxes not do selector matching at all and instead just do a single hashtable lookup

Comment 6

[Boris Zbarsky [:bzbarsky]]

Attachment: Part 6. Now that anon boxes don't use RuleProcessorData, it always has an mContent

Comment 7

[Boris Zbarsky [:bzbarsky]]

Attachment: Part 7. Move tree pseudos out of the rulehash

I'm not sure what the best approach is to the pseudo stats here....  I'm also not sure whether it's in fact worth putting the tree pseudos in a separate hashtable instead of just riding along on the rulehash.  It does remove at least one IsPseudoElement() check from the tree pseudo codepath, but that's peanuts.

Comment 8

[Boris Zbarsky [:bzbarsky]]

One other note.  We could make the -moz-list* pseudos into anonymous boxes instead of pseudo-elements if we're ok with applying the font-size quirk to *|*::-moz-list-bullet in quirks mode, not just to li::-moz-list-bullet.  That might make list items a tiny bit faster (no need for the RuleProcessorData data for the bullet).  Or not, if the hashtable op is enough more expensive than the array index...

Comment 9

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

Comment on attachment 409468 [details] [diff] [review]
Part 1.  Introduce an enum for pseudo-elements

r=dbaron, though I'm interested to see what uses some of those enum values turn out to have in the later patches

(I wonder if you should change from to passing null for the content node when resolving the frameset border styles, but I think it's ok as-is.)

Comment 10

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

(In reply to comment #9)
> (I wonder if you should change from to passing null for the content node when
> resolving the frameset border styles, but I think it's ok as-is.)

I guess that's moot after patch 3, though. :-)

Comment 11

[Boris Zbarsky [:bzbarsky]]

> what uses some of those enum values turn out to have in the later patches

The main uses are telling apart pseudo-element vs anon box vs tree pseudo (if nothing else for patch 3), and for the first of these looking up the pseudo atom quickly (mostly for impedance matching with existing code) and looking up the relevant rulehash in patch 4.

Comment 12

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

Comment on attachment 409469 [details] [diff] [review]
Part 2.  CSS parser changes

In ParsePseudoSelector and ParseSelector, could you either rename 
aPseudoType to be aPseudoElementType or rename
aPseudoElement/aPseudoElementArgs to aPseudo/aPseudoArgs.  I think I'd
prefer the former.  (Anonymous boxes really are just a variation of 
pseudo-elements.)

>+  NS_ASSERTION(!isPseudoClass ||
>+               pseudoType == nsCSSPseudoElements::ePseudo_NotPseudoElement,
>+               "Why is this atom both a pseudo-class and a pseudo-element?");

You might also want to assert that isPseudoClass + isPseudoElement +
isAnonBox <= 1.

> // -- nsCSSSelector -------------------------------
>-
> nsCSSSelector::nsCSSSelector(void)

I'd prefer keeping the blank line.

r=dbaron

Comment 13

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

Comment on attachment 409470 [details] [diff] [review]
Part 3.  Make consumers ask for different pseudo styles differently

nsStyleStruct.h:
+// See nsStyleContext::GetPseudoEnum
+#define NS_STYLE_CONTEXT_TYPE_SHIFT       28

Could you explicitly define the mask even if you don't use the constant?

nsStyleSet.cpp:

+#ifdef DEBUG
+  else {
+    NS_ASSERTION(result->GetPseudoType() == aPseudoType, "Unexpected type");
+  }
+#endif

No need for the #ifdefs.  (And you could check GetPseudoTag too if you
want.)


Are the changes to nsComputedDOMStyle::GetStyleContextForContent
changing compatibility?  Should we instead return an non-element style
inside the element?  Or does it matter?

(Also, while I'm there, shouldn't the recursive call inside
GetStyleContextForContentNoFlush call GetStyleContextForContentNoFlush
rather than just GetStyleContextForContent?  





It occurs to me that we might want to make :-moz-non-element be a
different type in the enum (at some time in the future).

r=dbaron

Comment 14

[Boris Zbarsky [:bzbarsky]]

> Could you explicitly define the mask even if you don't use the constant?

So just NS_STYLE_CONTEXT_TYPE_MASK defined to 0xf000000?

> Are the changes to nsComputedDOMStyle::GetStyleContextForContent
> changing compatibility?

Yes.  I'm absolutely open for changing the behavior here in various ways.  The current code (before this change) just always returns a style context pointing to the root rulenode for cases when an unknown (not anon box, not tree pseudo, not pseudo-element) pseudo is used; which is effectively a non-element style context inside the element, as you propose.  After my change, a call that uses a pseudo that's not a pseudo-element will throw.  We can change it to do the non-element thing, for sure.  Would you prefer that?  I don't have a strong opinion here; I suspect in practice no one ever uses the pseudo version of getComputedStyle, esp. not with random non-pseudo-element pseudos.

> shouldn't the recursive call inside GetStyleContextForContentNoFlush call
> GetStyleContextForContentNoFlush

Yes, it should.  I'll roll that change in.

> It occurs to me that we might want to make :-moz-non-element be a
> different type in the enum (at some time in the future)

Sure.  I'd be fine with that.

Comment 15

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

(In reply to comment #14)
> > Could you explicitly define the mask even if you don't use the constant?
> 
> So just NS_STYLE_CONTEXT_TYPE_MASK defined to 0xf000000?

Yes.

> > Are the changes to nsComputedDOMStyle::GetStyleContextForContent
> > changing compatibility?
> 
> Yes.  I'm absolutely open for changing the behavior here in various ways.  The
> current code (before this change) just always returns a style context pointing
> to the root rulenode for cases when an unknown (not anon box, not tree pseudo,
> not pseudo-element) pseudo is used; which is effectively a non-element style
> context inside the element, as you propose.  After my change, a call that uses
> a pseudo that's not a pseudo-element will throw.  We can change it to do the
> non-element thing, for sure.  Would you prefer that?  I don't have a strong
> opinion here; I suspect in practice no one ever uses the pseudo version of
> getComputedStyle, esp. not with random non-pseudo-element pseudos.

On the other hand, maybe throwing is better, because we're changing the code from actually computing the style correctly for some future pseudo-element to actually not being able to compute it.

Comment 16

[Boris Zbarsky [:bzbarsky]]

We didn't really compute it correctly before, since the future pseudo-element never had any rules applying to it (since they got dropped by the parser)...

Comment 17

[Boris Zbarsky [:bzbarsky]]

Attachment: Part 2 updated to comments

> rename aPseudoType to be aPseudoElementType

Done; similar for the locals.  Addressed the other two comments too.

Comment 18

[Boris Zbarsky [:bzbarsky]]

Addressed the issues from comment 13, except for deciding whether to make the behavior change.  Do we want that?

Comment 19

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

I guess throwing makes sense.

Comment 20

[Boris Zbarsky [:bzbarsky]]

Attachment: Part 3 updated to comments

Comment 21

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

Comment on attachment 409471 [details] [diff] [review]
Part 4.  The actual change to how pseudo-elements work

I think it would make more sense to store mQuirksMode on the 
RuleCascadeData rather than on each RuleHash.

+    RuleHash* ruleHash = cascade->mPseudoElementRuleHashes[pseudoType];

Maybe make this RuleHash*& or RuleHash** and then just assign right back 
to it?

You need to rev the nsIStyleRuleProcessor IID.

Also, in nsIStyleRuleProcessor.h, the comment for 
RulesMatching(PseudoRuleProcessorData*) should perhaps say anonymous box
rather than just "pseudo"?  (Hmmm... maybe you put that in a later 
patch?)

In nsStyleSet.cpp, you should put ResolvePseudoElementStyle before 
ResolvePseudoStyle, like it is everywhere else.


r=dbaron with that

Comment 22

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

(In reply to comment #21)
> Also, in nsIStyleRuleProcessor.h, the comment for 
> RulesMatching(PseudoRuleProcessorData*) should perhaps say anonymous box
> rather than just "pseudo"?  (Hmmm... maybe you put that in a later 
> patch?)

Given the later patches, ignore this.  (Though maybe there should be a patch on top to change it to be more clearly for only what's left, which I think is just the tree pseudos?)

Comment 23

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

Comment on attachment 409472 [details] [diff] [review]
Part 5.  Make anonymous boxes not do selector matching at all and instead just do a single hashtable lookup

r=dbaron

Comment 24

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

Comment on attachment 409473 [details] [diff] [review]
Part 6.  Now that anon boxes don't use RuleProcessorData, it always has an mContent

r=dbaron

Comment 25

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

One other question about patch 4:  should we really be using ContentEnumFunc directly?  Doesn't that do an entirely wasted SelectorMatches call on the pseudo-element selector?

Comment 26

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

Comment on attachment 409475 [details] [diff] [review]
Part 7.  Move tree pseudos out of the rulehash

>   PLDHashTable             mAttributeSelectors;
>   PLDHashTable             mAnonBoxRules;
>
>+#ifdef MOZ_XUL
>+  PLDHashTable             mXULTreeRules;
>+#endif

Drop the blank line before the #ifdef?

And yes, this patch has the comment changes in nsIStyleRuleProcessor.h 
(and the IID rev, but watch the 80th column in the comment above it) 
that I asked for for patch 4.

r=dbaron


And one other comment about AddRule: there might be value in having the 
most common case at the start of the if-else chain rather than at the
end.  (Maybe another patch on top?)

Comment 27

[Boris Zbarsky [:bzbarsky]]

> store mQuirksMode on the RuleCascadeData
> Maybe make this RuleHash*&

Excellent ideas.

> put ResolvePseudoElementStyle before ResolvePseudoStyle

Does that still matter since that last becomes ResolveXULTreePseudoStyle in the last patch on this bug?  I can move that last down to make the C++ order match the header order if desired, but would prefer to do that in the last diff to reduce merge pain if you don't have strong views about having the order correct in the intermediate states.

> Though maybe there should be a patch on top to change it to be more clearly
> for only what's left, which I think is just the tree pseudos?

I believe part 7 does this.

> Doesn't that do an entirely wasted SelectorMatches call on the
> pseudo-element selector?

No.  The key is that in the pseudo-element case we do:

  aRuleInfo->mSelector = aRuleInfo->mSelector->mNext;

before calling PrependRule on the rulehash for that pseudo-element.  So the rules in each pseudo-element rulehash only contain the selectors up to the pseudo-element.  Then we match the nsIContent the pseudo-element is for against those rules, which is exactly what we want.

Part 2 is what makes sure the mNext is non-null here; that part is pretty key.

Comment 28

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

(In reply to comment #27)
> Does that still matter since that last becomes ResolveXULTreePseudoStyle in the
> last patch on this bug?  I can move that last down to make the C++ order match
> the header order if desired, but would prefer to do that in the last diff to
> reduce merge pain if you don't have strong views about having the order correct
> in the intermediate states.

Doing it another patch on top is probably best.

> > Though maybe there should be a patch on top to change it to be more clearly
> > for only what's left, which I think is just the tree pseudos?
> 
> I believe part 7 does this.

Yep... hence my followup comments.

> > Doesn't that do an entirely wasted SelectorMatches call on the
> > pseudo-element selector?
> 
> No.  The key is that in the pseudo-element case we do:
> 
>   aRuleInfo->mSelector = aRuleInfo->mSelector->mNext;
> 
> before calling PrependRule on the rulehash for that pseudo-element.  So the
> rules in each pseudo-element rulehash only contain the selectors up to the
> pseudo-element.  Then we match the nsIContent the pseudo-element is for against
> those rules, which is exactly what we want.

ah, ok

> Part 2 is what makes sure the mNext is non-null here; that part is pretty key.

Is it?  Or could you then just null-check here?

Comment 29

[Boris Zbarsky [:bzbarsky]]

I could, sort of; some of my initial work on this bug did just that.  It leads to more complicated code, and in particular to being unable to just reuse ContentEnumFunc.  Since the case of a "naked" pseudo-element is rather rare (with the possible exception of ::selection), the space optimization of not creating the mNext for that rare case doesn't seem worthwhile if it makes the code more complicated (and possibly slower) here.

Comment 30

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

ok

Comment 31

[Boris Zbarsky [:bzbarsky]]

Attachment: Part 4 interdiff addressing review comments

Add |const PRBool mQuirksMode| on RuleCascadeData, use |RuleHash*&|.

Comment 32

[Boris Zbarsky [:bzbarsky]]

Attachment: Part 4 updated to review comments.

Comment 33

[Boris Zbarsky [:bzbarsky]]

Attachment: Part 7 interdiff addressing review comments (except the AddRule one)

Removes the blank line; fixes the wrapping; moves ResolveXULTreePseudoStyle to the right place in the .cpp.

Comment 34

[Boris Zbarsky [:bzbarsky]]

Attachment: Part 7 updated to review comments

Comment 35

[Boris Zbarsky [:bzbarsky]]

Attachment: Part 8. Reorder AddRule

Comment 36

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

Comment on attachment 415181 [details] [diff] [review]
Part 8.  Reorder AddRule

r=dbaron

Comment 37

[Boris Zbarsky [:bzbarsky]]

Pushed:
http://hg.mozilla.org/mozilla-central/rev/696a4ad5d011
http://hg.mozilla.org/mozilla-central/rev/909cbe6e8979
http://hg.mozilla.org/mozilla-central/rev/5c675fda7ba6
http://hg.mozilla.org/mozilla-central/rev/05b655b218dd
http://hg.mozilla.org/mozilla-central/rev/aa21350b7c67
http://hg.mozilla.org/mozilla-central/rev/95a7468a8a8e
http://hg.mozilla.org/mozilla-central/rev/c6665a0ce75d
http://hg.mozilla.org/mozilla-central/rev/9c8bd114fd20

with a slight change to part 2 to not use pseudoElementType if pseudoElement is null.

Comment 38

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

(In reply to comment #37)
> with a slight change to part 2 to not use pseudoElementType if pseudoElement is
> null.

Though I wonder if it would have made more sense to initialize pseudoElementType instead (to NotPseudoElement, I presume).

Comment 39

[Boris Zbarsky [:bzbarsky]]

Hmm.  Yeah, ok.  That would make sense too.  I'll change to that.

Comment 40

[Boris Zbarsky [:bzbarsky]]

Pushed http://hg.mozilla.org/mozilla-central/rev/5d2775cdebc8 with that change.