Eliminate the sequential/traversal parallel distinction in favor of a unified adaptive driver.

MozReview-Commit-ID: ADVTNJntzmp

1 files changed, 132 insertions, 0 deletions

diff --git a/components/style/driver.rs b/components/style/driver.rs
new file mode 100644
index 00000000000..568338c009b
--- /dev/null
+++ b/components/style/driver.rs
@@ -0,0 +1,132 @@
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+//! Implements traversal over the DOM tree. The traversal starts in sequential
+//! mode, and optionally parallelizes as it discovers work.
+
+#![deny(missing_docs)]
+
+use context::{StyleContext, ThreadLocalStyleContext};
+use dom::{SendNode, TElement, TNode};
+use parallel;
+use parallel::{DispatchMode, WORK_UNIT_MAX};
+use rayon;
+use scoped_tls::ScopedTLS;
+use std::borrow::Borrow;
+use std::collections::VecDeque;
+use std::mem;
+use time;
+use traversal::{DomTraversal, PerLevelTraversalData, PreTraverseToken};
+
+/// Do a DOM traversal for top-down and (optionally) bottom-up processing,
+/// generic over `D`.
+///
+/// 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,
+    root: E,
+    token: PreTraverseToken,
+    pool: Option<&rayon::ThreadPool>
+)
+where
+    E: TElement,
+    D: DomTraversal<E>,
+{
+    debug_assert!(token.should_traverse());
+
+    let dump_stats = traversal.shared_context().options.dump_style_statistics;
+    let start_time = if dump_stats { Some(time::precise_time_s()) } else { None };
+
+    // Declare the main-thread context, as well as the worker-thread contexts,
+    // which we may or may not instantiate. It's important to declare the worker-
+    // thread contexts first, so that they get dropped second. This matters because:
+    //   * ThreadLocalContexts borrow AtomicRefCells in TLS.
+    //   * Dropping a ThreadLocalContext can run SequentialTasks.
+    //   * Sequential tasks may call into functions like
+    //     Servo_StyleSet_GetBaseComputedValuesForElement, which instantiate a
+    //     ThreadLocalStyleContext on the main thread. If the main thread
+    //     ThreadLocalStyleContext has not released its TLS borrow by that point,
+    //     we'll panic on double-borrow.
+    let mut maybe_tls: Option<ScopedTLS<ThreadLocalStyleContext<E>>> = None;
+    let mut tlc = ThreadLocalStyleContext::new(traversal.shared_context());
+    let mut context = StyleContext {
+        shared: traversal.shared_context(),
+        thread_local: &mut tlc,
+    };
+
+    // Process the nodes breadth-first, just like the parallel traversal does.
+    // This helps keep similar traversal characteristics for the style sharing
+    // cache.
+    let mut discovered =
+        VecDeque::<SendNode<E::ConcreteNode>>::with_capacity(WORK_UNIT_MAX * 2);
+    let mut depth = root.depth();
+    let mut nodes_remaining_at_current_depth = 1;
+    discovered.push_back(unsafe { SendNode::new(root.as_node()) });
+    while let Some(node) = discovered.pop_front() {
+        let mut children_to_process = 0isize;
+        let traversal_data = PerLevelTraversalData { current_dom_depth: depth };
+        traversal.process_preorder(&traversal_data, &mut context, *node, |n| {
+            children_to_process += 1;
+            discovered.push_back(unsafe { SendNode::new(n) });
+        });
+
+        traversal.handle_postorder_traversal(&mut context, root.as_node().opaque(),
+                                             *node, children_to_process);
+
+        nodes_remaining_at_current_depth -= 1;
+        if nodes_remaining_at_current_depth == 0 {
+            depth += 1;
+            // If there is enough work to parallelize over, and the caller allows
+            // parallelism, switch to the parallel driver. We do this only when
+            // moving to the next level in the dom so that we can pass the same
+            // depth for all the children.
+            if pool.is_some() && discovered.len() > WORK_UNIT_MAX {
+                let pool = pool.unwrap();
+                maybe_tls = Some(ScopedTLS::<ThreadLocalStyleContext<E>>::new(pool));
+                let root_opaque = root.as_node().opaque();
+                let drain = discovered.drain(..);
+                pool.install(|| {
+                    rayon::scope(|scope| {
+                        parallel::traverse_nodes(
+                            drain,
+                            DispatchMode::TailCall,
+                            /* recursion_ok = */ true,
+                            root_opaque,
+                            PerLevelTraversalData { current_dom_depth: depth },
+                            scope,
+                            pool,
+                            traversal,
+                            maybe_tls.as_ref().unwrap()
+                        );
+                    });
+                });
+                break;
+            }
+            nodes_remaining_at_current_depth = discovered.len();
+        }
+    }
+
+    // Dump statistics to stdout if requested.
+    if dump_stats {
+        let mut aggregate =
+            mem::replace(&mut context.thread_local.statistics, Default::default());
+        let parallel = maybe_tls.is_some();
+        if let Some(tls) = maybe_tls {
+            let slots = unsafe { tls.unsafe_get() };
+            aggregate = slots.iter().fold(aggregate, |acc, t| {
+                match *t.borrow() {
+                    None => acc,
+                    Some(ref cx) => &cx.borrow().statistics + &acc,
+                }
+            });
+        }
+        aggregate.finish(traversal, parallel, start_time.unwrap());
+        if aggregate.is_large_traversal() {
+            println!("{}", aggregate);
+        }
+    }
+}