119114 2013-07-25 17:05:49 -0700 Avoid N^2 walk placing renderers when building the render tree 2013-11-06 23:09:36 -0800 1 1 1 Unclassified WebKit Layout and Rendering 528+ (Nightly build) Unspecified Unspecified NEW BlinkMergeCandidate P2 Normal --- 1 rniwa webkit-unassigned hyatt kling koivisto leviw simon.fraser oldest_to_newest 911806 0 rniwa 2013-07-25 17:05:49 -0700 Consider merging https://chromium.googlesource.com/chromium/blink/+/51dbeeec81d866ba47a04da2cd2bf7ab200d32f6 or come up with a better fix. Blink resolves style by walking each element from first children to last, but when we go to insert their renderer, we look for the next renderer to insert before. On the initial style resolve, this means we'll walk the entire DOM tree trying to find the right renderer to insert before leading to an N^2 loop over the DOM on load. This could be fixed by changing the semantics by which we insert renderers (insert after instead of insert before). Instead, here I reverse the order we resolve style. This should ensure that in the common case, we'll find the renderer to insert before immediately. While looking at this, I also found we have an N^2 loop for resolving Nth last child selectors, and reversing the style resolve loop would have caused the same issue for Nth child selectors. To fix prevent this regression, I'm piping the child index down to the style resolver in the common case. This ensures both Nth and Nth last should usually be O(1). The previous version of this patch resulted in a perf regression due to the extra in-order loop in Element::recalcStyle. This loop is now gated on the presence of child or sibling selectors. The common case should be faster. 911838 1 rniwa 2013-07-25 19:07:17 -0700 Partially reverted in https://chromium.googlesource.com/chromium/blink/+/6d7c7f5fa9535b5bb52c4d8c407cc078183bd6df. 911839 2 rniwa 2013-07-25 19:21:52 -0700 Fully reverted in https://chromium.googlesource.com/chromium/blink/+/4bab7e7cb5d1001480c42ebad633818b2771b140. 948084 3 rniwa 2013-11-06 23:09:36 -0800 Also see https://src.chromium.org/viewvc/blink?revision=159037&view=revision and https://src.chromium.org/viewvc/blink?revision=159190&view=revision