1335708 - stylo: Don't use a HashMap for pseudo-element styles.

Status: RESOLVED FIXED

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

Description

[Emilio Cobos Álvarez (:emilio)]

Should probably be something like `AutoTArray<(PseudoElement, ComputedValues), 2>`, or similar.

Comment 1

[Bobby Holley (:bholley)]

I'm doing this as a prereq for bug 1352565.

Comment 2

[Bobby Holley (:bholley)]

Note: I plan to clean this up a bit with some macros.

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

Comment 3

[Bobby Holley (:bholley)]

Attachment: Part 1 - Improve some ergonomics around pseudo-elements. v1

I think a lot of the current indirection predates the crate merge.

MozReview-Commit-ID: FM28dgZa5go

Comment 4

[Bobby Holley (:bholley)]

Attachment: Use a more compact representation to store eager pseudo-elements. v1

This means that ElementStyles only need a single word to store eager pseudos.

MozReview-Commit-ID: 5bDXlDweN46

Comment 5

[Bobby Holley (:bholley)]

Attachment: Part 2 - Use a more compact representation to store eager pseudo-elements. v2

Fixed a typo in the atom macro invocation.

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

MozReview-Commit-ID: 5bDXlDweN46

Comment 6

[Emilio Cobos Álvarez (:emilio)]

Comment on attachment 8853694 [details] [diff] [review]
Part 2 - Use a more compact representation to store eager pseudo-elements. v2

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

I think we really want to avoid all this EAGER_PSEUDO_COUNT complexity and handle all pseudos the same way from the first time, but I want to hear your opinion on it.

Apart from it it looks ok (modulo comments).

Clearing the review flag for now, but since I wake up earlier than you feel free to reply and address comments / re-request and I'll have this re-reviewed in the morning :P.

::: servo/components/style/data.rs
@@ +77,2 @@
>  #[derive(Clone, Debug)]
> +pub struct EagerPseudoStyles(Option<Box<[Option<ComputedStyle>]>>);

I'd prefer if `EagerPseudoStyles` was defined as `[Option<ComputedStyle>; EAGER_PSEUDO_COUNT]`, and we handled the lazy allocation complexity outside of. But in general, I believe we could just make this something like:

type PseudoStyles = SmallVec<[(PseudoElement, ComputedStyle); 10]>

And handle both eager and non-eager with an Option<Box<PseudoStyles>>, linear-probing them instead of having a special array for eager pseudos and diverging more between Servo and Gecko.

This may be needed anyway for the other bugs we've discussed, and seems easy to just do it now, instead of having to revert all the EAGER_PSEUDO_COUNT complexity later.

wdyt?

::: servo/components/style/gecko/selector_parser.rs
@@ +47,5 @@
> +    ($macro_name:ident, $atom_macro:ident) => {
> +        $macro_name!($atom_macro!(":after"), 0);
> +        $macro_name!($atom_macro!(":before"), 1);
> +    }
> +}

I wonder, since this is effectively linear probing, whether we should instead declare a static array.

Then eager_index() could just be EAGER_ATOMS.iter().position(..).expect("Non eager"), and from_eager_index would just be indexing in an array.

Also, each_eagerly_cascaded_... should just be iterating over an array.

::: servo/components/style/matching.rs
@@ +927,3 @@
>                  }
> +            } else if pseudos.has(&pseudo) {
> +                pseudos.remove(&pseudo);

Perhaps we could have a `take` function that did this?

::: servo/components/style/servo/selector_parser.rs
@@ +33,1 @@
>      After,

Perhaps After = 0, so it's clearer what we rely on?

@@ +72,5 @@
> +    /// Gets the canonical index of this eagerly-cascaded pseudo-element.
> +    #[inline]
> +    pub fn eager_index(&self) -> usize {
> +        debug_assert!(self.is_eager());
> +        self.clone() as usize

huh, do you really need the clone? Doesn't |*self as usize| work?

@@ +89,5 @@
>      #[inline]
>      pub fn is_before_or_after(&self) -> bool {
>          match *self {
> +            PseudoElement::After |
> +            PseudoElement::Before => true,

This change doesn't really seem necessary (is it only for consistency?), but while you're at it you could use the matches! macro.

@@ +390,5 @@
> +    #[inline]
> +    pub fn each_eagerly_cascaded_pseudo_element<F>(mut fun: F)
> +        where F: FnMut(PseudoElement),
> +    {
> +        Self::each_pseudo_element(|p| {

I guess you an write this now more efficiently as:

for i in 0..EAGER_PSEUDO_COUNT {
    fun(PseudoElement::from_eager_index(i))
}

Comment 7

[Bobby Holley (:bholley)]

(In reply to Emilio Cobos Álvarez [:emilio] from comment #6)
> Comment on attachment 8853694 [details] [diff] [review]
> Part 2 - Use a more compact representation to store eager pseudo-elements. v2
> 
> Review of attachment 8853694 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> I think we really want to avoid all this EAGER_PSEUDO_COUNT complexity and
> handle all pseudos the same way from the first time, but I want to hear your
> opinion on it.
> 
> Apart from it it looks ok (modulo comments).
> 
> Clearing the review flag for now, but since I wake up earlier than you feel
> free to reply and address comments / re-request and I'll have this
> re-reviewed in the morning :P.
> 
> ::: servo/components/style/data.rs
> @@ +77,2 @@
> >  #[derive(Clone, Debug)]
> > +pub struct EagerPseudoStyles(Option<Box<[Option<ComputedStyle>]>>);
> 
> I'd prefer if `EagerPseudoStyles` was defined as `[Option<ComputedStyle>;
> EAGER_PSEUDO_COUNT]`, and we handled the lazy allocation complexity outside
> of.

Can you clarify why? The current approach allows the encapsulation of all of the lazy allocation complexity, which seems preferable to having it floating around either the callers or around ElementStyles. The invariant that "no allocation means no eager pseudos" is a useful one (since it makes it very fast to confirm that there are no pseudos, which is the common case), and that requires some degree of complexity in insert/remove.

> But in general, I believe we could just make this something like:
> 
> type PseudoStyles = SmallVec<[(PseudoElement, ComputedStyle); 10]>
> 
> And handle both eager and non-eager with an Option<Box<PseudoStyles>>,
> linear-probing them instead of having a special array for eager pseudos and
> diverging more between Servo and Gecko.

My understanding of the plan in bug 1352743 is that we'd still only be storing eager pseudos on the Element. Lazy pseudos are layout-driven, and as a general principle, the style system doesn't have all the information to determine when they're needed (and therefore whether the pseudo style needs to be re-resolved when the originating element is restyled). Consider <input type="number">. That will resolve a whole bunch of lazy pseudos on the <input> element (like ::-moz-number-wrapper and ::-moz-number-spin-box). If we cache those on the element, and then someone later changes the |type| attribute to "text", we don't need to keep resolving all those pseudos every time we restyle the element, but the style system doesn't have any way of knowing that.

The post-traversal already needs to know how to find the frame to restyle these pseudos, and with the proposed bitmask (which will cover eager and non-eager pseudos), it should have all the information it needs to know how to do that efficiently.

And once we're only storing eager styles on the Element, the SmallVec approach has several disadvantages over the Array:
* There are very few eager pseudos, so we don't need the dynamic growing behavior.
* We can't quickly look up a pseudo by index.
* It takes twice the memory, because we have to store the two-word PseudoElement inline.

> This may be needed anyway for the other bugs we've discussed, and seems easy
> to just do it now, instead of having to revert all the EAGER_PSEUDO_COUNT
> complexity later.

Per above, I think we're still going to need the distinction between eager and non-eager: eager pseudos are the ones that servo drive styling for, lazy ones are driven by layout. We may want to add ::first-letter/::first-line to the set of eager pseudos (matching them after the primary style is cascaded, so that we can check for block-like elements), but that doesn't fundamentally alter the equation here.

> 
> wdyt?
> 
> ::: servo/components/style/gecko/selector_parser.rs
> @@ +47,5 @@
> > +    ($macro_name:ident, $atom_macro:ident) => {
> > +        $macro_name!($atom_macro!(":after"), 0);
> > +        $macro_name!($atom_macro!(":before"), 1);
> > +    }
> > +}
> 
> I wonder, since this is effectively linear probing, whether we should
> instead declare a static array.
> 
> Then eager_index() could just be EAGER_ATOMS.iter().position(..).expect("Non
> eager"), and from_eager_index would just be indexing in an array.
> 
> Also, each_eagerly_cascaded_... should just be iterating over an array.

Nice idea! I tried it though, and got hung up on the fact that the atom! macro refers to statics, and you can't refer to statics in the initialization of other statics: https://pastebin.mozilla.org/8984024

Happy to go with the array approach if you know of a way around that.

> 
> ::: servo/components/style/matching.rs
> @@ +927,3 @@
> >                  }
> > +            } else if pseudos.has(&pseudo) {
> > +                pseudos.remove(&pseudo);
> 
> Perhaps we could have a `take` function that did this?

Ok sure - those are probably better ergonomics, I agree.

> 
> ::: servo/components/style/servo/selector_parser.rs
> @@ +33,1 @@
> >      After,
> 
> Perhaps After = 0, so it's clearer what we rely on?

Sure.

> 
> @@ +72,5 @@
> > +    /// Gets the canonical index of this eagerly-cascaded pseudo-element.
> > +    #[inline]
> > +    pub fn eager_index(&self) -> usize {
> > +        debug_assert!(self.is_eager());
> > +        self.clone() as usize
> 
> huh, do you really need the clone? Doesn't |*self as usize| work?

No, |as| consumes. I would ordinarily just make PseudoElement |Copy|, but since gecko's PseudoElement is non-copy, that would create a footgun for code that compiles for servo but not for geckolib.
> 
> @@ +89,5 @@
> >      #[inline]
> >      pub fn is_before_or_after(&self) -> bool {
> >          match *self {
> > +            PseudoElement::After |
> > +            PseudoElement::Before => true,
> 
> This change doesn't really seem necessary (is it only for consistency?), but
> while you're at it you could use the matches! macro.

Yeah, for consistency. I put After first because that's what comes first in the generated code, and then I thought we should use a consistent ordering for the pseudos everywhere.

> 
> @@ +390,5 @@
> > +    #[inline]
> > +    pub fn each_eagerly_cascaded_pseudo_element<F>(mut fun: F)
> > +        where F: FnMut(PseudoElement),
> > +    {
> > +        Self::each_pseudo_element(|p| {
> 
> I guess you an write this now more efficiently as:
> 
> for i in 0..EAGER_PSEUDO_COUNT {
>     fun(PseudoElement::from_eager_index(i))
> }

Yeah good point.

Comment 8

[Bobby Holley (:bholley)]

Attachment: Part 2 - Use a more compact representation to store eager pseudo-elements. v3

MozReview-Commit-ID: 5bDXlDweN46

Comment 9

[Emilio Cobos Álvarez (:emilio)]

(In reply to Bobby Holley (:bholley) (busy with Stylo) from comment #7)
> (In reply to Emilio Cobos Álvarez [:emilio] from comment #6)
> > Comment on attachment 8853694 [details] [diff] [review]
> > Part 2 - Use a more compact representation to store eager pseudo-elements. v2
> > 
> > Review of attachment 8853694 [details] [diff] [review]:
> > -----------------------------------------------------------------
> > 
> > I think we really want to avoid all this EAGER_PSEUDO_COUNT complexity and
> > handle all pseudos the same way from the first time, but I want to hear your
> > opinion on it.
> > 
> > Apart from it it looks ok (modulo comments).
> > 
> > Clearing the review flag for now, but since I wake up earlier than you feel
> > free to reply and address comments / re-request and I'll have this
> > re-reviewed in the morning :P.
> > 
> > ::: servo/components/style/data.rs
> > @@ +77,2 @@
> > >  #[derive(Clone, Debug)]
> > > +pub struct EagerPseudoStyles(Option<Box<[Option<ComputedStyle>]>>);
> > 
> > I'd prefer if `EagerPseudoStyles` was defined as `[Option<ComputedStyle>;
> > EAGER_PSEUDO_COUNT]`, and we handled the lazy allocation complexity outside
> > of.
> 
> Can you clarify why? The current approach allows the encapsulation of all of
> the lazy allocation complexity, which seems preferable to having it floating
> around either the callers or around ElementStyles. The invariant that "no
> allocation means no eager pseudos" is a useful one (since it makes it very
> fast to confirm that there are no pseudos, which is the common case), and
> that requires some degree of complexity in insert/remove.

I'd prefer using two different types for that, but sure.

> > But in general, I believe we could just make this something like:
> > 
> > type PseudoStyles = SmallVec<[(PseudoElement, ComputedStyle); 10]>
> > 
> > And handle both eager and non-eager with an Option<Box<PseudoStyles>>,
> > linear-probing them instead of having a special array for eager pseudos and
> > diverging more between Servo and Gecko.
> 
> My understanding of the plan in bug 1352743 is that we'd still only be
> storing eager pseudos on the Element. Lazy pseudos are layout-driven, and as
> a general principle, the style system doesn't have all the information to
> determine when they're needed (and therefore whether the pseudo style needs
> to be re-resolved when the originating element is restyled). Consider <input
> type="number">. That will resolve a whole bunch of lazy pseudos on the
> <input> element (like ::-moz-number-wrapper and ::-moz-number-spin-box). If
> we cache those on the element, and then someone later changes the |type|
> attribute to "text", we don't need to keep resolving all those pseudos every
> time we restyle the element, but the style system doesn't have any way of
> knowing that.
> 
> The post-traversal already needs to know how to find the frame to restyle
> these pseudos, and with the proposed bitmask (which will cover eager and
> non-eager pseudos), it should have all the information it needs to know how
> to do that efficiently.
> 
> And once we're only storing eager styles on the Element, the SmallVec
> approach has several disadvantages over the Array:
> * There are very few eager pseudos, so we don't need the dynamic growing
> behavior.
> * We can't quickly look up a pseudo by index.
> * It takes twice the memory, because we have to store the two-word
> PseudoElement inline.
> 
> > This may be needed anyway for the other bugs we've discussed, and seems easy
> > to just do it now, instead of having to revert all the EAGER_PSEUDO_COUNT
> > complexity later.
> 
> Per above, I think we're still going to need the distinction between eager
> and non-eager: eager pseudos are the ones that servo drive styling for, lazy
> ones are driven by layout. We may want to add ::first-letter/::first-line to
> the set of eager pseudos (matching them after the primary style is cascaded,
> so that we can check for block-like elements), but that doesn't
> fundamentally alter the equation here.

Right, my point is that it's likely that finding those used by layout (specially ::first-line) might not be as efficient.

But since what to do about that is still in flux, let's just deal with it later.

> > 
> > wdyt?
> > 
> > ::: servo/components/style/gecko/selector_parser.rs
> > @@ +47,5 @@
> > > +    ($macro_name:ident, $atom_macro:ident) => {
> > > +        $macro_name!($atom_macro!(":after"), 0);
> > > +        $macro_name!($atom_macro!(":before"), 1);
> > > +    }
> > > +}
> > 
> > I wonder, since this is effectively linear probing, whether we should
> > instead declare a static array.
> > 
> > Then eager_index() could just be EAGER_ATOMS.iter().position(..).expect("Non
> > eager"), and from_eager_index would just be indexing in an array.
> > 
> > Also, each_eagerly_cascaded_... should just be iterating over an array.
> 
> Nice idea! I tried it though, and got hung up on the fact that the atom!
> macro refers to statics, and you can't refer to statics in the
> initialization of other statics: https://pastebin.mozilla.org/8984024
> 
> Happy to go with the array approach if you know of a way around that.

Yeah, on retrospective the proper static array won't work because destructors in statics are unstable. But would be easy to make it a lazy_static!, right?

> > huh, do you really need the clone? Doesn't |*self as usize| work?
> 
> No, |as| consumes. I would ordinarily just make PseudoElement |Copy|, but
> since gecko's PseudoElement is non-copy, that would create a footgun for
> code that compiles for servo but not for geckolib.

Fair enough.

Comment 10

[Emilio Cobos Álvarez (:emilio)]

Comment on attachment 8853844 [details] [diff] [review]
Part 2 - Use a more compact representation to store eager pseudo-elements. v3

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

r=me

Comment 11

[Bobby Holley (:bholley)]

(In reply to Emilio Cobos Álvarez [:emilio] from comment #9)
> (In reply to Bobby Holley (:bholley) (busy with Stylo) from comment #7)
> > (In reply to Emilio Cobos Álvarez [:emilio] from comment #6)
> > > Comment on attachment 8853694 [details] [diff] [review]
> > > Part 2 - Use a more compact representation to store eager pseudo-elements. v2
> > > 
> > > Review of attachment 8853694 [details] [diff] [review]:
> > > -----------------------------------------------------------------
> > > 
> > > I think we really want to avoid all this EAGER_PSEUDO_COUNT complexity and
> > > handle all pseudos the same way from the first time, but I want to hear your
> > > opinion on it.
> > > 
> > > Apart from it it looks ok (modulo comments).
> > > 
> > > Clearing the review flag for now, but since I wake up earlier than you feel
> > > free to reply and address comments / re-request and I'll have this
> > > re-reviewed in the morning :P.
> > > 
> > > ::: servo/components/style/data.rs
> > > @@ +77,2 @@
> > > >  #[derive(Clone, Debug)]
> > > > +pub struct EagerPseudoStyles(Option<Box<[Option<ComputedStyle>]>>);
> > > 
> > > I'd prefer if `EagerPseudoStyles` was defined as `[Option<ComputedStyle>;
> > > EAGER_PSEUDO_COUNT]`, and we handled the lazy allocation complexity outside
> > > of.
> > 
> > Can you clarify why? The current approach allows the encapsulation of all of
> > the lazy allocation complexity, which seems preferable to having it floating
> > around either the callers or around ElementStyles. The invariant that "no
> > allocation means no eager pseudos" is a useful one (since it makes it very
> > fast to confirm that there are no pseudos, which is the common case), and
> > that requires some degree of complexity in insert/remove.
> 
> I'd prefer using two different types for that, but sure.
> 
> > > But in general, I believe we could just make this something like:
> > > 
> > > type PseudoStyles = SmallVec<[(PseudoElement, ComputedStyle); 10]>
> > > 
> > > And handle both eager and non-eager with an Option<Box<PseudoStyles>>,
> > > linear-probing them instead of having a special array for eager pseudos and
> > > diverging more between Servo and Gecko.
> > 
> > My understanding of the plan in bug 1352743 is that we'd still only be
> > storing eager pseudos on the Element. Lazy pseudos are layout-driven, and as
> > a general principle, the style system doesn't have all the information to
> > determine when they're needed (and therefore whether the pseudo style needs
> > to be re-resolved when the originating element is restyled). Consider <input
> > type="number">. That will resolve a whole bunch of lazy pseudos on the
> > <input> element (like ::-moz-number-wrapper and ::-moz-number-spin-box). If
> > we cache those on the element, and then someone later changes the |type|
> > attribute to "text", we don't need to keep resolving all those pseudos every
> > time we restyle the element, but the style system doesn't have any way of
> > knowing that.
> > 
> > The post-traversal already needs to know how to find the frame to restyle
> > these pseudos, and with the proposed bitmask (which will cover eager and
> > non-eager pseudos), it should have all the information it needs to know how
> > to do that efficiently.
> > 
> > And once we're only storing eager styles on the Element, the SmallVec
> > approach has several disadvantages over the Array:
> > * There are very few eager pseudos, so we don't need the dynamic growing
> > behavior.
> > * We can't quickly look up a pseudo by index.
> > * It takes twice the memory, because we have to store the two-word
> > PseudoElement inline.
> > 
> > > This may be needed anyway for the other bugs we've discussed, and seems easy
> > > to just do it now, instead of having to revert all the EAGER_PSEUDO_COUNT
> > > complexity later.
> > 
> > Per above, I think we're still going to need the distinction between eager
> > and non-eager: eager pseudos are the ones that servo drive styling for, lazy
> > ones are driven by layout. We may want to add ::first-letter/::first-line to
> > the set of eager pseudos (matching them after the primary style is cascaded,
> > so that we can check for block-like elements), but that doesn't
> > fundamentally alter the equation here.
> 
> Right, my point is that it's likely that finding those used by layout
> (specially ::first-line) might not be as efficient.
> 
> But since what to do about that is still in flux, let's just deal with it
> later.

Sure.

> 
> > > 
> > > wdyt?
> > > 
> > > ::: servo/components/style/gecko/selector_parser.rs
> > > @@ +47,5 @@
> > > > +    ($macro_name:ident, $atom_macro:ident) => {
> > > > +        $macro_name!($atom_macro!(":after"), 0);
> > > > +        $macro_name!($atom_macro!(":before"), 1);
> > > > +    }
> > > > +}
> > > 
> > > I wonder, since this is effectively linear probing, whether we should
> > > instead declare a static array.
> > > 
> > > Then eager_index() could just be EAGER_ATOMS.iter().position(..).expect("Non
> > > eager"), and from_eager_index would just be indexing in an array.
> > > 
> > > Also, each_eagerly_cascaded_... should just be iterating over an array.
> > 
> > Nice idea! I tried it though, and got hung up on the fact that the atom!
> > macro refers to statics, and you can't refer to statics in the
> > initialization of other statics: https://pastebin.mozilla.org/8984024
> > 
> > Happy to go with the array approach if you know of a way around that.
> 
> Yeah, on retrospective the proper static array won't work because
> destructors in statics are unstable. But would be easy to make it a
> lazy_static!, right?

Yeah, but lazy_static would put a sequentially-consistent atomic op on this path, which I'd rather avoid.

> 
> > > huh, do you really need the clone? Doesn't |*self as usize| work?
> > 
> > No, |as| consumes. I would ordinarily just make PseudoElement |Copy|, but
> > since gecko's PseudoElement is non-copy, that would create a footgun for
> > code that compiles for servo but not for geckolib.
> 
> Fair enough.

Thanks for the review!

Comment 12

[Bobby Holley (:bholley)]

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