On Feb 18, 2014, at 2:32 PM, Bem Jones-Bey <bjone...@adobe.com> wrote:
>> Thanks, Adam. We hope that we will be successful implementing shadow DOM as >> well. >> >> 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? > > > I think it may be: https://codereview.chromium.org/24350009 Thanks for the pointer, Bem! On Feb 18, 2014, at 3:09 PM, Adam Barth <aba...@webkit.org> wrote: > 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). Thanks for the test case, Adam! Filed as: <https://bugs.webkit.org/show_bug.cgi?id=129065>. I think it's a fair point that we should evaluate performance impact of our Shadow DOM implementation in a context that has this bug fixed (and other related issues if we can find them), to get a fair comparison. I also think it is sensible to use a branch (as Ryosuke suggested). Regards, Maciej
_______________________________________________ webkit-dev mailing list webkit-dev@lists.webkit.org https://lists.webkit.org/mailman/listinfo/webkit-dev
