Changeset 77740 in webkit


Ignore:
Timestamp:
Feb 5, 2011 3:23:43 AM (13 years ago)
Author:
Antti Koivisto
Message:

Optimize matching of descendant selectors
https://bugs.webkit.org/show_bug.cgi?id=49876
<rdar://problem/8772822>

Reviewed by Dave Hyatt.

During style recalculation, maintain a filter of tags, ids and classes seen in ancestor elements.
Use the filter to quickly reject descendant and child selectors when doing style matching.

This speeds up style recalculations 3-6x on many major web sites.

  • css/CSSStyleSelector.cpp:

(WebCore::RuleData::RuleData):
(WebCore::RuleData::descendantSelectorIdentifierHashes):
(WebCore::collectElementIdentifiers):
(WebCore::CSSStyleSelector::pushParent):
(WebCore::CSSStyleSelector::popParent):
(WebCore::CSSStyleSelector::fastRejectSelector):
(WebCore::CSSStyleSelector::matchRulesForList):
(WebCore::RuleData::collectDescendantSelectorIdentifierHashes):

  • css/CSSStyleSelector.h:

(WebCore::CSSStyleSelector::ParentStackFrame::ParentStackFrame):

  • dom/Element.cpp:

(WebCore::StyleSelectorParentPusher::StyleSelectorParentPusher):
(WebCore::StyleSelectorParentPusher::push):
(WebCore::StyleSelectorParentPusher::~StyleSelectorParentPusher):
(WebCore::Element::attach):
(WebCore::Element::recalcStyle):

Location:
trunk/Source/WebCore
Files:
4 edited

Legend:

Unmodified
Added
Removed
  • trunk/Source/WebCore/ChangeLog

    r77738 r77740  
     12011-02-05  Antti Koivisto  <antti@apple.com>
     2
     3        Reviewed by Dave Hyatt.
     4
     5        Optimize matching of descendant selectors
     6        https://bugs.webkit.org/show_bug.cgi?id=49876
     7        <rdar://problem/8772822>
     8       
     9        During style recalculation, maintain a filter of tags, ids and classes seen in ancestor elements.
     10        Use the filter to quickly reject descendant and child selectors when doing style matching.
     11
     12        This speeds up style recalculations 3-6x on many major web sites.
     13
     14        * css/CSSStyleSelector.cpp:
     15        (WebCore::RuleData::RuleData):
     16        (WebCore::RuleData::descendantSelectorIdentifierHashes):
     17        (WebCore::collectElementIdentifiers):
     18        (WebCore::CSSStyleSelector::pushParent):
     19        (WebCore::CSSStyleSelector::popParent):
     20        (WebCore::CSSStyleSelector::fastRejectSelector):
     21        (WebCore::CSSStyleSelector::matchRulesForList):
     22        (WebCore::RuleData::collectDescendantSelectorIdentifierHashes):
     23        * css/CSSStyleSelector.h:
     24        (WebCore::CSSStyleSelector::ParentStackFrame::ParentStackFrame):
     25        * dom/Element.cpp:
     26        (WebCore::StyleSelectorParentPusher::StyleSelectorParentPusher):
     27        (WebCore::StyleSelectorParentPusher::push):
     28        (WebCore::StyleSelectorParentPusher::~StyleSelectorParentPusher):
     29        (WebCore::Element::attach):
     30        (WebCore::Element::recalcStyle):
     31
    1322011-02-05  Nate Chapin  <japhet@chromium.org>
    233
  • trunk/Source/WebCore/css/CSSStyleSelector.cpp

    r77664 r77740  
    360360        , m_position(position)
    361361    {
    362     }
     362        collectDescendantSelectorIdentifierHashes();
     363    }
     364    void collectDescendantSelectorIdentifierHashes();
    363365    unsigned position() const { return m_position; }
    364366    CSSStyleRule* rule() const { return m_rule; }
    365367    CSSSelector* selector() const { return m_selector; }
     368   
     369    // Try to balance between memory usage (there can be lots of RuleData objects) and good filtering performance.
     370    static const unsigned maximumIdentifierCount = 4;
     371    const unsigned* descendantSelectorIdentifierHashes() const { return m_descendantSelectorIdentifierHashes; }
    366372
    367373private:
     
    369375    CSSSelector* m_selector;
    370376    unsigned m_position;
     377    // Use plain array instead of a Vector to minimize memory overhead.
     378    unsigned m_descendantSelectorIdentifierHashes[maximumIdentifierCount];
    371379};
    372380
     
    643651    defaultViewSourceStyle->addRulesFromSheet(parseUASheet(sourceUserAgentStyleSheet, sizeof(sourceUserAgentStyleSheet)), screenEval());
    644652}
     653   
     654static inline void collectElementIdentifierHashes(Element* element, Vector<unsigned, 4>& identifierHashes)
     655{
     656    identifierHashes.append(element->localName().impl()->existingHash());
     657    if (element->hasID())
     658        identifierHashes.append(element->idForStyleResolution().impl()->existingHash());
     659    StyledElement* styledElement = element->isStyledElement() ? static_cast<StyledElement*>(element) : 0;
     660    if (styledElement && styledElement->hasClass()) {
     661        const SpaceSplitString& classNames = static_cast<StyledElement*>(element)->classNames();
     662        size_t count = classNames.size();
     663        for (size_t i = 0; i < count; ++i)
     664            identifierHashes.append(classNames[i].impl()->existingHash());
     665    }
     666}
     667   
     668void CSSStyleSelector::pushParent(Element* parent)
     669{
     670    // If we are not invoked consistently for each parent, just pause maintaining the stack.
     671    // There are all kinds of wacky special cases where the style recalc may temporarily branch to some random elements.
     672    // FIXME: Perhaps we should fix up the stack instead? There is some danger of getting into O(n^2) situations doing that.
     673    if (m_parentStack.isEmpty()) {
     674        ASSERT(m_ancestorIdentifierFilter.isEmpty());
     675        // We must start from the root.
     676        if (parent->parentElement())
     677            return;
     678    } else if (m_parentStack.last().element != parent->parentElement())
     679        return;
     680
     681    m_parentStack.append(ParentStackFrame(parent));
     682    ParentStackFrame& parentFrame = m_parentStack.last();
     683    // Mix tags, class names and ids into some sort of weird bouillabaisse.
     684    // The filter is used for fast rejection of child and descendant selectors.
     685    collectElementIdentifierHashes(parent, parentFrame.identifierHashes);
     686    size_t count = parentFrame.identifierHashes.size();
     687    for (size_t i = 0; i < count; ++i)
     688        m_ancestorIdentifierFilter.add(parentFrame.identifierHashes[i]);
     689}
     690
     691void CSSStyleSelector::popParent(Element* parent)
     692{
     693    if (m_parentStack.isEmpty() || m_parentStack.last().element != parent)
     694        return;
     695
     696    const ParentStackFrame& parentFrame = m_parentStack.last();
     697    size_t count = parentFrame.identifierHashes.size();
     698    for (size_t i = 0; i < count; ++i)
     699        m_ancestorIdentifierFilter.remove(parentFrame.identifierHashes[i]);
     700    m_parentStack.removeLast();
     701    ASSERT(!m_parentStack.isEmpty() || m_ancestorIdentifierFilter.isEmpty());
     702}
    645703
    646704void CSSStyleSelector::addMatchedDeclaration(CSSMutableStyleDeclaration* decl)
     
    694752}
    695753
     754inline bool CSSStyleSelector::fastRejectSelector(const RuleData& ruleData) const
     755{
     756    const unsigned* descendantSelectorIdentifierHashes = ruleData.descendantSelectorIdentifierHashes();
     757    for (unsigned n = 0; n < RuleData::maximumIdentifierCount && descendantSelectorIdentifierHashes[n]; ++n) {
     758        if (!m_ancestorIdentifierFilter.contains(descendantSelectorIdentifierHashes[n]))
     759            return true;
     760    }
     761    return false;
     762}
     763
    696764void CSSStyleSelector::matchRulesForList(const Vector<RuleData>* rules, int& firstRuleIndex, int& lastRuleIndex, bool includeEmptyRules)
    697765{
    698766    if (!rules)
    699767        return;
     768    // In some cases we may end up looking up style for random elements in the middle of a recursive tree resolve.
     769    // Ancestor identifier filter won't be up-to-date in that case and we can't use the fast path.
     770    bool canUseFastReject = !m_parentStack.isEmpty() && m_parentStack.last().element == m_parentNode;
     771
    700772    unsigned size = rules->size();
    701773    for (unsigned i = 0; i < size; ++i) {
    702774        const RuleData& ruleData = rules->at(i);
    703775        CSSStyleRule* rule = ruleData.rule();
    704         if (m_checker.m_sameOriginOnly && !m_checker.m_document->securityOrigin()->canRequest(rule->baseURL()))
    705             continue; 
     776        if (canUseFastReject && fastRejectSelector(ruleData))
     777            continue;
    706778        if (checkSelector(ruleData.selector())) {
    707779            // If the rule has no properties to apply, then ignore it in the non-debug mode.
     
    709781            if (!decl || (!decl->length() && !includeEmptyRules))
    710782                continue;
    711            
     783            if (m_checker.m_sameOriginOnly && !m_checker.m_document->securityOrigin()->canRequest(rule->baseURL()))
     784                continue;
    712785            // If we're matching normal rules, set a pseudo bit if
    713786            // we really just matched a pseudo-element.
     
    28512924
    28522925// -----------------------------------------------------------------
     2926
     2927inline void RuleData::collectDescendantSelectorIdentifierHashes()
     2928{
     2929    unsigned identifierCount = 0;
     2930    CSSSelector::Relation relation = m_selector->relation();
     2931    CSSSelector* selector = m_selector->tagHistory();
     2932    // Skip the topmost selector. It is handled quickly by the rule hashes.
     2933    for (; selector; selector = selector->tagHistory()) {
     2934        if (relation != CSSSelector::SubSelector)
     2935            break;
     2936        relation = selector->relation();
     2937    }
     2938    for (; selector; selector = selector->tagHistory()) {
     2939        // Only collect identifiers that match direct ancestors.
     2940        // FIXME: Intead of just stopping, this should skip over sibling selectors.
     2941        if (relation != CSSSelector::Descendant && relation != CSSSelector::Child && relation != CSSSelector::SubSelector)
     2942            break;
     2943        if ((selector->m_match == CSSSelector::Id || selector->m_match == CSSSelector::Class) && !selector->value().isEmpty())
     2944            m_descendantSelectorIdentifierHashes[identifierCount++] = selector->value().impl()->existingHash();
     2945        if (identifierCount == maximumIdentifierCount)
     2946            return;
     2947        const AtomicString& localName = selector->tag().localName();
     2948        if (localName != starAtom)
     2949            m_descendantSelectorIdentifierHashes[identifierCount++] = localName.impl()->existingHash();
     2950        if (identifierCount == maximumIdentifierCount)
     2951            return;
     2952        relation = selector->relation();
     2953    }
     2954    m_descendantSelectorIdentifierHashes[identifierCount] = 0;
     2955}
    28532956
    28542957RuleSet::RuleSet()
  • trunk/Source/WebCore/css/CSSStyleSelector.h

    r77376 r77740  
    2828#include "MediaQueryExp.h"
    2929#include "RenderStyle.h"
     30#include <wtf/HashCountedSet.h>
    3031#include <wtf/HashMap.h>
    3132#include <wtf/HashSet.h>
     
    9091                         bool strictParsing, bool matchAuthorAndUserStyles);
    9192        ~CSSStyleSelector();
     93       
     94        // Using these during tree walk will allow style selector to optimize child and descendant selector lookups.
     95        void pushParent(Element* parent);
     96        void popParent(Element* parent);
    9297
    9398        PassRefPtr<RenderStyle> styleForElement(Element* e, RenderStyle* parentStyle = 0, bool allowSharing = true, bool resolveForRootDefault = false, bool matchVisitedPseudoClass = false);
     
    187192        void matchRules(RuleSet*, int& firstRuleIndex, int& lastRuleIndex, bool includeEmptyRules);
    188193        void matchRulesForList(const Vector<RuleData>*, int& firstRuleIndex, int& lastRuleIndex, bool includeEmptyRules);
     194        bool fastRejectSelector(const RuleData&) const;
    189195        void sortMatchedRules(unsigned start, unsigned end);
    190196
     
    204210        OwnPtr<RuleSet> m_siblingRules;
    205211        HashSet<AtomicStringImpl*> m_idsInRules;
     212       
     213        struct ParentStackFrame {
     214            ParentStackFrame(Element* element) : element(element) {}
     215            Element* element;
     216            Vector<unsigned, 4> identifierHashes;
     217        };
     218        Vector<ParentStackFrame> m_parentStack;
     219        // FIXME: Replace this with a bloom filter.
     220        HashCountedSet<unsigned, AlreadyHashed> m_ancestorIdentifierFilter;
    206221
    207222        bool m_hasUAAppearance;
  • trunk/Source/WebCore/dom/Element.cpp

    r76183 r77740  
    6969using namespace XMLNames;
    7070   
     71class StyleSelectorParentPusher {
     72public:
     73    StyleSelectorParentPusher(CSSStyleSelector* styleSelector, Element* parent)
     74        : m_styleSelector(styleSelector)
     75        , m_parent(parent)
     76        , m_didPush(false)
     77    {
     78    }
     79    void push()
     80    {
     81        if (m_didPush)
     82            return;
     83        m_styleSelector->pushParent(m_parent);
     84        m_didPush = true;
     85    }
     86    ~StyleSelectorParentPusher()
     87    {
     88        if (m_didPush)
     89            m_styleSelector->popParent(m_parent);
     90    }
     91
     92private:
     93    CSSStyleSelector* m_styleSelector;
     94    Element* m_parent;
     95    bool m_didPush;
     96};
     97   
    7198PassRefPtr<Element> Element::create(const QualifiedName& tagName, Document* document)
    7299{
     
    918945
    919946    createRendererIfNeeded();
     947   
     948    StyleSelectorParentPusher parentPusher(document()->styleSelector(), this);
     949    if (firstChild())
     950        parentPusher.push();
    920951    ContainerNode::attach();
    921     if (Node* shadow = shadowRoot())
     952    if (Node* shadow = shadowRoot()) {
     953        parentPusher.push();
    922954        shadow->attach();
     955    }
    923956    if (hasRareData()) {   
    924957        ElementRareData* data = rareData();
     
    10601093        }
    10611094    }
    1062 
     1095    StyleSelectorParentPusher parentPusher(document()->styleSelector(), this);
    10631096    // FIXME: This check is good enough for :hover + foo, but it is not good enough for :hover + foo + bar.
    10641097    // For now we will just worry about the common case, since it's a lot trickier to get the second case right
     
    10691102        if (forceCheckOfNextElementSibling && n->isElementNode())
    10701103            n->setNeedsStyleRecalc();
    1071         if (change >= Inherit || n->isTextNode() || n->childNeedsStyleRecalc() || n->needsStyleRecalc())
     1104        if (change >= Inherit || n->isTextNode() || n->childNeedsStyleRecalc() || n->needsStyleRecalc()) {
     1105            parentPusher.push();
    10721106            n->recalcStyle(change);
     1107        }
    10731108        if (n->isElementNode())
    10741109            forceCheckOfNextElementSibling = childRulesChanged && hasDirectAdjacentRules;
     
    10761111    // FIXME: This does not care about sibling combinators. Will be necessary in XBL2 world.
    10771112    if (Node* shadow = shadowRoot()) {
    1078         if (change >= Inherit || shadow->isTextNode() || shadow->childNeedsStyleRecalc() || shadow->needsStyleRecalc())
     1113        if (change >= Inherit || shadow->isTextNode() || shadow->childNeedsStyleRecalc() || shadow->needsStyleRecalc()) {
     1114            parentPusher.push();
    10791115            shadow->recalcStyle(change);
     1116        }
    10801117    }
    10811118
Note: See TracChangeset for help on using the changeset viewer.