Use Gecko's simpler Bloom filter instead of one based on hash

stretching.

This preserves the usage of the Bloom filter throughout style recalc,
but the implementation is rewritten. Provides a 15% improvement on
Guardians of the Galaxy.

5 files changed, 78 insertions, 76 deletions

diff --git a/components/layout/css/matching.rs b/components/layout/css/matching.rs
index d618851a175..2c5207e7fd9 100644
--- a/components/layout/css/matching.rs
+++ b/components/layout/css/matching.rs
@@ -19,7 +19,6 @@ use servo_util::str::DOMString;
 use std::mem;
 use std::hash::{Hash, sip};
 use std::slice::Items;
-use style;
 use style::{After, Before, ComputedValues, DeclarationBlock, Stylist, TElement, TNode};
 use style::cascade;
 use sync::Arc;
@@ -299,13 +298,13 @@ pub trait MatchMethods {
     fn recalc_style_for_subtree(&self,
                                 stylist: &Stylist,
                                 layout_context: &LayoutContext,
-                                parent_bf: &mut Option<BloomFilter>,
+                                parent_bf: &mut Option<Box<BloomFilter>>,
                                 applicable_declarations: &mut ApplicableDeclarations,
                                 parent: Option<LayoutNode>);
 
     fn match_node(&self,
                   stylist: &Stylist,
-                  parent_bf: &Option<BloomFilter>,
+                  parent_bf: &Option<Box<BloomFilter>>,
                   applicable_declarations: &mut ApplicableDeclarations,
                   shareable: &mut bool);
 
@@ -421,7 +420,7 @@ impl<'ln> PrivateMatchMethods for LayoutNode<'ln> {
 impl<'ln> MatchMethods for LayoutNode<'ln> {
     fn match_node(&self,
                   stylist: &Stylist,
-                  parent_bf: &Option<BloomFilter>,
+                  parent_bf: &Option<Box<BloomFilter>>,
                   applicable_declarations: &mut ApplicableDeclarations,
                   shareable: &mut bool) {
         let style_attribute = self.as_element().style_attribute().as_ref();
@@ -506,13 +505,7 @@ impl<'ln> MatchMethods for LayoutNode<'ln> {
         element.get_id().map(|id| bf.insert(&id));
 
         // TODO: case-sensitivity depends on the document type and quirks mode
-        element
-            .get_attr(&ns!(""), "class")
-            .map(|attr| {
-                for c in attr.split(style::SELECTOR_WHITESPACE) {
-                    bf.insert(&c);
-                }
-            });
+        element.each_class(|class| bf.insert(class));
     }
 
     fn remove_from_bloom_filter(&self, bf: &mut BloomFilter) {
@@ -525,19 +518,13 @@ impl<'ln> MatchMethods for LayoutNode<'ln> {
         element.get_id().map(|id| bf.remove(&id));
 
         // TODO: case-sensitivity depends on the document type and quirks mode
-        element
-            .get_attr(&ns!(""), "class")
-            .map(|attr| {
-                for c in attr.split(style::SELECTOR_WHITESPACE) {
-                    bf.remove(&c);
-                }
-            });
+        element.each_class(|class| bf.remove(class));
     }
 
     fn recalc_style_for_subtree(&self,
                                 stylist: &Stylist,
                                 layout_context: &LayoutContext,
-                                parent_bf: &mut Option<BloomFilter>,
+                                parent_bf: &mut Option<Box<BloomFilter>>,
                                 applicable_declarations: &mut ApplicableDeclarations,
                                 parent: Option<LayoutNode>) {
         self.initialize_layout_data(layout_context.shared.layout_chan.clone());
@@ -573,7 +560,7 @@ impl<'ln> MatchMethods for LayoutNode<'ln> {
 
         match *parent_bf {
             None => {},
-            Some(ref mut pbf) => self.insert_into_bloom_filter(pbf),
+            Some(ref mut pbf) => self.insert_into_bloom_filter(&mut **pbf),
         }
 
         for kid in self.children() {
@@ -586,7 +573,7 @@ impl<'ln> MatchMethods for LayoutNode<'ln> {
 
         match *parent_bf {
             None => {},
-            Some(ref mut pbf) => self.remove_from_bloom_filter(pbf),
+            Some(ref mut pbf) => self.remove_from_bloom_filter(&mut **pbf),
         }
 
         // Construct flows.
diff --git a/components/layout/layout_task.rs b/components/layout/layout_task.rs
index d252b856f06..22068ae460b 100644
--- a/components/layout/layout_task.rs
+++ b/components/layout/layout_task.rs
@@ -63,9 +63,7 @@ use std::cell::Cell;
 use std::comm::{channel, Sender, Receiver, Select};
 use std::mem;
 use std::ptr;
-use style;
-use style::{TNode, AuthorOrigin, Stylesheet, Stylist};
-use style::iter_font_face_rules;
+use style::{AuthorOrigin, Stylesheet, Stylist, TNode, iter_font_face_rules};
 use sync::{Arc, Mutex, MutexGuard};
 use url::Url;
 
@@ -647,8 +645,7 @@ impl LayoutTask {
                 None => {
                     let layout_ctx = LayoutContext::new(&shared_layout_ctx);
                     let mut applicable_declarations = ApplicableDeclarations::new();
-                    let mut parent_bf = Some(BloomFilter::new(
-                        style::RECOMMENDED_SELECTOR_BLOOM_FILTER_SIZE));
+                    let mut parent_bf = Some(box BloomFilter::new());
                     node.recalc_style_for_subtree(&*rw_data.stylist,
                                                    &layout_ctx,
                                                    &mut parent_bf,
diff --git a/components/layout/parallel.rs b/components/layout/parallel.rs
index 3a85ee9a629..90e19f6db76 100644
--- a/components/layout/parallel.rs
+++ b/components/layout/parallel.rs
@@ -16,7 +16,7 @@ use url::Url;
 use util::{LayoutDataAccess, LayoutDataWrapper};
 use wrapper::{layout_node_to_unsafe_layout_node, layout_node_from_unsafe_layout_node, LayoutNode};
 use wrapper::{PostorderNodeMutTraversal, UnsafeLayoutNode};
-use wrapper::{PreorderDOMTraversal, PostorderDOMTraversal};
+use wrapper::{PreorderDomTraversal, PostorderDomTraversal};
 
 use servo_util::time::{TimeProfilerChan, profile};
 use servo_util::time;
@@ -78,7 +78,7 @@ impl DomParallelInfo {
 }
 
 /// A parallel top-down DOM traversal.
-pub trait ParallelPreorderDOMTraversal : PreorderDOMTraversal {
+pub trait ParallelPreorderDomTraversal : PreorderDomTraversal {
     fn run_parallel(&mut self,
                     node: UnsafeLayoutNode,
                     proxy: &mut WorkerProxy<*const SharedLayoutContext,UnsafeLayoutNode>);
@@ -127,7 +127,7 @@ pub trait ParallelPreorderDOMTraversal : PreorderDOMTraversal {
 }
 
 /// A parallel bottom-up DOM traversal.
-trait ParallelPostorderDOMTraversal : PostorderDOMTraversal {
+trait ParallelPostorderDomTraversal : PostorderDomTraversal {
     /// Process current node and potentially traverse its ancestors.
     ///
     /// If we are the last child that finished processing, recursively process
@@ -319,9 +319,9 @@ impl<'a> ParallelPreorderFlowTraversal for AssignISizes<'a> {
 
 impl<'a> ParallelPostorderFlowTraversal for AssignBSizesAndStoreOverflow<'a> {}
 
-impl<'a> ParallelPostorderDOMTraversal for ConstructFlows<'a> {}
+impl<'a> ParallelPostorderDomTraversal for ConstructFlows<'a> {}
 
-impl <'a> ParallelPreorderDOMTraversal for RecalcStyleForNode<'a> {
+impl <'a> ParallelPreorderDomTraversal for RecalcStyleForNode<'a> {
     fn run_parallel(&mut self,
                     unsafe_node: UnsafeLayoutNode,
                     proxy: &mut WorkerProxy<*const SharedLayoutContext, UnsafeLayoutNode>) {
diff --git a/components/layout/traversal.rs b/components/layout/traversal.rs
index a4417b55d45..d217e785321 100644
--- a/components/layout/traversal.rs
+++ b/components/layout/traversal.rs
@@ -13,11 +13,10 @@ use flow;
 use incremental::RestyleDamage;
 use wrapper::{layout_node_to_unsafe_layout_node, LayoutNode};
 use wrapper::{PostorderNodeMutTraversal, ThreadSafeLayoutNode, UnsafeLayoutNode};
-use wrapper::{PreorderDOMTraversal, PostorderDOMTraversal};
+use wrapper::{PreorderDomTraversal, PostorderDomTraversal};
 
 use servo_util::bloom::BloomFilter;
 use servo_util::tid::tid;
-use style;
 use style::TNode;
 
 /// Every time we do another layout, the old bloom filters are invalid. This is
@@ -44,48 +43,47 @@ type Generation = uint;
 /// Since a work-stealing queue is used for styling, sometimes, the bloom filter
 /// will no longer be the for the parent of the node we're currently on. When
 /// this happens, the task local bloom filter will be thrown away and rebuilt.
-local_data_key!(style_bloom: (BloomFilter, UnsafeLayoutNode, Generation))
+local_data_key!(style_bloom: (Box<BloomFilter>, UnsafeLayoutNode, Generation))
 
 /// Returns the task local bloom filter.
 ///
 /// If one does not exist, a new one will be made for you. If it is out of date,
 /// it will be thrown out and a new one will be made for you.
-fn take_task_local_bloom_filter(
-  parent_node: Option<LayoutNode>,
-  layout_context: &LayoutContext)
-      -> BloomFilter {
-
-    let new_bloom =
-        |p: Option<LayoutNode>| -> BloomFilter {
-            let mut bf = BloomFilter::new(style::RECOMMENDED_SELECTOR_BLOOM_FILTER_SIZE);
-            p.map(|p| insert_ancestors_into_bloom_filter(&mut bf, p, layout_context));
-            if p.is_none() {
-                debug!("[{}] No parent, but new bloom filter!", tid());
-            }
-            bf
-        };
-
+fn take_task_local_bloom_filter(parent_node: Option<LayoutNode>, layout_context: &LayoutContext)
+                                -> Box<BloomFilter> {
     match (parent_node, style_bloom.replace(None)) {
         // Root node. Needs new bloom filter.
-        (None,     _  ) => new_bloom(None),
+        (None,     _  ) => {
+            debug!("[{}] No parent, but new bloom filter!", tid());
+            box BloomFilter::new()
+        }
         // No bloom filter for this thread yet.
-        (Some(p), None) => new_bloom(Some(p)),
+        (Some(parent), None) => {
+            let mut bloom_filter = box BloomFilter::new();
+            insert_ancestors_into_bloom_filter(&mut bloom_filter, parent, layout_context);
+            bloom_filter
+        }
         // Found cached bloom filter.
-        (Some(p), Some((bf, old_node, old_generation))) => {
+        (Some(parent), Some((mut bloom_filter, old_node, old_generation))) => {
             // Hey, the cached parent is our parent! We can reuse the bloom filter.
-            if old_node == layout_node_to_unsafe_layout_node(&p) &&
+            if old_node == layout_node_to_unsafe_layout_node(&parent) &&
                 old_generation == layout_context.shared.generation {
                 debug!("[{}] Parent matches (={}). Reusing bloom filter.", tid(), old_node.val0());
-                bf
-            // Oh no. the cached parent is stale. I guess we need a new one...
+                bloom_filter
             } else {
-                new_bloom(Some(p))
+                // Oh no. the cached parent is stale. I guess we need a new one. Reuse the existing
+                // allocation to avoid malloc churn.
+                *bloom_filter = BloomFilter::new();
+                insert_ancestors_into_bloom_filter(&mut bloom_filter, parent, layout_context);
+                bloom_filter
             }
         },
     }
 }
 
-fn put_task_local_bloom_filter(bf: BloomFilter, unsafe_node: &UnsafeLayoutNode, layout_context: &LayoutContext) {
+fn put_task_local_bloom_filter(bf: Box<BloomFilter>,
+                               unsafe_node: &UnsafeLayoutNode,
+                               layout_context: &LayoutContext) {
     match style_bloom.replace(Some((bf, *unsafe_node, layout_context.shared.generation))) {
         None => {},
         Some(_) => fail!("Putting into a never-taken task-local bloom filter"),
@@ -93,14 +91,15 @@ fn put_task_local_bloom_filter(bf: BloomFilter, unsafe_node: &UnsafeLayoutNode,
 }
 
 /// "Ancestors" in this context is inclusive of ourselves.
-fn insert_ancestors_into_bloom_filter(
-  bf: &mut BloomFilter, mut n: LayoutNode, layout_context: &LayoutContext) {
+fn insert_ancestors_into_bloom_filter(bf: &mut Box<BloomFilter>,
+                                      mut n: LayoutNode,
+                                      layout_context: &LayoutContext) {
     debug!("[{}] Inserting ancestors.", tid());
     let mut ancestors = 0u;
     loop {
         ancestors += 1;
 
-        n.insert_into_bloom_filter(bf);
+        n.insert_into_bloom_filter(&mut **bf);
         n = match n.layout_parent_node(layout_context.shared) {
             None => break,
             Some(p) => p,
@@ -115,7 +114,7 @@ pub struct RecalcStyleForNode<'a> {
     pub layout_context: &'a LayoutContext<'a>,
 }
 
-impl<'a> PreorderDOMTraversal for RecalcStyleForNode<'a> {
+impl<'a> PreorderDomTraversal for RecalcStyleForNode<'a> {
     #[inline]
     fn process(&self, node: LayoutNode) {
         // Initialize layout data.
@@ -135,7 +134,8 @@ impl<'a> PreorderDOMTraversal for RecalcStyleForNode<'a> {
 
         if node.is_dirty() {
             // First, check to see whether we can share a style with someone.
-            let style_sharing_candidate_cache = self.layout_context.style_sharing_candidate_cache();
+            let style_sharing_candidate_cache =
+                self.layout_context.style_sharing_candidate_cache();
             let sharing_result = unsafe {
                 node.share_style_if_possible(style_sharing_candidate_cache,
                                              parent_opt.clone())
@@ -148,8 +148,11 @@ impl<'a> PreorderDOMTraversal for RecalcStyleForNode<'a> {
                     if node.is_element() {
                         // Perform the CSS selector matching.
                         let stylist = unsafe { &*self.layout_context.shared.stylist };
-                        node.match_node(stylist, &some_bf, &mut applicable_declarations, &mut shareable);
-                    }
+                        node.match_node(stylist,
+                                        &some_bf,
+                                        &mut applicable_declarations,
+                                        &mut shareable);
+                   }
 
                     // Perform the CSS cascade.
                     unsafe {
@@ -174,7 +177,7 @@ impl<'a> PreorderDOMTraversal for RecalcStyleForNode<'a> {
         // Before running the children, we need to insert our nodes into the bloom
         // filter.
         debug!("[{}] + {:X}", tid(), unsafe_layout_node.val0());
-        node.insert_into_bloom_filter(&mut bf);
+        node.insert_into_bloom_filter(&mut *bf);
 
         // NB: flow construction updates the bloom filter on the way up.
         put_task_local_bloom_filter(bf, &unsafe_layout_node, self.layout_context);
@@ -186,7 +189,7 @@ pub struct ConstructFlows<'a> {
     pub layout_context: &'a LayoutContext<'a>,
 }
 
-impl<'a> PostorderDOMTraversal for ConstructFlows<'a> {
+impl<'a> PostorderDomTraversal for ConstructFlows<'a> {
     #[inline]
     fn process(&self, node: LayoutNode) {
         // Construct flows for this node.
@@ -222,7 +225,7 @@ impl<'a> PostorderDOMTraversal for ConstructFlows<'a> {
             }
             Some(parent) => {
                 // Otherwise, put it back, but remove this node.
-                node.remove_from_bloom_filter(&mut bf);
+                node.remove_from_bloom_filter(&mut *bf);
                 let unsafe_parent = layout_node_to_unsafe_layout_node(&parent);
                 put_task_local_bloom_filter(bf, &unsafe_parent, self.layout_context);
             },
@@ -248,8 +251,8 @@ impl PreorderFlow for FlowTreeVerification {
     }
 }
 
-/// The bubble-inline-sizes traversal, the first part of layout computation. This computes preferred
-/// and intrinsic inline-sizes and bubbles them up the tree.
+/// The bubble-inline-sizes traversal, the first part of layout computation. This computes
+/// preferred and intrinsic inline-sizes and bubbles them up the tree.
 pub struct BubbleISizes<'a> {
     pub layout_context: &'a LayoutContext<'a>,
 }
@@ -283,9 +286,10 @@ impl<'a> PreorderFlowTraversal for AssignISizes<'a> {
     }
 }
 
-/// The assign-block-sizes-and-store-overflow traversal, the last (and most expensive) part of layout
-/// computation. Determines the final block-sizes for all layout objects, computes positions, and
-/// computes overflow regions. In Gecko this corresponds to `FinishAndStoreOverflow`.
+/// The assign-block-sizes-and-store-overflow traversal, the last (and most expensive) part of
+/// layout computation. Determines the final block-sizes for all layout objects, computes
+/// positions, and computes overflow regions. In Gecko this corresponds to `Reflow` and
+/// `FinishAndStoreOverflow`.
 pub struct AssignBSizesAndStoreOverflow<'a> {
     pub layout_context: &'a LayoutContext<'a>,
 }
diff --git a/components/layout/wrapper.rs b/components/layout/wrapper.rs
index 0a10bf0315d..7cde321f058 100644
--- a/components/layout/wrapper.rs
+++ b/components/layout/wrapper.rs
@@ -496,6 +496,20 @@ impl<'le> TElement<'le> for LayoutElement<'le> {
             self.element.has_class_for_layout(name)
         }
     }
+
+    #[inline(always)]
+    fn each_class(self, callback: |&Atom|) {
+        unsafe {
+            match self.element.get_classes_for_layout() {
+                None => {}
+                Some(mut classes) => {
+                    for class in classes {
+                        callback(class)
+                    }
+                }
+            }
+        }
+    }
 }
 
 fn get_content(content_list: &content::T) -> String {
@@ -890,13 +904,13 @@ pub unsafe fn layout_node_from_unsafe_layout_node(node: &UnsafeLayoutNode) -> La
 }
 
 /// A top-down traversal.
-pub trait PreorderDOMTraversal {
+pub trait PreorderDomTraversal {
     /// The operation to perform. Return true to continue or false to stop.
-    fn process(&self, _node: LayoutNode);
+    fn process(&self, node: LayoutNode);
 }
 
 /// A bottom-up traversal, with a optional in-order pass.
-pub trait PostorderDOMTraversal {
+pub trait PostorderDomTraversal {
     /// The operation to perform. Return true to continue or false to stop.
-    fn process(&self, _node: LayoutNode);
+    fn process(&self, node: LayoutNode);
 }