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