1360088 - stylo: Use a rulehash for revalidation selectors and dependency selectors

Status: RESOLVED FIXED

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

Description

[Bobby Holley (:bholley)]

Even with bug 1358693, we'll still end up matching a lot more revalidation selectors than necessary because we don't use a rulehash for it. I plan to do that tomorrow assuming nothing else comes up.

Comment 1

[Emilio Cobos Álvarez (:emilio)]

Are they really so many to justify the extra cost? If so, fine, but some numbers would be on point :)

Comment 2

[Bobby Holley (:bholley)]

Even with the deduplication in bug 1358693, there are 220 revalidation selectors in the UA sheets alone: https://pastebin.mozilla.org/9020116

Comment 3

[Bobby Holley (:bholley)]

And to be clear, we obviously wouldn't use an ID or Class map. but the localname map seems pretty critical to avoiding most of that work on the common case.

Comment 4

[Emilio Cobos Álvarez (:emilio)]

Should we special-case those attributes and just compare them instead?

For example, assume that something with different `dir` attribute to the candidate will never share style? Sounds like a reasonable assumption for `dir` and `hidden`, at least.

Comment 5

[Emilio Cobos Álvarez (:emilio)]

Also for `align`.

Comment 6

[Emilio Cobos Álvarez (:emilio)]

They don't even need to be exclussive optimizations, I guess. Attributes that appear as standalone and we should consider optimizing are align, dir, and hidden. Then the local name rule hash seems on point for everything else.

Comment 7

[Bobby Holley (:bholley)]

(In reply to Emilio Cobos Álvarez [:emilio] from comment #6)
> They don't even need to be exclussive optimizations, I guess. Attributes
> that appear as standalone and we should consider optimizing are align, dir,
> and hidden. Then the local name rule hash seems on point for everything else.

We could, but that would be extra complexity for just a couple of selectors, and general make the system less general. Unless those standalone attribute selectors appear many times, it seems like roughly the same amount of work to match them as to explicitly compare them between the candidate and the cache entry.

I'm going to measure the overhead after adding the rulehash and then we can see if we should do more.

Comment 8

[Bobby Holley (:bholley)]

Also, we should rulehash the DependencySet while we're at it.

Comment 9

[Bobby Holley (:bholley)]

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

Comment 10

[Bobby Holley (:bholley)]

Attachment: Part 1 - Generalize SelectorMap. v1

MozReview-Commit-ID: HX4EcLurrr8

Comment 11

[Bobby Holley (:bholley)]

Attachment: Part 2 - Use a rule hash for revalidation selectors. v1

MozReview-Commit-ID: 1mTZcfMxaw8

Comment 12

[Bobby Holley (:bholley)]

Attachment: Part 3 - Re-enable the style sharing cache. v1

MozReview-Commit-ID: C39vdHjPM7J

Comment 13

[Bobby Holley (:bholley)]

Attachment: Part 4 - Use a rulehash for DependencySet. v1

MozReview-Commit-ID: GXu6O4kiBE6

Comment 14

[Bobby Holley (:bholley)]

The issue yesterday had to do with me having disabled the class and id rulehashes to deal with the fact that they might be different between the element and snapshot. Part 4 takes a different approach.

Comment 15

[Bobby Holley (:bholley)]

https://treeherder.mozilla.org/#/jobs?repo=try&revision=4f721524cd2649678e6d373057a4a9a8fc255f21

Comment 16

[Emilio Cobos Álvarez (:emilio)]

Comment on attachment 8864688 [details] [diff] [review]
Part 1 - Generalize SelectorMap. v1

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

I don't know what those functions are supposed to do, given there are no docs.

Looks generally reasonable to me, but will come back to stamp when I've read the rest of the patches.

::: servo/components/style/stylist.rs
@@ +1263,2 @@
>  
> +impl<T: Clone + Borrow<SelectorInner<SelectorImpl>>> SelectorMap<T> {

nit: Can you move the bounds to a where clause?

@@ +1301,5 @@
>  
> +    /// Looks up entries by id, class, local name, and other (in order).
> +    ///
> +    /// FIXME(bholley) This overlaps with SelectorMap<Rule>::get_all_matching_rules,
> +    /// but that function is extremely hot and I'd rather not rearrange it.

This needs documentation on what F should be and should do

@@ +1357,4 @@
>      }
>  
> +    /// Performs a normal lookup, and also looks up entries for the passed-in
> +    /// id and classes.

Same kind of docs.

Comment 17

[Emilio Cobos Álvarez (:emilio)]

Comment on attachment 8864689 [details] [diff] [review]
Part 2 - Use a rule hash for revalidation selectors. v1

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

::: servo/components/style/stylist.rs
@@ +850,5 @@
>          let len = self.selectors_for_cache_revalidation.len();
>          let mut results = BitVec::from_elem(len, false);
>  
> +        self.selectors_for_cache_revalidation.lookup(*element, &mut |selector| {
> +            results.push(matches_selector(selector,

Why is push() right here? You're doing effectively:

vec![false; len];

vec.push...

Which afaik won't alter the previous entries.

Also, this doesn't map all the selectors to the same entry in the BitVec, given we can skip selectors due to the rulehash, so this needs to be a bit smarter I think.

Comment 18

[Emilio Cobos Álvarez (:emilio)]

Comment on attachment 8864690 [details] [diff] [review]
Part 3 - Re-enable the style sharing cache. v1

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

This, on isolation, is fine.

Comment 19

[Emilio Cobos Álvarez (:emilio)]

Comment on attachment 8864691 [details] [diff] [review]
Part 4 - Use a rulehash for DependencySet. v1

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

This also looks fine.

::: servo/components/style/restyle_hints.rs
@@ +512,4 @@
>  
>  /// A set of dependencies for a given stylist.
>  ///
>  /// Note that there are measurable perf wins from storing them separately

This comment is not accurate anymore, I think, please remove it, or better yet, update it.

Comment 20

[Emilio Cobos Álvarez (:emilio)]

Comment on attachment 8864688 [details] [diff] [review]
Part 1 - Generalize SelectorMap. v1

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

r=me, with the docs.

::: servo/components/style/stylist.rs
@@ +1301,5 @@
>  
> +    /// Looks up entries by id, class, local name, and other (in order).
> +    ///
> +    /// FIXME(bholley) This overlaps with SelectorMap<Rule>::get_all_matching_rules,
> +    /// but that function is extremely hot and I'd rather not rearrange it.

Ok, so from the other patches the boolean argument is only to stop the lookup. Please document it.

Comment 21

[Bobby Holley (:bholley)]

(In reply to Emilio Cobos Álvarez [:emilio] from comment #17)
> Comment on attachment 8864689 [details] [diff] [review]
> Part 2 - Use a rule hash for revalidation selectors. v1
> 
> Review of attachment 8864689 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> ::: servo/components/style/stylist.rs
> @@ +850,5 @@
> >          let len = self.selectors_for_cache_revalidation.len();
> >          let mut results = BitVec::from_elem(len, false);
> >  
> > +        self.selectors_for_cache_revalidation.lookup(*element, &mut |selector| {
> > +            results.push(matches_selector(selector,
> 
> Why is push() right here? You're doing effectively:
> 
> vec![false; len];
> 
> vec.push...
> 
> Which afaik won't alter the previous entries.

Whoops, holdover from the old setup - that should have been BitVec::new.

> 
> Also, this doesn't map all the selectors to the same entry in the BitVec,
> given we can skip selectors due to the rulehash, so this needs to be a bit
> smarter I think.

The element and candidate are guaranteed to have the same id, classes, and local name, so they'll always get the same rulehash buckets. This is double-checked by the fact that we assert that the bitvec from the element and candidate are same-length.

Comment 22

[Emilio Cobos Álvarez (:emilio)]

Comment on attachment 8864689 [details] [diff] [review]
Part 2 - Use a rule hash for revalidation selectors. v1

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

Oh, right. Mind leaving it in a comment in the function?

(Perhaps an assertion would be even better, but since it'd be long maybe it doesn't matter that much).

With that bit fixed and the docs. r=me

Comment 23

[Bobby Holley (:bholley)]

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