- Revision
- 225482
- Author
- an...@apple.com
- Date
- 2017-12-04 10:37:00 -0800 (Mon, 04 Dec 2017)
Log Message
Remove duplicates from selector filter hashes
https://bugs.webkit.org/show_bug.cgi?id=180354
Reviewed by Simon Fraser.
We have only four slots for hashes in RuleSet and adding more regresses performance. To use the limited slots
better we should eliminate duplicates.
This patch also switches to using std::array instead of a C array for the hashes.
The patch reduces the number of selectors passing through the selector filter in StyleBench by ~0.4%.
* css/ElementRuleCollector.cpp:
(WebCore::ElementRuleCollector::collectMatchingRulesForList):
* css/RuleSet.cpp:
(WebCore::RuleData::RuleData):
* css/RuleSet.h:
(WebCore::RuleData::descendantSelectorIdentifierHashes const):
* css/SelectorFilter.cpp:
(WebCore::collectDescendantSelectorIdentifierHashes):
(WebCore::SelectorFilter::collectIdentifierHashes):
* css/SelectorFilter.h:
(WebCore::SelectorFilter::fastRejectSelector const):
Modified Paths
Diff
Modified: trunk/Source/WebCore/ChangeLog (225481 => 225482)
--- trunk/Source/WebCore/ChangeLog 2017-12-04 18:13:45 UTC (rev 225481)
+++ trunk/Source/WebCore/ChangeLog 2017-12-04 18:37:00 UTC (rev 225482)
@@ -1,3 +1,29 @@
+2017-12-04 Antti Koivisto <an...@apple.com>
+
+ Remove duplicates from selector filter hashes
+ https://bugs.webkit.org/show_bug.cgi?id=180354
+
+ Reviewed by Simon Fraser.
+
+ We have only four slots for hashes in RuleSet and adding more regresses performance. To use the limited slots
+ better we should eliminate duplicates.
+
+ This patch also switches to using std::array instead of a C array for the hashes.
+
+ The patch reduces the number of selectors passing through the selector filter in StyleBench by ~0.4%.
+
+ * css/ElementRuleCollector.cpp:
+ (WebCore::ElementRuleCollector::collectMatchingRulesForList):
+ * css/RuleSet.cpp:
+ (WebCore::RuleData::RuleData):
+ * css/RuleSet.h:
+ (WebCore::RuleData::descendantSelectorIdentifierHashes const):
+ * css/SelectorFilter.cpp:
+ (WebCore::collectDescendantSelectorIdentifierHashes):
+ (WebCore::SelectorFilter::collectIdentifierHashes):
+ * css/SelectorFilter.h:
+ (WebCore::SelectorFilter::fastRejectSelector const):
+
2017-12-04 Youenn Fablet <you...@apple.com>
WorkerCacheStorageConnection should handle the case of terminated workers
Modified: trunk/Source/WebCore/css/ElementRuleCollector.cpp (225481 => 225482)
--- trunk/Source/WebCore/css/ElementRuleCollector.cpp 2017-12-04 18:13:45 UTC (rev 225481)
+++ trunk/Source/WebCore/css/ElementRuleCollector.cpp 2017-12-04 18:37:00 UTC (rev 225482)
@@ -464,7 +464,7 @@
if (!ruleData.canMatchPseudoElement() && m_pseudoStyleRequest.pseudoId != NOPSEUDO)
continue;
- if (m_selectorFilter && m_selectorFilter->fastRejectSelector<RuleData::maximumIdentifierCount>(ruleData.descendantSelectorIdentifierHashes()))
+ if (m_selectorFilter && m_selectorFilter->fastRejectSelector(ruleData.descendantSelectorIdentifierHashes()))
continue;
StyleRule* rule = ruleData.rule();
Modified: trunk/Source/WebCore/css/RuleSet.cpp (225481 => 225482)
--- trunk/Source/WebCore/css/RuleSet.cpp 2017-12-04 18:13:45 UTC (rev 225481)
+++ trunk/Source/WebCore/css/RuleSet.cpp 2017-12-04 18:37:00 UTC (rev 225482)
@@ -164,7 +164,7 @@
{
ASSERT(m_position == position);
ASSERT(m_selectorIndex == selectorIndex);
- SelectorFilter::collectIdentifierHashes(selector(), m_descendantSelectorIdentifierHashes, maximumIdentifierCount);
+ SelectorFilter::collectIdentifierHashes(*selector(), m_descendantSelectorIdentifierHashes);
}
RuleSet::RuleSet() = default;
Modified: trunk/Source/WebCore/css/RuleSet.h (225481 => 225482)
--- trunk/Source/WebCore/css/RuleSet.h 2017-12-04 18:13:45 UTC (rev 225481)
+++ trunk/Source/WebCore/css/RuleSet.h 2017-12-04 18:37:00 UTC (rev 225482)
@@ -23,6 +23,7 @@
#include "RuleFeature.h"
#include "SelectorCompiler.h"
+#include "SelectorFilter.h"
#include "StyleRule.h"
#include <wtf/Forward.h>
#include <wtf/HashMap.h>
@@ -76,9 +77,7 @@
unsigned linkMatchType() const { return m_linkMatchType; }
bool hasDocumentSecurityOrigin() const { return m_hasDocumentSecurityOrigin; }
PropertyWhitelistType propertyWhitelistType() const { return static_cast<PropertyWhitelistType>(m_propertyWhitelistType); }
- // Try to balance between memory usage (there can be lots of RuleData objects) and good filtering performance.
- static const unsigned maximumIdentifierCount = 4;
- const unsigned* descendantSelectorIdentifierHashes() const { return m_descendantSelectorIdentifierHashes; }
+ const SelectorFilter::Hashes& descendantSelectorIdentifierHashes() const { return m_descendantSelectorIdentifierHashes; }
void disableSelectorFiltering() { m_descendantSelectorIdentifierHashes[0] = 0; }
@@ -112,8 +111,7 @@
unsigned m_containsUncommonAttributeSelector : 1;
unsigned m_linkMatchType : 2; // SelectorChecker::LinkMatchMask
unsigned m_propertyWhitelistType : 2;
- // Use plain array instead of a Vector to minimize memory overhead.
- unsigned m_descendantSelectorIdentifierHashes[maximumIdentifierCount];
+ SelectorFilter::Hashes m_descendantSelectorIdentifierHashes;
#if ENABLE(CSS_SELECTOR_JIT)
mutable SelectorCompilationStatus m_compilationStatus;
mutable JSC::MacroAssemblerCodeRef m_compiledSelectorCodeRef;
Modified: trunk/Source/WebCore/css/SelectorFilter.cpp (225481 => 225482)
--- trunk/Source/WebCore/css/SelectorFilter.cpp 2017-12-04 18:13:45 UTC (rev 225481)
+++ trunk/Source/WebCore/css/SelectorFilter.cpp 2017-12-04 18:37:00 UTC (rev 225482)
@@ -96,21 +96,30 @@
pushParentStackFrame(parent);
}
-static inline void collectDescendantSelectorIdentifierHashes(const CSSSelector* selector, unsigned*& hash)
+static inline void collectDescendantSelectorIdentifierHashes(const CSSSelector& selector, const SelectorFilter::Hashes& hashes, SelectorFilter::Hashes::iterator& hashIt)
{
- switch (selector->match()) {
+ auto addIfNew = [&] (unsigned hash) {
+ for (auto it = hashes.begin(); it != hashIt; ++it) {
+ if (*it == hash)
+ return;
+ }
+ *hashIt = hash;
+ hashIt++;
+ };
+
+ switch (selector.match()) {
case CSSSelector::Id:
- if (!selector->value().isEmpty())
- (*hash++) = selector->value().impl()->existingHash() * IdAttributeSalt;
+ if (!selector.value().isEmpty())
+ addIfNew(selector.value().impl()->existingHash() * IdAttributeSalt);
break;
case CSSSelector::Class:
- if (!selector->value().isEmpty())
- (*hash++) = selector->value().impl()->existingHash() * ClassAttributeSalt;
+ if (!selector.value().isEmpty())
+ addIfNew(selector.value().impl()->existingHash() * ClassAttributeSalt);
break;
case CSSSelector::Tag: {
- const AtomicString& tagLowercaseLocalName = selector->tagLowercaseLocalName();
+ auto& tagLowercaseLocalName = selector.tagLowercaseLocalName();
if (tagLowercaseLocalName != starAtom())
- (*hash++) = tagLowercaseLocalName.impl()->existingHash() * TagNameSalt;
+ addIfNew(tagLowercaseLocalName.impl()->existingHash() * TagNameSalt);
break;
}
default:
@@ -118,12 +127,13 @@
}
}
-void SelectorFilter::collectIdentifierHashes(const CSSSelector* selector, unsigned* identifierHashes, unsigned maximumIdentifierCount)
+void SelectorFilter::collectIdentifierHashes(const CSSSelector& rightmostSelector, Hashes& hashes)
{
- unsigned* hash = identifierHashes;
- unsigned* end = identifierHashes + maximumIdentifierCount;
+ auto* selector = &rightmostSelector;
auto relation = selector->relation();
+ auto hashIt = hashes.begin();
+
// Skip the topmost selector. It is handled quickly by the rule hashes.
bool skipOverSubselectors = true;
for (selector = selector->tagHistory(); selector; selector = selector->tagHistory()) {
@@ -131,7 +141,7 @@
switch (relation) {
case CSSSelector::Subselector:
if (!skipOverSubselectors)
- collectDescendantSelectorIdentifierHashes(selector, hash);
+ collectDescendantSelectorIdentifierHashes(*selector, hashes, hashIt);
break;
case CSSSelector::DirectAdjacent:
case CSSSelector::IndirectAdjacent:
@@ -141,14 +151,15 @@
case CSSSelector::DescendantSpace:
case CSSSelector::Child:
skipOverSubselectors = false;
- collectDescendantSelectorIdentifierHashes(selector, hash);
+ collectDescendantSelectorIdentifierHashes(*selector, hashes, hashIt);
break;
}
- if (hash == end)
+ if (hashIt == hashes.end())
return;
relation = selector->relation();
}
- *hash = 0;
+
+ *hashIt = 0;
}
}
Modified: trunk/Source/WebCore/css/SelectorFilter.h (225481 => 225482)
--- trunk/Source/WebCore/css/SelectorFilter.h 2017-12-04 18:13:45 UTC (rev 225481)
+++ trunk/Source/WebCore/css/SelectorFilter.h 2017-12-04 18:37:00 UTC (rev 225482)
@@ -47,9 +47,9 @@
bool parentStackIsEmpty() const { return m_parentStack.isEmpty(); }
bool parentStackIsConsistent(const ContainerNode* parentNode) const;
- template <unsigned maximumIdentifierCount>
- inline bool fastRejectSelector(const unsigned* identifierHashes) const;
- static void collectIdentifierHashes(const CSSSelector*, unsigned* identifierHashes, unsigned maximumIdentifierCount);
+ using Hashes = std::array<unsigned, 4>;
+ bool fastRejectSelector(const Hashes&) const;
+ static void collectIdentifierHashes(const CSSSelector&, Hashes&);
private:
struct ParentStackFrame {
@@ -65,11 +65,10 @@
CountingBloomFilter<bloomFilterKeyBits> m_ancestorIdentifierFilter;
};
-template <unsigned maximumIdentifierCount>
-inline bool SelectorFilter::fastRejectSelector(const unsigned* identifierHashes) const
+inline bool SelectorFilter::fastRejectSelector(const Hashes& hashes) const
{
- for (unsigned n = 0; n < maximumIdentifierCount && identifierHashes[n]; ++n) {
- if (!m_ancestorIdentifierFilter.mayContain(identifierHashes[n]))
+ for (unsigned n = 0; n < hashes.size() && hashes[n]; ++n) {
+ if (!m_ancestorIdentifierFilter.mayContain(hashes[n]))
return true;
}
return false;
