Bug 52832 - New float positioning is O(k*n^2) for n k-height floats
Summary: New float positioning is O(k*n^2) for n k-height floats
Alias: None
Product: WebKit
Classification: Unclassified
Component: Layout and Rendering (show other bugs)
Version: 528+ (Nightly build)
Hardware: All All
: P2 Normal
Assignee: Dave Hyatt
Keywords: InRadar
Depends on:
Reported: 2011-01-20 12:24 PST by mitz
Modified: 2011-03-22 13:26 PDT (History)
5 users (show)

See Also:

This would help? (1.36 KB, patch)
2011-03-22 13:26 PDT, Dave Hyatt
no flags Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
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?