[Webkit-unassigned] [Bug 119114] New: Avoid N^2 walk placing renderers when building the render tree
bugzilla-daemon at webkit.org
bugzilla-daemon at webkit.org
Thu Jul 25 17:06:01 PDT 2013
https://bugs.webkit.org/show_bug.cgi?id=119114
Summary: Avoid N^2 walk placing renderers when building the
render tree
Product: WebKit
Version: 528+ (Nightly build)
Platform: Unspecified
OS/Version: Unspecified
Status: NEW
Keywords: BlinkMergeCandidate
Severity: Normal
Priority: P2
Component: Layout and Rendering
AssignedTo: webkit-unassigned at lists.webkit.org
ReportedBy: rniwa at webkit.org
CC: hyatt at apple.com, koivisto at iki.fi,
simon.fraser at apple.com, akling at apple.com,
leviw at chromium.org
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.
--
Configure bugmail: https://bugs.webkit.org/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are the assignee for the bug.
More information about the webkit-unassigned
mailing list