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

RESOLVED FIXED

Status

()

RESOLVED FIXED
a year ago
a year ago

People

(Reporter: bholley, Assigned: bholley)

Tracking

(Blocks: 2 bugs)

unspecified
Points:
---
Dependency tree / graph

Firefox Tracking Flags

(firefox57 fixed)

Details

Attachments

(3 attachments)

(Assignee)

Description

a year ago
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.
(Assignee)

Comment 2

a year ago
Created attachment 8900986 [details] [diff] [review]
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
Attachment #8900986 - Flags: review?(emilio+bugs)
(Assignee)

Comment 3

a year ago
Created attachment 8900987 [details] [diff] [review]
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
Attachment #8900987 - Flags: review?(emilio+bugs)
(Assignee)

Comment 4

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

MozReview-Commit-ID: ADVTNJntzmp
Attachment #8900988 - Flags: review?(emilio+bugs)
Attachment #8900986 - Flags: review?(emilio+bugs) → review+
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`
Attachment #8900987 - Flags: review?(emilio+bugs) → review+
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.
Attachment #8900988 - Flags: review?(emilio+bugs) → review+
(Assignee)

Comment 8

a year ago
https://hg.mozilla.org/integration/autoland/rev/a9f5863c9d48
Status: NEW → RESOLVED
Last Resolved: a year ago
Resolution: --- → FIXED
status-firefox57: --- → fixed
You need to log in before you can comment on or make changes to this bug.