<html><head><meta http-equiv="Content-Type" content="text/html charset=iso-8859-1"></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 3:59 PM, Ryosuke Niwa <<a href="mailto:rniwa@webkit.org">rniwa@webkit.org</a>> wrote:</div><br class="Apple-interchange-newline"><blockquote type="cite"><div dir="ltr">On Tue, Feb 18, 2014 at 3:09 PM, Adam Barth <span dir="ltr"><<a href="mailto:abarth@webkit.org" target="_blank">abarth@webkit.org</a>></span> wrote:<br><div class="gmail_extra"><div class="gmail_quote">
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="ltr"><div class=""><div class="gmail_extra"><div class="gmail_quote">
On Tue, Feb 18, 2014 at 2:41 PM, Adam Barth <span dir="ltr"><<a href="mailto:abarth@webkit.org" target="_blank">abarth@webkit.org</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="ltr"><div><div class="gmail_extra">
<div class="gmail_quote"><span style="color:rgb(34,34,34)">On Tue, Feb 18, 2014 at 1:54 PM, Maciej Stachowiak </span><span dir="ltr" style="color:rgb(34,34,34)"><<a href="mailto:mjs@apple.com" target="_blank">mjs@apple.com</a>></span><span style="color:rgb(34,34,34)"> </span><span style="color:rgb(34,34,34)">wrote:</span><br>
</div></div></div><div class="gmail_extra"><div class="gmail_quote"><div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
<div style="word-wrap:break-word"><div><span style="color:rgb(34,34,34)">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?</span></div>
</div></blockquote><div><br></div></div><div>Removing the N^2 algorithms from render tree construction in Blink was an effort that occurred an extended period of time. As Bem mentioned one of the changes involved was the change below:</div>
<div><br></div><div><a href="https://src.chromium.org/viewvc/blink?revision=158839&view=revision" target="_blank">https://src.chromium.org/viewvc/blink?revision=158839&view=revision</a><br></div></div></div><div class="gmail_extra">
<br></div><div class="gmail_extra">I believe that WebKit has done some similar work recently, but I haven't followed along in enough detail to know whether these N^2 algorithms still exist in WebKit.</div></div></blockquote>
<div><br></div><div></div></div></div></div><div class="gmail_extra">It appears that WebKit still contains some N^2 algorithms in render tree construction:</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/" target="_blank">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><br></div><div>Thanks for the clarification & info!</div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
<div dir="ltr"><div class="gmail_extra"><div>My point is not that Chrome is faster at this particular test case but rather that we were able to resolve the issues that appear to concern Ryosuke about shadow DOM by making general, algorithmic improvements to the engine.</div>
</div></div></blockquote><div><br></div><div>Turning O(n^2) into O(n) algorithms is great but my goal here is to assess the total cost of implementing shadow DOM, not whether we can make compensating performance improvements.<br>
</div><div><br></div><div>JSC team has been utilizing SVN branches to work on Concurrent JIT, Generational GC, FTL, etc... to quantity the total performance cost and benefit of each feature, and it has been working very well as far as I could tell.</div></div></div></div></blockquote><div><br></div><div>I think this strategy has worked well for us. Branches make it easier to embark on risky projects. Also, it's great to be able to see the total impact of a feature.</div><div><br></div><div>I can appreciate Adam's great theories about asymptotic complexity, but I think that in practice any major change to the system will have some impact and it's good to know what it is.</div><div><br></div><div>-Filip</div><div><br></div><br><blockquote type="cite"><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">
<div><br></div><div>- R. Niwa</div><div><br></div></div></div></div>
_______________________________________________<br>webkit-dev mailing list<br><a href="mailto:webkit-dev@lists.webkit.org">webkit-dev@lists.webkit.org</a><br>https://lists.webkit.org/mailman/listinfo/webkit-dev<br></blockquote></div><br></body></html>