[Webkit-unassigned] [Bug 52832] New: New float positioning is O(k*n^2) for n k-height floats

[bugzilla-daemon at webkit.org]

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

           Summary: New float positioning is O(k*n^2) for n k-height
                    floats
           Product: WebKit
           Version: 528+ (Nightly build)
          Platform: All
        OS/Version: All
            Status: NEW
          Keywords: InRadar
          Severity: Normal
          Priority: P2
         Component: Layout and Rendering
        AssignedTo: webkit-unassigned at lists.webkit.org
        ReportedBy: mitz at webkit.org
                CC: hyatt at apple.com, koivisto at iki.fi, joepeck at webkit.org


<rdar://problem/8534202>

Positioning a single new float is pretty bad. It is as bad as O(k*n) where n is the number of already-placed floats and k is the height of the last float. The *RelOffset() is O(n) and the inner while loop in positionNewFloats() can end up calling *RelOffset() up to k times, since strangely if there are no interfering floats on one side, the remainingHeight for that side is set to 1, and so we advance k times. That’s just bizarre. So we end up with positioning n floats being O(k*n^2).

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