1393632 - stylo: Replace the sequential/parallel distinction with a unified adaptive traversal

Status: RESOLVED FIXED

(Core :: CSS Parsing and Computation, enhancement)

Description

[Bobby Holley (:bholley)]

One long running issue for stylo has been the overhead involved in spinning up the parallel traversals, which hurts us on small workloads.

Given the way style invalidation works, it's not easy to predict the workload. However, I've been pondering an adaptive approach that would use the sequential traversal until a sufficiently large amount of work is discovered (if ever), at which point we kick over to parallel.

I prototyped it today and it seems to work well. Running through try now.

Comment 1

[Bobby Holley (:bholley)]

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

Comment 2

[Bobby Holley (:bholley)]

Attachment: Part 1 - Stop storing depth per-node in the sequential traversal. v1

This has two advantages:
* It allows us to store nodes in the same format that the parallel traversal uses.
* It allows us to double the size of the sequential work queue without increasing
  the storage, which allows us to have WORK_UNIT_MAX * 2 entries before heap-
  allocating, which is about what we want for adaptive mode.

MozReview-Commit-ID: 6VQwGfTQgct

Comment 3

[Bobby Holley (:bholley)]

Attachment: Part 2 - Switch to an iterator for traverse_nodes. v1

We can't use a slice anymore, because the input might be the VecDeque from the
sequential traversal, which requires an iterator to handle the ring buffer.

MozReview-Commit-ID: JwH6MtRgMfY

Comment 4

[Bobby Holley (:bholley)]

Attachment: Part 3 - Eliminate the sequential/traversal parallel distinction in favor of a unified adaptive driver. v1

MozReview-Commit-ID: ADVTNJntzmp

Comment 5

[Emilio Cobos Álvarez (:emilio)]

Comment on attachment 8900987 [details] [diff] [review]
Part 2 - Switch to an iterator for traverse_nodes. v1

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

::: servo/components/style/parallel.rs
@@ +281,2 @@
>  {
> +    debug_assert!(!nodes.len() != 0);

This assertion doesn't make any sense. Just `nodes.len() != 0`

Comment 6

[Emilio Cobos Álvarez (:emilio)]

Comment on attachment 8900988 [details] [diff] [review]
Part 3 - Eliminate the sequential/traversal parallel distinction in favor of a unified adaptive driver. v1

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

Looks nice! r=me, with the formatting nits.

::: servo/components/style/driver.rs
@@ +25,5 @@
> +/// We use an adaptive traversal strategy. We start out with simple sequential
> +/// processing, until we arrive at a wide enough level in the DOM that the
> +/// parallel traversal would parallelize it. If a thread pool is provided, we
> +/// then transfer control over to the parallel traversal.
> +pub fn traverse_dom<E, D>(traversal: &D,

Let's rustfmt this? :P

@@ +88,5 @@
> +                let drain = discovered.drain(..);
> +                pool.install(|| {
> +                    rayon::scope(|scope| {
> +                        parallel::traverse_nodes(
> +                           drain,

nit: Indentation here looks pretty weird (three spaces). Please fix it up.

Comment 7

[Bobby Holley (:bholley)]

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

Comment 8

[Bobby Holley (:bholley)]

https://hg.mozilla.org/integration/autoland/rev/a9f5863c9d48