[Webkit-unassigned] [Bug 129065] New: Render tree construction is O(N^2) in number of siblings

[bugzilla-daemon at webkit.org]

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

           Summary: Render tree construction is O(N^2) in number of
                    siblings
           Product: WebKit
           Version: 528+ (Nightly build)
          Platform: Unspecified
               URL: http://jsfiddle.net/vwG2J/2/
        OS/Version: Unspecified
            Status: NEW
          Severity: Normal
          Priority: P2
         Component: Layout and Rendering
        AssignedTo: webkit-unassigned at lists.webkit.org
        ReportedBy: mjs at apple.com


Render tree construction is O(N^2) in the number of sibling nodes.

Here is a test case and JSFiddle link demonstrating the issue; if you create 10x as many nodes, the time growth is approximately quadratic, rather than linear.

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;

http://jsfiddle.net/vwG2J/2/


Blink fixed this by assembling the Render tree (approximately) backwards:
https://codereview.chromium.org/24350009


I am not sure offhand if this is the best or only solution.

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