1358635 - stylo: Consider avoiding selector matching a second time for !important rules

Status: RESOLVED FIXED

(Core :: CSS Parsing and Computation, enhancement, P1)

Description

[Bobby Holley (:bholley)]

See the discussion in bug 1358375 comment 5 and onward.

Right now Servo does selector matching twice, once when gathering normal rules and once when gathering important rules. We have booleans on the Rule that tell us whether there are any normal and any important declarations, and use that to bail out of matching. However, if a rule has both, we will match it twice.

Now that we have the rule tree, we have another option - we can just walk the rule tree, gathering any rules that have !important in them. We could either:
(a) Do this during matching, and re-insert additional rule nodes for the same rule at the important cascade level, or
(b) Handle it during the cascade, by just iterating the list of rule nodes multiple times depending on whether we want !important or not.

Given how fast selector matching is now, it's not 100% obvious to me that either (a) or (b) would be a win, but I wanted to get this on file.

Comment 1

[Bobby Holley (:bholley)]

(In reply to Bobby Holley (:bholley) (busy with Stylo) from comment #0)
> See the discussion in bug 1358375 comment 5 and onward.
> 
> Right now Servo does selector matching twice, once when gathering normal
> rules and once when gathering important rules. We have booleans on the Rule
> that tell us whether there are any normal and any important declarations,
> and use that to bail out of matching. However, if a rule has both, we will
> match it twice.
> 
> Now that we have the rule tree, we have another option - we can just walk
> the rule tree, gathering any rules that have !important in them. We could
> either:
> (a) Do this during matching, and re-insert additional rule nodes for the
> same rule at the important cascade level, or
> (b) Handle it during the cascade, by just iterating the list of rule nodes
> multiple times depending on whether we want !important or not.
> 
> Given how fast selector matching is now, it's not 100% obvious to me that
> either (a) or (b) would be a win, but I wanted to get this on file.

Turns out I can make bloom-basic almost twice as fast by ignoring author !important rules. Given that I  think we should do something about this. I'm going to investigate (b).

Comment 2

[Emilio Cobos Álvarez (:emilio)]

(In reply to Bobby Holley (:bholley) (busy with Stylo) from comment #1)
> (In reply to Bobby Holley (:bholley) (busy with Stylo) from comment #0)
> > See the discussion in bug 1358375 comment 5 and onward.
> > 
> > Right now Servo does selector matching twice, once when gathering normal
> > rules and once when gathering important rules. We have booleans on the Rule
> > that tell us whether there are any normal and any important declarations,
> > and use that to bail out of matching. However, if a rule has both, we will
> > match it twice.
> > 
> > Now that we have the rule tree, we have another option - we can just walk
> > the rule tree, gathering any rules that have !important in them. We could
> > either:
> > (a) Do this during matching, and re-insert additional rule nodes for the
> > same rule at the important cascade level, or
> > (b) Handle it during the cascade, by just iterating the list of rule nodes
> > multiple times depending on whether we want !important or not.
> > 
> > Given how fast selector matching is now, it's not 100% obvious to me that
> > either (a) or (b) would be a win, but I wanted to get this on file.
> 
> Turns out I can make bloom-basic almost twice as fast by ignoring author
> !important rules. Given that I  think we should do something about this. I'm
> going to investigate (b).

Note that as of right now we don't have the rule nodes inserted until we finish the whole selector-matching process, so I guess you need to look at the applicable declarations vector (which btw should probably be a SmallVec).

But yeah, doing it that way looks reasonable to me, I guess.

Comment 3

[Bobby Holley (:bholley)]

Emilio and I discussed, and decided to do this during rule tree insertion.

https://treeherder.mozilla.org/#/jobs?repo=try&revision=325f114abcc313d59d43991b2e583c63b527c6e6

Comment 4

[Bobby Holley (:bholley)]

Attachment: Handle importance when inserting into the rule tree. v1

Comment 5

[Bobby Holley (:bholley)]

This almost doubles performance on bloom-basic.html.

Comment 6

[Bobby Holley (:bholley)]

Hm, that lone crashtest assertion is curious. Maybe I mixed up the order of some ua important rule or something? Let me know if you spot the issue, otherwise I'll debug it (probably tomorrow).

Comment 7

[Emilio Cobos Álvarez (:emilio)]

Comment on attachment 8866389 [details] [diff] [review]
Handle importance when inserting into the rule tree. v1

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

::: servo/components/style/rule_tree/mod.rs
@@ +128,5 @@
> +    /// Inserts the given rules, that must be in proper order by specifity, and
> +    /// returns the corresponding rule node representing the last inserted one.
> +    ///
> +    /// !important rules are detected and inserted into the appropriate position
> +    /// in the rule tree.

Explaining the motivation for this method here could be nice.

@@ +146,5 @@
> +        let mut important_user = SmallVec::<[StyleSource; 4]>::new();
> +        let mut important_ua = SmallVec::<[StyleSource; 4]>::new();
> +
> +        for (source, level) in iter {
> +            debug_assert!(last_level <= level, "Not really ordered");

Assert the level is not !important? (right now you only assert it if there's any important declaration).

@@ +149,5 @@
> +        for (source, level) in iter {
> +            debug_assert!(last_level <= level, "Not really ordered");
> +            let (any_normal, any_important) = {
> +                let pdb = source.read(level.guard(guards));
> +                (pdb.any_normal(), pdb.any_important())

Just curious: How important is this pointer-chase vs. the two bits in the specificity field of the rule? Perhaps the important thing for perf was not having pointer-chasing during the main selector-matching process? That'd be interesting.

@@ +157,5 @@
> +                match level {
> +                    AuthorNormal => important_author.push(source.clone()),
> +                    UANormal => important_ua.push(source.clone()),
> +                    UserNormal => important_user.push(source.clone()),
> +                    StyleAttributeNormal => important_style_attr = Some(source.clone()),

Assert important_style_attribute.is_none().

@@ +190,5 @@
> +        }
> +
> +        for source in important_ua.into_iter() {
> +            current = current.ensure_child(self.root.downgrade(), source, UAImportant);
> +        }

So there's a case you don't handle here, which is the transitions level, which sohuld be after the important ua rules.

Given there's only one transition rule for a given element, we could defer it in the same way we do for the style attribute important rules, and assert there's no more than one.

::: servo/components/style/stylist.rs
@@ +763,5 @@
>          } else {
>              debug!("skipping non-agent rules");
>          }
>  
> +        // Step 7: Transitions.

Let's keep the step number as it was, and comment that we handle the !important rules later, while inserting in the rule tree.

Comment 8

[Emilio Cobos Álvarez (:emilio)]

The assertion is because now we're not optimizing away the empty first-line rule in that test-case, basically.

In lazily_compute_pseudo_element_style, we have |if declarations.is_empty() { return None; }|.

Before, declarations was an empty vector. Now declarations contains the empty rule, but we filter it out while inserting into the rule tree. To preserve behavior you can use if rule_node == self.rule_tree.root() { return None }.

Comment 9

[Boris Zbarsky [:bzbarsky]]

> The assertion is because now we're not optimizing away the empty first-line rule in that test-case, basically.

Hmm.  I don't think Gecko optimizes it out either, in that case.  That testcase doesn't test what it thinks it's testing if a rule with no declarations gets optimized out, for what it's worth...

Comment 10

[Bobby Holley (:bholley)]

(In reply to Emilio Cobos Álvarez [:emilio] from comment #7)
> Comment on attachment 8866389 [details] [diff] [review]
> Handle importance when inserting into the rule tree. v1
> 
> Review of attachment 8866389 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> ::: servo/components/style/rule_tree/mod.rs
> @@ +128,5 @@
> > +    /// Inserts the given rules, that must be in proper order by specifity, and
> > +    /// returns the corresponding rule node representing the last inserted one.
> > +    ///
> > +    /// !important rules are detected and inserted into the appropriate position
> > +    /// in the rule tree.
> 
> Explaining the motivation for this method here could be nice.

Sure.

> 
> @@ +146,5 @@
> > +        let mut important_user = SmallVec::<[StyleSource; 4]>::new();
> > +        let mut important_ua = SmallVec::<[StyleSource; 4]>::new();
> > +
> > +        for (source, level) in iter {
> > +            debug_assert!(last_level <= level, "Not really ordered");
> 
> Assert the level is not !important? (right now you only assert it if there's
> any important declaration).

Done.

> 
> @@ +149,5 @@
> > +        for (source, level) in iter {
> > +            debug_assert!(last_level <= level, "Not really ordered");
> > +            let (any_normal, any_important) = {
> > +                let pdb = source.read(level.guard(guards));
> > +                (pdb.any_normal(), pdb.any_important())
> 
> Just curious: How important is this pointer-chase vs. the two bits in the
> specificity field of the rule? Perhaps the important thing for perf was not
> having pointer-chasing during the main selector-matching process? That'd be
> interesting.

Well, there are basically two speedups in this patch:
(1) Not iterating the entire array of selectors twice.
(2) Not doing the extra checks during selector matching, which gets us to bloom rejection faster.

On bloom-basic, both of these were significant IIRC. I didn't break down the various pieces of (2).

> 
> @@ +157,5 @@
> > +                match level {
> > +                    AuthorNormal => important_author.push(source.clone()),
> > +                    UANormal => important_ua.push(source.clone()),
> > +                    UserNormal => important_user.push(source.clone()),
> > +                    StyleAttributeNormal => important_style_attr = Some(source.clone()),
> 
> Assert important_style_attribute.is_none().

Good point.

> 
> @@ +190,5 @@
> > +        }
> > +
> > +        for source in important_ua.into_iter() {
> > +            current = current.ensure_child(self.root.downgrade(), source, UAImportant);
> > +        }
> 
> So there's a case you don't handle here, which is the transitions level,
> which sohuld be after the important ua rules.

Ah yes, of course. :-)

> 
> Given there's only one transition rule for a given element, we could defer
> it in the same way we do for the style attribute important rules, and assert
> there's no more than one.

Sounds good.

> 
> ::: servo/components/style/stylist.rs
> @@ +763,5 @@
> >          } else {
> >              debug!("skipping non-agent rules");
> >          }
> >  
> > +        // Step 7: Transitions.
> 
> Let's keep the step number as it was, and comment that we handle the
> !important rules later, while inserting in the rule tree.

I can, but do these "steps" actually correspond to anything in a spec or elsewhere?

(In reply to Emilio Cobos Álvarez [:emilio] from comment #8)
> The assertion is because now we're not optimizing away the empty first-line
> rule in that test-case, basically.
> 
> In lazily_compute_pseudo_element_style, we have |if declarations.is_empty()
> { return None; }|.
> 
> Before, declarations was an empty vector. Now declarations contains the
> empty rule, but we filter it out while inserting into the rule tree. To
> preserve behavior you can use if rule_node == self.rule_tree.root() { return
> None }.

I'll handle it in lazy_pseudo_rules instead, so that the other callers can also benefit.

Comment 11

[Bobby Holley (:bholley)]

Attachment: Handle importance when inserting into the rule tree. v2

Comment 12

[Bobby Holley (:bholley)]

https://treeherder.mozilla.org/#/jobs?repo=try&revision=1ac60313c1a2d2c8a6b447e3676315b75ed44b34

Comment 13

[Emilio Cobos Álvarez (:emilio)]

Comment on attachment 8866742 [details] [diff] [review]
Handle importance when inserting into the rule tree. v2

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

Looks good!

Comment 14

[Bobby Holley (:bholley)]

https://github.com/servo/servo/pull/16813