Changeset 225596 in webkit

Timestamp:

Dec 6, 2017 2:24:06 PM (6 years ago)

Author:

Antti Koivisto

Message:

Prefer ids and classes over tag names in selector filter
​https://bugs.webkit.org/show_bug.cgi?id=180433
<rdar://problem/35859103>

Reviewed by Zalan Bujtas.

There are only four slots in the filter and currently we just pick whatever identifiers we find traversing the selector
from right to left. More specific selector types are on average more valuable (id > class > tag) so we should prefer them.

This appears to be 4-5% StyleBench progression.

• css/RuleSet.cpp:

(WebCore::RuleData::RuleData):

• css/SelectorFilter.cpp:

(WebCore::collectSimpleSelectorHash):
(WebCore::collectSelectorHashes):

This function collects all hashes from the selector.

(WebCore::chooseSelectorHashesForFilter):

This function chooses the most valuable hashes to use with the filter.

(WebCore::SelectorFilter::collectHashes):

Factor into two separate steps.

(WebCore::collectDescendantSelectorIdentifierHashes): Deleted.
(WebCore::SelectorFilter::collectIdentifierHashes): Deleted.

• css/SelectorFilter.h:

(WebCore::SelectorFilter::fastRejectSelector const):

Location:

trunk/Source/WebCore

Files:

• ChangeLog (modified) (1 diff)
• css/RuleSet.cpp (modified) (2 diffs)
• css/SelectorFilter.cpp (modified) (4 diffs)
• css/SelectorFilter.h (modified) (2 diffs)

trunk/Source/WebCore/ChangeLog

@@ +1 @@
+2017-12-06  Antti Koivisto  <antti@apple.com>
+
+        Prefer ids and classes over tag names in selector filter
+        https://bugs.webkit.org/show_bug.cgi?id=180433
+        <rdar://problem/35859103>
+
+        Reviewed by Zalan Bujtas.
+
+        There are only four slots in the filter and currently we just pick whatever identifiers we find traversing the selector
+        from right to left. More specific selector types are on average more valuable (id > class > tag) so we should prefer them.
+
+        This appears to be 4-5% StyleBench progression.
+
+        * css/RuleSet.cpp:
+        (WebCore::RuleData::RuleData):
+        * css/SelectorFilter.cpp:
+        (WebCore::collectSimpleSelectorHash):
+        (WebCore::collectSelectorHashes):
+
+            This function collects all hashes from the selector.
+
+        (WebCore::chooseSelectorHashesForFilter):
+
+            This function chooses the most valuable hashes to use with the filter.
+
+        (WebCore::SelectorFilter::collectHashes):
+
+            Factor into two separate steps.
+
+        (WebCore::collectDescendantSelectorIdentifierHashes): Deleted.
+        (WebCore::SelectorFilter::collectIdentifierHashes): Deleted.
+        * css/SelectorFilter.h:
+        (WebCore::SelectorFilter::fastRejectSelector const):
+
 2017-12-06  Jer Noble  <jer.noble@apple.com>
 

trunk/Source/WebCore/css/RuleSet.cpp

@@ -159 +159 @@
     , m_linkMatchType(SelectorChecker::determineLinkMatchType(selector()))
     , m_propertyWhitelistType(determinePropertyWhitelistType(selector()))
+    , m_descendantSelectorIdentifierHashes(SelectorFilter::collectHashes(*selector()))
 #if ENABLE(CSS_SELECTOR_JIT) && CSS_SELECTOR_JIT_PROFILING
     , m_compiledSelectorUseCount(0)
@@ -165 +166 @@
     ASSERT(m_position == position);
     ASSERT(m_selectorIndex == selectorIndex);
-    SelectorFilter::collectIdentifierHashes(*selector(), m_descendantSelectorIdentifierHashes);
 }
 

trunk/Source/WebCore/css/SelectorFilter.cpp

@@ -97 +97 @@
 }
 
-static inline void collectDescendantSelectorIdentifierHashes(const CSSSelector& selector, const SelectorFilter::Hashes& hashes, SelectorFilter::Hashes::iterator& hashIt)
-{
-    auto addIfNew = [&] (unsigned hash) {
-        for (auto it = hashes.begin(); it != hashIt; ++it) {
-            if (*it == hash)
-                return;
-        }
-        *hashIt = hash;
-        hashIt++;
-    };
-
+struct CollectedSelectorHashes {
+    using HashVector = Vector<unsigned, 8>;
+    HashVector ids;
+    HashVector classes;
+    HashVector tags;
+};
+
+static inline void collectSimpleSelectorHash(CollectedSelectorHashes& collectedHashes, const CSSSelector& selector)
+{
     switch (selector.match()) {
     case CSSSelector::Id:
         if (!selector.value().isEmpty())
-            addIfNew(selector.value().impl()->existingHash() * IdAttributeSalt);
+            collectedHashes.ids.append(selector.value().impl()->existingHash() * IdAttributeSalt);
         break;
     case CSSSelector::Class:
         if (!selector.value().isEmpty())
-            addIfNew(selector.value().impl()->existingHash() * ClassAttributeSalt);
+            collectedHashes.classes.append(selector.value().impl()->existingHash() * ClassAttributeSalt);
         break;
     case CSSSelector::Tag: {
         auto& tagLowercaseLocalName = selector.tagLowercaseLocalName();
         if (tagLowercaseLocalName != starAtom())
-            addIfNew(tagLowercaseLocalName.impl()->existingHash() * TagNameSalt);
+            collectedHashes.tags.append(tagLowercaseLocalName.impl()->existingHash() * TagNameSalt);
         break;
     }
@@ -128 +126 @@
 }
 
-void SelectorFilter::collectIdentifierHashes(const CSSSelector& rightmostSelector, Hashes& hashes)
-{
+static CollectedSelectorHashes collectSelectorHashes(const CSSSelector& rightmostSelector)
+{
+    CollectedSelectorHashes collectedHashes;
+
     auto* selector = &rightmostSelector;
     auto relation = selector->relation();
-
-    auto hashIt = hashes.begin();
 
     // Skip the topmost selector. It is handled quickly by the rule hashes.
@@ -142 +140 @@
         case CSSSelector::Subselector:
             if (!skipOverSubselectors)
-                collectDescendantSelectorIdentifierHashes(*selector, hashes, hashIt);
+                collectSimpleSelectorHash(collectedHashes, *selector);
             break;
         case CSSSelector::DirectAdjacent:
@@ -152 +150 @@
         case CSSSelector::Child:
             skipOverSubselectors = false;
-            collectDescendantSelectorIdentifierHashes(*selector, hashes, hashIt);
+            collectSimpleSelectorHash(collectedHashes, *selector);
             break;
         }
-        if (hashIt == hashes.end())
-            return;
         relation = selector->relation();
     }
-
-    *hashIt = 0;
-}
-
-}
-
+    return collectedHashes;
+}
+
+static SelectorFilter::Hashes chooseSelectorHashesForFilter(const CollectedSelectorHashes& collectedSelectorHashes)
+{
+    SelectorFilter::Hashes resultHashes;
+    unsigned index = 0;
+
+    auto addIfNew = [&] (unsigned hash) {
+        for (unsigned i = 0; i < index; ++i) {
+            if (resultHashes[i] == hash)
+                return;
+        }
+        resultHashes[index++] = hash;
+    };
+
+    auto copyHashes = [&] (auto& hashes) {
+        for (auto& hash : hashes) {
+            addIfNew(hash);
+            if (index == resultHashes.size())
+                return true;
+        }
+        return false;
+    };
+
+    // There is a limited number of slots. Prefer more specific selector types.
+    if (copyHashes(collectedSelectorHashes.ids))
+        return resultHashes;
+    if (copyHashes(collectedSelectorHashes.classes))
+        return resultHashes;
+    if (copyHashes(collectedSelectorHashes.tags))
+        return resultHashes;
+
+    // Null-terminate if not full.
+    resultHashes[index] = 0;
+    return resultHashes;
+}
+
+SelectorFilter::Hashes SelectorFilter::collectHashes(const CSSSelector& selector)
+{
+    auto hashes = collectSelectorHashes(selector);
+    return chooseSelectorHashesForFilter(hashes);
+}
+
+}
+

trunk/Source/WebCore/css/SelectorFilter.h

@@ -50 +50 @@
     using Hashes = std::array<unsigned, 4>;
     bool fastRejectSelector(const Hashes&) const;
-    static void collectIdentifierHashes(const CSSSelector&, Hashes&);
+    static Hashes collectHashes(const CSSSelector&);
 
 private:
@@ -68 +68 @@
 inline bool SelectorFilter::fastRejectSelector(const Hashes& hashes) const
 {
-    for (unsigned n = 0; n < hashes.size() && hashes[n]; ++n) {
-        if (!m_ancestorIdentifierFilter.mayContain(hashes[n]))
+    for (auto& hash : hashes) {
+        if (!hash)
+            return false;
+        if (!m_ancestorIdentifierFilter.mayContain(hash))
             return true;
     }