Changeset 30667 in webkit

Timestamp:

Feb 29, 2008 10:58:06 AM (16 years ago)

Author:

hyatt@apple.com

Message:

<rdar://problem/5755916> REGRESSION: Loading HTML5 spec is 5x slower on TOT than in 3.0.4

Improve the performance of dynamic sibling and CSS3 selectors so that there is no slowdown any more.
Be more precise in terms of what nodes we mark dirty.

Reviewed by Beth

• css/CSSStyleSelector.cpp: (WebCore::CSSStyleSelector::checkSelector):
• dom/Element.cpp: (WebCore::Element::recalcStyle): (WebCore::checkForSiblingStyleChanges): (WebCore::Element::childrenChanged): (WebCore::Element::finishParsingChildren):
• rendering/RenderStyle.cpp: (WebCore::RenderStyle::RenderStyle):
• rendering/RenderStyle.h: (WebCore::RenderStyle::childrenAffectedByPositionalRules): (WebCore::RenderStyle::childrenAffectedByDirectAdjacentRules): (WebCore::RenderStyle::setChildrenAffectedByDirectAdjacentRules):

Location:

trunk/WebCore

Files:

• ChangeLog (modified) (1 diff)
• css/CSSStyleSelector.cpp (modified) (1 diff)
• dom/Element.cpp (modified) (6 diffs)
• rendering/RenderStyle.cpp (modified) (3 diffs)
• rendering/RenderStyle.h (modified) (2 diffs)

trunk/WebCore/ChangeLog

@@ +1 @@
+2008-02-29  David Hyatt  <hyatt@apple.com>
+
+        <rdar://problem/5755916> REGRESSION: Loading HTML5 spec is 5x slower on TOT than in 3.0.4
+
+        Improve the performance of dynamic sibling and CSS3 selectors so that there is no slowdown any more.
+        Be more precise in terms of what nodes we mark dirty.
+
+        Reviewed by Beth
+
+        * css/CSSStyleSelector.cpp:
+        (WebCore::CSSStyleSelector::checkSelector):
+        * dom/Element.cpp:
+        (WebCore::Element::recalcStyle):
+        (WebCore::checkForSiblingStyleChanges):
+        (WebCore::Element::childrenChanged):
+        (WebCore::Element::finishParsingChildren):
+        * rendering/RenderStyle.cpp:
+        (WebCore::RenderStyle::RenderStyle):
+        * rendering/RenderStyle.h:
+        (WebCore::RenderStyle::childrenAffectedByPositionalRules):
+        (WebCore::RenderStyle::childrenAffectedByDirectAdjacentRules):
+        (WebCore::RenderStyle::setChildrenAffectedByDirectAdjacentRules):
+
 2008-02-29  Alexey Proskuryakov  <ap@webkit.org>
 

trunk/WebCore/css/CSSStyleSelector.cpp

@@ -1430 +1430 @@
                 RenderStyle* parentStyle = (m_element == e) ? m_parentStyle : e->parentNode()->renderStyle();
                 if (parentStyle)
-                    parentStyle->setChildrenAffectedByForwardPositionalRules();
+                    parentStyle->setChildrenAffectedByDirectAdjacentRules();
             }
             Node* n = e->previousSibling();

trunk/WebCore/dom/Element.cpp

@@ -707 +707 @@
     RenderStyle* currentStyle = renderStyle();
     bool hasParentStyle = parentNode() ? parentNode()->renderStyle() : false;
-    bool hasPositionalChildren = currentStyle && (currentStyle->childrenAffectedByFirstChildRules() || currentStyle->childrenAffectedByLastChildRules() ||
-                                                  currentStyle->childrenAffectedByForwardPositionalRules() || currentStyle->childrenAffectedByBackwardPositionalRules());
+    bool hasPositionalRules = changed() && currentStyle && currentStyle->childrenAffectedByPositionalRules();
 
 #if ENABLE(SVG)
@@ -751 +750 @@
             if (currentStyle->childrenAffectedByLastChildRules())
                 newStyle->setChildrenAffectedByLastChildRules();
+            if (currentStyle->childrenAffectedByDirectAdjacentRules())
+                newStyle->setChildrenAffectedByDirectAdjacentRules();
         }
 
@@ -769 +770 @@
 
         if (change != Force) {
-            if ((document()->usesDescendantRules() || hasPositionalChildren) && styleChangeType() == FullStyleChange)
+            if ((document()->usesDescendantRules() || hasPositionalRules) && styleChangeType() == FullStyleChange)
                 change = Force;
             else
@@ -801 +802 @@
 }
 
-static void checkFirstChildRules(Element* e, RenderStyle* style)
-{
-    if (style->childrenAffectedByFirstChildRules()) {
-        // Check our first two children.  They need to be true and false respectively.
-        bool checkingFirstChild = true;
-        for (Node* n = e->firstChild(); n; n = n->nextSibling()) {
-            if (n->isElementNode()) {
-                if (checkingFirstChild) {
-                    if (n->attached() && n->renderStyle() && !n->renderStyle()->firstChildState())
-                        n->setChanged();
-                    checkingFirstChild = false;
-                } else {
-                    if (n->attached() && n->renderStyle() && n->renderStyle()->firstChildState())
-                        n->setChanged();
-                    break;
-                }
-            }
-        }
-    } 
-}
-
-static void checkLastChildRules(Element* e, RenderStyle* style)
-{
-    if (style->childrenAffectedByLastChildRules()) {
-        // Check our last two children.  They need to be true and false respectively.
-        bool checkingLastChild = true;
-        for (Node* n = e->lastChild(); n; n = n->previousSibling()) {
-            if (n->isElementNode()) {
-                if (checkingLastChild) {
-                    if (n->attached() && n->renderStyle() && !n->renderStyle()->lastChildState())
-                        n->setChanged();
-                    checkingLastChild = false;
-                } else {
-                    if (n->attached() && n->renderStyle() && n->renderStyle()->lastChildState())
-                        n->setChanged();
-                    break;
-                }
-            }
-        }
-    }
-}
-
-static bool checkEmptyRules(Element* e, RenderStyle* style)
-{
-    return style->affectedByEmpty() && (!style->emptyState() || e->hasChildNodes());
-}
-
-static void checkStyleRules(Element* e, RenderStyle* style, bool changedByParser)
-{
-    if (e->changed() || !style)
-        return;
-
-    if (style->childrenAffectedByBackwardPositionalRules() || 
-        (!changedByParser && style->childrenAffectedByForwardPositionalRules()) ||
-        checkEmptyRules(e, style)) {
+static void checkForSiblingStyleChanges(Element* e, RenderStyle* style, bool finishedParsingCallback,
+                                        Node* beforeChange, Node* afterChange, int childCountDelta)
+{
+    if (!style || (e->changed() && style->childrenAffectedByPositionalRules()))
+        return;
+
+    // :first-child.  In the parser callback case, we don't have to check anything, since we were right the first time.
+    // In the DOM case, we only need to do something if |afterChange| is not 0.
+    // |afterChange| is 0 in the parser case, so it works out that we'll skip this block.
+    if (style->childrenAffectedByFirstChildRules() && afterChange) {
+        // Find our new first child.
+        Node* newFirstChild = 0;
+        for (newFirstChild = e->firstChild(); newFirstChild && !newFirstChild->isElementNode(); newFirstChild = newFirstChild->nextSibling()) {};
+        
+        // Find the first element node following |afterChange|
+        Node* firstElementAfterInsertion = 0;
+        for (firstElementAfterInsertion = afterChange;
+             firstElementAfterInsertion && !firstElementAfterInsertion->isElementNode();
+             firstElementAfterInsertion = firstElementAfterInsertion->nextSibling()) {};
+        
+        // This is the insert/append case.
+        if (newFirstChild != firstElementAfterInsertion && firstElementAfterInsertion && firstElementAfterInsertion->attached() &&
+            firstElementAfterInsertion->renderStyle() && firstElementAfterInsertion->renderStyle()->firstChildState())
+            firstElementAfterInsertion->setChanged();
+            
+        // We also have to handle node removal.
+        if (childCountDelta < 0 && newFirstChild == firstElementAfterInsertion && newFirstChild && newFirstChild->renderStyle() && !newFirstChild->renderStyle()->firstChildState())
+            newFirstChild->setChanged();
+    }
+
+    // :last-child.  In the parser callback case, we don't have to check anything, since we were right the first time.
+    // In the DOM case, we only need to do something if |afterChange| is not 0.
+    if (style->childrenAffectedByLastChildRules() && beforeChange) {
+        // Find our new last child.
+        Node* newLastChild = 0;
+        for (newLastChild = e->lastChild(); newLastChild && !newLastChild->isElementNode(); newLastChild = newLastChild->previousSibling()) {};
+        
+        // Find the last element node going backwards from |beforeChange|
+        Node* lastElementBeforeInsertion = 0;
+        for (lastElementBeforeInsertion = beforeChange;
+             lastElementBeforeInsertion && !lastElementBeforeInsertion->isElementNode();
+             lastElementBeforeInsertion = lastElementBeforeInsertion->previousSibling()) {};
+        
+        if (newLastChild != lastElementBeforeInsertion && lastElementBeforeInsertion && lastElementBeforeInsertion->attached() &&
+            lastElementBeforeInsertion->renderStyle() && lastElementBeforeInsertion->renderStyle()->lastChildState())
+            lastElementBeforeInsertion->setChanged();
+            
+        // We also have to handle node removal.  The parser callback case is similar to node removal as well in that we need to change the last child
+        // to match now.
+        if ((childCountDelta < 0 || finishedParsingCallback) && newLastChild == lastElementBeforeInsertion && newLastChild && newLastChild->renderStyle() && !newLastChild->renderStyle()->lastChildState())
+            newLastChild->setChanged();
+    }
+
+    // The + selector.  We need to invalidate the first element following the insertion point.  It is the only possible element
+    // that could be affected by this DOM change.
+    if (style->childrenAffectedByDirectAdjacentRules() && afterChange) {
+        Node* firstElementAfterInsertion = 0;
+        for (firstElementAfterInsertion = afterChange;
+             firstElementAfterInsertion && !firstElementAfterInsertion->isElementNode();
+             firstElementAfterInsertion = firstElementAfterInsertion->nextSibling()) {};
+        if (firstElementAfterInsertion && firstElementAfterInsertion->attached())
+            firstElementAfterInsertion->setChanged();
+    }
+
+    // Forward positional selectors include the ~ selector, nth-child, nth-of-type, first-of-type and only-of-type.
+    // Backward positional selectors include nth-last-child, nth-last-of-type, last-of-type and only-of-type.
+    // We have to invalidate everything following the insertion point in the forward case, and everything before the insertion point in the
+    // backward case.
+    // |afterChange| is 0 in the parser callback case, so we won't do any work for the forward case if we don't have to.
+    // For performance reasons we just mark the parent node as changed, since we don't want to make childrenChanged O(n^2) by crawling all our kids
+    // here.  recalcStyle will then force a walk of the children when it sees that this has happened.
+    if ((style->childrenAffectedByForwardPositionalRules() && afterChange) ||
+        (style->childrenAffectedByBackwardPositionalRules() && beforeChange))
         e->setChanged();
-        return;
-    }
-
-    checkFirstChildRules(e, style);
-    checkLastChildRules(e, style);
+    
+    // :empty selector.
+    if (style->affectedByEmpty() && (!style->emptyState() || e->hasChildNodes()))
+        e->setChanged();
 }
 
@@ -868 +886 @@
     ContainerNode::childrenChanged(changedByParser, beforeChange, afterChange, childCountDelta);
     if (!changedByParser)
-        checkStyleRules(this, renderStyle(), false);
+        checkForSiblingStyleChanges(this, renderStyle(), false, beforeChange, afterChange, childCountDelta);
 }
 
@@ -875 +893 @@
     ContainerNode::finishParsingChildren();
     m_parsingChildrenFinished = true;
-    checkStyleRules(this, renderStyle(), true);
+    checkForSiblingStyleChanges(this, renderStyle(), true, lastChild(), 0, 0);
 }
 

trunk/WebCore/rendering/RenderStyle.cpp

@@ -951 +951 @@
     , m_childrenAffectedByFirstChildRules(false)
     , m_childrenAffectedByLastChildRules(false)
+    , m_childrenAffectedByDirectAdjacentRules(false)
     , m_childrenAffectedByForwardPositionalRules(false)
     , m_childrenAffectedByBackwardPositionalRules(false)
@@ -973 +974 @@
     , m_childrenAffectedByFirstChildRules(false)
     , m_childrenAffectedByLastChildRules(false)
+    , m_childrenAffectedByDirectAdjacentRules(false)
     , m_childrenAffectedByForwardPositionalRules(false)
     , m_childrenAffectedByBackwardPositionalRules(false)
@@ -1017 +1019 @@
     , m_childrenAffectedByFirstChildRules(false)
     , m_childrenAffectedByLastChildRules(false)
+    , m_childrenAffectedByDirectAdjacentRules(false)
     , m_childrenAffectedByForwardPositionalRules(false)
     , m_childrenAffectedByBackwardPositionalRules(false)

trunk/WebCore/rendering/RenderStyle.h

@@ -1515 +1515 @@
     bool m_childrenAffectedByFirstChildRules : 1;
     bool m_childrenAffectedByLastChildRules  : 1;
+    bool m_childrenAffectedByDirectAdjacentRules : 1;
     bool m_childrenAffectedByForwardPositionalRules : 1;
     bool m_childrenAffectedByBackwardPositionalRules : 1;
     bool m_firstChildState : 1;
     bool m_lastChildState : 1;
-    unsigned m_childIndex : 19; // Plenty of bits to cache an index.
+    unsigned m_childIndex : 18; // Plenty of bits to cache an index.
 
     int m_ref;
@@ -2166 +2167 @@
     bool emptyState() const { return m_emptyState; }
     void setEmptyState(bool b) { m_affectedByEmpty = true; m_unique = true; m_emptyState = b; }
+    bool childrenAffectedByPositionalRules() const { return childrenAffectedByForwardPositionalRules() || childrenAffectedByBackwardPositionalRules(); }
     bool childrenAffectedByFirstChildRules() const { return m_childrenAffectedByFirstChildRules; }
     void setChildrenAffectedByFirstChildRules() { m_childrenAffectedByFirstChildRules = true; }
     bool childrenAffectedByLastChildRules() const { return m_childrenAffectedByLastChildRules; }
     void setChildrenAffectedByLastChildRules() { m_childrenAffectedByLastChildRules = true; }
+    bool childrenAffectedByDirectAdjacentRules() const { return m_childrenAffectedByDirectAdjacentRules; }
+    void setChildrenAffectedByDirectAdjacentRules() { m_childrenAffectedByDirectAdjacentRules = true; }
     bool childrenAffectedByForwardPositionalRules() const { return m_childrenAffectedByForwardPositionalRules; }
     void setChildrenAffectedByForwardPositionalRules() { m_childrenAffectedByForwardPositionalRules = true; }