<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On Tue, Feb 18, 2014 at 1:41 PM, Ryosuke Niwa <span dir="ltr"><<a href="mailto:rniwa@webkit.org" target="_blank">rniwa@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>On Tue, Feb 18, 2014 at 7:44 AM, Adam Barth <span dir="ltr"><<a href="mailto:abarth@webkit.org" target="_blank">abarth@webkit.org</a>></span> wrote:</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 dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><div>On Sat, Feb 15, 2014 at 4:07 PM, Ryosuke Niwa <span dir="ltr"><<a href="mailto:rniwa@webkit.org" target="_blank">rniwa@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>Now that we've removed all of the existing shadow DOM implementations from trunk in <a href="http://trac.webkit.org/changeset/164131" target="_blank">http://trac.webkit.org/changeset/164131</a>, I'm intending to work on new web components implementations in a branch based on the feedback Apple has given on public-webapps and www-style in near future, probably starting with custom elements.<br>
</div>
<div><br></div><div>I'd like to implement them in a branch to not inadvertently introduce performance regressions. The old implementation on trunk resulted in 5% overall slowdown in the page load time but we didn't quantify that until we removed the feature entirely last year. That's probably because the feature was added over years as a pile of small changesets each of which introduced immeasurably small performance regressions. Development in a branch allows a faithful performance comparison between the two.</div>
</div></blockquote><div><br></div></div><div>The approach we were successful with in Blink was to restructure how we construct the render tree. At the time Blink branched from WebKit, the algorithm we both used to construct the render tree was N^2. The inner loop of the N^2 algorithm contained more complex DOM traversals due to shadow DOM. When you profile the code, it looks like shadow DOM is expensive, but the bigger win is just to remove the N^2 algorithm, which we've done in Blink. After removing the N^2 algorithm, shadow DOM related code falls off the profile completely.</div>
</div></div></div></blockquote><div><br></div></div><div>Makes sense. I think one big problem with the old implementation was that it started off with a completely different API and feature set and the code had to "evolve" as the spec developed further over years and accumulated design kinks. I'm sure we can avoid introducing O(n^2) algorithms if we started from scratch looking at the latest design.</div>
</div></div></div></blockquote><div><br></div><div></div></div></div><div class="gmail_extra">To clarify: the N^2 algorithms we removed from Blink weren't specific to shadow DOM. We just fixed render tree construction in general not to be N^2.</div>
<div class="gmail_extra"><br><div class="gmail_quote">On Tue, Feb 18, 2014 at 1:54 PM, Maciej Stachowiak <span dir="ltr"><<a href="mailto:mjs@apple.com" target="_blank">mjs@apple.com</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 style="word-wrap:break-word"><div><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></div></blockquote><div><br></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">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 class="gmail_extra">
<br></div><div class="gmail_extra">Adam</div><div class="gmail_extra"><br></div></div>