<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN"
"http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head><meta http-equiv="content-type" content="text/html; charset=utf-8" />
<title>[81950] trunk/Source/WebCore</title>
</head>
<body>

<style type="text/css"><!--
#msg dl.meta { border: 1px #006 solid; background: #369; padding: 6px; color: #fff; }
#msg dl.meta dt { float: left; width: 6em; font-weight: bold; }
#msg dt:after { content:':';}
#msg dl, #msg dt, #msg ul, #msg li, #header, #footer, #logmsg { font-family: verdana,arial,helvetica,sans-serif; font-size: 10pt;  }
#msg dl a { font-weight: bold}
#msg dl a:link    { color:#fc3; }
#msg dl a:active  { color:#ff0; }
#msg dl a:visited { color:#cc6; }
h3 { font-family: verdana,arial,helvetica,sans-serif; font-size: 10pt; font-weight: bold; }
#msg pre { overflow: auto; background: #ffc; border: 1px #fa0 solid; padding: 6px; }
#logmsg { background: #ffc; border: 1px #fa0 solid; padding: 1em 1em 0 1em; }
#logmsg p, #logmsg pre, #logmsg blockquote { margin: 0 0 1em 0; }
#logmsg p, #logmsg li, #logmsg dt, #logmsg dd { line-height: 14pt; }
#logmsg h1, #logmsg h2, #logmsg h3, #logmsg h4, #logmsg h5, #logmsg h6 { margin: .5em 0; }
#logmsg h1:first-child, #logmsg h2:first-child, #logmsg h3:first-child, #logmsg h4:first-child, #logmsg h5:first-child, #logmsg h6:first-child { margin-top: 0; }
#logmsg ul, #logmsg ol { padding: 0; list-style-position: inside; margin: 0 0 0 1em; }
#logmsg ul { text-indent: -1em; padding-left: 1em; }#logmsg ol { text-indent: -1.5em; padding-left: 1.5em; }
#logmsg > ul, #logmsg > ol { margin: 0 0 1em 0; }
#logmsg pre { background: #eee; padding: 1em; }
#logmsg blockquote { border: 1px solid #fa0; border-left-width: 10px; padding: 1em 1em 0 1em; background: white;}
#logmsg dl { margin: 0; }
#logmsg dt { font-weight: bold; }
#logmsg dd { margin: 0; padding: 0 0 0.5em 0; }
#logmsg dd:before { content:'\00bb';}
#logmsg table { border-spacing: 0px; border-collapse: collapse; border-top: 4px solid #fa0; border-bottom: 1px solid #fa0; background: #fff; }
#logmsg table th { text-align: left; font-weight: normal; padding: 0.2em 0.5em; border-top: 1px dotted #fa0; }
#logmsg table td { text-align: right; border-top: 1px dotted #fa0; padding: 0.2em 0.5em; }
#logmsg table thead th { text-align: center; border-bottom: 1px solid #fa0; }
#logmsg table th.Corner { text-align: left; }
#logmsg hr { border: none 0; border-top: 2px dashed #fa0; height: 1px; }
#header, #footer { color: #fff; background: #636; border: 1px #300 solid; padding: 6px; }
#patch { width: 100%; }
#patch h4 {font-family: verdana,arial,helvetica,sans-serif;font-size:10pt;padding:8px;background:#369;color:#fff;margin:0;}
#patch .propset h4, #patch .binary h4 {margin:0;}
#patch pre {padding:0;line-height:1.2em;margin:0;}
#patch .diff {width:100%;background:#eee;padding: 0 0 10px 0;overflow:auto;}
#patch .propset .diff, #patch .binary .diff  {padding:10px 0;}
#patch span {display:block;padding:0 10px;}
#patch .modfile, #patch .addfile, #patch .delfile, #patch .propset, #patch .binary, #patch .copfile {border:1px solid #ccc;margin:10px 0;}
#patch ins {background:#dfd;text-decoration:none;display:block;padding:0 10px;}
#patch del {background:#fdd;text-decoration:none;display:block;padding:0 10px;}
#patch .lines, .info {color:#888;background:#fff;}
--></style>
<div id="msg">
<dl class="meta">
<dt>Revision</dt> <dd><a href="http://trac.webkit.org/projects/webkit/changeset/81950">81950</a></dd>
<dt>Author</dt> <dd>commit-queue@webkit.org</dd>
<dt>Date</dt> <dd>2011-03-25 02:19:55 -0700 (Fri, 25 Mar 2011)</dd>
</dl>

<h3>Log Message</h3>
<pre>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:</pre>

<h3>Modified Paths</h3>
<ul>
<li><a href="#trunkSourceWebCoreChangeLog">trunk/Source/WebCore/ChangeLog</a></li>
<li><a href="#trunkSourceWebCoresvgSVGUseElementcpp">trunk/Source/WebCore/svg/SVGUseElement.cpp</a></li>
<li><a href="#trunkSourceWebCoresvgSVGUseElementh">trunk/Source/WebCore/svg/SVGUseElement.h</a></li>
</ul>

</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkSourceWebCoreChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/ChangeLog (81949 => 81950)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/ChangeLog   2011-03-25 09:19:22 UTC (rev 81949)
+++ trunk/Source/WebCore/ChangeLog      2011-03-25 09:19:55 UTC (rev 81950)
</span><span class="lines">@@ -1,3 +1,36 @@
</span><ins>+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:
+
</ins><span class="cx"> 2011-03-25  Dominic Cooney  <dominicc@google.com>
</span><span class="cx"> 
</span><span class="cx">         Reviewed by Kent Tamura.
</span></span></pre></div>
<a id="trunkSourceWebCoresvgSVGUseElementcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/svg/SVGUseElement.cpp (81949 => 81950)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/svg/SVGUseElement.cpp       2011-03-25 09:19:22 UTC (rev 81949)
+++ trunk/Source/WebCore/svg/SVGUseElement.cpp  2011-03-25 09:19:55 UTC (rev 81950)
</span><span class="lines">@@ -568,11 +568,11 @@
</span><span class="cx"> #if ENABLE(SVG) && ENABLE(SVG_USE)
</span><span class="cx">     // Expand all <use> elements in the shadow tree.
</span><span class="cx">     // Expand means: replace the actual <use> element by what it references.
</span><del>-    expandUseElementsInShadowTree(shadowRoot, shadowRoot);
</del><ins>+    expandUseElementsInShadowTree(shadowRoot);
</ins><span class="cx"> 
</span><span class="cx">     // Expand all <symbol> elements in the shadow tree.
</span><span class="cx">     // Expand means: replace the actual <symbol> element by the <svg> element.
</span><del>-    expandSymbolElementsInShadowTree(shadowRoot, shadowRoot);
</del><ins>+    expandSymbolElementsInShadowTree(shadowRoot);
</ins><span class="cx"> #endif
</span><span class="cx"> 
</span><span class="cx">     // Now that the shadow tree is completly expanded, we can associate
</span><span class="lines">@@ -821,7 +821,7 @@
</span><span class="cx"> }
</span><span class="cx"> 
</span><span class="cx"> #if ENABLE(SVG) && ENABLE(SVG_USE)
</span><del>-void SVGUseElement::expandUseElementsInShadowTree(SVGShadowTreeRootElement* shadowRoot, Node* element)
</del><ins>+void SVGUseElement::expandUseElementsInShadowTree(Node* element)
</ins><span class="cx"> {
</span><span class="cx">     // Why expand the <use> elements in the shadow tree here, and not just
</span><span class="cx">     // do this directly in buildShadowTree, if we encounter a <use> element?
</span><span class="lines">@@ -869,21 +869,25 @@
</span><span class="cx">         if (subtreeContainsDisallowedElement(cloneParent.get()))
</span><span class="cx">             removeDisallowedElementsFromSubtree(cloneParent.get());
</span><span class="cx"> 
</span><ins>+        RefPtr<Node> replacingElement(cloneParent.get());
+
</ins><span class="cx">         // Replace <use> with referenced content.
</span><span class="cx">         ASSERT(use->parentNode()); 
</span><span class="cx">         use->parentNode()->replaceChild(cloneParent.release(), use, ec);
</span><span class="cx">         ASSERT(!ec);
</span><span class="cx"> 
</span><del>-        // Immediately stop here, and restart expanding.
-        expandUseElementsInShadowTree(shadowRoot, shadowRoot);
-        return;
</del><ins>+        // 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());
</ins><span class="cx">     }
</span><span class="cx"> 
</span><span class="cx">     for (RefPtr<Node> child = element->firstChild(); child; child = child->nextSibling())
</span><del>-        expandUseElementsInShadowTree(shadowRoot, child.get());
</del><ins>+        expandUseElementsInShadowTree(child.get());
</ins><span class="cx"> }
</span><span class="cx"> 
</span><del>-void SVGUseElement::expandSymbolElementsInShadowTree(SVGShadowTreeRootElement* shadowRoot, Node* element)
</del><ins>+void SVGUseElement::expandSymbolElementsInShadowTree(Node* element)
</ins><span class="cx"> {
</span><span class="cx">     if (element->hasTagName(SVGNames::symbolTag)) {
</span><span class="cx">         // Spec: The referenced 'symbol' and its contents are deep-cloned into the generated tree,
</span><span class="lines">@@ -913,18 +917,22 @@
</span><span class="cx">         if (subtreeContainsDisallowedElement(svgElement.get()))
</span><span class="cx">             removeDisallowedElementsFromSubtree(svgElement.get());
</span><span class="cx"> 
</span><ins>+        RefPtr<Node> replacingElement(svgElement.get());
+
</ins><span class="cx">         // Replace <symbol> with <svg>.
</span><span class="cx">         ASSERT(element->parentNode()); 
</span><span class="cx">         element->parentNode()->replaceChild(svgElement.release(), element, ec);
</span><span class="cx">         ASSERT(!ec);
</span><span class="cx"> 
</span><del>-        // Immediately stop here, and restart expanding.
-        expandSymbolElementsInShadowTree(shadowRoot, shadowRoot);
-        return;
</del><ins>+        // 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());
</ins><span class="cx">     }
</span><span class="cx"> 
</span><span class="cx">     for (RefPtr<Node> child = element->firstChild(); child; child = child->nextSibling())
</span><del>-        expandSymbolElementsInShadowTree(shadowRoot, child.get());
</del><ins>+        expandSymbolElementsInShadowTree(child.get());
</ins><span class="cx"> }
</span><span class="cx"> 
</span><span class="cx"> #endif
</span></span></pre></div>
<a id="trunkSourceWebCoresvgSVGUseElementh"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/svg/SVGUseElement.h (81949 => 81950)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/svg/SVGUseElement.h 2011-03-25 09:19:22 UTC (rev 81949)
+++ trunk/Source/WebCore/svg/SVGUseElement.h    2011-03-25 09:19:55 UTC (rev 81950)
</span><span class="lines">@@ -91,8 +91,8 @@
</span><span class="cx">     void buildShadowTree(SVGShadowTreeRootElement*, SVGElement* target, SVGElementInstance* targetInstance);
</span><span class="cx"> 
</span><span class="cx"> #if ENABLE(SVG) && ENABLE(SVG_USE)
</span><del>-    void expandUseElementsInShadowTree(SVGShadowTreeRootElement*, Node* element);
-    void expandSymbolElementsInShadowTree(SVGShadowTreeRootElement*, Node* element);
</del><ins>+    void expandUseElementsInShadowTree(Node* element);
+    void expandSymbolElementsInShadowTree(Node* element);
</ins><span class="cx"> #endif
</span><span class="cx"> 
</span><span class="cx">     // "Tree connector" 
</span></span></pre>
</div>
</div>

</body>
</html>