servo: Merge #18798 - style: Optimize custom properties cycle removal (from emilio:faster-custom-props); r=SimonSapin
authorEmilio Cobos Álvarez <emilio@crisal.io>
Tue, 10 Oct 2017 02:47:29 -0500
changeset 385299 9ffdf501b79961a39d905ca047a4dbe0c3d3f815
parent 385298 3cbeb81d083a4f40224c6af755a90ee9bfbee0f5
child 385300 61aeae25af583b6d1b2a4c4723765e1132fe8fda
push id32652
push userarchaeopteryx@coole-files.de
push dateTue, 10 Oct 2017 21:49:31 +0000
treeherdermozilla-central@f1ecd5c26948 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersSimonSapin
bugs1405411
milestone58.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 #18798 - style: Optimize custom properties cycle removal (from emilio:faster-custom-props); r=SimonSapin After #18791, this is the major custom_properties perf bottleneck in the testcase from bug 1405411. I'm looking into how to efficiently merge this into `substitute_all`, but meanwhile this is worth landing, and makes most of the overhead go away. Source-Repo: https://github.com/servo/servo Source-Revision: 27cb13314e5d4a0653887768c374cbc81d7f098b
servo/components/style/custom_properties.rs
--- a/servo/components/style/custom_properties.rs
+++ b/servo/components/style/custom_properties.rs
@@ -8,16 +8,17 @@
 
 use Atom;
 use cssparser::{Delimiter, Parser, ParserInput, SourcePosition, Token, TokenSerializationType};
 use precomputed_hash::PrecomputedHash;
 use properties::{CSSWideKeyword, DeclaredValue};
 use selector_map::{PrecomputedHashSet, PrecomputedHashMap, PrecomputedDiagnosticHashMap};
 use selectors::parser::SelectorParseError;
 use servo_arc::Arc;
+use smallvec::SmallVec;
 use std::ascii::AsciiExt;
 use std::borrow::{Borrow, Cow};
 use std::fmt;
 use std::hash::Hash;
 use style_traits::{ToCss, StyleParseError, ParseError};
 
 /// A custom property name is just an `Atom`.
 ///
@@ -541,51 +542,58 @@ impl<'a> CustomPropertiesBuilder<'a> {
 
 /// https://drafts.csswg.org/css-variables/#cycles
 ///
 /// The initial value of a custom property is represented by this property not
 /// being in the map.
 fn remove_cycles(map: &mut CustomPropertiesMap) {
     let mut to_remove = PrecomputedHashSet::default();
     {
+        type VisitedNamesStack<'a> = SmallVec<[&'a Name; 10]>;
+
         let mut visited = PrecomputedHashSet::default();
-        let mut stack = Vec::new();
-        for name in &map.index {
-            walk(map, name, &mut stack, &mut visited, &mut to_remove);
+        let mut stack = VisitedNamesStack::new();
+        for (name, value) in map.iter() {
+            walk(map, name, value, &mut stack, &mut visited, &mut to_remove);
 
             fn walk<'a>(
                 map: &'a CustomPropertiesMap,
                 name: &'a Name,
-                stack: &mut Vec<&'a Name>,
+                value: &'a Arc<VariableValue>,
+                stack: &mut VisitedNamesStack<'a>,
                 visited: &mut PrecomputedHashSet<&'a Name>,
                 to_remove: &mut PrecomputedHashSet<Name>,
             ) {
+                if value.references.is_empty() {
+                    return;
+                }
+
                 let already_visited_before = !visited.insert(name);
                 if already_visited_before {
                     return
                 }
-                if let Some(ref value) = map.get(name) {
-                    if !value.references.is_empty() {
-                        stack.push(name);
-                        for next in value.references.iter() {
-                            if let Some(position) = stack.iter().position(|x| *x == next) {
-                                // Found a cycle
-                                for &in_cycle in &stack[position..] {
-                                    to_remove.insert(in_cycle.clone());
-                                }
-                            } else {
-                                walk(map, next, stack, visited, to_remove);
-                            }
+
+                stack.push(name);
+                for next in value.references.iter() {
+                    if let Some(position) = stack.iter().position(|x| *x == next) {
+                        // Found a cycle
+                        for &in_cycle in &stack[position..] {
+                            to_remove.insert(in_cycle.clone());
                         }
-                        stack.pop();
+                    } else {
+                        if let Some(value) = map.get(next) {
+                            walk(map, next, value, stack, visited, to_remove);
+                        }
                     }
                 }
+                stack.pop();
             }
         }
     }
+
     for name in to_remove {
         map.remove(&name);
     }
 }
 
 /// Replace `var()` functions for all custom properties.
 fn substitute_all(custom_properties_map: &mut CustomPropertiesMap) {
     // FIXME(emilio): This stash is needed because we can't prove statically to