Title: [263092] trunk/Source/WebCore
Revision
263092
Author
[email protected]
Date
2020-06-16 08:12:32 -0700 (Tue, 16 Jun 2020)

Log Message

O(n^2) behavior in media query resolution
https://bugs.webkit.org/show_bug.cgi?id=213243

Reviewed by Anders Carlsson.

We were traversing all rules in a RuleSet inside a loop over all media queries that change value.
This becomes problematic when you have thousands of media queries.

* style/RuleSet.cpp:
(WebCore::Style::RuleSet::evaluteDynamicMediaQueryRules):

Instead collect the rule positions that need flipping into a map and then traverse only once
to do the actual flipping.

Longer term we should maintain a data stucture that can map directly from a position to RuleDatas.
This will require some data structure rethink so this patch takes a simpler approach.

(WebCore::Style::RuleSet::MediaQueryCollector::pop):
* style/RuleSet.h:

Modified Paths

Diff

Modified: trunk/Source/WebCore/ChangeLog (263091 => 263092)


--- trunk/Source/WebCore/ChangeLog	2020-06-16 15:06:36 UTC (rev 263091)
+++ trunk/Source/WebCore/ChangeLog	2020-06-16 15:12:32 UTC (rev 263092)
@@ -1,3 +1,25 @@
+2020-06-16  Antti Koivisto  <[email protected]>
+
+        O(n^2) behavior in media query resolution
+        https://bugs.webkit.org/show_bug.cgi?id=213243
+
+        Reviewed by Anders Carlsson.
+
+        We were traversing all rules in a RuleSet inside a loop over all media queries that change value.
+        This becomes problematic when you have thousands of media queries.
+
+        * style/RuleSet.cpp:
+        (WebCore::Style::RuleSet::evaluteDynamicMediaQueryRules):
+
+        Instead collect the rule positions that need flipping into a map and then traverse only once
+        to do the actual flipping.
+
+        Longer term we should maintain a data stucture that can map directly from a position to RuleDatas.
+        This will require some data structure rethink so this patch takes a simpler approach.
+
+        (WebCore::Style::RuleSet::MediaQueryCollector::pop):
+        * style/RuleSet.h:
+
 2020-06-16  Per Arne Vollan  <[email protected]>
 
         [iOS] Collecting screen properties in the UI process introduced a Safari launch time regression.

Modified: trunk/Source/WebCore/style/RuleSet.cpp (263091 => 263092)


--- trunk/Source/WebCore/style/RuleSet.cpp	2020-06-16 15:06:36 UTC (rev 263091)
+++ trunk/Source/WebCore/style/RuleSet.cpp	2020-06-16 15:12:32 UTC (rev 263092)
@@ -422,6 +422,8 @@
 {
     CollectedMediaQueryChanges collectedChanges;
 
+    HashMap<size_t, bool, DefaultHash<size_t>::Hash, WTF::UnsignedWithZeroKeyHashTraits<size_t>> affectedRulePositionsAndResults;
+
     for (size_t i = startIndex; i < m_dynamicMediaQueryRules.size(); ++i) {
         auto& dynamicRules = m_dynamicMediaQueryRules[i];
         bool result = true;
@@ -440,11 +442,8 @@
                 continue;
             }
 
-            traverseRuleDatas([&](RuleData& ruleData) {
-                if (!dynamicRules.affectedRulePositions.contains(ruleData.position()))
-                    return;
-                ruleData.setEnabled(result);
-            });
+            for (auto position : dynamicRules.affectedRulePositions)
+                affectedRulePositionsAndResults.add(position, result);
 
             collectedChanges.changedQueryIndexes.append(i);
             collectedChanges.ruleFeatures.append(&dynamicRules.ruleFeatures);
@@ -451,6 +450,16 @@
         }
     }
 
+    if (affectedRulePositionsAndResults.isEmpty())
+        return collectedChanges;
+
+    traverseRuleDatas([&](RuleData& ruleData) {
+        auto it = affectedRulePositionsAndResults.find(ruleData.position());
+        if (it == affectedRulePositionsAndResults.end())
+            return;
+        ruleData.setEnabled(it->value);
+    });
+
     return collectedChanges;
 }
 
@@ -523,9 +532,7 @@
             rules.mediaQuerySets.append(context.set.get());
 
         if (collectDynamic) {
-            auto& toAdd = dynamicContextStack.last().affectedRulePositions;
-            rules.affectedRulePositions.add(toAdd.begin(), toAdd.end());
-
+            rules.affectedRulePositions.appendVector(dynamicContextStack.last().affectedRulePositions);
             rules.ruleFeatures = WTFMove(dynamicContextStack.last().ruleFeatures);
             rules.ruleFeatures.shrinkToFit();
         } else

Modified: trunk/Source/WebCore/style/RuleSet.h (263091 => 263092)


--- trunk/Source/WebCore/style/RuleSet.h	2020-06-16 15:06:36 UTC (rev 263091)
+++ trunk/Source/WebCore/style/RuleSet.h	2020-06-16 15:12:32 UTC (rev 263092)
@@ -72,7 +72,7 @@
 
     struct DynamicMediaQueryRules {
         Vector<Ref<const MediaQuerySet>> mediaQuerySets;
-        HashSet<size_t, DefaultHash<size_t>::Hash, WTF::UnsignedWithZeroKeyHashTraits<size_t>> affectedRulePositions;
+        Vector<size_t> affectedRulePositions;
         Vector<RuleFeature> ruleFeatures;
         bool requiresFullReset { false };
         bool result { true };
_______________________________________________
webkit-changes mailing list
[email protected]
https://lists.webkit.org/mailman/listinfo/webkit-changes

Reply via email to