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
Status: ASSIGNED
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
URL:
Keywords: InRadar
Depends on:
Blocks:
 
Reported: 2011-01-20 12:24 PST by mitz
Modified: 2023-09-28 07:05 PDT (History)
7 users (show)

See Also:

Attachments
This would help? (1.36 KB, patch)
2011-03-22 13:26 PDT, Dave Hyatt 		no flags Details | Formatted Diff | Diff
View All Add an attachment (proposed patch, testcase, etc.)

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 
<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).
Comment 1 Dave Hyatt 2011-03-22 13:26:18 PDT 
Created attachment 86497 [details]
This would help?
Comment 2 Ahmad Saleem 2023-09-27 16:03:56 PDT 
@Alan - is this optimisation still applicable or required?

We don't have it applied:

https://searchfox.org/wubkat/source/Source/WebCore/rendering/RenderBlockFlow.cpp#2721

if (RenderStyle::usedFloat(childBox) == UsedFloat::Left) {
        LayoutUnit heightRemainingLeft = 1_lu;
        LayoutUnit heightRemainingRight = 1_lu;
Comment 3 zalan 2023-09-28 07:05:35 PDT 
This change may not help too much anymore as most of the floats are positioned by LFC's FloatingContext but the bug report may still be valid (for the new float code).