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

[Adam Barth]

On Tue, Feb 18, 2014 at 1:41 PM, Ryosuke Niwa <rniwa at webkit.org> wrote:

> On Tue, Feb 18, 2014 at 7:44 AM, Adam Barth <abarth at webkit.org> wrote:
>
>> On Sat, Feb 15, 2014 at 4:07 PM, Ryosuke Niwa <rniwa at 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 <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.

Adam
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.webkit.org/pipermail/webkit-dev/attachments/20140218/8ca13545/attachment.html>