On Tue, Feb 18, 2014 at 2:41 PM, Adam Barth <aba...@webkit.org> wrote:
> 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. > It appears that WebKit still contains some N^2 algorithms in render tree construction: var t = Date.now(); 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). 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. Adam
_______________________________________________ webkit-dev mailing list webkit-dev@lists.webkit.org https://lists.webkit.org/mailman/listinfo/webkit-dev
