[Webkit-unassigned] [Bug 117489] New: Avoid N^2 walk placing renderers when building the render tree

[bugzilla-daemon at webkit.org]

https://bugs.webkit.org/show_bug.cgi?id=117489

           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, simon.fraser at apple.com,
                    barraclough at apple.com, benjamin at webkit.org,
                    psolanki at apple.com


Consider merging https://chromium.googlesource.com/chromium/blink/+/48a78373952b2bb07675602b8661f3dbbe79ef49

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). 

Using the microbenchmark created for lazy layout,
http://elliottsprehn.com/personal/lazyblock/, this yields a speedup of
nearly 50% (4.75s -> 2.51s).

-- 
Configure bugmail: https://bugs.webkit.org/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are the assignee for the bug.