Changeset 78457 in webkit
- Timestamp:
- Feb 14, 2011 12:05:15 AM (13 years ago)
- Location:
- trunk/Source/WebCore
- Files:
-
- 3 edited
Legend:
- Unmodified
- Added
- Removed
-
trunk/Source/WebCore/ChangeLog
r78451 r78457 1 2011-02-13 Antti Koivisto <antti@apple.com> 2 3 Reviewed by Dan Bernstein. 4 5 https://bugs.webkit.org/show_bug.cgi?id=54376 6 Make sorting of matched rules faster 7 8 - use std::sort 9 - cache specificity, it is slow to compute 10 - inline compare function 11 12 * css/CSSStyleSelector.cpp: 13 (WebCore::RuleData::specificity): 14 (WebCore::CSSStyleSelector::matchRules): 15 (WebCore::compareRules): 16 (WebCore::CSSStyleSelector::sortMatchedRules): 17 (WebCore::RuleData::RuleData): 18 (WebCore::CSSStyleSelector::matchPageRules): 19 * css/CSSStyleSelector.h: 20 1 21 2011-02-12 Darin Adler <darin@apple.com> 2 22 -
trunk/Source/WebCore/css/CSSStyleSelector.cpp
r78322 r78457 364 364 bool hasMultipartSelector() const { return m_hasMultipartSelector; } 365 365 bool hasTopSelectorMatchingHTMLBasedOnRuleHash() const { return m_hasTopSelectorMatchingHTMLBasedOnRuleHash; } 366 unsigned specificity() const { return m_specificity; } 366 367 367 368 // Try to balance between memory usage (there can be lots of RuleData objects) and good filtering performance. … … 375 376 CSSStyleRule* m_rule; 376 377 CSSSelector* m_selector; 378 unsigned m_specificity; 377 379 unsigned m_position : 29; 378 380 bool m_hasFastCheckableSelector : 1; … … 773 775 774 776 // Sort the set of matched rules. 775 sortMatchedRules( 0, m_matchedRules.size());777 sortMatchedRules(); 776 778 777 779 // Now transfer the set of matched rules over to our list of decls. … … 840 842 } 841 843 842 static bool operator >(const RuleData& r1, const RuleData& r2) 843 { 844 int spec1 = r1.selector()->specificity(); 845 int spec2 = r2.selector()->specificity(); 846 return (spec1 == spec2) ? r1.position() > r2.position() : spec1 > spec2; 847 } 848 849 static bool operator <=(const RuleData& r1, const RuleData& r2) 850 { 851 return !(r1 > r2); 852 } 853 854 void CSSStyleSelector::sortMatchedRules(unsigned start, unsigned end) 855 { 856 if (start >= end || (end - start == 1)) 857 return; // Sanity check. 858 859 if (end - start <= 6) { 860 // Apply a bubble sort for smaller lists. 861 for (unsigned i = end - 1; i > start; i--) { 862 bool sorted = true; 863 for (unsigned j = start; j < i; j++) { 864 const RuleData* elt = m_matchedRules[j]; 865 const RuleData* elt2 = m_matchedRules[j + 1]; 866 if (*elt > *elt2) { 867 sorted = false; 868 m_matchedRules[j] = elt2; 869 m_matchedRules[j + 1] = elt; 870 } 871 } 872 if (sorted) 873 return; 874 } 875 return; 876 } 877 878 // Perform a merge sort for larger lists. 879 unsigned mid = (start + end) / 2; 880 sortMatchedRules(start, mid); 881 sortMatchedRules(mid, end); 882 883 const RuleData* elt = m_matchedRules[mid - 1]; 884 const RuleData* elt2 = m_matchedRules[mid]; 885 886 // Handle the fast common case (of equal specificity). The list may already 887 // be completely sorted. 888 if (*elt <= *elt2) 889 return; 890 891 // We have to merge sort. Ensure our merge buffer is big enough to hold 892 // all the items. 893 Vector<const RuleData*> rulesMergeBuffer; 894 rulesMergeBuffer.reserveInitialCapacity(end - start); 895 896 unsigned i1 = start; 897 unsigned i2 = mid; 898 899 elt = m_matchedRules[i1]; 900 elt2 = m_matchedRules[i2]; 901 902 while (i1 < mid || i2 < end) { 903 if (i1 < mid && (i2 == end || *elt <= *elt2)) { 904 rulesMergeBuffer.append(elt); 905 if (++i1 < mid) 906 elt = m_matchedRules[i1]; 907 } else { 908 rulesMergeBuffer.append(elt2); 909 if (++i2 < end) 910 elt2 = m_matchedRules[i2]; 911 } 912 } 913 914 for (unsigned i = start; i < end; i++) 915 m_matchedRules[i] = rulesMergeBuffer[i - start]; 844 static inline bool compareRules(const RuleData* r1, const RuleData* r2) 845 { 846 unsigned specificity1 = r1->specificity(); 847 unsigned specificity2 = r2->specificity(); 848 return (specificity1 == specificity2) ? r1->position() < r2->position() : specificity1 < specificity2; 849 } 850 851 void CSSStyleSelector::sortMatchedRules() 852 { 853 std::sort(m_matchedRules.begin(), m_matchedRules.end(), compareRules); 916 854 } 917 855 … … 3053 2991 : m_rule(rule) 3054 2992 , m_selector(selector) 2993 , m_specificity(selector->specificity()) 3055 2994 , m_position(position) 3056 2995 , m_hasFastCheckableSelector(isFastCheckableSelector(selector)) … … 3364 3303 3365 3304 // Sort the set of matched rules. 3366 sortMatchedRules( 0, m_matchedRules.size());3305 sortMatchedRules(); 3367 3306 3368 3307 // Now transfer the set of matched rules over to our list of decls. -
trunk/Source/WebCore/css/CSSStyleSelector.h
r78322 r78457 193 193 void matchRulesForList(const Vector<RuleData>*, int& firstRuleIndex, int& lastRuleIndex, bool includeEmptyRules); 194 194 bool fastRejectSelector(const RuleData&) const; 195 void sortMatchedRules( unsigned start, unsigned end);195 void sortMatchedRules(); 196 196 197 197 bool checkSelector(const RuleData&);
Note: See TracChangeset
for help on using the changeset viewer.