servo: Merge #14256 - GC the rule tree only when the free list gets to a certain size (from heycam:rn-gc-heuristic); r=emilio
authorCameron McCormack <cam@mcc.id.au>
Sat, 19 Nov 2016 22:01:12 -0600
changeset 340182 c1d796b0e1c561788a76ac73672072fa5ca3684f
parent 340181 c864d614303038237d62f5bcc5cff2b8e0f7f222
child 340183 4b1b281874d66bb230da646c962088caed0bc9de
push id31307
push usergszorc@mozilla.com
push dateSat, 04 Feb 2017 00:59:06 +0000
treeherdermozilla-central@94079d43835f [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersemilio
servo: Merge #14256 - GC the rule tree only when the free list gets to a certain size (from heycam:rn-gc-heuristic); r=emilio <!-- Please describe your changes on the following line: --> Use a heuristic similar to Gecko's to decide when to GC the rule tree. r? @emilio Source-Repo: https://github.com/servo/servo Source-Revision: b78622bd53b0b605c777b4af2319e032eb3fe190
servo/components/layout_thread/lib.rs
servo/components/style/rule_tree/mod.rs
--- a/servo/components/layout_thread/lib.rs
+++ b/servo/components/layout_thread/lib.rs
@@ -1175,21 +1175,18 @@ impl LayoutThread {
         if opts::get().dump_style_tree {
             node.dump_style();
         }
 
         if opts::get().dump_rule_tree {
             shared_layout_context.style_context.stylist.rule_tree.dump_stdout();
         }
 
-        // GC The rule tree.
-        //
-        // FIXME(emilio): The whole point of the free list is not always freeing
-        // the list, find a good heuristic here for that.
-        unsafe { shared_layout_context.style_context.stylist.rule_tree.gc() }
+        // GC the rule tree if some heuristics are met.
+        unsafe { shared_layout_context.style_context.stylist.rule_tree.maybe_gc(); }
 
         // Perform post-style recalculation layout passes.
         self.perform_post_style_recalc_layout_passes(&data.reflow_info,
                                                      Some(&data.query_type),
                                                      Some(&document),
                                                      &mut rw_data,
                                                      &mut shared_layout_context);
 
--- a/servo/components/style/rule_tree/mod.rs
+++ b/servo/components/style/rule_tree/mod.rs
@@ -119,18 +119,28 @@ impl RuleTree {
         }
         current
     }
 
     /// This can only be called when no other threads is accessing this tree.
     pub unsafe fn gc(&self) {
         self.root.gc();
     }
+
+    /// This can only be called when no other threads is accessing this tree.
+    pub unsafe fn maybe_gc(&self) {
+        self.root.maybe_gc();
+    }
 }
 
+/// The number of RuleNodes added to the free list before we will consider
+/// doing a GC when calling maybe_gc().  (The value is copied from Gecko,
+/// where it likely did not result from a rigorous performance analysis.)
+const RULE_TREE_GC_INTERVAL: usize = 300;
+
 struct RuleNode {
     /// The root node. Only the root has no root pointer, for obvious reasons.
     root: Option<WeakRuleNode>,
 
     /// The parent rule node. Only the root has no parent.
     parent: Option<StrongRuleNode>,
 
     /// The actual style source, either coming from a selector in a StyleRule,
@@ -143,16 +153,24 @@ struct RuleNode {
 
     refcount: AtomicUsize,
     first_child: AtomicPtr<RuleNode>,
     next_sibling: AtomicPtr<RuleNode>,
     prev_sibling: AtomicPtr<RuleNode>,
 
     /// The next item in the rule tree free list, that starts on the root node.
     next_free: AtomicPtr<RuleNode>,
+
+    /// Number of RuleNodes we have added to the free list since the last GC.
+    /// (We don't update this if we rescue a RuleNode from the free list.  It's
+    /// just used as a heuristic to decide when to run GC.)
+    ///
+    /// Only used on the root RuleNode.  (We could probably re-use one of the
+    /// sibling pointers to save space.)
+    free_count: AtomicUsize,
 }
 
 unsafe impl Sync for RuleTree {}
 unsafe impl Send for RuleTree {}
 
 impl RuleNode {
     fn new(root: WeakRuleNode,
            parent: StrongRuleNode,
@@ -164,30 +182,32 @@ impl RuleNode {
             parent: Some(parent),
             source: Some(source),
             importance: importance,
             refcount: AtomicUsize::new(1),
             first_child: AtomicPtr::new(ptr::null_mut()),
             next_sibling: AtomicPtr::new(ptr::null_mut()),
             prev_sibling: AtomicPtr::new(ptr::null_mut()),
             next_free: AtomicPtr::new(ptr::null_mut()),
+            free_count: AtomicUsize::new(0),
         }
     }
 
     fn root() -> Self {
         RuleNode {
             root: None,
             parent: None,
             source: None,
             importance: Importance::Normal,
             refcount: AtomicUsize::new(1),
             first_child: AtomicPtr::new(ptr::null_mut()),
             next_sibling: AtomicPtr::new(ptr::null_mut()),
             prev_sibling: AtomicPtr::new(ptr::null_mut()),
             next_free: AtomicPtr::new(FREE_LIST_SENTINEL),
+            free_count: AtomicUsize::new(0),
         }
     }
 
     fn is_root(&self) -> bool {
         self.parent.is_none()
     }
 
     /// Remove this rule node from the child list.
@@ -405,20 +425,22 @@ impl StrongRuleNode {
             current: Some(self)
         }
     }
 
     unsafe fn pop_from_free_list(&self) -> Option<WeakRuleNode> {
         debug_assert!(thread_state::get().is_layout() &&
                       !thread_state::get().is_worker());
 
+        // NB: This can run from the root node destructor, so we can't use
+        // `get()`, since it asserts the refcount is bigger than zero.
         let me = &*self.ptr;
         debug_assert!(me.is_root());
 
-        let current = self.get().next_free.load(Ordering::SeqCst);
+        let current = me.next_free.load(Ordering::SeqCst);
         if current == FREE_LIST_SENTINEL {
             return None;
         }
 
         let current = WeakRuleNode { ptr: current };
 
         let node = &*current.ptr();
         let next = node.next_free.swap(ptr::null_mut(), Ordering::SeqCst);
@@ -448,18 +470,27 @@ impl StrongRuleNode {
             };
 
             debug!("GC'ing {:?}: {}", weak.ptr(), needs_drop);
             if needs_drop {
                 let _ = Box::from_raw(weak.ptr());
             }
         }
 
+        me.free_count.store(0, Ordering::SeqCst);
+
         debug_assert!(me.next_free.load(Ordering::SeqCst) == FREE_LIST_SENTINEL);
     }
+
+    unsafe fn maybe_gc(&self) {
+        debug_assert!(self.get().is_root(), "Can't call GC on a non-root node!");
+        if self.get().free_count.load(Ordering::SeqCst) > RULE_TREE_GC_INTERVAL {
+            self.gc();
+        }
+    }
 }
 
 #[derive(Clone)]
 pub struct SelfAndAncestors<'a> {
     current: Option<&'a StrongRuleNode>,
 }
 
 impl<'a> Iterator for SelfAndAncestors<'a> {
@@ -514,30 +545,31 @@ impl Drop for StrongRuleNode {
             return;
         }
 
         // The node is already in the free list, so do nothing.
         if node.next_free.load(Ordering::SeqCst) != ptr::null_mut() {
             return;
         }
 
-        let free_list =
-            &unsafe { &*node.root.as_ref().unwrap().ptr() }.next_free;
+        let root = unsafe { &*node.root.as_ref().unwrap().ptr() };
+        let free_list = &root.next_free;
         loop {
             let next_free = free_list.load(Ordering::SeqCst);
             debug_assert!(!next_free.is_null());
 
             node.next_free.store(next_free, Ordering::SeqCst);
 
             let existing =
                 free_list.compare_and_swap(next_free,
                                            self.ptr(),
                                            Ordering::SeqCst);
             if existing == next_free {
                 // Successfully inserted, yay! Otherwise try again.
+                root.free_count.fetch_add(1, Ordering::Relaxed);
                 break;
             }
         }
     }
 }
 
 impl<'a> From<&'a StrongRuleNode> for WeakRuleNode {
     fn from(node: &'a StrongRuleNode) -> Self {