[Refactoring] Introduce a traversal strategy in SelectorChecker
authorhayato@chromium.org <hayato@chromium.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 5 Oct 2012 04:47:21 +0000 (04:47 +0000)
committerhayato@chromium.org <hayato@chromium.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 5 Oct 2012 04:47:21 +0000 (04:47 +0000)
https://bugs.webkit.org/show_bug.cgi?id=97298

Reviewed by Antti Koivisto.

PerformanceTests:

Introduces querySelector() performance tests to check SelectorChecker performance.

* CSS/PseudoClassSelectors.html: Added.

Source/WebCore:

We extract DOM traversal code from SelectorChecker so that we can use another traversal strategy.
Another traversal strategy will be introduced in Bug 96990.

Since this code path is very hot, we were very careful not to regress performance.
We will use template specialization to change the traversal implementation.

We confirmed that this patch does not regress SelectorCheckerPerformance. I have checked the performance of
the added test in my Linux Box using run-perf-tests.

The performance of the added test before using this patch was:

  RESULT CSS: PseudoClassSelectors= 3399.68308031 runs/s
  median= 3404.48685564 runs/s, stdev= 37.3480114449 runs/s, min= 3272.64871114 runs/s, max= 3438.72385184 runs/s

When we used this patch, the performance was:

  RESULT CSS: PseudoClassSelectors= 3367.74473886 runs/s
  median= 3367.12072755 runs/s, stdev= 14.1464547639 runs/s, min= 3348.55881171 runs/s, max= 3395.98212857 runs/s

Test: PerformanceTests/CSS/PseudoClass-Selectors.html

* css/SelectorChecker.cpp:
(WebCore):
(WebCore::SelectorChecker::checkSelector): Make this a template method to accept another Context type.
Another Context type will be introduced in coming patch.
(WebCore::SelectorChecker::checkOneSelector):
(WebCore::SelectorChecker::DOMTraversalStrategy::isFirstChild):
(WebCore::SelectorChecker::DOMTraversalStrategy::isLastChild):
(WebCore::SelectorChecker::DOMTraversalStrategy::isFirstOfType):
(WebCore::SelectorChecker::DOMTraversalStrategy::isLastOfType):
(WebCore::SelectorChecker::DOMTraversalStrategy::countElementsBefore):
(WebCore::SelectorChecker::DOMTraversalStrategy::countElementsOfTypeBefore):
(WebCore::SelectorChecker::DOMTraversalStrategy::countElementsAfter):
(WebCore::SelectorChecker::DOMTraversalStrategy::countElementsOfTypeAfter):
* css/SelectorChecker.h:
(WebCore::SelectorChecker::SelectorCheckingContext::SelectorCheckingContext):
(SelectorCheckingContext):
(SelectorChecker):
(DOMTraversalStrategy): Extracted the DOM traversal code from SelectorChecker. Another traversal code
will be introduced the coming patch.

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@130459 268f45cc-cd09-0410-ab3c-d52691b4dbfc

PerformanceTests/CSS/PseudoClassSelectors.html [new file with mode: 0644]
PerformanceTests/ChangeLog
Source/WebCore/ChangeLog
Source/WebCore/css/SelectorChecker.cpp
Source/WebCore/css/SelectorChecker.h

diff --git a/PerformanceTests/CSS/PseudoClassSelectors.html b/PerformanceTests/CSS/PseudoClassSelectors.html
new file mode 100644 (file)
index 0000000..edc40b0
--- /dev/null
@@ -0,0 +1,43 @@
+<!DOCTYPE html>
+<html>
+<body>
+<div id="test-target">
+    <div>
+        <div></div>
+        <div>
+            <p></p>
+            <p></p>
+            <p></p>
+        </div>
+        <div></div>
+    </div>
+    <div>
+        <div>
+            <p></p>
+        </div>
+    </div>
+    <p></p>
+    <p></p>
+    <p></p>
+    <p></p>
+</div>
+<script src="../resources/runner.js"></script>
+<script>
+PerfTestRunner.runPerSecond({
+    description: "This benchmark tests CSS Selector performance with querySelector().",
+    run: function() {
+        for (var i = 0; i < 100; i++) {
+            document.querySelector("p:first-child");
+            document.querySelector("p:last-child");
+            document.querySelector("p:first-of-type");
+            document.querySelector("p:last-of-type");
+            document.querySelector("p:nth-child(4n+3)");
+            document.querySelector("p:nth-last-child(4n+3)");
+            document.querySelector("p:nth-of-type(4n+3)");
+            document.querySelector("p:nth-last-of-type(4n+3)");
+        }
+    }
+});
+</script>
+</body>
+</html>
index b7da049..7c75cf9 100644 (file)
@@ -1,3 +1,14 @@
+2012-10-04  Hayato Ito  <hayato@chromium.org>
+
+        [Refactoring] Introduce a traversal strategy in SelectorChecker
+        https://bugs.webkit.org/show_bug.cgi?id=97298
+
+        Reviewed by Antti Koivisto.
+
+        Introduces querySelector() performance tests to check SelectorChecker performance.
+
+        * CSS/PseudoClassSelectors.html: Added.
+
 2012-10-03  Philip Rogers  <pdr@google.com>
 
         Force GC between PageLoad tests.
index 31b10b9..89fa2c0 100644 (file)
@@ -1,3 +1,51 @@
+2012-10-04  Hayato Ito  <hayato@chromium.org>
+
+        [Refactoring] Introduce a traversal strategy in SelectorChecker
+        https://bugs.webkit.org/show_bug.cgi?id=97298
+
+        Reviewed by Antti Koivisto.
+
+        We extract DOM traversal code from SelectorChecker so that we can use another traversal strategy.
+        Another traversal strategy will be introduced in Bug 96990.
+
+        Since this code path is very hot, we were very careful not to regress performance.
+        We will use template specialization to change the traversal implementation.
+
+        We confirmed that this patch does not regress SelectorCheckerPerformance. I have checked the performance of
+        the added test in my Linux Box using run-perf-tests.
+
+        The performance of the added test before using this patch was:
+
+          RESULT CSS: PseudoClassSelectors= 3399.68308031 runs/s
+          median= 3404.48685564 runs/s, stdev= 37.3480114449 runs/s, min= 3272.64871114 runs/s, max= 3438.72385184 runs/s
+
+        When we used this patch, the performance was:
+
+          RESULT CSS: PseudoClassSelectors= 3367.74473886 runs/s
+          median= 3367.12072755 runs/s, stdev= 14.1464547639 runs/s, min= 3348.55881171 runs/s, max= 3395.98212857 runs/s
+
+        Test: PerformanceTests/CSS/PseudoClass-Selectors.html
+
+        * css/SelectorChecker.cpp:
+        (WebCore):
+        (WebCore::SelectorChecker::checkSelector): Make this a template method to accept another Context type.
+        Another Context type will be introduced in coming patch.
+        (WebCore::SelectorChecker::checkOneSelector):
+        (WebCore::SelectorChecker::DOMTraversalStrategy::isFirstChild):
+        (WebCore::SelectorChecker::DOMTraversalStrategy::isLastChild):
+        (WebCore::SelectorChecker::DOMTraversalStrategy::isFirstOfType):
+        (WebCore::SelectorChecker::DOMTraversalStrategy::isLastOfType):
+        (WebCore::SelectorChecker::DOMTraversalStrategy::countElementsBefore):
+        (WebCore::SelectorChecker::DOMTraversalStrategy::countElementsOfTypeBefore):
+        (WebCore::SelectorChecker::DOMTraversalStrategy::countElementsAfter):
+        (WebCore::SelectorChecker::DOMTraversalStrategy::countElementsOfTypeAfter):
+        * css/SelectorChecker.h:
+        (WebCore::SelectorChecker::SelectorCheckingContext::SelectorCheckingContext):
+        (SelectorCheckingContext):
+        (SelectorChecker):
+        (DOMTraversalStrategy): Extracted the DOM traversal code from SelectorChecker. Another traversal code
+        will be introduced the coming patch.
+
 2012-10-04  Eric Seidel  <eric@webkit.org>
 
         SVGAttributeHashTranslator does not need to copy QualifiedName in the common case
index 403b218..bf5803d 100644 (file)
@@ -439,7 +439,8 @@ bool SelectorChecker::isFastCheckableSelector(const CSSSelector* selector)
 // * SelectorFailsLocally     - the selector fails for the element e
 // * SelectorFailsAllSiblings - the selector fails for e and any sibling of e
 // * SelectorFailsCompletely  - the selector fails for e and any sibling or ancestor of e
-SelectorChecker::SelectorMatch SelectorChecker::checkSelector(const SelectorCheckingContext& context, PseudoId& dynamicPseudo, bool& hasUnknownPseudoElements) const
+template<typename CheckingContext>
+SelectorChecker::SelectorMatch SelectorChecker::checkSelector(const CheckingContext& context, PseudoId& dynamicPseudo, bool& hasUnknownPseudoElements) const
 {
     // first selector has to match
     if (!checkOneSelector(context))
@@ -472,7 +473,7 @@ SelectorChecker::SelectorMatch SelectorChecker::checkSelector(const SelectorChec
     if (!historySelector)
         return SelectorMatches;
 
-    SelectorCheckingContext nextContext(context);
+    CheckingContext nextContext(context);
     nextContext.selector = historySelector;
 
     PseudoId ignoreDynamicPseudo = NOPSEUDO;
@@ -726,7 +727,8 @@ static bool anyAttributeMatches(Element* element, CSSSelector::Match match, cons
     return false;
 }
 
-bool SelectorChecker::checkOneSelector(const SelectorCheckingContext& context) const
+template<typename CheckingContext>
+bool SelectorChecker::checkOneSelector(const CheckingContext& context) const
 {
     Element* const & element = context.element;
     CSSSelector* const & selector = context.selector;
@@ -763,7 +765,7 @@ bool SelectorChecker::checkOneSelector(const SelectorCheckingContext& context) c
             if (!selectorList)
                 return false;
 
-            SelectorCheckingContext subContext(context);
+            CheckingContext subContext(context);
             subContext.isSubSelector = true;
             for (subContext.selector = selectorList->first(); subContext.selector; subContext.selector = subContext.selector->tagHistory()) {
                 // :not cannot nest. I don't really know why this is a
@@ -817,9 +819,7 @@ bool SelectorChecker::checkOneSelector(const SelectorCheckingContext& context) c
         case CSSSelector::PseudoFirstChild:
             // first-child matches the first child that is an element
             if (element->parentElement()) {
-                bool result = false;
-                if (!element->previousElementSibling())
-                    result = true;
+                bool result = DOMTraversalStrategy<CheckingContext>::isFirstChild(context, element);
                 if (m_mode == ResolvingStyle) {
                     RenderStyle* childStyle = context.elementStyle ? context.elementStyle : element->renderStyle();
                     RenderStyle* parentStyle = context.elementStyle ? context.elementParentStyle : element->parentNode()->renderStyle();
@@ -834,14 +834,7 @@ bool SelectorChecker::checkOneSelector(const SelectorCheckingContext& context) c
         case CSSSelector::PseudoFirstOfType:
             // first-of-type matches the first element of its type
             if (element->parentElement()) {
-                bool result = true;
-                const QualifiedName& type = element->tagQName();
-                for (const Element* sibling = element->previousElementSibling(); sibling; sibling = sibling->previousElementSibling()) {
-                    if (sibling->hasTagName(type)) {
-                        result = false;
-                        break;
-                    }
-                }
+                bool result = DOMTraversalStrategy<CheckingContext>::isFirstOfType(context, element, element->tagQName());
                 if (m_mode == ResolvingStyle) {
                     RenderStyle* parentStyle = context.elementStyle ? context.elementParentStyle : element->parentNode()->renderStyle();
                     if (parentStyle)
@@ -853,7 +846,7 @@ bool SelectorChecker::checkOneSelector(const SelectorCheckingContext& context) c
         case CSSSelector::PseudoLastChild:
             // last-child matches the last child that is an element
             if (Element* parentElement = element->parentElement()) {
-                bool result = parentElement->isFinishedParsingChildren() && !element->nextElementSibling();
+                bool result = parentElement->isFinishedParsingChildren() && DOMTraversalStrategy<CheckingContext>::isLastChild(context, element);
                 if (m_mode == ResolvingStyle) {
                     RenderStyle* childStyle = context.elementStyle ? context.elementStyle : element->renderStyle();
                     RenderStyle* parentStyle = context.elementStyle ? context.elementParentStyle : parentElement->renderStyle();
@@ -875,19 +868,13 @@ bool SelectorChecker::checkOneSelector(const SelectorCheckingContext& context) c
                 }
                 if (!parentElement->isFinishedParsingChildren())
                     return false;
-                const QualifiedName& type = element->tagQName();
-                for (const Element* sibling = element->nextElementSibling(); sibling; sibling = sibling->nextElementSibling()) {
-                    if (sibling->hasTagName(type))
-                        return false;
-                }
-                return true;
+                return DOMTraversalStrategy<CheckingContext>::isLastOfType(context, element, element->tagQName());
             }
             break;
         case CSSSelector::PseudoOnlyChild:
             if (Element* parentElement = element->parentElement()) {
-                bool firstChild = !element->previousElementSibling();
-                bool onlyChild = firstChild && parentElement->isFinishedParsingChildren() && !element->nextElementSibling();
-
+                bool firstChild = DOMTraversalStrategy<CheckingContext>::isFirstChild(context, element);
+                bool onlyChild = firstChild && parentElement->isFinishedParsingChildren() && DOMTraversalStrategy<CheckingContext>::isLastChild(context, element);
                 if (m_mode == ResolvingStyle) {
                     RenderStyle* childStyle = context.elementStyle ? context.elementStyle : element->renderStyle();
                     RenderStyle* parentStyle = context.elementStyle ? context.elementParentStyle : parentElement->renderStyle();
@@ -915,33 +902,14 @@ bool SelectorChecker::checkOneSelector(const SelectorCheckingContext& context) c
                 }
                 if (!parentElement->isFinishedParsingChildren())
                     return false;
-                const QualifiedName& type = element->tagQName();
-                for (const Element* sibling = element->previousElementSibling(); sibling; sibling = sibling->previousElementSibling()) {
-                    if (sibling->hasTagName(type))
-                        return false;
-                }
-                for (const Element* sibling = element->nextElementSibling(); sibling; sibling = sibling->nextElementSibling()) {
-                    if (sibling->hasTagName(type))
-                        return false;
-                }
-                return true;
+                return DOMTraversalStrategy<CheckingContext>::isFirstOfType(context, element, element->tagQName()) && DOMTraversalStrategy<CheckingContext>::isLastOfType(context, element, element->tagQName());
             }
             break;
         case CSSSelector::PseudoNthChild:
             if (!selector->parseNth())
                 break;
             if (Element* parentElement = element->parentElement()) {
-                int count = 1;
-                for (const Element* sibling = element->previousElementSibling(); sibling; sibling = sibling->previousElementSibling()) {
-                    RenderStyle* s = sibling->renderStyle();
-                    unsigned index = s ? s->childIndex() : 0;
-                    if (index) {
-                        count += index;
-                        break;
-                    }
-                    count++;
-                }
-
+                int count = 1 + DOMTraversalStrategy<CheckingContext>::countElementsBefore(context, element);
                 if (m_mode == ResolvingStyle) {
                     RenderStyle* childStyle = context.elementStyle ? context.elementStyle : element->renderStyle();
                     RenderStyle* parentStyle = context.elementStyle ? context.elementParentStyle : parentElement->renderStyle();
@@ -959,12 +927,7 @@ bool SelectorChecker::checkOneSelector(const SelectorCheckingContext& context) c
             if (!selector->parseNth())
                 break;
             if (Element* parentElement = element->parentElement()) {
-                int count = 1;
-                const QualifiedName& type = element->tagQName();
-                for (const Element* sibling = element->previousElementSibling(); sibling; sibling = sibling->previousElementSibling()) {
-                    if (sibling->hasTagName(type))
-                        ++count;
-                }
+                int count = 1 + DOMTraversalStrategy<CheckingContext>::countElementsOfTypeBefore(context, element, element->tagQName());
                 if (m_mode == ResolvingStyle) {
                     RenderStyle* parentStyle = context.elementStyle ? context.elementParentStyle : parentElement->renderStyle();
                     if (parentStyle)
@@ -986,9 +949,7 @@ bool SelectorChecker::checkOneSelector(const SelectorCheckingContext& context) c
                 }
                 if (!parentElement->isFinishedParsingChildren())
                     return false;
-                int count = 1;
-                for (const Element* sibling = element->nextElementSibling(); sibling; sibling = sibling->nextElementSibling())
-                    ++count;
+                int count = 1 + DOMTraversalStrategy<CheckingContext>::countElementsAfter(context, element);
                 if (selector->matchNth(count))
                     return true;
             }
@@ -1004,12 +965,8 @@ bool SelectorChecker::checkOneSelector(const SelectorCheckingContext& context) c
                 }
                 if (!parentElement->isFinishedParsingChildren())
                     return false;
-                int count = 1;
-                const QualifiedName& type = element->tagQName();
-                for (const Element* sibling = element->nextElementSibling(); sibling; sibling = sibling->nextElementSibling()) {
-                    if (sibling->hasTagName(type))
-                        ++count;
-                }
+
+                int count = 1 + DOMTraversalStrategy<CheckingContext>::countElementsOfTypeAfter(context, element, element->tagQName());
                 if (selector->matchNth(count))
                     return true;
             }
@@ -1020,7 +977,7 @@ bool SelectorChecker::checkOneSelector(const SelectorCheckingContext& context) c
             break;
         case CSSSelector::PseudoAny:
             {
-                SelectorCheckingContext subContext(context);
+                CheckingContext subContext(context);
                 subContext.isSubSelector = true;
                 bool hasUnknownPseudoElements = false;
                 PseudoId ignoreDynamicPseudo = NOPSEUDO;
@@ -1402,4 +1359,90 @@ bool SelectorChecker::determineSelectorScopes(const CSSSelectorList& selectorLis
     return true;
 }
 
+template<>
+inline bool SelectorChecker::DOMTraversalStrategy<SelectorChecker::SelectorCheckingContext>::isFirstChild(const SelectorChecker::SelectorCheckingContext&, Element* element)
+{
+    return !element->previousElementSibling();
+}
+
+template<>
+inline bool SelectorChecker::DOMTraversalStrategy<SelectorChecker::SelectorCheckingContext>::isLastChild(const SelectorChecker::SelectorCheckingContext&, Element* element)
+{
+    return !element->nextElementSibling();
+}
+
+template<>
+inline bool SelectorChecker::DOMTraversalStrategy<SelectorChecker::SelectorCheckingContext>::isFirstOfType(const SelectorChecker::SelectorCheckingContext&, Element* element, const QualifiedName& type)
+{
+    for (const Element* sibling = element->previousElementSibling(); sibling; sibling = sibling->previousElementSibling()) {
+        if (sibling->hasTagName(type))
+            return false;
+    }
+    return true;
+}
+
+template<>
+inline bool SelectorChecker::DOMTraversalStrategy<SelectorChecker::SelectorCheckingContext>::isLastOfType(const SelectorChecker::SelectorCheckingContext&, Element* element, const QualifiedName& type)
+{
+    for (const Element* sibling = element->nextElementSibling(); sibling; sibling = sibling->nextElementSibling()) {
+        if (sibling->hasTagName(type))
+            return false;
+    }
+    return true;
+}
+
+template<>
+inline int SelectorChecker::DOMTraversalStrategy<SelectorChecker::SelectorCheckingContext>::countElementsBefore(const SelectorChecker::SelectorCheckingContext&, Element* element)
+{
+    int count = 0;
+    for (const Element* sibling = element->previousElementSibling(); sibling; sibling = sibling->previousElementSibling()) {
+        RenderStyle* s = sibling->renderStyle();
+        unsigned index = s ? s->childIndex() : 0;
+        if (index) {
+            count += index;
+            break;
+        }
+        count++;
+    }
+
+    return count;
+}
+
+template<>
+inline int SelectorChecker::DOMTraversalStrategy<SelectorChecker::SelectorCheckingContext>::countElementsOfTypeBefore(const SelectorChecker::SelectorCheckingContext&, Element* element, const QualifiedName& type)
+{
+    int count = 0;
+    for (const Element* sibling = element->previousElementSibling(); sibling; sibling = sibling->previousElementSibling()) {
+        if (sibling->hasTagName(type))
+            ++count;
+    }
+
+    return count;
+}
+
+template<>
+inline int SelectorChecker::DOMTraversalStrategy<SelectorChecker::SelectorCheckingContext>::countElementsAfter(const SelectorChecker::SelectorCheckingContext&, Element* element)
+{
+    int count = 0;
+    for (const Element* sibling = element->nextElementSibling(); sibling; sibling = sibling->nextElementSibling())
+        ++count;
+
+    return count;
+}
+
+template<>
+inline int SelectorChecker::DOMTraversalStrategy<SelectorChecker::SelectorCheckingContext>::countElementsOfTypeAfter(const SelectorChecker::SelectorCheckingContext&, Element* element, const QualifiedName& type)
+{
+    int count = 0;
+    for (const Element* sibling = element->nextElementSibling(); sibling; sibling = sibling->nextElementSibling()) {
+        if (sibling->hasTagName(type))
+            ++count;
+    }
+
+    return count;
+}
+
+template
+SelectorChecker::SelectorMatch SelectorChecker::checkSelector<SelectorChecker::SelectorCheckingContext>(const SelectorCheckingContext&, PseudoId&, bool&) const;
+
 }
index 79ebaf6..1f3490c 100644 (file)
@@ -81,8 +81,25 @@ public:
         bool hasSelectionPseudo;
     };
 
+    template<typename Context>
+    struct DOMTraversalStrategy {
+        static bool isFirstChild(const Context&, Element*);
+        static bool isLastChild(const Context&, Element*);
+        static bool isFirstOfType(const Context&, Element*, const QualifiedName&);
+        static bool isLastOfType(const Context&, Element*, const QualifiedName&);
+
+        static int countElementsBefore(const Context&, Element*);
+        static int countElementsAfter(const Context&, Element*);
+        static int countElementsOfTypeBefore(const Context&, Element*, const QualifiedName&);
+        static int countElementsOfTypeAfter(const Context&, Element*, const QualifiedName&);
+    };
+
     bool checkSelector(CSSSelector*, Element*, bool isFastCheckableSelector = false) const;
-    SelectorMatch checkSelector(const SelectorCheckingContext&, PseudoId&, bool& hasUnknownPseudoElements) const;
+    template<typename CheckingContext>
+    SelectorMatch checkSelector(const CheckingContext&, PseudoId&, bool& hasUnknownPseudoElements) const;
+    template<typename CheckingContext>
+    bool checkOneSelector(const CheckingContext&) const;
+
     static bool isFastCheckableSelector(const CSSSelector*);
     bool fastCheckSelector(const CSSSelector*, const Element*) const;
 
@@ -121,7 +138,6 @@ public:
     static bool elementMatchesSelectorScopes(const StyledElement*, const HashSet<AtomicStringImpl*>& idScopes, const HashSet<AtomicStringImpl*>& classScopes);
 
 private:
-    bool checkOneSelector(const SelectorCheckingContext&) const;
     bool checkScrollbarPseudoClass(CSSSelector*) const;
     static bool isFrameFocused(const Element*);