1354806 - stylo: do sequential traversal breadth-first

Status: RESOLVED FIXED

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

Description

[Bobby Holley (:bholley)]

Right now the sequential traversal is implemented depth-first because that's the easy thing to do, and the parallel traversal is implemented breadth-first because that maximizes parallelism opportunities.

This inconsistency causes problems though - in particular it messes up the assumptions of the style sharing cache (bug 1332525), since we flush the cache every time the parent changes, which makes sense for breadth-first but not for depth-first.

Emilio was planning to implement a depth-first mode for the style sharing cache, but I think we should just make the sequential traversal breadth-first. The overhead of this should be negligible compared to the actual styling work involved, and having fewer differences between parallel and sequential mode is a Good Thing.

As a nice side bonus, the sequential traversal will be easier to profile, because we won't have to deal with the differently-nested-number-of-doit-calls issue that fragments the profiler samples. Plus the whole issue of not running out of stack space for deep DOMs.

I banged out some patches on the plane. I'm pretty sleepy so they're probably buggy, but we can at least get a try push.

Comment 1

[Bobby Holley (:bholley)]

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

Comment 2

[Bobby Holley (:bholley)]

(In reply to Bobby Holley (:bholley) (busy with Stylo) from comment #1)
> https://treeherder.mozilla.org/#/
> jobs?repo=try&revision=e782b7ff14878674e12b24391ff6279266e9d61a

This is green. I'm going to factor out some of the shared logic and post patches for review.

Comment 3

[Bobby Holley (:bholley)]

Attachment: Part 1 - Factor out the bottom-up postorder traversal logic. v1

Comment 4

[Bobby Holley (:bholley)]

Attachment: Part 2 - Do the sequential traversal breadth-first. v1

While we're at it, we also eliminate the 'unknown' dom depth for the
bloom filter. Computing depth has negligible cost relative to the
amount of work we do setting up the bloom filter at a given depth.
Doing it once per traversal should be totally fine.

I originally separated the elimination of unknown dom depth from the
traversal changes, but I got bloom filter crashes on the intermediate
patch, presumably because I didn't properly fix the sequential traversal
for this case. Given that the final state is green, I just decided to
squash and move on.

Comment 5

[Bobby Holley (:bholley)]

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

Comment 6

[Emilio Cobos Álvarez [:emilio]]

Comment on attachment 8856148 [details] [diff] [review]
Part 2 - Do the sequential traversal breadth-first. v1

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

::: servo/components/style/bloom.rs
@@ +143,4 @@
>      {
>          // Easy case, we're in a different restyle, or we're empty.
>          if self.elements.is_empty() {
> +            self.rebuild(element);

Do we use the return value from rebuild() for this patch? If not, consider remove it and keep self.rebuild(element).

@@ +162,4 @@
>          }
>  
> +        if element_depth == 0 {
> +            self.rebuild(element);

self.filter.clear(), which will clear entries that have overflowed the count of elements.

::: servo/components/style/sequential.rs
@@ +44,5 @@
> +
> +    // Process the nodes breadth-first, just like the parallel traversal does.
> +    // This helps keep similar traversal characteristics for the style sharing
> +    // cache.
> +    while !discovered.is_empty() {

nit: while let Some((node, depth)) = discovered.pop_front()

Comment 7

[Bobby Holley (:bholley)]

(In reply to Emilio Cobos Álvarez [:emilio] from comment #6)
> Comment on attachment 8856148 [details] [diff] [review]
> Part 2 - Do the sequential traversal breadth-first. v1
> 
> Review of attachment 8856148 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> ::: servo/components/style/bloom.rs
> @@ +143,4 @@
> >      {
> >          // Easy case, we're in a different restyle, or we're empty.
> >          if self.elements.is_empty() {
> > +            self.rebuild(element);
> 
> Do we use the return value from rebuild() for this patch? If not, consider
> remove it and keep self.rebuild(element).

Fixed.

> 
> @@ +162,4 @@
> >          }
> >  
> > +        if element_depth == 0 {
> > +            self.rebuild(element);
> 
> self.filter.clear(), which will clear entries that have overflowed the count
> of elements.

Fixed.

> 
> ::: servo/components/style/sequential.rs
> @@ +44,5 @@
> > +
> > +    // Process the nodes breadth-first, just like the parallel traversal does.
> > +    // This helps keep similar traversal characteristics for the style sharing
> > +    // cache.
> > +    while !discovered.is_empty() {
> 
> nit: while let Some((node, depth)) = discovered.pop_front()

Fixed.

Comment 8

[Bobby Holley (:bholley)]

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