servo: Merge #17172 - Parent mismatch should not clear style sharing cache (from bzbarsky:cache-parent-level); r=emilio
authorBoris Zbarsky <bzbarsky@mit.edu>
Mon, 05 Jun 2017 14:36:35 -0700
changeset 410543 2d7a5edd935126b48e9dc389906bd11213c23648
parent 410542 e39f4e926692dc1b2c82b1c6cb7d5ac406a90a69
child 410544 e709485195e6ca9855a618036297ae5b988f7169
push id7391
push usermtabara@mozilla.com
push dateMon, 12 Jun 2017 13:08:53 +0000
treeherdermozilla-beta@2191d7f87e2e [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersemilio
bugs17172, 1369620
milestone55.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
servo: Merge #17172 - Parent mismatch should not clear style sharing cache (from bzbarsky:cache-parent-level); r=emilio We can have cousins in the cache whose parent doesn't match ours, and other cousins whose parent does. When we encounter one of the former, that's not a reason to stop lookin for the latter. Fixes https://bugzilla.mozilla.org/show_bug.cgi?id=1369620 <!-- Please describe your changes on the following line: --> --- <!-- Thank you for contributing to Servo! Please replace each `[ ]` by `[X]` when the step is complete, and replace `__` with appropriate data: --> - [X] `./mach build -d` does not report any errors - [X] `./mach test-tidy` does not report any errors - [X] These changes fix https://bugzilla.mozilla.org/show_bug.cgi?id=1369620" <!-- Either: --> - [ ] There are tests for these changes OR - [ ] These changes do not require tests because _____ <!-- Also, please make sure that "Allow edits from maintainers" checkbox is checked, so that we can help you if you get stuck somewhere along the way.--> <!-- Pull requests that do not address these steps are welcome, but they will require additional verification as part of the review process. --> Source-Repo: https://github.com/servo/servo Source-Revision: bba5339efc620b519f9bfd62b5b1e4654cd4234c
servo/components/style/bloom.rs
servo/components/style/matching.rs
servo/components/style/sharing/mod.rs
--- a/servo/components/style/bloom.rs
+++ b/servo/components/style/bloom.rs
@@ -117,16 +117,22 @@ impl<E: TElement> StyleBloom<E> {
         popped
     }
 
     /// Returns true if the bloom filter is empty.
     pub fn is_empty(&self) -> bool {
         self.elements.is_empty()
     }
 
+    /// Returns the DOM depth of elements that can be correctly
+    /// matched against the bloom filter (that is, the number of
+    /// elements in our list).
+    pub fn matching_depth(&self) -> usize {
+        self.elements.len()
+    }
 
     /// Clears the bloom filter.
     pub fn clear(&mut self) {
         self.filter.clear();
         self.elements.clear();
     }
 
     /// Rebuilds the bloom filter up to the parent of the given element.
--- a/servo/components/style/matching.rs
+++ b/servo/components/style/matching.rs
@@ -878,22 +878,24 @@ pub trait MatchMethods : TElement {
             // checker.
             let validation_data =
                 context.thread_local
                     .current_element_info
                     .as_mut().unwrap()
                     .validation_data
                     .take();
 
+            let dom_depth = context.thread_local.bloom_filter.matching_depth();
             context.thread_local
                    .style_sharing_candidate_cache
                    .insert_if_possible(self,
                                        data.styles().primary.values(),
                                        primary_results.relations,
-                                       validation_data);
+                                       validation_data,
+                                       dom_depth);
         }
 
         child_cascade_requirement
     }
 
     /// Performs the cascade, without matching.
     fn cascade_primary_and_pseudos(&self,
                                    context: &mut StyleContext<Self>,
--- a/servo/components/style/sharing/mod.rs
+++ b/servo/components/style/sharing/mod.rs
@@ -321,25 +321,30 @@ impl<E: TElement> StyleSharingTarget<E> 
 
     /// Attempts to share a style with another node.
     pub fn share_style_if_possible(
         mut self,
         context: &mut StyleContext<E>,
         data: &mut ElementData)
         -> StyleSharingResult
     {
+        let cache = &mut context.thread_local.style_sharing_candidate_cache;
         let shared_context = &context.shared;
         let selector_flags_map = &mut context.thread_local.selector_flags;
         let bloom_filter = &context.thread_local.bloom_filter;
 
+        if cache.dom_depth != bloom_filter.matching_depth() {
+            debug!("Can't share style, because DOM depth changed from {:?} to {:?}, element: {:?}",
+                   cache.dom_depth, bloom_filter.matching_depth(), self.element);
+            return StyleSharingResult::CannotShare;
+        }
         debug_assert_eq!(bloom_filter.current_parent(),
                          self.element.parent_element());
 
-        let result = context.thread_local
-            .style_sharing_candidate_cache
+        let result = cache
             .share_style_if_possible(shared_context,
                                      selector_flags_map,
                                      bloom_filter,
                                      &mut self,
                                      data);
 
 
         context.thread_local.current_element_info.as_mut().unwrap().validation_data =
@@ -393,23 +398,28 @@ pub enum StyleSharingResult {
 
 /// An LRU cache of the last few nodes seen, so that we can aggressively try to
 /// reuse their styles.
 ///
 /// Note that this cache is flushed every time we steal work from the queue, so
 /// storing nodes here temporarily is safe.
 pub struct StyleSharingCandidateCache<E: TElement> {
     cache: LRUCache<[StyleSharingCandidate<E>; STYLE_SHARING_CANDIDATE_CACHE_SIZE + 1]>,
+    /// The DOM depth we're currently at.  This is used as an optimization to
+    /// clear the cache when we change depths, since we know at that point
+    /// nothing in the cache will match.
+    dom_depth: usize,
 }
 
 impl<E: TElement> StyleSharingCandidateCache<E> {
     /// Create a new style sharing candidate cache.
     pub fn new() -> Self {
         StyleSharingCandidateCache {
             cache: LRUCache::new(),
+            dom_depth: 0,
         }
     }
 
     /// Returns the number of entries in the cache.
     pub fn num_entries(&self) -> usize {
         self.cache.num_entries()
     }
 
@@ -419,17 +429,18 @@ impl<E: TElement> StyleSharingCandidateC
 
     /// Tries to insert an element in the style sharing cache.
     ///
     /// Fails if we know it should never be in the cache.
     pub fn insert_if_possible(&mut self,
                               element: &E,
                               style: &ComputedValues,
                               relations: StyleRelations,
-                              mut validation_data: ValidationData) {
+                              mut validation_data: ValidationData,
+                              dom_depth: usize) {
         use selectors::matching::AFFECTED_BY_PRESENTATIONAL_HINTS;
 
         let parent = match element.parent_element() {
             Some(element) => element,
             None => {
                 debug!("Failing to insert to the cache: no parent element");
                 return;
             }
@@ -462,16 +473,22 @@ impl<E: TElement> StyleSharingCandidateC
         // selector-matching.
         if !relations.intersects(AFFECTED_BY_PRESENTATIONAL_HINTS) {
             debug_assert!(validation_data.pres_hints.as_ref().map_or(true, |v| v.is_empty()));
             validation_data.pres_hints = Some(SmallVec::new());
         }
 
         debug!("Inserting into cache: {:?} with parent {:?}", element, parent);
 
+        if self.dom_depth != dom_depth {
+            debug!("Clearing cache because depth changed from {:?} to {:?}, element: {:?}",
+                   self.dom_depth, dom_depth, element);
+            self.clear();
+            self.dom_depth = dom_depth;
+        }
         self.cache.insert(StyleSharingCandidate {
             element: unsafe { SendElement::new(*element) },
             validation_data: validation_data,
         });
     }
 
     /// Touch a given index in the style sharing candidate cache.
     pub fn touch(&mut self, index: usize) {
@@ -504,17 +521,16 @@ impl<E: TElement> StyleSharingCandidateC
             return StyleSharingResult::CannotShare
         }
 
         if target.is_native_anonymous() {
             debug!("{:?} Cannot share style: NAC", target.element);
             return StyleSharingResult::CannotShare;
         }
 
-        let mut should_clear_cache = false;
         for (i, candidate) in self.iter_mut().enumerate() {
             let sharing_result =
                 Self::test_candidate(
                     target,
                     candidate,
                     &shared_context,
                     bloom_filter,
                     selector_flags_map
@@ -548,38 +564,29 @@ impl<E: TElement> StyleSharingCandidateC
                     return StyleSharingResult::StyleWasShared(i, child_cascade_requirement)
                 }
                 Err(miss) => {
                     debug!("Cache miss: {:?}", miss);
 
                     // Cache miss, let's see what kind of failure to decide
                     // whether we keep trying or not.
                     match miss {
-                        // Cache miss because of parent, clear the candidate cache.
-                        CacheMiss::Parent => {
-                            should_clear_cache = true;
-                            break;
-                        },
                         // Too expensive failure, give up, we don't want another
                         // one of these.
                         CacheMiss::PresHints |
                         CacheMiss::Revalidation => break,
                         _ => {}
                     }
                 }
             }
         }
 
         debug!("{:?} Cannot share style: {} cache entries", target.element,
                self.cache.num_entries());
 
-        if should_clear_cache {
-            self.clear();
-        }
-
         StyleSharingResult::CannotShare
     }
 
     fn test_candidate(target: &mut StyleSharingTarget<E>,
                       candidate: &mut StyleSharingCandidate<E>,
                       shared: &SharedStyleContext,
                       bloom: &StyleBloom<E>,
                       selector_flags_map: &mut SelectorFlagsMap<E>)