Bug 52832

Summary: New float positioning is O(k*n^2) for n k-height floats
Product: WebKit Reporter: mitz
Component: Layout and RenderingAssignee: Dave Hyatt <hyatt>
Status: ASSIGNED ---    
Severity: Normal CC: hyatt, joepeck, koivisto, sam, simon.fraser
Priority: P2 Keywords: InRadar
Version: 528+ (Nightly build)   
Hardware: All   
OS: All   
Description Flags
This would help? none

Description mitz 2011-01-20 12:24:38 PST

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).
Comment 1 Dave Hyatt 2011-03-22 13:26:18 PDT
Created attachment 86497 [details]
This would help?