2011-03-25 Leo Yang <leo.yang@torchmobile.com.cn>
authorcommit-queue@webkit.org <commit-queue@webkit.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 25 Mar 2011 09:19:55 +0000 (09:19 +0000)
committercommit-queue@webkit.org <commit-queue@webkit.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 25 Mar 2011 09:19:55 +0000 (09:19 +0000)
        Reviewed by Nikolas Zimmermann.

        SVG <use> element performance improvement
        https://bugs.webkit.org/show_bug.cgi?id=57077

        SVG <use> element was expanding nesting <use> and <symbol> elements
        in an inefficient way. After it expanded an <use> or a <symbol>
        element it would restart expanding from the shadow tree root.
        This behavior was leading about 160 millions of calls to
        expandUseElementInShadowTree or expandSymbolElementInShadowTree for
        a single shadow tree which is illustrated by
        http://upload.wikimedia.org/wikipedia/commons/4/4e/Sierpinski_carpet_6.svg.
        But the effective calls, which really expand <use> or <symbol>
        elements, were about 5200; others were passing-by calls, which are
        recursively down to the children.

        This patch is altering the expanding path to reduce the passing-by
        calls. It will expand elements in sibling chain where there is an
        effective call, because the effective call replaces element which is
        expanded and the replacement results lose of the sibling chain of
        the replaced on the upper recursion stack. With this patch the
        passing-by calls are reduced from about 160 millions to about 30
        thousands.

        No functionality change, no new tests.

        * svg/SVGUseElement.cpp:
        (WebCore::SVGUseElement::expandUseElementsInShadowTree):
        (WebCore::SVGUseElement::expandSymbolElementsInShadowTree):
        * svg/SVGUseElement.h:

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

Source/WebCore/ChangeLog
Source/WebCore/svg/SVGUseElement.cpp
Source/WebCore/svg/SVGUseElement.h

index ac1ca24..d4677d3 100644 (file)
@@ -1,3 +1,36 @@
+2011-03-25  Leo Yang  <leo.yang@torchmobile.com.cn>
+
+        Reviewed by Nikolas Zimmermann.
+
+        SVG <use> element performance improvement
+        https://bugs.webkit.org/show_bug.cgi?id=57077
+
+        SVG <use> element was expanding nesting <use> and <symbol> elements
+        in an inefficient way. After it expanded an <use> or a <symbol>
+        element it would restart expanding from the shadow tree root.
+        This behavior was leading about 160 millions of calls to
+        expandUseElementInShadowTree or expandSymbolElementInShadowTree for
+        a single shadow tree which is illustrated by
+        http://upload.wikimedia.org/wikipedia/commons/4/4e/Sierpinski_carpet_6.svg.
+        But the effective calls, which really expand <use> or <symbol>
+        elements, were about 5200; others were passing-by calls, which are
+        recursively down to the children.
+
+        This patch is altering the expanding path to reduce the passing-by
+        calls. It will expand elements in sibling chain where there is an
+        effective call, because the effective call replaces element which is
+        expanded and the replacement results lose of the sibling chain of
+        the replaced on the upper recursion stack. With this patch the
+        passing-by calls are reduced from about 160 millions to about 30
+        thousands.
+
+        No functionality change, no new tests.
+
+        * svg/SVGUseElement.cpp:
+        (WebCore::SVGUseElement::expandUseElementsInShadowTree):
+        (WebCore::SVGUseElement::expandSymbolElementsInShadowTree):
+        * svg/SVGUseElement.h:
+
 2011-03-25  Dominic Cooney  <dominicc@google.com>
 
         Reviewed by Kent Tamura.
index 91d15df..21f0954 100644 (file)
@@ -568,11 +568,11 @@ void SVGUseElement::buildShadowAndInstanceTree(SVGShadowTreeRootElement* shadowR
 #if ENABLE(SVG) && ENABLE(SVG_USE)
     // Expand all <use> elements in the shadow tree.
     // Expand means: replace the actual <use> element by what it references.
-    expandUseElementsInShadowTree(shadowRoot, shadowRoot);
+    expandUseElementsInShadowTree(shadowRoot);
 
     // Expand all <symbol> elements in the shadow tree.
     // Expand means: replace the actual <symbol> element by the <svg> element.
-    expandSymbolElementsInShadowTree(shadowRoot, shadowRoot);
+    expandSymbolElementsInShadowTree(shadowRoot);
 #endif
 
     // Now that the shadow tree is completly expanded, we can associate
@@ -821,7 +821,7 @@ void SVGUseElement::buildShadowTree(SVGShadowTreeRootElement* shadowRoot, SVGEle
 }
 
 #if ENABLE(SVG) && ENABLE(SVG_USE)
-void SVGUseElement::expandUseElementsInShadowTree(SVGShadowTreeRootElement* shadowRoot, Node* element)
+void SVGUseElement::expandUseElementsInShadowTree(Node* element)
 {
     // Why expand the <use> elements in the shadow tree here, and not just
     // do this directly in buildShadowTree, if we encounter a <use> element?
@@ -869,21 +869,25 @@ void SVGUseElement::expandUseElementsInShadowTree(SVGShadowTreeRootElement* shad
         if (subtreeContainsDisallowedElement(cloneParent.get()))
             removeDisallowedElementsFromSubtree(cloneParent.get());
 
+        RefPtr<Node> replacingElement(cloneParent.get());
+
         // Replace <use> with referenced content.
         ASSERT(use->parentNode()); 
         use->parentNode()->replaceChild(cloneParent.release(), use, ec);
         ASSERT(!ec);
 
-        // Immediately stop here, and restart expanding.
-        expandUseElementsInShadowTree(shadowRoot, shadowRoot);
-        return;
+        // Expand the siblings because the *element* is replaced and we will
+        // lose the sibling chain when we are back from recursion.
+        element = replacingElement.get();
+        for (RefPtr<Node> sibling = element->nextSibling(); sibling; sibling = sibling->nextSibling())
+            expandUseElementsInShadowTree(sibling.get());
     }
 
     for (RefPtr<Node> child = element->firstChild(); child; child = child->nextSibling())
-        expandUseElementsInShadowTree(shadowRoot, child.get());
+        expandUseElementsInShadowTree(child.get());
 }
 
-void SVGUseElement::expandSymbolElementsInShadowTree(SVGShadowTreeRootElement* shadowRoot, Node* element)
+void SVGUseElement::expandSymbolElementsInShadowTree(Node* element)
 {
     if (element->hasTagName(SVGNames::symbolTag)) {
         // Spec: The referenced 'symbol' and its contents are deep-cloned into the generated tree,
@@ -913,18 +917,22 @@ void SVGUseElement::expandSymbolElementsInShadowTree(SVGShadowTreeRootElement* s
         if (subtreeContainsDisallowedElement(svgElement.get()))
             removeDisallowedElementsFromSubtree(svgElement.get());
 
+        RefPtr<Node> replacingElement(svgElement.get());
+
         // Replace <symbol> with <svg>.
         ASSERT(element->parentNode()); 
         element->parentNode()->replaceChild(svgElement.release(), element, ec);
         ASSERT(!ec);
 
-        // Immediately stop here, and restart expanding.
-        expandSymbolElementsInShadowTree(shadowRoot, shadowRoot);
-        return;
+        // Expand the siblings because the *element* is replaced and we will
+        // lose the sibling chain when we are back from recursion.
+        element = replacingElement.get();
+        for (RefPtr<Node> sibling = element->nextSibling(); sibling; sibling = sibling->nextSibling())
+            expandSymbolElementsInShadowTree(sibling.get());
     }
 
     for (RefPtr<Node> child = element->firstChild(); child; child = child->nextSibling())
-        expandSymbolElementsInShadowTree(shadowRoot, child.get());
+        expandSymbolElementsInShadowTree(child.get());
 }
 
 #endif
index 10c9be9..30569b5 100644 (file)
@@ -91,8 +91,8 @@ private:
     void buildShadowTree(SVGShadowTreeRootElement*, SVGElement* target, SVGElementInstance* targetInstance);
 
 #if ENABLE(SVG) && ENABLE(SVG_USE)
-    void expandUseElementsInShadowTree(SVGShadowTreeRootElement*, Node* element);
-    void expandSymbolElementsInShadowTree(SVGShadowTreeRootElement*, Node* element);
+    void expandUseElementsInShadowTree(Node* element);
+    void expandSymbolElementsInShadowTree(Node* element);
 #endif
 
     // "Tree connector"