- Revision
- 293100
- Author
- obru...@igalia.com
- Date
- 2022-04-20 09:35:01 -0700 (Wed, 20 Apr 2022)
Log Message
[css-cascade] Optimize code for deferred properties
https://bugs.webkit.org/show_bug.cgi?id=238260
Reviewed by Darin Adler.
CSS declarations for deferred properties were just appended to a vector,
which could grow huge. Then StyleBuilder would apply them one by one,
doing useless work if a property appeared multiple times.
The point of deferred properties is that they should be applied in
relative order. But if a property appears multiple times, we should only
care about the last occurrence.
So this patch removes the vector and instead stores the Property in the
same array as non-deferred properties. To track the indices, it uses an
array instead of a HashMap.
When applying the properties, the property IDs are placed in a vector,
which is then sorted according to the corresponding indices. This can
have some overhead, but the size of the vector will be limited by the
number of deferred properties. Currently there are only 8 of these (in
bug 236199 I plan to add 96 more, but 104 is still not that big).
No new tests since there should be no change in behavior.
* style/PropertyCascade.cpp:
(WebCore::Style::PropertyCascade::buildCascade):
Call sortDeferredPropertyIDs().
(WebCore::Style::initializeCSSValue):
Move a low-level idiom into its own function.
(WebCore::Style::PropertyCascade::set):
Use the new initializeCSSValue().
(WebCore::Style::PropertyCascade::setDeferred):
Use the new data structures for deferred properties.
(WebCore::Style::PropertyCascade::sortDeferredPropertyIDs):
New private method to sort the deferred property IDs according to their
index.
* style/PropertyCascade.h:
(WebCore::Style::PropertyCascade::deferredPropertyIndex const):
New private method to get the index of the deferred property.
(WebCore::Style::PropertyCascade::setDeferredPropertyIndex):
New private method to set the index of a deferred property.
(WebCore::Style::PropertyCascade::hasDeferredProperty const):
Use the new data structures for deferred properties.
(WebCore::Style::PropertyCascade::deferredProperty const):
Use the new data structures for deferred properties.
(WebCore::Style::PropertyCascade::deferredPropertyIDs const):
New method to get the deferred property IDs sorted by their index.
(WebCore::Style::PropertyCascade::deferredProperties const): Deleted.
* style/StyleBuilder.cpp:
(WebCore::Style::Builder::applyDeferredProperties):
Use the new data structures for deferred properties.
Modified Paths
Diff
Modified: trunk/Source/WebCore/ChangeLog (293099 => 293100)
--- trunk/Source/WebCore/ChangeLog 2022-04-20 16:17:41 UTC (rev 293099)
+++ trunk/Source/WebCore/ChangeLog 2022-04-20 16:35:01 UTC (rev 293100)
@@ -1,3 +1,69 @@
+2022-04-20 Oriol Brufau <obru...@igalia.com>
+
+ [css-cascade] Optimize code for deferred properties
+ https://bugs.webkit.org/show_bug.cgi?id=238260
+
+ Reviewed by Darin Adler.
+
+ CSS declarations for deferred properties were just appended to a vector,
+ which could grow huge. Then StyleBuilder would apply them one by one,
+ doing useless work if a property appeared multiple times.
+
+ The point of deferred properties is that they should be applied in
+ relative order. But if a property appears multiple times, we should only
+ care about the last occurrence.
+
+ So this patch removes the vector and instead stores the Property in the
+ same array as non-deferred properties. To track the indices, it uses an
+ array instead of a HashMap.
+
+ When applying the properties, the property IDs are placed in a vector,
+ which is then sorted according to the corresponding indices. This can
+ have some overhead, but the size of the vector will be limited by the
+ number of deferred properties. Currently there are only 8 of these (in
+ bug 236199 I plan to add 96 more, but 104 is still not that big).
+
+ No new tests since there should be no change in behavior.
+
+ * style/PropertyCascade.cpp:
+ (WebCore::Style::PropertyCascade::buildCascade):
+ Call sortDeferredPropertyIDs().
+
+ (WebCore::Style::initializeCSSValue):
+ Move a low-level idiom into its own function.
+
+ (WebCore::Style::PropertyCascade::set):
+ Use the new initializeCSSValue().
+
+ (WebCore::Style::PropertyCascade::setDeferred):
+ Use the new data structures for deferred properties.
+
+ (WebCore::Style::PropertyCascade::sortDeferredPropertyIDs):
+ New private method to sort the deferred property IDs according to their
+ index.
+
+ * style/PropertyCascade.h:
+ (WebCore::Style::PropertyCascade::deferredPropertyIndex const):
+ New private method to get the index of the deferred property.
+
+ (WebCore::Style::PropertyCascade::setDeferredPropertyIndex):
+ New private method to set the index of a deferred property.
+
+ (WebCore::Style::PropertyCascade::hasDeferredProperty const):
+ Use the new data structures for deferred properties.
+
+ (WebCore::Style::PropertyCascade::deferredProperty const):
+ Use the new data structures for deferred properties.
+
+ (WebCore::Style::PropertyCascade::deferredPropertyIDs const):
+ New method to get the deferred property IDs sorted by their index.
+
+ (WebCore::Style::PropertyCascade::deferredProperties const): Deleted.
+
+ * style/StyleBuilder.cpp:
+ (WebCore::Style::Builder::applyDeferredProperties):
+ Use the new data structures for deferred properties.
+
2022-04-20 Simon Fraser <simon.fra...@apple.com>
Some AutoscrollController cleanup
Modified: trunk/Source/WebCore/style/PropertyCascade.cpp (293099 => 293100)
--- trunk/Source/WebCore/style/PropertyCascade.cpp 2022-04-20 16:17:41 UTC (rev 293099)
+++ trunk/Source/WebCore/style/PropertyCascade.cpp 2022-04-20 16:35:01 UTC (rev 293100)
@@ -77,6 +77,8 @@
continue;
addImportantMatches(cascadeLevel);
}
+
+ sortDeferredPropertyIDs();
}
void PropertyCascade::setPropertyInternal(Property& property, CSSPropertyID id, CSSValue& cssValue, const MatchedProperties& matchedProperties, CascadeLevel cascadeLevel)
@@ -96,6 +98,11 @@
property.cssValue[matchedProperties.linkMatchType] = &cssValue;
}
+static void initializeCSSValue(PropertyCascade::Property& property)
+{
+ property.cssValue = { };
+}
+
void PropertyCascade::set(CSSPropertyID id, CSSValue& cssValue, const MatchedProperties& matchedProperties, CascadeLevel cascadeLevel)
{
if (CSSProperty::isDirectionAwareProperty(id)) {
@@ -114,7 +121,7 @@
if (!hasValue) {
Property property;
property.id = id;
- memset(property.cssValue, 0, sizeof(property.cssValue));
+ initializeCSSValue(property);
setPropertyInternal(property, id, cssValue, matchedProperties, cascadeLevel);
m_customProperties.set(customValue.name(), property);
} else {
@@ -126,7 +133,7 @@
}
if (!m_propertyIsPresent[id])
- memset(property.cssValue, 0, sizeof(property.cssValue));
+ initializeCSSValue(property);
m_propertyIsPresent.set(id);
setPropertyInternal(property, id, cssValue, matchedProperties, cascadeLevel);
}
@@ -135,12 +142,16 @@
{
ASSERT(!CSSProperty::isDirectionAwareProperty(id));
ASSERT(id >= firstDeferredProperty);
+ ASSERT(id <= lastDeferredProperty);
- Property property;
- memset(property.cssValue, 0, sizeof(property.cssValue));
+ auto& property = m_properties[id];
+ if (!hasDeferredProperty(id)) {
+ initializeCSSValue(property);
+ m_lowestSeenDeferredProperty = std::min(m_lowestSeenDeferredProperty, id);
+ m_highestSeenDeferredProperty = std::max(m_highestSeenDeferredProperty, id);
+ }
+ setDeferredPropertyIndex(id, ++m_lastIndexForDeferred);
setPropertyInternal(property, id, cssValue, matchedProperties, cascadeLevel);
- m_deferredPropertiesIndices.set(id, m_deferredProperties.size());
- m_deferredProperties.append(property);
}
@@ -315,5 +326,20 @@
return m_direction;
}
+void PropertyCascade::sortDeferredPropertyIDs()
+{
+ auto begin = m_deferredPropertyIDs.begin();
+ auto end = begin;
+ for (uint16_t id = m_lowestSeenDeferredProperty; id <= m_highestSeenDeferredProperty; ++id) {
+ auto propertyID = static_cast<CSSPropertyID>(id);
+ if (hasDeferredProperty(propertyID))
+ *end++ = propertyID;
+ }
+ m_seenDeferredPropertyCount = end - begin;
+ std::sort(begin, end, [&](auto id1, auto id2) {
+ return deferredPropertyIndex(id1) < deferredPropertyIndex(id2);
+ });
}
+
}
+}
Modified: trunk/Source/WebCore/style/PropertyCascade.h (293099 => 293100)
--- trunk/Source/WebCore/style/PropertyCascade.h 2022-04-20 16:17:41 UTC (rev 293099)
+++ trunk/Source/WebCore/style/PropertyCascade.h 2022-04-20 16:35:01 UTC (rev 293100)
@@ -56,7 +56,7 @@
ScopeOrdinal styleScopeOrdinal;
CascadeLayerPriority cascadeLayerPriority;
FromStyleAttribute fromStyleAttribute;
- CSSValue* cssValue[3]; // Values for link match states MatchDefault, MatchLink and MatchVisited
+ std::array<CSSValue*, 3> cssValue; // Values for link match states MatchDefault, MatchLink and MatchVisited
};
bool hasNormalProperty(CSSPropertyID) const;
@@ -68,7 +68,7 @@
bool hasCustomProperty(const String&) const;
Property customProperty(const String&) const;
- const Vector<Property, 8>& deferredProperties() const { return m_deferredProperties; }
+ Span<const CSSPropertyID> deferredPropertyIDs() const;
const HashMap<AtomString, Property>& customProperties() const { return m_customProperties; }
Direction direction() const;
@@ -85,6 +85,10 @@
Direction resolveDirectionAndWritingMode(Direction inheritedDirection) const;
+ unsigned deferredPropertyIndex(CSSPropertyID) const;
+ void setDeferredPropertyIndex(CSSPropertyID, unsigned);
+ void sortDeferredPropertyIDs();
+
const MatchResult& m_matchResult;
const IncludedProperties m_includedProperties;
const CascadeLevel m_maximumCascadeLevel;
@@ -92,11 +96,24 @@
mutable Direction m_direction;
mutable bool m_directionIsUnresolved { true };
- Property m_properties[firstDeferredProperty];
- std::bitset<firstDeferredProperty> m_propertyIsPresent;
+ // The CSSPropertyID enum is sorted like this:
+ // 1. CSSPropertyInvalid and CSSPropertyCustom.
+ // 2. Normal properties (high priority ones followed by low priority ones).
+ // 3. Deferred properties.
+ //
+ // 'm_properties' is used for both normal and deferred properties, so it has size 'lastDeferredProperty + 1'.
+ // It could actually use 'numCSSProperties', but then we would have to subtract 'firstCSSProperty', which may not be worth it.
+ // 'm_propertyIsPresent' is not used for deferred properties, so we only need to cover up to the last low priority one.
+ std::array<Property, lastDeferredProperty + 1> m_properties;
+ std::bitset<lastLowPriorityProperty + 1> m_propertyIsPresent;
- Vector<Property, 8> m_deferredProperties;
- HashMap<CSSPropertyID, unsigned> m_deferredPropertiesIndices;
+ static constexpr unsigned deferredPropertyCount = lastDeferredProperty - firstDeferredProperty + 1;
+ std::array<unsigned, deferredPropertyCount> m_deferredPropertyIndices { };
+ unsigned m_lastIndexForDeferred { 0 };
+ std::array<CSSPropertyID, deferredPropertyCount> m_deferredPropertyIDs { };
+ unsigned m_seenDeferredPropertyCount { 0 };
+ CSSPropertyID m_lowestSeenDeferredProperty { lastDeferredProperty };
+ CSSPropertyID m_highestSeenDeferredProperty { firstDeferredProperty };
HashMap<AtomString, Property> m_customProperties;
};
@@ -113,20 +130,36 @@
return m_properties[id];
}
-inline bool PropertyCascade::hasDeferredProperty(CSSPropertyID id) const
+inline unsigned PropertyCascade::deferredPropertyIndex(CSSPropertyID id) const
{
ASSERT(id >= firstDeferredProperty);
- return m_deferredPropertiesIndices.contains(id);
+ ASSERT(id <= lastDeferredProperty);
+ return m_deferredPropertyIndices[id - firstDeferredProperty];
}
+inline void PropertyCascade::setDeferredPropertyIndex(CSSPropertyID id, unsigned index)
+{
+ ASSERT(id >= firstDeferredProperty);
+ ASSERT(id <= lastDeferredProperty);
+ m_deferredPropertyIndices[id - firstDeferredProperty] = index;
+}
+
+inline bool PropertyCascade::hasDeferredProperty(CSSPropertyID id) const
+{
+ return deferredPropertyIndex(id);
+}
+
inline const PropertyCascade::Property& PropertyCascade::deferredProperty(CSSPropertyID id) const
{
ASSERT(hasDeferredProperty(id));
- unsigned index = m_deferredPropertiesIndices.get(id);
- ASSERT(index < m_deferredProperties.size());
- return m_deferredProperties[index];
+ return m_properties[id];
}
+inline Span<const CSSPropertyID> PropertyCascade::deferredPropertyIDs() const
+{
+ return { m_deferredPropertyIDs.data(), m_seenDeferredPropertyCount };
+}
+
inline bool PropertyCascade::hasCustomProperty(const String& name) const
{
return m_customProperties.contains(name);
Modified: trunk/Source/WebCore/style/StyleBuilder.cpp (293099 => 293100)
--- trunk/Source/WebCore/style/StyleBuilder.cpp 2022-04-20 16:17:41 UTC (rev 293099)
+++ trunk/Source/WebCore/style/StyleBuilder.cpp 2022-04-20 16:35:01 UTC (rev 293100)
@@ -123,8 +123,8 @@
void Builder::applyDeferredProperties()
{
- for (auto& property : m_cascade.deferredProperties())
- applyCascadeProperty(property);
+ for (auto id : m_cascade.deferredPropertyIDs())
+ applyCascadeProperty(m_cascade.deferredProperty(id));
}
void Builder::applyProperties(int firstProperty, int lastProperty)
