<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN"
"http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head><meta http-equiv="content-type" content="text/html; charset=utf-8" />
<title>[225482] trunk/Source/WebCore</title>
</head>
<body>

<style type="text/css"><!--
#msg dl.meta { border: 1px #006 solid; background: #369; padding: 6px; color: #fff; }
#msg dl.meta dt { float: left; width: 6em; font-weight: bold; }
#msg dt:after { content:':';}
#msg dl, #msg dt, #msg ul, #msg li, #header, #footer, #logmsg { font-family: verdana,arial,helvetica,sans-serif; font-size: 10pt;  }
#msg dl a { font-weight: bold}
#msg dl a:link    { color:#fc3; }
#msg dl a:active  { color:#ff0; }
#msg dl a:visited { color:#cc6; }
h3 { font-family: verdana,arial,helvetica,sans-serif; font-size: 10pt; font-weight: bold; }
#msg pre { overflow: auto; background: #ffc; border: 1px #fa0 solid; padding: 6px; }
#logmsg { background: #ffc; border: 1px #fa0 solid; padding: 1em 1em 0 1em; }
#logmsg p, #logmsg pre, #logmsg blockquote { margin: 0 0 1em 0; }
#logmsg p, #logmsg li, #logmsg dt, #logmsg dd { line-height: 14pt; }
#logmsg h1, #logmsg h2, #logmsg h3, #logmsg h4, #logmsg h5, #logmsg h6 { margin: .5em 0; }
#logmsg h1:first-child, #logmsg h2:first-child, #logmsg h3:first-child, #logmsg h4:first-child, #logmsg h5:first-child, #logmsg h6:first-child { margin-top: 0; }
#logmsg ul, #logmsg ol { padding: 0; list-style-position: inside; margin: 0 0 0 1em; }
#logmsg ul { text-indent: -1em; padding-left: 1em; }#logmsg ol { text-indent: -1.5em; padding-left: 1.5em; }
#logmsg > ul, #logmsg > ol { margin: 0 0 1em 0; }
#logmsg pre { background: #eee; padding: 1em; }
#logmsg blockquote { border: 1px solid #fa0; border-left-width: 10px; padding: 1em 1em 0 1em; background: white;}
#logmsg dl { margin: 0; }
#logmsg dt { font-weight: bold; }
#logmsg dd { margin: 0; padding: 0 0 0.5em 0; }
#logmsg dd:before { content:'\00bb';}
#logmsg table { border-spacing: 0px; border-collapse: collapse; border-top: 4px solid #fa0; border-bottom: 1px solid #fa0; background: #fff; }
#logmsg table th { text-align: left; font-weight: normal; padding: 0.2em 0.5em; border-top: 1px dotted #fa0; }
#logmsg table td { text-align: right; border-top: 1px dotted #fa0; padding: 0.2em 0.5em; }
#logmsg table thead th { text-align: center; border-bottom: 1px solid #fa0; }
#logmsg table th.Corner { text-align: left; }
#logmsg hr { border: none 0; border-top: 2px dashed #fa0; height: 1px; }
#header, #footer { color: #fff; background: #636; border: 1px #300 solid; padding: 6px; }
#patch { width: 100%; }
#patch h4 {font-family: verdana,arial,helvetica,sans-serif;font-size:10pt;padding:8px;background:#369;color:#fff;margin:0;}
#patch .propset h4, #patch .binary h4 {margin:0;}
#patch pre {padding:0;line-height:1.2em;margin:0;}
#patch .diff {width:100%;background:#eee;padding: 0 0 10px 0;overflow:auto;}
#patch .propset .diff, #patch .binary .diff  {padding:10px 0;}
#patch span {display:block;padding:0 10px;}
#patch .modfile, #patch .addfile, #patch .delfile, #patch .propset, #patch .binary, #patch .copfile {border:1px solid #ccc;margin:10px 0;}
#patch ins {background:#dfd;text-decoration:none;display:block;padding:0 10px;}
#patch del {background:#fdd;text-decoration:none;display:block;padding:0 10px;}
#patch .lines, .info {color:#888;background:#fff;}
--></style>
<div id="msg">
<dl class="meta">
<dt>Revision</dt> <dd><a href="http://trac.webkit.org/projects/webkit/changeset/225482">225482</a></dd>
<dt>Author</dt> <dd>antti@apple.com</dd>
<dt>Date</dt> <dd>2017-12-04 10:37:00 -0800 (Mon, 04 Dec 2017)</dd>
</dl>

<h3>Log Message</h3>
<pre>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):</pre>

<h3>Modified Paths</h3>
<ul>
<li><a href="#trunkSourceWebCoreChangeLog">trunk/Source/WebCore/ChangeLog</a></li>
<li><a href="#trunkSourceWebCorecssElementRuleCollectorcpp">trunk/Source/WebCore/css/ElementRuleCollector.cpp</a></li>
<li><a href="#trunkSourceWebCorecssRuleSetcpp">trunk/Source/WebCore/css/RuleSet.cpp</a></li>
<li><a href="#trunkSourceWebCorecssRuleSeth">trunk/Source/WebCore/css/RuleSet.h</a></li>
<li><a href="#trunkSourceWebCorecssSelectorFiltercpp">trunk/Source/WebCore/css/SelectorFilter.cpp</a></li>
<li><a href="#trunkSourceWebCorecssSelectorFilterh">trunk/Source/WebCore/css/SelectorFilter.h</a></li>
</ul>

</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkSourceWebCoreChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/ChangeLog (225481 => 225482)</h4>
<pre class="diff"><span>
<span class="info">--- 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)
</span><span class="lines">@@ -1,3 +1,29 @@
</span><ins>+2017-12-04  Antti Koivisto  <antti@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):
+
</ins><span class="cx"> 2017-12-04  Youenn Fablet  <youenn@apple.com>
</span><span class="cx"> 
</span><span class="cx">         WorkerCacheStorageConnection should handle the case of terminated workers
</span></span></pre></div>
<a id="trunkSourceWebCorecssElementRuleCollectorcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/css/ElementRuleCollector.cpp (225481 => 225482)</h4>
<pre class="diff"><span>
<span class="info">--- 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)
</span><span class="lines">@@ -464,7 +464,7 @@
</span><span class="cx">         if (!ruleData.canMatchPseudoElement() && m_pseudoStyleRequest.pseudoId != NOPSEUDO)
</span><span class="cx">             continue;
</span><span class="cx"> 
</span><del>-        if (m_selectorFilter && m_selectorFilter->fastRejectSelector<RuleData::maximumIdentifierCount>(ruleData.descendantSelectorIdentifierHashes()))
</del><ins>+        if (m_selectorFilter && m_selectorFilter->fastRejectSelector(ruleData.descendantSelectorIdentifierHashes()))
</ins><span class="cx">             continue;
</span><span class="cx"> 
</span><span class="cx">         StyleRule* rule = ruleData.rule();
</span></span></pre></div>
<a id="trunkSourceWebCorecssRuleSetcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/css/RuleSet.cpp (225481 => 225482)</h4>
<pre class="diff"><span>
<span class="info">--- 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)
</span><span class="lines">@@ -164,7 +164,7 @@
</span><span class="cx"> {
</span><span class="cx">     ASSERT(m_position == position);
</span><span class="cx">     ASSERT(m_selectorIndex == selectorIndex);
</span><del>-    SelectorFilter::collectIdentifierHashes(selector(), m_descendantSelectorIdentifierHashes, maximumIdentifierCount);
</del><ins>+    SelectorFilter::collectIdentifierHashes(*selector(), m_descendantSelectorIdentifierHashes);
</ins><span class="cx"> }
</span><span class="cx"> 
</span><span class="cx"> RuleSet::RuleSet() = default;
</span></span></pre></div>
<a id="trunkSourceWebCorecssRuleSeth"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/css/RuleSet.h (225481 => 225482)</h4>
<pre class="diff"><span>
<span class="info">--- 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)
</span><span class="lines">@@ -23,6 +23,7 @@
</span><span class="cx"> 
</span><span class="cx"> #include "RuleFeature.h"
</span><span class="cx"> #include "SelectorCompiler.h"
</span><ins>+#include "SelectorFilter.h"
</ins><span class="cx"> #include "StyleRule.h"
</span><span class="cx"> #include <wtf/Forward.h>
</span><span class="cx"> #include <wtf/HashMap.h>
</span><span class="lines">@@ -76,9 +77,7 @@
</span><span class="cx">     unsigned linkMatchType() const { return m_linkMatchType; }
</span><span class="cx">     bool hasDocumentSecurityOrigin() const { return m_hasDocumentSecurityOrigin; }
</span><span class="cx">     PropertyWhitelistType propertyWhitelistType() const { return static_cast<PropertyWhitelistType>(m_propertyWhitelistType); }
</span><del>-    // 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; }
</del><ins>+    const SelectorFilter::Hashes& descendantSelectorIdentifierHashes() const { return m_descendantSelectorIdentifierHashes; }
</ins><span class="cx"> 
</span><span class="cx">     void disableSelectorFiltering() { m_descendantSelectorIdentifierHashes[0] = 0; }
</span><span class="cx"> 
</span><span class="lines">@@ -112,8 +111,7 @@
</span><span class="cx">     unsigned m_containsUncommonAttributeSelector : 1;
</span><span class="cx">     unsigned m_linkMatchType : 2; //  SelectorChecker::LinkMatchMask
</span><span class="cx">     unsigned m_propertyWhitelistType : 2;
</span><del>-    // Use plain array instead of a Vector to minimize memory overhead.
-    unsigned m_descendantSelectorIdentifierHashes[maximumIdentifierCount];
</del><ins>+    SelectorFilter::Hashes m_descendantSelectorIdentifierHashes;
</ins><span class="cx"> #if ENABLE(CSS_SELECTOR_JIT)
</span><span class="cx">     mutable SelectorCompilationStatus m_compilationStatus;
</span><span class="cx">     mutable JSC::MacroAssemblerCodeRef m_compiledSelectorCodeRef;
</span></span></pre></div>
<a id="trunkSourceWebCorecssSelectorFiltercpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/css/SelectorFilter.cpp (225481 => 225482)</h4>
<pre class="diff"><span>
<span class="info">--- 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)
</span><span class="lines">@@ -96,21 +96,30 @@
</span><span class="cx">     pushParentStackFrame(parent);
</span><span class="cx"> }
</span><span class="cx"> 
</span><del>-static inline void collectDescendantSelectorIdentifierHashes(const CSSSelector* selector, unsigned*& hash)
</del><ins>+static inline void collectDescendantSelectorIdentifierHashes(const CSSSelector& selector, const SelectorFilter::Hashes& hashes, SelectorFilter::Hashes::iterator& hashIt)
</ins><span class="cx"> {
</span><del>-    switch (selector->match()) {
</del><ins>+    auto addIfNew = [&] (unsigned hash) {
+        for (auto it = hashes.begin(); it != hashIt; ++it) {
+            if (*it == hash)
+                return;
+        }
+        *hashIt = hash;
+        hashIt++;
+    };
+
+    switch (selector.match()) {
</ins><span class="cx">     case CSSSelector::Id:
</span><del>-        if (!selector->value().isEmpty())
-            (*hash++) = selector->value().impl()->existingHash() * IdAttributeSalt;
</del><ins>+        if (!selector.value().isEmpty())
+            addIfNew(selector.value().impl()->existingHash() * IdAttributeSalt);
</ins><span class="cx">         break;
</span><span class="cx">     case CSSSelector::Class:
</span><del>-        if (!selector->value().isEmpty())
-            (*hash++) = selector->value().impl()->existingHash() * ClassAttributeSalt;
</del><ins>+        if (!selector.value().isEmpty())
+            addIfNew(selector.value().impl()->existingHash() * ClassAttributeSalt);
</ins><span class="cx">         break;
</span><span class="cx">     case CSSSelector::Tag: {
</span><del>-        const AtomicString& tagLowercaseLocalName = selector->tagLowercaseLocalName();
</del><ins>+        auto& tagLowercaseLocalName = selector.tagLowercaseLocalName();
</ins><span class="cx">         if (tagLowercaseLocalName != starAtom())
</span><del>-            (*hash++) = tagLowercaseLocalName.impl()->existingHash() * TagNameSalt;
</del><ins>+            addIfNew(tagLowercaseLocalName.impl()->existingHash() * TagNameSalt);
</ins><span class="cx">         break;
</span><span class="cx">     }
</span><span class="cx">     default:
</span><span class="lines">@@ -118,12 +127,13 @@
</span><span class="cx">     }
</span><span class="cx"> }
</span><span class="cx"> 
</span><del>-void SelectorFilter::collectIdentifierHashes(const CSSSelector* selector, unsigned* identifierHashes, unsigned maximumIdentifierCount)
</del><ins>+void SelectorFilter::collectIdentifierHashes(const CSSSelector& rightmostSelector, Hashes& hashes)
</ins><span class="cx"> {
</span><del>-    unsigned* hash = identifierHashes;
-    unsigned* end = identifierHashes + maximumIdentifierCount;
</del><ins>+    auto* selector = &rightmostSelector;
</ins><span class="cx">     auto relation = selector->relation();
</span><span class="cx"> 
</span><ins>+    auto hashIt = hashes.begin();
+
</ins><span class="cx">     // Skip the topmost selector. It is handled quickly by the rule hashes.
</span><span class="cx">     bool skipOverSubselectors = true;
</span><span class="cx">     for (selector = selector->tagHistory(); selector; selector = selector->tagHistory()) {
</span><span class="lines">@@ -131,7 +141,7 @@
</span><span class="cx">         switch (relation) {
</span><span class="cx">         case CSSSelector::Subselector:
</span><span class="cx">             if (!skipOverSubselectors)
</span><del>-                collectDescendantSelectorIdentifierHashes(selector, hash);
</del><ins>+                collectDescendantSelectorIdentifierHashes(*selector, hashes, hashIt);
</ins><span class="cx">             break;
</span><span class="cx">         case CSSSelector::DirectAdjacent:
</span><span class="cx">         case CSSSelector::IndirectAdjacent:
</span><span class="lines">@@ -141,14 +151,15 @@
</span><span class="cx">         case CSSSelector::DescendantSpace:
</span><span class="cx">         case CSSSelector::Child:
</span><span class="cx">             skipOverSubselectors = false;
</span><del>-            collectDescendantSelectorIdentifierHashes(selector, hash);
</del><ins>+            collectDescendantSelectorIdentifierHashes(*selector, hashes, hashIt);
</ins><span class="cx">             break;
</span><span class="cx">         }
</span><del>-        if (hash == end)
</del><ins>+        if (hashIt == hashes.end())
</ins><span class="cx">             return;
</span><span class="cx">         relation = selector->relation();
</span><span class="cx">     }
</span><del>-    *hash = 0;
</del><ins>+
+    *hashIt = 0;
</ins><span class="cx"> }
</span><span class="cx"> 
</span><span class="cx"> }
</span></span></pre></div>
<a id="trunkSourceWebCorecssSelectorFilterh"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/css/SelectorFilter.h (225481 => 225482)</h4>
<pre class="diff"><span>
<span class="info">--- 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)
</span><span class="lines">@@ -47,9 +47,9 @@
</span><span class="cx">     bool parentStackIsEmpty() const { return m_parentStack.isEmpty(); }
</span><span class="cx">     bool parentStackIsConsistent(const ContainerNode* parentNode) const;
</span><span class="cx"> 
</span><del>-    template <unsigned maximumIdentifierCount>
-    inline bool fastRejectSelector(const unsigned* identifierHashes) const;
-    static void collectIdentifierHashes(const CSSSelector*, unsigned* identifierHashes, unsigned maximumIdentifierCount);
</del><ins>+    using Hashes = std::array<unsigned, 4>;
+    bool fastRejectSelector(const Hashes&) const;
+    static void collectIdentifierHashes(const CSSSelector&, Hashes&);
</ins><span class="cx"> 
</span><span class="cx"> private:
</span><span class="cx">     struct ParentStackFrame {
</span><span class="lines">@@ -65,11 +65,10 @@
</span><span class="cx">     CountingBloomFilter<bloomFilterKeyBits> m_ancestorIdentifierFilter;
</span><span class="cx"> };
</span><span class="cx"> 
</span><del>-template <unsigned maximumIdentifierCount>
-inline bool SelectorFilter::fastRejectSelector(const unsigned* identifierHashes) const
</del><ins>+inline bool SelectorFilter::fastRejectSelector(const Hashes& hashes) const
</ins><span class="cx"> {
</span><del>-    for (unsigned n = 0; n < maximumIdentifierCount && identifierHashes[n]; ++n) {
-        if (!m_ancestorIdentifierFilter.mayContain(identifierHashes[n]))
</del><ins>+    for (unsigned n = 0; n < hashes.size() && hashes[n]; ++n) {
+        if (!m_ancestorIdentifierFilter.mayContain(hashes[n]))
</ins><span class="cx">             return true;
</span><span class="cx">     }
</span><span class="cx">     return false;
</span></span></pre>
</div>
</div>

</body>
</html>