Title: [118712] trunk/Source/WebCore
- Revision
- 118712
- Author
- macpher...@chromium.org
- Date
- 2012-05-28 16:56:36 -0700 (Mon, 28 May 2012)
Log Message
Make CSSParser::filteredProperties() O(n) instead of O(n^2) and improve readability.
https://bugs.webkit.org/show_bug.cgi?id=87078
Reviewed by Darin Adler.
This patch implements a number of improvements to filteredProperties:
1) Make the code more linearly readable by separating out handling of important and non-important properties.
2) Eliminate one BitArray instance (reduces hot memory so more cache friendly).
3) Remove O(n^2) behavior caused by scanning for and removing previously encountered definitions of each property.
The key algorithmic change is to add properties in decreasing precedence:
a) Iterating once per (important, !important) so that important properties are visited first.
b) Reverse iteration of m_parsedProperties visits the properties in decreasing precedence.
Covered by loads of existing tests - getting CSS property precedence wrong results in too many errors to list.
In particular fast/css contains test cases for important corner cases like duplicated important properties.
* css/CSSParser.cpp:
(WebCore::CSSParser::createStylePropertySet):
* css/CSSProperty.h:
Add vector traits so that CSSProperty can just be memset by vector without calling constructor.
Modified Paths
Diff
Modified: trunk/Source/WebCore/ChangeLog (118711 => 118712)
--- trunk/Source/WebCore/ChangeLog 2012-05-28 23:52:47 UTC (rev 118711)
+++ trunk/Source/WebCore/ChangeLog 2012-05-28 23:56:36 UTC (rev 118712)
@@ -1,3 +1,26 @@
+2012-05-28 Luke Macpherson <macpher...@chromium.org>
+
+ Make CSSParser::filteredProperties() O(n) instead of O(n^2) and improve readability.
+ https://bugs.webkit.org/show_bug.cgi?id=87078
+
+ Reviewed by Darin Adler.
+
+ This patch implements a number of improvements to filteredProperties:
+ 1) Make the code more linearly readable by separating out handling of important and non-important properties.
+ 2) Eliminate one BitArray instance (reduces hot memory so more cache friendly).
+ 3) Remove O(n^2) behavior caused by scanning for and removing previously encountered definitions of each property.
+ The key algorithmic change is to add properties in decreasing precedence:
+ a) Iterating once per (important, !important) so that important properties are visited first.
+ b) Reverse iteration of m_parsedProperties visits the properties in decreasing precedence.
+
+ Covered by loads of existing tests - getting CSS property precedence wrong results in too many errors to list.
+ In particular fast/css contains test cases for important corner cases like duplicated important properties.
+
+ * css/CSSParser.cpp:
+ (WebCore::CSSParser::createStylePropertySet):
+ * css/CSSProperty.h:
+ Add vector traits so that CSSProperty can just be memset by vector without calling constructor.
+
2012-05-28 MORITA Hajime <morr...@google.com>
Can't edit <input> elements with :first-letter
Modified: trunk/Source/WebCore/css/CSSParser.cpp (118711 => 118712)
--- trunk/Source/WebCore/css/CSSParser.cpp 2012-05-28 23:52:47 UTC (rev 118711)
+++ trunk/Source/WebCore/css/CSSParser.cpp 2012-05-28 23:56:36 UTC (rev 118712)
@@ -1177,38 +1177,33 @@
return m_mediaQuery.release();
}
-PassRefPtr<StylePropertySet> CSSParser::createStylePropertySet()
+static inline void filterProperties(bool important, const CSSParser::ParsedPropertyVector& input, StylePropertyVector& output, size_t& unusedEntries, BitArray<numCSSProperties>& seenProperties)
{
- BitArray<numCSSProperties> seenProperties;
- BitArray<numCSSProperties> seenImportantProperties;
-
- StylePropertyVector results;
- results.reserveInitialCapacity(m_parsedProperties.size());
-
- for (unsigned i = 0; i < m_parsedProperties.size(); ++i) {
- const CSSProperty& property = m_parsedProperties[i];
+ // Add properties in reverse order so that highest priority definitions are reached first. Duplicate definitions can then be ignored when found.
+ for (int i = input.size() - 1; i >= 0; --i) {
+ const CSSProperty& property = input[i];
+ if (property.isImportant() != important)
+ continue;
const unsigned propertyIDIndex = property.id() - firstCSSProperty;
-
- // Ignore non-important properties if we already have an important property with the same ID.
- if (!property.isImportant() && seenImportantProperties.get(propertyIDIndex))
+ if (seenProperties.get(propertyIDIndex))
continue;
+ seenProperties.set(propertyIDIndex);
+ output[--unusedEntries] = property;
+ }
+}
- // If we already had this property, this new one takes precedence, so wipe out the old one.
- if (seenProperties.get(propertyIDIndex)) {
- for (unsigned i = 0; i < results.size(); ++i) {
- if (results[i].id() == property.id()) {
- results.remove(i);
- break;
- }
- }
- }
+PassRefPtr<StylePropertySet> CSSParser::createStylePropertySet()
+{
+ BitArray<numCSSProperties> seenProperties;
+ size_t unusedEntries = m_parsedProperties.size();
+ StylePropertyVector results = Vector<CSSProperty>(unusedEntries);
- if (property.isImportant())
- seenImportantProperties.set(propertyIDIndex);
- seenProperties.set(propertyIDIndex);
+ // Important properties have higher priority, so add them first. Duplicate definitions can then be ignored when found.
+ filterProperties(true, m_parsedProperties, results, unusedEntries, seenProperties);
+ filterProperties(false, m_parsedProperties, results, unusedEntries, seenProperties);
- results.uncheckedAppend(property);
- }
+ if (unusedEntries)
+ results.remove(0, unusedEntries);
return StylePropertySet::adopt(results, m_context.mode);
}
Modified: trunk/Source/WebCore/css/CSSParser.h (118711 => 118712)
--- trunk/Source/WebCore/css/CSSParser.h 2012-05-28 23:52:47 UTC (rev 118711)
+++ trunk/Source/WebCore/css/CSSParser.h 2012-05-28 23:56:36 UTC (rev 118712)
@@ -293,7 +293,8 @@
RefPtr<StyleKeyframe> m_keyframe;
OwnPtr<MediaQuery> m_mediaQuery;
OwnPtr<CSSParserValueList> m_valueList;
- Vector<CSSProperty, 256> m_parsedProperties;
+ typedef Vector<CSSProperty, 256> ParsedPropertyVector;
+ ParsedPropertyVector m_parsedProperties;
CSSSelectorList* m_selectorListForParseSelector;
unsigned m_numParsedPropertiesBeforeMarginBox;
Modified: trunk/Source/WebCore/css/CSSProperty.h (118711 => 118712)
--- trunk/Source/WebCore/css/CSSProperty.h 2012-05-28 23:52:47 UTC (rev 118711)
+++ trunk/Source/WebCore/css/CSSProperty.h 2012-05-28 23:56:36 UTC (rev 118712)
@@ -71,4 +71,11 @@
} // namespace WebCore
+namespace WTF {
+template <> struct VectorTraits<WebCore::CSSProperty> : VectorTraitsBase<false, WebCore::CSSProperty> {
+ static const bool canInitializeWithMemset = true;
+ static const bool canMoveWithMemcpy = true;
+};
+}
+
#endif // CSSProperty_h
_______________________________________________
webkit-changes mailing list
webkit-changes@lists.webkit.org
http://lists.webkit.org/mailman/listinfo.cgi/webkit-changes
