<html><head><meta http-equiv="Content-Type" content="text/html charset=us-ascii"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;"><br><div><div>On Feb 18, 2014, at 2:32 PM, Bem Jones-Bey <<a href="mailto:bjonesbe@adobe.com">bjonesbe@adobe.com</a>> wrote:</div><br class="Apple-interchange-newline"><blockquote type="cite">
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; font-size: 14px; font-family: Calibri, sans-serif;">
<span id="OLK_SRC_BODY_SECTION"><blockquote id="MAC_OUTLOOK_ATTRIBUTION_BLOCKQUOTE" style="BORDER-LEFT: #b5c4df 5 solid; PADDING:0 0 0 5; MARGIN:0 0 0 5;" type="cite"><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;"><div>Thanks, Adam. We hope that we will be successful implementing shadow DOM as well.</div>
<div><br>
</div>
<div>Do you have any more specific pointers that Ryosuke et al could look at for the O(N^2) algorithm? Like a commit range or a function to look at?</div>
</div>
</blockquote>
</span>
<div><br>
</div>
<div>I think it may be: <a href="https://codereview.chromium.org/24350009">https://codereview.chromium.org/24350009</a></div>
</div>
</blockquote></div><br><div>Thanks for the pointer, Bem!</div><div><br></div><div><br></div><div><div>On Feb 18, 2014, at 3:09 PM, Adam Barth <<a href="mailto:abarth@webkit.org">abarth@webkit.org</a>> wrote:</div><br class="Apple-interchange-newline"><blockquote type="cite"><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">It appears that WebKit still contains some N^2 algorithms in render tree construction:</div></div><div class="gmail_extra"><br></div><div class="gmail_extra"><div class="gmail_extra">var t = Date.now();</div><div class="gmail_extra">for (var i = 0; i < 5000; ++i)</div><div class="gmail_extra"> document.body.appendChild(document.createElement('div'));</div><div class="gmail_extra">document.body.offsetTop;</div><div class="gmail_extra">document.body.textContent = Date.now() - t;</div><div><br></div><div><div>Here's a jsfiddle if you'd like to experiment yourself:</div><div><br></div><div><a href="http://jsfiddle.net/vwG2J/2/">http://jsfiddle.net/vwG2J/2/</a></div></div><div><br></div><div>In today's WebKit nightly build, the code above reports a runtime of ~96. If I multiply the loop bound by a factor of ten, the runtime goes up to ~7625, which is a factor of 79.4 (i.e., roughly quadratic). By way of contrast, in today's Chrome canary build, the code above reports a runtime of ~30. If I multiply the loop bound by a factor of ten, the runtime goes up to ~264, which is a factor of 8.8 (i.e., roughly linear).</div></div></div></blockquote></div><div><div dir="ltr"><div class="gmail_extra"><div><br></div><div>Thanks for the test case, Adam!</div><div><br></div><div>Filed as: <<a href="https://bugs.webkit.org/show_bug.cgi?id=129065">https://bugs.webkit.org/show_bug.cgi?id=129065</a>>.</div><div><br></div><div><br></div><div>I think it's a fair point that we should evaluate performance impact of our Shadow DOM implementation in a context that has this bug fixed (and other related issues if we can find them), to get a fair comparison. I also think it is sensible to use a branch (as Ryosuke suggested).</div><div><br></div><div><br></div><div>Regards,</div><div>Maciej</div><div><br></div></div></div></div></body></html>