[webkit-dev] Web Components development will continue in a branch in near future

[Ryosuke Niwa]

On Tue, Feb 18, 2014 at 5:47 PM, Adam Barth <abarth at webkit.org> wrote:

> On Feb 18, 2014 3:59 PM, "Ryosuke Niwa" <rniwa at webkit.org> wrote:
> >
> > On Tue, Feb 18, 2014 at 3:09 PM, Adam Barth <abarth at webkit.org> wrote:
> >>
> >> On Tue, Feb 18, 2014 at 2:41 PM, Adam Barth <abarth at webkit.org> wrote:
> >>>
> >>> On Tue, Feb 18, 2014 at 1:54 PM, Maciej Stachowiak <mjs at 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.
> >>
> >>
> >> It appears that WebKit still contains some N^2 algorithms in render
> tree construction:
> >>
> >> var t = Date.bra();
>
> >> for (var i = 0; i < 5000; ++i)
> >>   document.body.appendChild(document.createElement('div'));
> >> document.body.offsetTop;
> >> document.body.textContent = Date.now() - t;
> >>
> >> Here's a jsfiddle if you'd like to experiment yourself:
> >>
> >> http://jsfiddle.net/vwG2J/2/
> >>
> >> 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).
> >
> >
> > Thanks for the clarification & info!
> >
> >> 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.
> >
> >
> > 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.
>
> As I wrote above, once we removed the N^2 algorithms in Blink, the shadow
> DOM code dropped off the profile because we called it N times instead of
> N^2 times.  You might have a different experience in your implementation,
> but I wanted to share our experience with this topic.
>
Yes, I understand that I appreciate your information.

However, as I understand the problem, the true cost of shadow DOM code lies
in added branches in inlined functions, bloated binary size, and other
miscellenous things that are hard to measure on ordinary profiling tools.
 It's trivial, for example, to add one or two branches in a hot inline
function and cause more CPU branch prediction misses, or even add a few CPU
instructions in a hot function and trigger a higher rate of op-code cache
misses.

- R. Niwa
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.webkit.org/pipermail/webkit-dev/attachments/20140218/a50a3bd0/attachment.html>