On Tue, Feb 18, 2014 at 1:41 PM, Ryosuke Niwa <rn...@webkit.org> wrote:
> On Tue, Feb 18, 2014 at 7:44 AM, Adam Barth <aba...@webkit.org> wrote: > >> On Sat, Feb 15, 2014 at 4:07 PM, Ryosuke Niwa <rn...@webkit.org> wrote: >> >>> Now that we've removed all of the existing shadow DOM implementations >>> from trunk in http://trac.webkit.org/changeset/164131, 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. >>> >>> 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. >>> >> >> 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. >> > > 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. > 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. On Tue, Feb 18, 2014 at 1:54 PM, Maciej Stachowiak <m...@apple.com> wrote: > 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? > 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: https://src.chromium.org/viewvc/blink?revision=158839&view=revision 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. Adam
_______________________________________________ webkit-dev mailing list webkit-dev@lists.webkit.org https://lists.webkit.org/mailman/listinfo/webkit-dev
