On Feb 18, 2014, at 3:59 PM, Ryosuke Niwa <rn...@webkit.org> wrote: > On Tue, Feb 18, 2014 at 3:09 PM, Adam Barth <aba...@webkit.org> wrote: > 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). > > 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. > > JSC team has been utilizing SVN branches to work on Concurrent JIT, > Generational GC, FTL, etc... to quantity the total performance cost and > benefit of each feature, and it has been working very well as far as I could > tell.
I think this strategy has worked well for us. Branches make it easier to embark on risky projects. Also, it's great to be able to see the total impact of a feature. I can appreciate Adam's great theories about asymptotic complexity, but I think that in practice any major change to the system will have some impact and it's good to know what it is. -Filip > > - R. Niwa > > _______________________________________________ > webkit-dev mailing list > webkit-dev@lists.webkit.org > https://lists.webkit.org/mailman/listinfo/webkit-dev
_______________________________________________ webkit-dev mailing list webkit-dev@lists.webkit.org https://lists.webkit.org/mailman/listinfo/webkit-dev
