Changeset 78457 in webkit

Timestamp:

Feb 14, 2011 12:05:15 AM (13 years ago)

Author:

Antti Koivisto

Message:

​https://bugs.webkit.org/show_bug.cgi?id=54376
Make sorting of matched rules faster

Reviewed by Dan Bernstein.

• use std::sort
• cache specificity, it is slow to compute
• inline compare function

• css/CSSStyleSelector.cpp:

(WebCore::RuleData::specificity):
(WebCore::CSSStyleSelector::matchRules):
(WebCore::compareRules):
(WebCore::CSSStyleSelector::sortMatchedRules):
(WebCore::RuleData::RuleData):
(WebCore::CSSStyleSelector::matchPageRules):

• css/CSSStyleSelector.h:

Location:

trunk/Source/WebCore

Files:

• ChangeLog (modified) (1 diff)
• css/CSSStyleSelector.cpp (modified) (6 diffs)
• css/CSSStyleSelector.h (modified) (1 diff)

trunk/Source/WebCore/ChangeLog

@@ +1 @@
+2011-02-13  Antti Koivisto  <antti@apple.com>
+
+        Reviewed by Dan Bernstein.
+
+        https://bugs.webkit.org/show_bug.cgi?id=54376
+        Make sorting of matched rules faster
+        
+        - use std::sort
+        - cache specificity, it is slow to compute
+        - inline compare function
+
+        * css/CSSStyleSelector.cpp:
+        (WebCore::RuleData::specificity):
+        (WebCore::CSSStyleSelector::matchRules):
+        (WebCore::compareRules):
+        (WebCore::CSSStyleSelector::sortMatchedRules):
+        (WebCore::RuleData::RuleData):
+        (WebCore::CSSStyleSelector::matchPageRules):
+        * css/CSSStyleSelector.h:
+
 2011-02-12  Darin Adler  <darin@apple.com>
 

trunk/Source/WebCore/css/CSSStyleSelector.cpp

@@ -364 +364 @@
     bool hasMultipartSelector() const { return m_hasMultipartSelector; }
     bool hasTopSelectorMatchingHTMLBasedOnRuleHash() const { return m_hasTopSelectorMatchingHTMLBasedOnRuleHash; }
+    unsigned specificity() const { return m_specificity; }
     
     // Try to balance between memory usage (there can be lots of RuleData objects) and good filtering performance.
@@ -375 +376 @@
     CSSStyleRule* m_rule;
     CSSSelector* m_selector;
+    unsigned m_specificity;
     unsigned m_position : 29;
     bool m_hasFastCheckableSelector : 1;
@@ -773 +775 @@
     
     // Sort the set of matched rules.
-    sortMatchedRules(0, m_matchedRules.size());
+    sortMatchedRules();
     
     // Now transfer the set of matched rules over to our list of decls.
@@ -840 +842 @@
 }
 
-static bool operator >(const RuleData& r1, const RuleData& r2)
-{
-    int spec1 = r1.selector()->specificity();
-    int spec2 = r2.selector()->specificity();
-    return (spec1 == spec2) ? r1.position() > r2.position() : spec1 > spec2; 
-}
-    
-static bool operator <=(const RuleData& r1, const RuleData& r2)
-{
-    return !(r1 > r2);
-}
-
-void CSSStyleSelector::sortMatchedRules(unsigned start, unsigned end)
-{
-    if (start >= end || (end - start == 1))
-        return; // Sanity check.
-
-    if (end - start <= 6) {
-        // Apply a bubble sort for smaller lists.
-        for (unsigned i = end - 1; i > start; i--) {
-            bool sorted = true;
-            for (unsigned j = start; j < i; j++) {
-                const RuleData* elt = m_matchedRules[j];
-                const RuleData* elt2 = m_matchedRules[j + 1];
-                if (*elt > *elt2) {
-                    sorted = false;
-                    m_matchedRules[j] = elt2;
-                    m_matchedRules[j + 1] = elt;
-                }
-            }
-            if (sorted)
-                return;
-        }
-        return;
-    }
-
-    // Perform a merge sort for larger lists.
-    unsigned mid = (start + end) / 2;
-    sortMatchedRules(start, mid);
-    sortMatchedRules(mid, end);
-    
-    const RuleData* elt = m_matchedRules[mid - 1];
-    const RuleData* elt2 = m_matchedRules[mid];
-    
-    // Handle the fast common case (of equal specificity).  The list may already
-    // be completely sorted.
-    if (*elt <= *elt2)
-        return;
-    
-    // We have to merge sort.  Ensure our merge buffer is big enough to hold
-    // all the items.
-    Vector<const RuleData*> rulesMergeBuffer;
-    rulesMergeBuffer.reserveInitialCapacity(end - start); 
-
-    unsigned i1 = start;
-    unsigned i2 = mid;
-    
-    elt = m_matchedRules[i1];
-    elt2 = m_matchedRules[i2];
-    
-    while (i1 < mid || i2 < end) {
-        if (i1 < mid && (i2 == end || *elt <= *elt2)) {
-            rulesMergeBuffer.append(elt);
-            if (++i1 < mid)
-                elt = m_matchedRules[i1];
-        } else {
-            rulesMergeBuffer.append(elt2);
-            if (++i2 < end)
-                elt2 = m_matchedRules[i2];
-        }
-    }
-    
-    for (unsigned i = start; i < end; i++)
-        m_matchedRules[i] = rulesMergeBuffer[i - start];
+static inline bool compareRules(const RuleData* r1, const RuleData* r2)
+{
+    unsigned specificity1 = r1->specificity();
+    unsigned specificity2 = r2->specificity();
+    return (specificity1 == specificity2) ? r1->position() < r2->position() : specificity1 < specificity2; 
+}
+
+void CSSStyleSelector::sortMatchedRules()
+{
+    std::sort(m_matchedRules.begin(), m_matchedRules.end(), compareRules);
 }
 
@@ -3053 +2991 @@
     : m_rule(rule)
     , m_selector(selector)
+    , m_specificity(selector->specificity())
     , m_position(position)
     , m_hasFastCheckableSelector(isFastCheckableSelector(selector))
@@ -3364 +3303 @@
 
     // Sort the set of matched rules.
-    sortMatchedRules(0, m_matchedRules.size());
+    sortMatchedRules();
 
     // Now transfer the set of matched rules over to our list of decls.

trunk/Source/WebCore/css/CSSStyleSelector.h

@@ -193 +193 @@
         void matchRulesForList(const Vector<RuleData>*, int& firstRuleIndex, int& lastRuleIndex, bool includeEmptyRules);
         bool fastRejectSelector(const RuleData&) const;
-        void sortMatchedRules(unsigned start, unsigned end);
+        void sortMatchedRules();
         
         bool checkSelector(const RuleData&);