Bug 1487137 - Shrink CascadeData by turning the bloom filters into hash sets. r=xidorn
authorEmilio Cobos Álvarez <emilio@crisal.io>
Sun, 02 Sep 2018 23:03:47 +0000
changeset 482803 c89d5d8a9f2cfb9d1d00992fdbc81c001b016bbb
parent 482802 bd240b5fa7f37aa89a321aa83cc8a501da85a1ed
child 482804 f2ded2a48b5cc785b29103aa9ae40d1e6d28107d
push id232
push userfmarier@mozilla.com
push dateWed, 05 Sep 2018 20:45:54 +0000
reviewersxidorn
bugs1487137
milestone63.0a1
Bug 1487137 - Shrink CascadeData by turning the bloom filters into hash sets. r=xidorn We're wasting 1kb there, which is kind of stupid. The only advantage of using a bloom filter is that memory usage doesn't increase even if there's a gazillion attribute selectors and such. But: * For IDs we already have a bunch of data structures for invalidation and such which key on the id, so the bloom filter would be a very minor thing. * For attribute selectors we don't have such a data structure, but if people used a gazillion attribute selectors we should! Differential Revision: https://phabricator.services.mozilla.com/D4668
servo/components/style/stylist.rs
--- a/servo/components/style/stylist.rs
+++ b/servo/components/style/stylist.rs
@@ -19,21 +19,21 @@ use invalidation::media_queries::{Effect
 use malloc_size_of::{MallocShallowSizeOf, MallocSizeOf, MallocSizeOfOps};
 #[cfg(feature = "gecko")]
 use malloc_size_of::MallocUnconditionalShallowSizeOf;
 use media_queries::Device;
 use properties::{self, CascadeMode, ComputedValues};
 use properties::{AnimationRules, PropertyDeclarationBlock};
 use rule_cache::{RuleCache, RuleCacheConditions};
 use rule_tree::{CascadeLevel, RuleTree, ShadowCascadeOrder, StrongRuleNode, StyleSource};
-use selector_map::{PrecomputedHashMap, SelectorMap, SelectorMapEntry};
+use selector_map::{PrecomputedHashMap, PrecomputedHashSet, SelectorMap, SelectorMapEntry};
 use selector_parser::{PerPseudoElementMap, PseudoElement, SelectorImpl, SnapshotMap};
 use selectors::NthIndexCache;
 use selectors::attr::{CaseSensitivity, NamespaceConstraint};
-use selectors::bloom::{BloomFilter, NonCountingBloomFilter};
+use selectors::bloom::BloomFilter;
 use selectors::matching::{matches_selector, ElementSelectorFlags, MatchingContext, MatchingMode};
 use selectors::matching::VisitedHandlingMode;
 use selectors::parser::{AncestorHashes, Combinator, Component, Selector};
 use selectors::parser::{SelectorIter, Visit};
 use selectors::visitor::SelectorVisitor;
 use servo_arc::{Arc, ArcBorrow};
 use shared_lock::{Locked, SharedRwLockReadGuard, StylesheetGuards};
 use smallbitvec::SmallBitVec;
@@ -1394,18 +1394,17 @@ impl Stylist {
     {
         // If id needs to be compared case-insensitively, the logic below
         // wouldn't work. Just conservatively assume it may have such rules.
         match self.quirks_mode().classes_and_ids_case_sensitivity() {
             CaseSensitivity::AsciiCaseInsensitive => return true,
             CaseSensitivity::CaseSensitive => {},
         }
 
-        let hash = id.get_hash();
-        self.any_applicable_rule_data(element, |data| data.mapped_ids.might_contain_hash(hash))
+        self.any_applicable_rule_data(element, |data| data.mapped_ids.contains(id))
     }
 
     /// Returns the registered `@keyframes` animation for the specified name.
     #[inline]
     pub fn get_animation<'a, E>(
         &'a self,
         name: &Atom,
         element: E,
@@ -1751,21 +1750,19 @@ impl SelectorMapEntry for RevalidationSe
 struct StylistSelectorVisitor<'a> {
     /// Whether the selector needs revalidation for the style sharing cache.
     needs_revalidation: bool,
     /// Whether we've past the rightmost compound selector, not counting
     /// pseudo-elements.
     passed_rightmost_selector: bool,
     /// The filter with all the id's getting referenced from rightmost
     /// selectors.
-    mapped_ids: &'a mut NonCountingBloomFilter,
+    mapped_ids: &'a mut PrecomputedHashSet<Atom>,
     /// The filter with the local names of attributes there are selectors for.
-    attribute_dependencies: &'a mut NonCountingBloomFilter,
-    /// Whether there's any attribute selector for the [style] attribute.
-    style_attribute_dependency: &'a mut bool,
+    attribute_dependencies: &'a mut PrecomputedHashSet<LocalName>,
     /// All the states selectors in the page reference.
     state_dependencies: &'a mut ElementState,
     /// All the document states selectors in the page reference.
     document_state_dependencies: &'a mut DocumentState,
 }
 
 fn component_needs_revalidation(
     c: &Component<SelectorImpl>,
@@ -1820,23 +1817,18 @@ impl<'a> SelectorVisitor for StylistSele
     }
 
     fn visit_attribute_selector(
         &mut self,
         _ns: &NamespaceConstraint<&Namespace>,
         name: &LocalName,
         lower_name: &LocalName,
     ) -> bool {
-        if *lower_name == local_name!("style") {
-            *self.style_attribute_dependency = true;
-        } else {
-            self.attribute_dependencies.insert_hash(name.get_hash());
-            self.attribute_dependencies
-                .insert_hash(lower_name.get_hash());
-        }
+        self.attribute_dependencies.insert(name.clone());
+        self.attribute_dependencies.insert(lower_name.clone());
         true
     }
 
     fn visit_simple_selector(&mut self, s: &Component<SelectorImpl>) -> bool {
         self.needs_revalidation = self.needs_revalidation ||
             component_needs_revalidation(s, self.passed_rightmost_selector);
 
         match *s {
@@ -1852,17 +1844,17 @@ impl<'a> SelectorVisitor for StylistSele
                 // That can be detected by a visit_complex_selector call with a
                 // combinator other than None and PseudoElement.
                 //
                 // Importantly, this call happens before we visit any of the
                 // simple selectors in that ComplexSelector.
                 //
                 // NOTE(emilio): See the comment regarding on when this may
                 // break in visit_complex_selector.
-                self.mapped_ids.insert_hash(id.get_hash());
+                self.mapped_ids.insert(id.clone());
             },
             _ => {},
         }
 
         true
     }
 }
 
@@ -1952,45 +1944,35 @@ pub struct CascadeData {
     /// containing style scopes starting from the closest assigned slot.
     slotted_rules: Option<Box<ElementAndPseudoRules>>,
 
     /// The invalidation map for these rules.
     invalidation_map: InvalidationMap,
 
     /// The attribute local names that appear in attribute selectors.  Used
     /// to avoid taking element snapshots when an irrelevant attribute changes.
-    /// (We don't bother storing the namespace, since namespaced attributes
-    /// are rare.)
-    #[ignore_malloc_size_of = "just an array"]
-    attribute_dependencies: NonCountingBloomFilter,
-
-    /// Whether `"style"` appears in an attribute selector.  This is not common,
-    /// and by tracking this explicitly, we can avoid taking an element snapshot
-    /// in the common case of style=""` changing due to modifying
-    /// `element.style`.  (We could track this in `attribute_dependencies`, like
-    /// all other attributes, but we should probably not risk incorrectly
-    /// returning `true` for `"style"` just due to a hash collision.)
-    style_attribute_dependency: bool,
+    /// (We don't bother storing the namespace, since namespaced attributes are
+    /// rare.)
+    attribute_dependencies: PrecomputedHashSet<Atom>,
 
     /// The element state bits that are relied on by selectors.  Like
     /// `attribute_dependencies`, this is used to avoid taking element snapshots
     /// when an irrelevant element state bit changes.
     state_dependencies: ElementState,
 
     /// The document state bits that are relied on by selectors.  This is used
     /// to tell whether we need to restyle the entire document when a document
     /// state bit changes.
     document_state_dependencies: DocumentState,
 
     /// The ids that appear in the rightmost complex selector of selectors (and
     /// hence in our selector maps).  Used to determine when sharing styles is
     /// safe: we disallow style sharing for elements whose id matches this
     /// filter, and hence might be in one of our selector maps.
-    #[ignore_malloc_size_of = "just an array"]
-    mapped_ids: NonCountingBloomFilter,
+    mapped_ids: PrecomputedHashSet<LocalName>,
 
     /// Selectors that require explicit cache revalidation (i.e. which depend
     /// on state that is not otherwise visible to the cache, like attributes or
     /// tree-structural state like child index and pseudos).
     #[ignore_malloc_size_of = "Arc"]
     selectors_for_cache_revalidation: SelectorMap<RevalidationSelectorAndHashes>,
 
     /// A map with all the animations at this `CascadeData`'s origin, indexed
@@ -2017,21 +1999,20 @@ pub struct CascadeData {
 impl CascadeData {
     /// Creates an empty `CascadeData`.
     pub fn new() -> Self {
         Self {
             normal_rules: ElementAndPseudoRules::default(),
             host_rules: None,
             slotted_rules: None,
             invalidation_map: InvalidationMap::new(),
-            attribute_dependencies: NonCountingBloomFilter::new(),
-            style_attribute_dependency: false,
+            attribute_dependencies: PrecomputedHashSet::default(),
             state_dependencies: ElementState::empty(),
             document_state_dependencies: DocumentState::empty(),
-            mapped_ids: NonCountingBloomFilter::new(),
+            mapped_ids: PrecomputedHashSet::default(),
             selectors_for_cache_revalidation: SelectorMap::new(),
             animations: Default::default(),
             extra_data: ExtraStyleData::default(),
             effective_media_query_results: EffectiveMediaQueryResults::new(),
             rules_source_order: 0,
             num_selectors: 0,
             num_declarations: 0,
         }
@@ -2086,23 +2067,19 @@ impl CascadeData {
     pub fn has_state_dependency(&self, state: ElementState) -> bool {
         self.state_dependencies.intersects(state)
     }
 
     /// Returns whether the given attribute might appear in an attribute
     /// selector of some rule.
     #[inline]
     pub fn might_have_attribute_dependency(&self, local_name: &LocalName) -> bool {
-        if *local_name == local_name!("style") {
-            return self.style_attribute_dependency;
-        }
+        self.attribute_dependencies.contains(local_name)
+    }
 
-        self.attribute_dependencies
-            .might_contain_hash(local_name.get_hash())
-    }
     #[inline]
     fn normal_rules(&self, pseudo: Option<&PseudoElement>) -> Option<&SelectorMap<Rule>> {
         self.normal_rules.rules(pseudo)
     }
 
     #[inline]
     fn host_rules(&self, pseudo: Option<&PseudoElement>) -> Option<&SelectorMap<Rule>> {
         self.host_rules.as_ref().and_then(|d| d.rules(pseudo))
@@ -2219,17 +2196,16 @@ impl CascadeData {
                         );
 
                         if rebuild_kind.should_rebuild_invalidation() {
                             self.invalidation_map.note_selector(selector, quirks_mode)?;
                             let mut visitor = StylistSelectorVisitor {
                                 needs_revalidation: false,
                                 passed_rightmost_selector: false,
                                 attribute_dependencies: &mut self.attribute_dependencies,
-                                style_attribute_dependency: &mut self.style_attribute_dependency,
                                 state_dependencies: &mut self.state_dependencies,
                                 document_state_dependencies: &mut self.document_state_dependencies,
                                 mapped_ids: &mut self.mapped_ids,
                             };
 
                             rule.selector.visit(&mut visitor);
 
                             if visitor.needs_revalidation {
@@ -2429,17 +2405,16 @@ impl CascadeData {
         self.num_selectors = 0;
         self.num_declarations = 0;
     }
 
     fn clear(&mut self) {
         self.clear_cascade_data();
         self.invalidation_map.clear();
         self.attribute_dependencies.clear();
-        self.style_attribute_dependency = false;
         self.state_dependencies = ElementState::empty();
         self.document_state_dependencies = DocumentState::empty();
         self.mapped_ids.clear();
         self.selectors_for_cache_revalidation.clear();
         self.effective_media_query_results.clear();
     }
 
     /// Measures heap usage.
@@ -2525,25 +2500,23 @@ impl Rule {
             style_rule: style_rule,
             source_order: source_order,
         }
     }
 }
 
 /// A function to be able to test the revalidation stuff.
 pub fn needs_revalidation_for_testing(s: &Selector<SelectorImpl>) -> bool {
-    let mut attribute_dependencies = NonCountingBloomFilter::new();
-    let mut mapped_ids = NonCountingBloomFilter::new();
-    let mut style_attribute_dependency = false;
+    let mut attribute_dependencies = Default::default();
+    let mut mapped_ids = Default::default();
     let mut state_dependencies = ElementState::empty();
     let mut document_state_dependencies = DocumentState::empty();
     let mut visitor = StylistSelectorVisitor {
         needs_revalidation: false,
         passed_rightmost_selector: false,
         attribute_dependencies: &mut attribute_dependencies,
-        style_attribute_dependency: &mut style_attribute_dependency,
         state_dependencies: &mut state_dependencies,
         document_state_dependencies: &mut document_state_dependencies,
         mapped_ids: &mut mapped_ids,
     };
     s.visit(&mut visitor);
     visitor.needs_revalidation
 }