Bug 52832 – New float positioning is O(k*n^2) for n k-height floats

• Status: ASSIGNED
• Component: Layout and Rendering

<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).

[Dave Hyatt]

Created attachment 86497 [details]
This would help?

[Ahmad Saleem]

@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;

[alan]

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).