Closed Bug 1368240 Opened 2 years ago Closed 2 years ago

stylo: Try to do better than eRestyle_Subtree for changes to selectors with descendant combinators.

Categories

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

enhancement

Tracking

()

RESOLVED FIXED
mozilla56
Tracking Status
firefox56 --- fixed

People

(Reporter: emilio, Assigned: emilio)

References

(Blocks 1 open bug)

Details

Attachments

(10 files, 2 obsolete files)

59 bytes, text/x-review-board-request
heycam
: review+
Details
59 bytes, text/x-review-board-request
heycam
: review+
Details
59 bytes, text/x-review-board-request
heycam
: review+
Details
59 bytes, text/x-review-board-request
heycam
: review+
Details
59 bytes, text/x-review-board-request
heycam
: review+
Details
59 bytes, text/x-review-board-request
heycam
: review+
Details
59 bytes, text/x-review-board-request
jryans
: review+
Details
59 bytes, text/x-review-board-request
jryans
: review+
Details
59 bytes, text/x-review-board-request
heycam
: review+
Details
59 bytes, text/x-review-board-request
heycam
: review+
Details
So I've been thinking a bit about how to handle changes to elements that match selectors with descendant combinators better than throwing a eRestyle_Subtree, and I think I've got a plan to do it nicely.

It seems this stuff is hitting on sites like Twitter (see bug 1342220 comment 22), so I think it's important to address.

The observation is that going into the DOM with a few selectors is always cheaper than doing a eRestyle_Subtree (which includes that work, plus styling, plus matching all the other selectors), except in the case when _all_ the descendants match the selector, which is not the usual case.

There are a few things we do for restyle hints that we could do much better:

 * We look to all the classes of the element when we could just look at the classes that changed.
 * Ditto for the ID. No need to look at selectors for that id if it didn't change.
 * We could try to do the same for other attributes, but it's not clear how to do it fast with the snapshot stuff.

On top of that, my plan would be something like the following:

 * Change RestyleHint to be a few flags again, and remove the "later siblings" hint. In particular, it should be able to represent:

    * The whole subtree is invalid (that's eRestyle_Subtree right now).
    * The element is invalid (that is, eRestyle_Self).
    * All the replacement stuff (this includes StyleAttribute, and the various animation hints).
    * We need to recascade the element style.

 * When we compute the changes for an element, we do have access to that element's descendants and later siblings. The idea is, roughly:

    * Store dependencies as the original selector and an index into it, instead of just the slice of the original selector.
    * Instead of computing (RestyleHint, bool), the bool representing the "later siblings bit", we'd compute _two_ sets of selectors, one for descendants, one for siblings, with the _full_ selector that dependency represented, instead of the partial one.
    * With those two selector sets, we traverse the DOM, and match against the descendants, inserting Self hints at them, and stopping if we see a Subtree hint.

Note that those two selector sets are intended to be a very small subset of the selectors of the page.

We could, instead of traversing the DOM in-place, do it as we go down the tree, but I can't find an easy way to do that off-hand without a lot of copying.

That would make the restyles in cases like bug 1342220 comment 22 and similar much cheaper.

Thoughts?
NI heycam, who is the expert in these classes of optimizations.
Flags: needinfo?(cam)
(In reply to Emilio Cobos Álvarez [:emilio] from comment #0)
>     * Store dependencies as the original selector and an index into it,
> instead of just the slice of the original selector.
>     * Instead of computing (RestyleHint, bool), the bool representing the
> "later siblings bit", we'd compute _two_ sets of selectors, one for
> descendants, one for siblings, with the _full_ selector that dependency
> represented, instead of the partial one.

Because we want to do a full selector match when we traverse down the tree, yes?

>     * With those two selector sets, we traverse the DOM, and match against
> the descendants, inserting Self hints at them, and stopping if we see a
> Subtree hint.
> 
> Note that those two selector sets are intended to be a very small subset of
> the selectors of the page.

Will it still be worth storing the selectors in SelectorMaps?

> We could, instead of traversing the DOM in-place, do it as we go down the
> tree, but I can't find an easy way to do that off-hand without a lot of
> copying.

Yeah, I guess that is one of the downsides of what Gecko is doing with the SomeDescendants stuff.  (It's not awful, because we maintain a single array of right-most selectors to check, that we expand and contract as we traverse down and up the tree.  Though that wouldn't be possible with the non-depth first traversal we've got.)

How much work would it be to do this in a separate parallel pass, prior to the actual restyle traversal?

> Thoughts?

I think this sounds good, and we should try it.

With the SomeDescendants work, I found it quite difficult to come up with a useful heuristic for when we should fall back to just propagating a RestyleSubtree, since it really depends on the structure of the DOM, so I was kind of conservative.  I'm not sure if we should have one here too, in terms of number of selectors in these two sets, or if we should just not bother.

Once you have some patches I'd love to see some timing comparisons of this versus just doing RestyleSubtree for some more pathalogical documents, like the full page HTML spec.
Flags: needinfo?(cam)
(In reply to Cameron McCormack (:heycam) from comment #2)
> (In reply to Emilio Cobos Álvarez [:emilio] from comment #0)
> >     * Store dependencies as the original selector and an index into it,
> > instead of just the slice of the original selector.
> >     * Instead of computing (RestyleHint, bool), the bool representing the
> > "later siblings bit", we'd compute _two_ sets of selectors, one for
> > descendants, one for siblings, with the _full_ selector that dependency
> > represented, instead of the partial one.
> 
> Because we want to do a full selector match when we traverse down the tree,
> yes?

Right.

> > Note that those two selector sets are intended to be a very small subset of
> > the selectors of the page.
> 
> Will it still be worth storing the selectors in SelectorMaps?

Maybe! I'll need to measure.

> > We could, instead of traversing the DOM in-place, do it as we go down the
> > tree, but I can't find an easy way to do that off-hand without a lot of
> > copying.

> Yeah, I guess that is one of the downsides of what Gecko is doing with the
> SomeDescendants stuff.  (It's not awful, because we maintain a single array
> of right-most selectors to check, that we expand and contract as we traverse
> down and up the tree.  Though that wouldn't be possible with the non-depth
> first traversal we've got.)
> 
> How much work would it be to do this in a separate parallel pass, prior to
> the actual restyle traversal?

Probably not too much. I think it may even be worth to do it sequentially on ContentStateChanged/AttributeChanged, given we have more info there about what changed and what not. In particular, we can check only the classes that changed (which may be important), or the attributes that changed...

> With the SomeDescendants work, I found it quite difficult to come up with a
> useful heuristic for when we should fall back to just propagating a
> RestyleSubtree, since it really depends on the structure of the DOM, so I
> was kind of conservative.  I'm not sure if we should have one here too, in
> terms of number of selectors in these two sets, or if we should just not
> bother.
> 
> Once you have some patches I'd love to see some timing comparisons of this
> versus just doing RestyleSubtree for some more pathalogical documents, like
> the full page HTML spec.

Sure.

I plan to start on this as soon as Bobby's patches that change how we store selectors land, given it probably changes how we store dependencies too.
Attached patch WIP (obsolete) — Splinter Review
So, I was on a train today, and this is what I got.

This implements my original idea of going down the tree checking compound selectors, instead of going down with the full subtree. I'm doing a release build right now, but this seems to be quite faster than what we do right now.

Thinks to note and measure:

 * Code needs to be cleaned up, and get properly tested (obviously). I just smoke tested this browsing through random websites in a debug build, but needs probably another day of work. I'm pretty sure there are rough edges and bugs.

 * Need to handle eRestyle_LaterSiblings manually in ServoRestyleManager instead of on the rust side (not that it's impossible to do it the other way around, but it's just annoying, and expanding it in PostRestyleEvent is easy enough).

 * Didn't account for :visited stuff yet, so I expect a few visited tests to fail with this patch. Should be easy to add.

 * I'm mapping from id/class to selector, so need to take into account quirkness of the document. I plan to reuse whatever machinery Simon ends up adding in https://github.com/servo/servo/pull/17213.

 * I thought about whether this can be made to blow up, but after thinking a bit into it, I think the worst case is having as many invalidations originating from a selector as compound selectors separated with ~ or descendant combinators, which is low. Invalidations are cheap (two words), and they match a single compound selector, so I don't think it will be an issue, but we can always bail out and restyle the world if we find too many invalidations.

After this, killing RestyleData is trivial, so I plan to do it next if this looks fine.
Assignee: nobody → emilio+bugs
Status: NEW → ASSIGNED
Attachment #8875804 - Flags: feedback?(cam)
Attachment #8875804 - Flags: feedback?(bobbyholley)
Attached patch fixes.diff (obsolete) — Splinter Review
Here are a few easy fixes on top of that patch. This makes us do the correct thing, actually.

Makes twitter way less Janky, and fixes bug 1365510 while at it.
Sorry I didn't get to this today, too much going on. Will look tomorrow.
Comment on attachment 8875804 [details] [diff] [review]
WIP

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

I think this generally looks good but I haven't the read entire patch super closely (since it's a bit hard to see which bits of code is new and which is just moved around, although I looked a bit closer at invalidation_map.rs and invalidator.rs).

::: servo/components/style/invalidation/element/invalidator.rs
@@ +306,5 @@
> +            );
> +        }
> +
> +        if any_children {
> +            unsafe { self.element.set_dirty_descendants() };

I guess having to do this will make it slightly harder to parallelize the processing of invalidations, if we wanted to try that later...

@@ +347,5 @@
> +                    if next_combinator.is_ancestor() {
> +                        descendant_invalidations.push(Invalidation {
> +                            selector: invalidation.selector.clone(),
> +                            offset: next_combinator_offset,
> +                        })

Is this sufficient to handle invalidation selectors like "div span > b" where the tree structure looks like for example <div><span><span><b>...</b></span></span></div>?  Don't we need to treat ">" and " " differently, where the latter needs to push two entries to descendant_invalidations, when it sees a span?  (One to handle the case where we've "correctly" chosen to match against the current span, using next_combinator_offset, and one to handle the case where we've "incorrectly" chosen to match agains the current span, by pushing it back with invalidation.offset?)
Attachment #8875804 - Flags: feedback?(cam) → feedback+
(In reply to Cameron McCormack (:heycam) from comment #7)
> Comment on attachment 8875804 [details] [diff] [review]
> WIP
> 
> Review of attachment 8875804 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> I think this generally looks good but I haven't the read entire patch super
> closely (since it's a bit hard to see which bits of code is new and which is
> just moved around, although I looked a bit closer at invalidation_map.rs and
> invalidator.rs).
> 
> ::: servo/components/style/invalidation/element/invalidator.rs
> @@ +306,5 @@
> > +            );
> > +        }
> > +
> > +        if any_children {
> > +            unsafe { self.element.set_dirty_descendants() };
> 
> I guess having to do this will make it slightly harder to parallelize the
> processing of invalidations, if we wanted to try that later...
> 
> @@ +347,5 @@
> > +                    if next_combinator.is_ancestor() {
> > +                        descendant_invalidations.push(Invalidation {
> > +                            selector: invalidation.selector.clone(),
> > +                            offset: next_combinator_offset,
> > +                        })
> 
> Is this sufficient to handle invalidation selectors like "div span > b"
> where the tree structure looks like for example
> <div><span><span><b>...</b></span></span></div>?  Don't we need to treat ">"
> and " " differently, where the latter needs to push two entries to
> descendant_invalidations, when it sees a span?  (One to handle the case
> where we've "correctly" chosen to match against the current span, using
> next_combinator_offset, and one to handle the case where we've "incorrectly"
> chosen to match agains the current span, by pushing it back with
> invalidation.offset?)

Yes, I noticed that too, I've refactored it and fixed that in the meantime. This is green:

https://treeherder.mozilla.org/#/jobs?repo=try&revision=36dc4f09373ae9ffda6450b49946555b443a0121&selectedJob=105766894

Modulo a timeout in layout/style/test/test_animations_omta.html, which I think it's just a pre-existing animation bug, but I'll debug it a bit more.
(Note that the crash in layout/base/crashtests/507119.html isn't due to this patch, but because my try run is based on a tree before the fix for the style sharing cache bump).
Comment on attachment 8876173 [details]
Bug 1368240: Add missing visitedness check.

https://reviewboard.mozilla.org/r/147586/#review151874

Looks good to me!  Thanks for updating the comments. :)
Attachment #8876173 - Flags: review?(jryans) → review+
Comment on attachment 8876174 [details]
Bug 1368240: Add an AllLinksVisitedAndUnvisited for selector-matching, and use it for invalidation.

https://reviewboard.mozilla.org/r/147588/#review151876

Thanks, seems good overall!

::: commit-message-8400f:5
(Diff revision 1)
> +Bug 1368240: Add an AllLinksVisitedAndUnvisited for selector-matching, and use it for invalidation. r?jryans
> +
> +Otherwise, tests like the following fail, given we always match as unvisited:
> +
> +<!doctype html>

Really wish we had a good way to land this test!  For now, I added reference to it in bug 1367186.

::: servo/components/selectors/matching.rs:98
(Diff revision 1)
>  #[derive(PartialEq, Eq, Copy, Clone, Debug)]
>  pub enum VisitedHandlingMode {
>      /// All links are matched as if they are unvisted.
>      AllLinksUnvisited,
> +    /// All links are matched as if they are visited and unvisited (both :link
> +    /// and :visited match).

Please expand this comment to explain this mode is only meant to be used for the invalidation / restyle detection path.

::: servo/components/selectors/matching.rs:257
(Diff revision 1)
>      /// exists for the element, and the visited handling mode is set to accept
>      /// relevant links as visited.
>      pub fn is_visited<E>(&self, element: &E, context: &MatchingContext) -> bool
>          where E: Element,
>      {
> +        if context.visited_handling == VisitedHandlingMode::AllLinksVisitedAndUnvisited {

Seems like this should be moved after the `is_link` check, to ensure it's actually linkable to begin with.

::: servo/components/selectors/matching.rs:282
(Diff revision 1)
>      /// visited handling mode is set to treat all links as unvisted (including
>      /// relevant links).
>      pub fn is_unvisited<E>(&self, element: &E, context: &MatchingContext) -> bool
>          where E: Element,
>      {
> +        if context.visited_handling == VisitedHandlingMode::AllLinksVisitedAndUnvisited {

Same here, move after `is_link`.
Attachment #8876174 - Flags: review?(jryans) → review+
Comment on attachment 8876174 [details]
Bug 1368240: Add an AllLinksVisitedAndUnvisited for selector-matching, and use it for invalidation.

https://reviewboard.mozilla.org/r/147588/#review151876

> Seems like this should be moved after the `is_link` check, to ensure it's actually linkable to begin with.

Ick, good catch.
Comment on attachment 8875804 [details] [diff] [review]
WIP

Per IRC discussion, please measure the impact on stylist::update. Otherwise, this sounds great! I don't have an in-depth picture of how the guts of the subtree analysis work, but I'll defer that to heycam.
Attachment #8875804 - Flags: feedback?(bobbyholley) → feedback+
Blocks: 1366422
This is with all the patches rebased to autoland on top of heycam's selector-matching changes.

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

Note that this still doesn't fix bug 1371130. I'm deferring it because we need a kind of iterator where we iterate over the DOM children, but also over pseudo-elements.
(In reply to Bobby Holley (:bholley) (busy with Stylo) from comment #33)
> Comment on attachment 8875804 [details] [diff] [review]
> WIP
> 
> Per IRC discussion, please measure the impact on stylist::update. Otherwise,
> this sounds great! I don't have an in-depth picture of how the guts of the
> subtree analysis work, but I'll defer that to heycam.

Without this patch:

 * https://perfht.ml/2rMyjjt

With this patch:

 * https://perfht.ml/2rMEKmH

That is, about 15ms more in Stylist::add_stylesheet, most (all? :O) of it in the HashMap::entry API. That is, in the maps that take care of storing by class or id.

Memory usage seems to be slightly lower with this patch (presumably because of RestyleData and Dependency being smaller, even though we have more dependencies).

Thinks I could do:

 * Store all the dependencies together as they were (but this makes us scan way more dependencies, which is undesirable IMO).
 * Look into why ::entry is so slow, presumably we're hashing the hash as we were doing with the bloom filter.

But I don't think it's too much of a price to pay, and I definitely think I can shrink that back to where it was (either doing one of the above things, or coalescing calls to visit_selector, etc).

If you're very very concerned about those 15ms right now, I could do one of those before landing, but I'd prefer to investigate afterwards, my feeling is that we're doing some very dumb stuff while hashing atoms, and that would also affect all the SelectorMaps.

Also, since Cameron asked me to do some profiling on the HTML spec, I did so. Adding the following script to the HTML spec:

document.onclick = function() {
	document.documentElement.offsetTop;
	var start = Date.now();
	document.documentElement.classList.toggle('status-LS-COMMIT');
	document.documentElement.offsetTop;
	alert(Date.now() - start);
}

(The class name is one that is chosen carefully to not make us reflow the whole document, because that takes most of the time otherwise).

I get:

 * Stock Gecko: 800ms
 * Stylo without my patch: 2218ms.
 * Blink: 42ms
 * Stylo with my patch: 40ms

So I'm assuming Blink is doing a very similar analysis (and from looking at RuleFeature.cpp[1], it seems they build a list of classes, tag names, etc for descendants, instead of running selector-matching right to left, so I expect them to do worse at ">" and "+" combinators, for that matter). They seem to process everything in another phase, called StyleInvalidation[2].

Toggling a selector that affects everything, which is pretty much the worse case, like "bad" instead of "status-LS-COMMIT", which has a rule like:

  .bad, .bad *:not(.X\58X) { color: gray; border-color: gray; background: transparent; }

(That is, pretty much everything needs to be invalidated)

I get:

 * Stock Gecko: 800ms
 * Stylo without my patch: 2305ms
 * Blink: 925ms
 * Stylo with my patch: 2328ms

So it seems the invalidation phase, even when restyling the whole subtree, is not going to be a problem (we could check for universal selectors and what not in this case).

We should probably look into what makes our restyling take double in the HTML Spec. I took a profile (https://perfht.ml/2rhqkax), and Styling seems comparable to Gecko or Blink, but seems we're doing a lot of reflow that just isn't there on Stock Gecko.

Anyway, that's all I've got to say re. perf with this patch so far, thoughts appreciated :)

[1]: https://cs.chromium.org/chromium/src/third_party/WebKit/Source/core/css/RuleFeature.cpp?gsn=ScheduleInvalidationSetsForNode&l=689
[2]: https://cs.chromium.org/chromium/src/third_party/WebKit/Source/core/css/invalidation/StyleInvalidator.cpp
See Also: → 1371955
> but seems we're doing a lot of reflow that just isn't there on Stock Gecko.

You might be able to separate these out by doing:

  getComputedStyle(document.documentElement).color

instead of the second "document.documentElement.offsetTop" to just trigger restyling but not reflow, at least in Gecko.
(In reply to Boris Zbarsky [:bz] (if a patch has no decent message, automatic r-) from comment #36)
> > but seems we're doing a lot of reflow that just isn't there on Stock Gecko.
> 
> You might be able to separate these out by doing:
> 
>   getComputedStyle(document.documentElement).color
> 
> instead of the second "document.documentElement.offsetTop" to just trigger
> restyling but not reflow, at least in Gecko.

That's true, but that doesn't explain why we consistently reflow, which is what bug 1371955 is about... Perhaps some stale change hint state or something like that? I need to investigate.
Sure, I'm just saying this might give a way to measure just the styling time so that can be compared directly.

We do need to sort out bug 1371955.
See Also: → 1371975
Just for the record, with the fix in bug 1371955, the counter style comparison that makes us reflow the world commented out, and the same for the first-line thing that makes us reframe a bunch of <pre>s, I get ~950ms in total, of which 450+ are in the post-traversal:

 * https://perfht.ml/2rOKKLt
Attachment #8875838 - Attachment is obsolete: true
Attachment #8875804 - Attachment is obsolete: true
See Also: → 1372058
I found bug 1372058, which is an easy way to take back that extra Stylist::update time right now :)
Comment on attachment 8876167 [details]
Bug 1368240: Manually expand later sibling hints.

https://reviewboard.mozilla.org/r/147574/#review152232

::: commit-message-68f27:1
(Diff revision 3)
> +Bug 1368240: Manually expand later sibling hints. r?heycam
> +

Can you comment here in the commit message why we need to do this, because all else being equal, it's better to expand them later, during traversal, to avoid doing the traversal here too.  (I gather it's to help in shrinking the RestyleHint data.)
Attachment #8876167 - Flags: review?(cam) → review+
Comment on attachment 8876168 [details]
Bug 1368240: Record whether an snapshot is recording a class attribute change or id change.

https://reviewboard.mozilla.org/r/147576/#review152240

::: layout/style/ServoElementSnapshot.h:95
(Diff revision 3)
>    /**
>     * Captures the given element attributes (if not previously captured).
>     */

Please mention in the comment what the two new arguments are used for.

::: servo/components/style/gecko/snapshot.rs:71
(Diff revision 3)
> +    #[inline]
> +    pub fn id_changed(&self) -> bool {
> +        self.mIdAttributeChanged()
> +    }
> +
> +    /// Returns true if the snapshot recorded an id change.

s/an id/a class/
Attachment #8876168 - Flags: review?(cam) → review+
Comment on attachment 8876169 [details]
Bug 1368240: Add a way to match a single compound selector, and improve ergonomics of matches_complex_selector.

https://reviewboard.mozilla.org/r/147578/#review152242

::: servo/components/selectors/matching.rs:470
(Diff revision 3)
> -    matches_complex_selector(&selector, offset, element, &mut local_context, flags_setter)
> +    let iter = if offset == 0 {
> +        selector.iter()
> +    } else {
> +        selector.iter_from(offset)
> +    };

I know this is just moving code, but I wonder as a follow up whether we should make iter_from() do this check for offset == 0 and defer to iter(), rather than make callers do it.

::: servo/components/selectors/matching.rs:484
(Diff revision 3)
> +/// selector inside the complex selector.
> +pub enum CompoundSelectorMatchingResult {
> +    /// The compound selector matched, and the next combinator offset is
> +    /// `next_combinator_offset`.
> +    ///
> +    /// If the next combinator offset is zero, it means that its' the rightmost

s/its'/it's/

::: servo/components/selectors/matching.rs:490
(Diff revision 3)
> +/// Matches a compound selector belonging to `selector`, starting at offset
> +/// `from_offset` _from the left_.

This sounds like the index counts from the left, but I think it's the matching that happens from the left.  Please reword to clarify.

::: servo/components/selectors/matching.rs:504
(Diff revision 3)
> +    if cfg!(debug_assertions) {
> +        selector.combinator_at(from_offset); // This asserts.
> +    }

Can you mention in the doc comment that from_offset must point to a combinator.

::: servo/components/selectors/matching.rs:509
(Diff revision 3)
> +    if cfg!(debug_assertions) {
> +        selector.combinator_at(from_offset); // This asserts.
> +    }
> +
> +    let mut local_context = LocalMatchingContext::new(context, selector);
> +    for component in selector.iter_raw_rev_from(from_offset - 1) {

I find the indexing a bit confusing, but I convinced myself it's right. :-)  One thing is that it seems it's impossible to match on the left-most sequence of simple selectors, because there's no combinator to point to.  I guess we happen not to need this, but it would be good to mention it in the doc comment too.

::: servo/components/selectors/matching.rs:542
(Diff revision 3)
> -    let mut iter = if offset == 0 {
> -        complex_selector.iter()
> -    } else {
> -        complex_selector.iter_from(offset)
> -    };
>  

Nit: Drop this blank line?

::: servo/components/selectors/parser.rs:441
(Diff revision 3)
>              iter: iter,
>              next_combinator: None,
>          }
>      }
>  
> -    /// Returns an iterator over the entire sequence of simple selectors and combinators,
> +    pub fn iter_until(&self, offset: usize) -> SelectorIter<Impl> {

Please add a doc comment.

::: servo/components/selectors/parser.rs:473
(Diff revision 3)
> +    /// Returns an iterator over the entire sequence of simple selectors and
> +    /// combinators, from left to right, from the offset `offset`.
> +    pub fn iter_raw_rev_from(&self, offset: usize) -> slice::Iter<Component<Impl>> {
> +        self.0.slice[(self.0.slice.len() - offset)..].iter()
> +    }

I guess it's not the entire sequence of simple selectors and combinators, since we're limiting it by the use of the offset.
Attachment #8876169 - Flags: review?(cam) → review+
Comment on attachment 8876170 [details]
Bug 1368240: Also print the class name when logging elements.

https://reviewboard.mozilla.org/r/147580/#review152250
Attachment #8876170 - Flags: review?(cam) → review+
Comment on attachment 8876171 [details]
Bug 1368240: Implement a more fine-grained invalidation method.

https://reviewboard.mozilla.org/r/147582/#review152256

This looks good!  A bunch of (mostly small) comments, so might take a look at one more version of the patch.

::: servo/components/style/data.rs:528
(Diff revision 3)
> -    /// Computes the final restyle hint for this element, potentially allocating
> -    /// a `RestyleData` if we need to.
> +    /// Invalidates style for this element if needed due to a style change, and
> +    /// invalidates also descendants or sibling styles too if needed.

Nit: Maybe say that it does this based on the snapshot?  So maybe something like the following:

  /// Invalidates style for this element, its descendants, and later siblings,
  /// based on the snapshot in this `ElementData`.

::: servo/components/style/data.rs:537
(Diff revision 3)
>      {
> -        debug!("compute_final_hint: {:?}, {:?}",
> +        use invalidation::element::invalidator::TreeStyleInvalidator;
> -               element,
> -               shared_context.traversal_flags);
>  
> -        let mut hint = match self.get_restyle() {
> +        debug!("compute_final_hint: {:?}, flags: {:?}, has_snapshot: {}, \

Update the function name here.

::: servo/components/style/invalidation/element/invalidation_map.rs:84
(Diff revision 3)
> +    /// NOTE(emilio): pseudo-elements need to be here to account for eager
> +    /// pseudos, so the state doesn't get out of sync.

By state do you mean ElementState?  Or something else?

::: servo/components/style/invalidation/element/invalidation_map.rs:137
(Diff revision 3)
> +/// This is slightly different to a SelectorMap, in the sense of that the same
> +/// selector may appear multiple times.

So a given selector (well, slice of a selector) will still only appear once in a given SelectorMap under the InvalidationMap, but may appear in class_to_selector and in id_to_selector, etc.?

::: servo/components/style/invalidation/element/invalidation_map.rs:148
(Diff revision 3)
> +    /// A map from a given id to all the selectors with that ID in the document.
> +    pub id_to_selector: FnvHashMap<Atom, SelectorMap<Dependency>>,

By "in the document" do you mean that this will only includes selectors containing IDs that are used on elements in the document?  (Not clear whether it says that, or the "in the document" applies to "selectors with that ID".)

::: servo/components/style/invalidation/element/invalidation_map.rs:150
(Diff revision 3)
> +    /// A map of all the state dependencies.
> +    pub state_affecting_selectors: SelectorMap<StateDependency>,

Is it a deliberate choice not to make this some kind of table mapping ElementState bits to SelectorMaps, maybe because we don't tend to have as many rules involving state-based pseudo-classes as other kinds of rules?

::: servo/components/style/invalidation/element/invalidation_map.rs:197
(Diff revision 3)
> +fn is_non_id_or_class_attr_based_selector(sel: &Component<SelectorImpl>) -> bool {
> +    match *sel {
> +        Component::AttributeInNoNamespaceExists { .. } |
> +        Component::AttributeInNoNamespace { .. } |
> +        Component::AttributeOther(_) => true,
> +        Component::NonTSPseudoClass(ref pc) => pc.is_attr_based(),
> +        _ => false,
> +    }
> +}

The name is a little misleading (I think) because we could still have selectors like [class=x] which will return true, even though it is based on a class attribute.

Can you either check for this, or verify that we'll do the right thing when checking dependencies like [class=x] and a comment here (and maybe also up on InvalidationMap::other_attribute_affecting_selectors) pointing out that dependencies on id and class can creep in here like this.

::: servo/components/style/invalidation/element/invalidation_map.rs:221
(Diff revision 3)
> +        Component::NonTSPseudoClass(ref pc) => pc.state_flag(),
> +        _ => ElementState::empty(),
> +    }
> +}
> +
> +/// A structs that collects invalidations for a given compound selector.

*A struct

::: servo/components/style/invalidation/element/invalidation_map.rs:228
(Diff revision 3)
> +    /// NB: This will be almost always a single, class, but could be multiple in
> +    /// presence of :not, :-moz-any, .foo.bar.baz, etc.

s/single, class/single class/

Also I think .foo.bar.baz selectors aren't that uncommon... so maybe s/almost always/often/? :-)

::: servo/components/style/invalidation/element/invalidation_map.rs:234
(Diff revision 3)
> +    /// NB: This will be almost always a single, class, but could be multiple in
> +    /// presence of :not, :-moz-any, #foo#bar, etc.

s/single, class/single ID/

::: servo/components/style/invalidation/element/invalidation_map.rs:238
(Diff revision 3)
> +    /// Whether it affects other attributes that aren't ID or class.
> +    other_attributes: bool,

Oh, comment here too if we make is_non_id_or_class_attr_based_selector continue to return true for [class] and [id].

::: servo/components/style/invalidation/element/invalidation_map.rs:267
(Diff revision 3)
> +    fn collect_invalidations_for(
> +        &mut self,
> +        selector_and_hashes: &SelectorAndHashes<SelectorImpl>)

Since we only create a DependencyCollector object in one place, to call collect_invalidations_for on it, maybe we can just move this to be a function on InvalidationMap itself.

::: servo/components/style/invalidation/element/invalidation_map.rs:291
(Diff revision 3)
> +            // NB(emilio): This calls visit_complex_selector properly, we just
> +            // need to record the proper state. Even with that is not clear we
> +            // should do anything?

I didn't quite understand this...

::: servo/components/style/invalidation/element/invalidation_map.rs:303
(Diff revision 3)
> +            let mut get_hashes = || -> AncestorHashes {
> +                if hashes.is_none() {
> +                    hashes = Some(if sequence_start == 0 {
> +                        selector_and_hashes.hashes.clone()
> +                    } else {
> +                        let seq_iter = selector_and_hashes.selector.iter_from(sequence_start);
> +                        AncestorHashes::from_iter(seq_iter)
> +                    });
> +                }
> +                hashes.clone().unwrap()
> +            };

Aside: after looking at AncestorHashes::from_iter, I wonder if it should be trying to avoid including duplicate hashes, so that for selectors like |body > div > div > [...]| we could store two hashes instead of three.

::: servo/components/style/invalidation/element/invalidation_map.rs:303
(Diff revision 3)
> +
> +            // Reuse the bloom hashes if this is the base selector. Otherwise,
> +            // rebuild them.
> +            let mut hashes = None;
> +
> +            let mut get_hashes = || -> AncestorHashes {

Is the explicit return type needed here?

::: servo/components/style/invalidation/element/invalidator.rs:37
(Diff revision 3)
> +/// An invalidation represents either a compound selector, which needs to match
> +/// in order to alter style of the element, or the whole complex selector.
> +///
> +/// Note that it only actually "dirties" the element, if the offset is zero,
> +/// that is, if we've arrived to the end of the selector.

I wonder if this might be clearer expressed something like this:

  An `Invalidation` is a complex selector that describes which elements,
  relative to a current element we are processing, must be restyled.
  When `offset` points to the right-most compound selector in `selector`,
  then the Invalidation `represents` the fact that the current element
  must be restyled if the compound selector matches.  Otherwise, if
  describes which descendants (or later siblings) must be restyled.

::: servo/components/style/invalidation/element/invalidator.rs:64
(Diff revision 3)
> +    invalidated_self: bool,
> +    effective_for_next: bool,

Please document what these fields mean (especially "effective_for_next", which isn't obvious).

::: servo/components/style/invalidation/element/invalidator.rs:92
(Diff revision 3)
> +        let wrapper =
> +            ElementWrapper::new(self.element, shared_context.snapshot_map);

Nit: You know our preferred line limit is 99 characters, right? ;-)

::: servo/components/style/invalidation/element/invalidator.rs:132
(Diff revision 3)
> +            }
> +        }
> +
> +        let lookup_element =
> +            if self.element.implemented_pseudo_element().is_some() {
> +                self.element.closest_non_native_anonymous_ancestor().unwrap()

I think we should probably make pseudo_element_originating_element a function on TElement so that we can call it here, since it's a clearer description of what we need.

::: servo/components/style/invalidation/element/invalidator.rs:189
(Diff revision 3)
> +
> +            collector.invalidates_self
> +        };
> +
> +        if invalidated_self {
> +            if let Some(ref mut data) = self.data {

Why is TreeStyleInvalidator::data an Option?  Are there situations where we can encounter an Element with no ElementData, as we propagate the Invalidations, but then upon propagating them even further, we find Elements that do have ElementData?

It seems like as soon as we hit an Element that has no ElementData we can stop propagating the invalidations, but maybe there is a case I haven't thought of.

::: servo/components/style/invalidation/element/invalidator.rs:213
(Diff revision 3)
> +        if sibling_invalidations.is_empty() {
> +            return false;
> +        }

May as well do that first?

::: servo/components/style/invalidation/element/invalidator.rs:319
(Diff revision 3)
> +    /// The sibling invalidations are somewhat special because they can be
> +    /// modified on the fly. New invalidations may be added and removed.

Can you explain a bit more about the difference between propagating invalidations to descendants and propagating to later siblings?  Don't they add and remove invalidations in the same way?

::: servo/components/style/invalidation/element/invalidator.rs:340
(Diff revision 3)
> +            if !result.effective_for_next {
> +                sibling_invalidations.remove(i);

For a moment I was concerned about the removal of invalidations as we traverse the later siblings, because which element "~" traverses too might be different after some DOM mutations, but I guess the NODE_HAS_SLOW_SELECTOR_LATER_SIBLINGS flag handles that case for us?

::: servo/components/style/invalidation/element/invalidator.rs:470
(Diff revision 3)
> +        let removed_id = self.removed_id;
> +        let classes_removed = self.classes_removed;
> +        let lookup_element = self.lookup_element;
> +        map.lookup_with_additional(
> +            lookup_element,
> +            removed_id,
> +            classes_removed,

Can you just write:

  map.lookup_with_additional(
      self.lookup_element,
      self.removed_id,
      ...

instead of using the local variables?

::: servo/components/style/invalidation/element/invalidator.rs:488
(Diff revision 3)
> +        let removed_id = self.removed_id;
> +        let classes_removed = self.classes_removed;
> +        let lookup_element = self.lookup_element;
> +
> +        map.lookup_with_additional(
> +            lookup_element,
> +            removed_id,
> +            classes_removed,

Here too.

::: servo/components/style/invalidation/element/invalidator.rs:511
(Diff revision 3)
> +    fn scan_dependency(&mut self, dependency: &Dependency) {
> +        if !self.dependency_may_be_relevant(dependency) {
> +            return;
> +        }
> +
> +        // TODO(emilio): Bloom filter here!

Might be worth carrying over the comment from restyle_hints.rs talking about considerations for the Bloom filter usage here on the real element vs the snapshot.

::: servo/components/style/invalidation/element/invalidator.rs:565
(Diff revision 3)
> +                offset: dependency.selector_offset,
> +            });
> +        }
> +    }
> +
> +    fn dependency_may_be_relevant(&self, dependency: &Dependency) -> bool {

Add a comment here explaining what "relevant" means.

::: servo/components/style/invalidation/element/restyle_hints.rs:13
(Diff revision 3)
> +        /// Do a selector match of the element.
> +        const RESTYLE_SELF = 1 << 0,
> +        /// Do a selector match of the element and all its descendants.
> +        const RESTYLE_DESCENDANTS = 1 << 1,
> +        /// Recascade the current element.
> +        const RECASCADE_SELF = 1 << 2,
> +        /// Recascade all descendant elements.
> +        const RECASCADE_DESCENDANTS = 1 << 3,
> +        /// Replace the style data coming from CSS transitions without updating
> +        /// any other style data. This hint is only processed in animation-only
> +        /// traversal which is prior to normal traversal.
> +        const RESTYLE_CSS_TRANSITIONS = 0x10,

Nit: put blank lines betweeen the first four (since we do it for the last few) and use consistent numbering (i.e. all `1 << n` or all `0xnn`).

::: servo/components/style/invalidation/element/restyle_hints.rs:98
(Diff revision 3)
> +    /// Returns whether the hint specifies that later siblings must be restyled.
> +    #[inline]
> +    pub fn affects_later_siblings(&self) -> bool {
> +        false
> +    }

Can we remove this?

::: servo/components/style/invalidation/element/restyle_hints.rs:114
(Diff revision 3)
> +    pub fn has_non_animation_hint(&self) -> bool {
> +        (*self & Self::for_animations()) == Self::empty()
> +    }

Is this wrong?  It looks like you're looking for whether we have no animation hints.

::: servo/components/style/invalidation/element/restyle_hints.rs:187
(Diff revision 3)
> +#[cfg(feature = "servo")]
> +impl ::heapsize::HeapSizeOf for RestyleHint {
> +    fn heap_size_of_children(&self) -> usize { 0 }
> +}
> +
> +/// Asserts that all RestyleReplacements have a matching nsRestyleHint value.

s/RestyleReplacements/replacement RestyleHints/

::: servo/components/style/invalidation/element/restyle_hints.rs:196
(Diff revision 3)
> +                let mut replacements = RestyleHint::all();
> +                $(
> +                    assert_eq!(structs::$a.0 as usize, $b.bits() as usize, stringify!($b));
> +                    replacements.remove($b);
> +                )*
> +                // assert_eq!(replacements, RestyleReplacements::empty(),
> +                //            "all RestyleReplacements bits should have an assertion");

Make this start as RestyleHint::replacements() instead of RestyleHint::all(), then you can uncomment the other assertion.

::: servo/components/style/traversal.rs:247
(Diff revision 3)
>          // Expanding snapshots here may create a LATER_SIBLINGS restyle hint, which
>          // we propagate to the next sibling element.

Please update this comment.

::: servo/components/style/traversal.rs:250
(Diff revision 3)
> -            let later_siblings =
> -                data.compute_final_hint(root,
> +            data.invalidate_style_if_needed(
> +                root,
> -                                        shared_context,
> +                shared_context,
> -                                        HintComputationContext::Root);
> +            );

Small nit, but wouldn't this be easier to read on a single line?  It would only reach column 66! :-)

::: servo/components/style/traversal.rs:871
(Diff revision 3)
>          // Handle element snapshots and sibling restyle hints.
>          //
>          // NB: This will be a no-op if there's no restyle data and no snapshot.

Please update this comment, since there should be no sibling restyle hints outside of Gecko any more.

::: servo/components/style/traversal.rs:896
(Diff revision 3)
>              continue;
>          }
>  
>          let mut restyle_data = child_data.ensure_restyle();
>  
>          // Propagate the parent and sibling restyle hint.

This comment too.
Comment on attachment 8876172 [details]
Bug 1368240: Properly handle invalidation of eager pseudo-elements with the new setup.

https://reviewboard.mozilla.org/r/147584/#review152308

::: servo/components/style/invalidation/element/invalidator.rs:407
(Diff revision 3)
>          );
>  
>          let mut invalidated_self = false;
>          match matching_result {
>              CompoundSelectorMatchingResult::Matched { next_combinator_offset: 0 } => {
> +                debug!("> Invalidation matched completely");

Nit: I notice you normally put a space before ">" in these debug message, so maybe you want one here too.

(These added debug!() statements probably belong in the previous patch.)

::: servo/components/style/invalidation/element/invalidator.rs:443
(Diff revision 3)
> +                        if let Some(ref mut data) = self.data {
> +                            data.ensure_restyle().hint.insert(RESTYLE_SELF.into());
> +                        }
> +                        invalidated_self = true;

Can you factor out this block (since we do the same above for a normal CompoundSelectorMatchingResult::Matched when we reach the end), and do it after the match statement?
Attachment #8876172 - Flags: review?(cam) → review+
Comment on attachment 8876175 [details]
Bug 1368240: Update test expectations.

https://reviewboard.mozilla.org/r/147592/#review152314
Attachment #8876175 - Flags: review?(cam) → review+
Comment on attachment 8876535 [details]
Bug 1368240: Very basic smoketests for this.

https://reviewboard.mozilla.org/r/147862/#review152316

::: commit-message-3f90f:3
(Diff revision 1)
> +Bug 1368240: Very basic smoketests for this. r?heycam
> +
> +I need to add an API to WindowUtils to tests this further I fear.

s/tests/test/

::: layout/style/test/test_invalidation_basic.html:4
(Diff revision 1)
> +<!doctype html>
> +<meta charset="utf-8">
> +<title>
> +  Test for bug 1368240: We only invalidate style as less as needed

*as little as needed

::: layout/style/test/test_invalidation_basic.html:28
(Diff revision 1)
> +<script>
> +SimpleTest.waitForExplicitFinish();
> +const utils = SpecialPowers.getDOMWindowUtils(window);
> +
> +// TODO(emilio): Add an API to get the style contexts we've recreated, to make
> +// more elaborated tests.

*elaborated
Attachment #8876535 - Flags: review?(cam) → review+
Comment on attachment 8876171 [details]
Bug 1368240: Implement a more fine-grained invalidation method.

https://reviewboard.mozilla.org/r/147582/#review152256

> By state do you mean ElementState?  Or something else?

I clarified the comment.

> So a given selector (well, slice of a selector) will still only appear once in a given SelectorMap under the InvalidationMap, but may appear in class_to_selector and in id_to_selector, etc.?

Right.

> By "in the document" do you mean that this will only includes selectors containing IDs that are used on elements in the document?  (Not clear whether it says that, or the "in the document" applies to "selectors with that ID".)

Also clarified :)

> Is it a deliberate choice not to make this some kind of table mapping ElementState bits to SelectorMaps, maybe because we don't tend to have as many rules involving state-based pseudo-classes as other kinds of rules?

Yeah, it didn't seem worth it given we have the exact changed state handy when invalidating, and we can reject them pretty easily. Also, we'd have to iterate over all the possible states and do a hashmap lookup for each, which may get hairy.

> The name is a little misleading (I think) because we could still have selectors like [class=x] which will return true, even though it is based on a class attribute.
> 
> Can you either check for this, or verify that we'll do the right thing when checking dependencies like [class=x] and a comment here (and maybe also up on InvalidationMap::other_attribute_affecting_selectors) pointing out that dependencies on id and class can creep in here like this.

Eek, great catch, I totally overlooked [class] and [id] selectors, I've added a fix with a test :)

> s/single, class/single class/
> 
> Also I think .foo.bar.baz selectors aren't that uncommon... so maybe s/almost always/often/? :-)

Fair enough :)

> Oh, comment here too if we make is_non_id_or_class_attr_based_selector continue to return true for [class] and [id].

My fix makes it clearer, I hope :)

> Since we only create a DependencyCollector object in one place, to call collect_invalidations_for on it, maybe we can just move this to be a function on InvalidationMap itself.

Done, yeah. Inititally DependencyCollector was going to be a bit more complex... will do.

> I didn't quite understand this...

My point was that if we allowed combinators, etc in `:not`, it's not clear we'd need to track more dependencies, only noting that the `:not` selector could affect descendants... Though perhaps it's worth to just track them as a normal dependency? I don't know, I've restored the original comment :)

> Aside: after looking at AncestorHashes::from_iter, I wonder if it should be trying to avoid including duplicate hashes, so that for selectors like |body > div > div > [...]| we could store two hashes instead of three.

AncestorHashes is fixed-size, and checking them is relatively easy... But yeah. Right now they're not used at all, I plan to re-introduce the bloom filter here or, alternatively, drop them to save the memory and time to compute them.

> Is the explicit return type needed here?

I guess it's not, but I found it more obvious to read.

> I wonder if this might be clearer expressed something like this:
> 
>   An `Invalidation` is a complex selector that describes which elements,
>   relative to a current element we are processing, must be restyled.
>   When `offset` points to the right-most compound selector in `selector`,
>   then the Invalidation `represents` the fact that the current element
>   must be restyled if the compound selector matches.  Otherwise, if
>   describes which descendants (or later siblings) must be restyled.

Yup, indeed, thanks! :)

> Nit: You know our preferred line limit is 99 characters, right? ;-)

Hmmm... https://github.com/servo/servo/blob/master/rustfmt.toml#L1 :)

> I think we should probably make pseudo_element_originating_element a function on TElement so that we can call it here, since it's a clearer description of what we need.

We already have it (on `selectors::tree::Element`)! Will use that instead :)

> Why is TreeStyleInvalidator::data an Option?  Are there situations where we can encounter an Element with no ElementData, as we propagate the Invalidations, but then upon propagating them even further, we find Elements that do have ElementData?
> 
> It seems like as soon as we hit an Element that has no ElementData we can stop propagating the invalidations, but maybe there is a case I haven't thought of.

So I did this thinking on the case of a new element with no data in a row of siblings.

If we had a selector like `.foo + div + div`, and we had three divs in a row, the first of which gets the class `foo`, and the second of which has no data, if we just didn't do the processing, we'd never restyle the third.

Perhaps you're right the later siblings flags save us here, but seemed simple enough to support...

> May as well do that first?

Yup!

> Can you explain a bit more about the difference between propagating invalidations to descendants and propagating to later siblings?  Don't they add and remove invalidations in the same way?

Not really, for siblings we change the invalidation vector on the fly.

In particular, all descendants get the same set of invalidations from the parent, but the invalidations from a given sibling depend on the ones we got from the previous one.

> For a moment I was concerned about the removal of invalidations as we traverse the later siblings, because which element "~" traverses too might be different after some DOM mutations, but I guess the NODE_HAS_SLOW_SELECTOR_LATER_SIBLINGS flag handles that case for us?

Yeah, for `~` it shouldn't matter, because we won't remove it (`effective_for_next` would be true), but for `+` it might. That being said, I think in this case we're saved by the slow selector flags, yeah.

> Can you just write:
> 
>   map.lookup_with_additional(
>       self.lookup_element,
>       self.removed_id,
>       ...
> 
> instead of using the local variables?

I thought no, because then rust would think I'm borrowing `self` and gets pissed off at me below in the closure... But I can, so will do.

> Can we remove this?

Yup!

> Is this wrong?  It looks like you're looking for whether we have no animation hints.

D'oh. Hopefully enough it was only used for an assertion :)

> Small nit, but wouldn't this be easier to read on a single line?  It would only reach column 66! :-)

Right, this was an artifact of having removed the `HintComputationContext` stuff. Will merge into a line.
Comment on attachment 8876169 [details]
Bug 1368240: Add a way to match a single compound selector, and improve ergonomics of matches_complex_selector.

https://reviewboard.mozilla.org/r/147578/#review152242

> I know this is just moving code, but I wonder as a follow up whether we should make iter_from() do this check for offset == 0 and defer to iter(), rather than make callers do it.

Agreed.

> Please add a doc comment.

I just removed it, since it was unused.

> I guess it's not the entire sequence of simple selectors and combinators, since we're limiting it by the use of the offset.

Fixed, thanks :)
Comment on attachment 8876167 [details]
Bug 1368240: Manually expand later sibling hints.

https://reviewboard.mozilla.org/r/147574/#review152232

> Can you comment here in the commit message why we need to do this, because all else being equal, it's better to expand them later, during traversal, to avoid doing the traversal here too.  (I gather it's to help in shrinking the RestyleHint data.)

Yeah, it's due to that and to reduce complexity in general. Will note in the commit message.
Comment on attachment 8876172 [details]
Bug 1368240: Properly handle invalidation of eager pseudo-elements with the new setup.

https://reviewboard.mozilla.org/r/147584/#review152308

> Can you factor out this block (since we do the same above for a normal CompoundSelectorMatchingResult::Matched when we reach the end), and do it after the match statement?

Agreed, done :)
Comment on attachment 8876171 [details]
Bug 1368240: Implement a more fine-grained invalidation method.

https://reviewboard.mozilla.org/r/147582/#review152674

Looks great, thanks!

::: servo/components/style/invalidation/element/invalidation_map.rs:350
(Diff revisions 3 - 4)
> +    ///
> +    /// NB: This will be almost always a single id, but could be multiple in
> +    /// presence of :not, :-moz-any, #foo#bar, etc.
> +    ids: SmallVec<[Atom; 5]>,
> +
> +    /// Whether it affects other attributes that aren't ID or class.

This comment isn't entirely accurate, since we'll still set it even if the only thing we find is e.g. [class].

::: servo/components/style/traversal.rs:245
(Diff revisions 3 - 4)
>                  unstyled_children_only: true,
>              };
>          }
>  
> -        // Expand the snapshot, if any. This is normally handled by the parent, so
> -        // we need a special case for the root.
> +        // Look at whether there has been any attribute or state change, and
> +        // invalidate our style, and the one of our siblings and descendants as

"the one of our" sounds wrong.  "also on our"?

::: layout/reftests/w3c-css/submitted/selectors4/class-id-attr-selector-invalidation-01.html:22
(Diff revision 4)
> +<script>
> +onload = function() {
> +  document.documentElement.offsetTop;
> +  foo.classList.add("foo");
> +  bar.setAttribute("id", "baz");
> +  document.documentElement.offsetTop;

Nit: no need to flush at the end, since the reftest framework should wait until pending restyles/layout has been flushed before taking the snapshot.
Attachment #8876171 - Flags: review?(cam) → review+
Comment on attachment 8876171 [details]
Bug 1368240: Implement a more fine-grained invalidation method.

https://reviewboard.mozilla.org/r/147582/#review152684

::: commit-message-288c9:6
(Diff revision 4)
> +The only straight-forward move/copy is
> +components/style/invalidation/element/element_wrapper.rs. The rest of the code
> +should be reviewed carefully.

This probably doesn't need to be in the final commit message that lands.  (Although a short one or two sentence description of the overall strategy of the patch might be good.)
Emilio, could you also add one or more tests to https://github.com/heycam/style-perf-tests/ to confirm the optimizations work?  The existing some-descendants-1.html test should pass with your patches, but it would be good to have some checks for the kinds of things this patch supports that Gecko's eRestyle_SomeDescendants support does not.
(In reply to Cameron McCormack (:heycam) from comment #76)
> Emilio, could you also add one or more tests to
> https://github.com/heycam/style-perf-tests/ to confirm the optimizations
> work?  The existing some-descendants-1.html test should pass with your
> patches, but it would be good to have some checks for the kinds of things
> this patch supports that Gecko's eRestyle_SomeDescendants support does not.

Yes, I'll open a bug to test this most thoroughly. I also want some mochitests for hard cases.
Blocks: 1372533
Pushed by ecoal95@gmail.com:
https://hg.mozilla.org/integration/autoland/rev/77cf36250272
Manually expand later sibling hints. r=heycam
https://hg.mozilla.org/integration/autoland/rev/e2c830394d47
Record whether an snapshot is recording a class attribute change or id change. r=heycam
https://hg.mozilla.org/integration/autoland/rev/2addc637dc89
Implement a more fine-grained invalidation method. r=heycam
https://hg.mozilla.org/integration/autoland/rev/2bff7e8982a5
Properly handle invalidation of eager pseudo-elements with the new setup. r=heycam
https://hg.mozilla.org/integration/autoland/rev/842b0d4520d4
Update test expectations. r=heycam
https://hg.mozilla.org/integration/autoland/rev/59e15d08cf41
Very basic smoketests for this. r=heycam
Blocks: 1372056
Priority: -- → P1
(In reply to Emilio Cobos Álvarez [:emilio] from comment #35)
> (In reply to Bobby Holley (:bholley) (busy with Stylo) from comment #33)
> > Comment on attachment 8875804 [details] [diff] [review]
> > WIP
> > 
> > Per IRC discussion, please measure the impact on stylist::update. Otherwise,
> > this sounds great! I don't have an in-depth picture of how the guts of the
> > subtree analysis work, but I'll defer that to heycam.
> 
> Without this patch:
> 
>  * https://perfht.ml/2rMyjjt
> 
> With this patch:
> 
>  * https://perfht.ml/2rMEKmH
> 
> That is, about 15ms more in Stylist::add_stylesheet, most (all? :O) of it in
> the HashMap::entry API. That is, in the maps that take care of storing by
> class or id.
> 
> Memory usage seems to be slightly lower with this patch (presumably because
> of RestyleData and Dependency being smaller, even though we have more
> dependencies).
> 
> Thinks I could do:
> 
>  * Store all the dependencies together as they were (but this makes us scan
> way more dependencies, which is undesirable IMO).
>  * Look into why ::entry is so slow, presumably we're hashing the hash as we
> were doing with the bloom filter.
> 
> But I don't think it's too much of a price to pay, and I definitely think I
> can shrink that back to where it was (either doing one of the above things,
> or coalescing calls to visit_selector, etc).
> 
> If you're very very concerned about those 15ms right now, I could do one of
> those before landing, but I'd prefer to investigate afterwards, my feeling
> is that we're doing some very dumb stuff while hashing atoms, and that would
> also affect all the SelectorMaps.

Yeah that sounds reasonable. In general, entry is slow because of [1], which causes us to do unnecessary atomic refcounting on atoms. I don't think we're re-hashing atoms, because the Hash impl for Atom just grabs the precomputed hash (which may miss L2, but there's not much we can do about that).

It's not the end of the world if we don't win this back, and I don't think we should compromise traversal performance to do so. That said, if you have any ideas on how we might make it faster, now would be a good time to get it written down. In particular, I'm not sure what you mean about coalescing calls to visit_selector, but if you think there's a viable strategy there, worth filing a bug.

[1] https://github.com/rust-lang/rfcs/pull/1769
Flags: needinfo?(emilio+bugs)
(In reply to Bobby Holley (:bholley) (busy with Stylo) from comment #79)
> (In reply to Emilio Cobos Álvarez [:emilio] from comment #35)
> > (In reply to Bobby Holley (:bholley) (busy with Stylo) from comment #33)
> > > Comment on attachment 8875804 [details] [diff] [review]
> > > WIP
> > > 
> > > Per IRC discussion, please measure the impact on stylist::update. Otherwise,
> > > this sounds great! I don't have an in-depth picture of how the guts of the
> > > subtree analysis work, but I'll defer that to heycam.
> > 
> > Without this patch:
> > 
> >  * https://perfht.ml/2rMyjjt
> > 
> > With this patch:
> > 
> >  * https://perfht.ml/2rMEKmH
> > 
> > That is, about 15ms more in Stylist::add_stylesheet, most (all? :O) of it in
> > the HashMap::entry API. That is, in the maps that take care of storing by
> > class or id.
> > 
> > Memory usage seems to be slightly lower with this patch (presumably because
> > of RestyleData and Dependency being smaller, even though we have more
> > dependencies).
> > 
> > Thinks I could do:
> > 
> >  * Store all the dependencies together as they were (but this makes us scan
> > way more dependencies, which is undesirable IMO).
> >  * Look into why ::entry is so slow, presumably we're hashing the hash as we
> > were doing with the bloom filter.
> > 
> > But I don't think it's too much of a price to pay, and I definitely think I
> > can shrink that back to where it was (either doing one of the above things,
> > or coalescing calls to visit_selector, etc).
> > 
> > If you're very very concerned about those 15ms right now, I could do one of
> > those before landing, but I'd prefer to investigate afterwards, my feeling
> > is that we're doing some very dumb stuff while hashing atoms, and that would
> > also affect all the SelectorMaps.
> 
> Yeah that sounds reasonable. In general, entry is slow because of [1], which
> causes us to do unnecessary atomic refcounting on atoms. I don't think we're
> re-hashing atoms, because the Hash impl for Atom just grabs the precomputed
> hash (which may miss L2, but there's not much we can do about that).
> 
> It's not the end of the world if we don't win this back, and I don't think
> we should compromise traversal performance to do so. That said, if you have
> any ideas on how we might make it faster, now would be a good time to get it
> written down. In particular, I'm not sure what you mean about coalescing
> calls to visit_selector, but if you think there's a viable strategy there,
> worth filing a bug.
> 
> [1] https://github.com/rust-lang/rfcs/pull/1769

Well, I was just talking about the fact that right now we do a few walk ups over each selector for different stuff...

> self.invalidation_map.note_selector(selector_and_hashes, self.quirks_mode);
> if needs_revalidation(&selector_and_hashes.selector) {
>     self.selectors_for_cache_revalidation.insert(
> 	RevalidationSelectorAndHashes::new(&selector_and_hashes),
> 	self.quirks_mode);
> }
> selector_and_hashes.selector.visit(&mut AttributeAndStateDependencyVisitor {
>     attribute_dependencies: &mut self.attribute_dependencies,
>     style_attribute_dependency: &mut self.style_attribute_dependency,
>     state_dependencies: &mut self.state_dependencies,
> });
> selector_and_hashes.selector.visit(&mut MappedIdVisitor {
>     mapped_ids: &mut self.mapped_ids,
> });

A few of those could potentially be merged together. In particular, the AttributeAndStateDependencyVisitor probably belong to the InvalidationMap anyway.
Flags: needinfo?(emilio+bugs)
(In reply to Emilio Cobos Álvarez [:emilio] from comment #81)
> 
> Well, I was just talking about the fact that right now we do a few walk ups
> over each selector for different stuff...
> 
> ...
> 
> A few of those could potentially be merged together. In particular, the
> AttributeAndStateDependencyVisitor probably belong to the InvalidationMap
> anyway.

Oh I see. I think that's something we can revisit when we do bug 1362538.
You need to log in before you can comment on or make changes to this bug.