|Summary:||New float positioning is O(k*n^2) for n k-height floats|
|Component:||Layout and Rendering||Assignee:||Dave Hyatt <hyatt>|
|Severity:||Normal||CC:||hyatt, joepeck, koivisto, sam, simon.fraser|
|Version:||528+ (Nightly build)|
Description mitz 2011-01-20 12:24:38 PST
<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).