52832 2011-01-20 12:24:38 -0800 New float positioning is O(k*n^2) for n k-height floats 2023-09-28 07:05:35 -0700 1 1 1 Unclassified WebKit Layout and Rendering 528+ (Nightly build) All All ASSIGNED InRadar P2 Normal --- 1 mitz hyatt ahmad.saleem792 hyatt joepeck koivisto sam simon.fraser zalan oldest_to_newest 337502 0 mitz 2011-01-20 12:24:38 -0800 <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). 371588 1 86497 hyatt 2011-03-22 13:26:18 -0700 Created attachment 86497 This would help? 1980696 2 ahmad.saleem792 2023-09-27 16:03:56 -0700 @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; 1980950 3 zalan 2023-09-28 07:05:35 -0700 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). 86497 2011-03-22 13:26:18 -0700 2011-03-22 13:26:18 -0700 This would help? patch.txt text/plain 1389 hyatt SW5kZXg6IFNvdXJjZS9XZWJDb3JlL3JlbmRlcmluZy9SZW5kZXJCbG9jay5jcHAKPT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09 PQotLS0gU291cmNlL1dlYkNvcmUvcmVuZGVyaW5nL1JlbmRlckJsb2NrLmNwcAkocmV2aXNpb24g ODE2OTEpCisrKyBTb3VyY2UvV2ViQ29yZS9yZW5kZXJpbmcvUmVuZGVyQmxvY2suY3BwCSh3b3Jr aW5nIGNvcHkpCkBAIC0zMjE4LDcgKzMyMTgsNyBAQCBib29sIFJlbmRlckJsb2NrOjpwb3NpdGlv bk5ld0Zsb2F0cygpCiAgICAgICAgIGludCBmbG9hdExvZ2ljYWxMZWZ0OwogICAgICAgICBpZiAo Y2hpbGRCb3gtPnN0eWxlKCktPmZsb2F0aW5nKCkgPT0gRkxFRlQpIHsKICAgICAgICAgICAgIGlu dCBoZWlnaHRSZW1haW5pbmdMZWZ0ID0gMTsKLSAgICAgICAgICAgIGludCBoZWlnaHRSZW1haW5p bmdSaWdodCA9IDE7CisgICAgICAgICAgICBpbnQgaGVpZ2h0UmVtYWluaW5nUmlnaHQgPSBJTlRf TUFYOwogICAgICAgICAgICAgZmxvYXRMb2dpY2FsTGVmdCA9IGxvZ2ljYWxMZWZ0T2Zmc2V0Rm9y TGluZShsb2dpY2FsVG9wLCBsZWZ0T2Zmc2V0LCBmYWxzZSwgJmhlaWdodFJlbWFpbmluZ0xlZnQp OwogICAgICAgICAgICAgd2hpbGUgKGxvZ2ljYWxSaWdodE9mZnNldEZvckxpbmUobG9naWNhbFRv cCwgcmlnaHRPZmZzZXQsIGZhbHNlLCAmaGVpZ2h0UmVtYWluaW5nUmlnaHQpIC0gZmxvYXRMb2dp Y2FsTGVmdCA8IGZsb2F0TG9naWNhbFdpZHRoKSB7CiAgICAgICAgICAgICAgICAgbG9naWNhbFRv cCArPSBtaW4oaGVpZ2h0UmVtYWluaW5nTGVmdCwgaGVpZ2h0UmVtYWluaW5nUmlnaHQpOwpAQCAt MzIyNiw3ICszMjI2LDcgQEAgYm9vbCBSZW5kZXJCbG9jazo6cG9zaXRpb25OZXdGbG9hdHMoKQog ICAgICAgICAgICAgfQogICAgICAgICAgICAgZmxvYXRMb2dpY2FsTGVmdCA9IG1heCgwLCBmbG9h dExvZ2ljYWxMZWZ0KTsKICAgICAgICAgfSBlbHNlIHsKLSAgICAgICAgICAgIGludCBoZWlnaHRS ZW1haW5pbmdMZWZ0ID0gMTsKKyAgICAgICAgICAgIGludCBoZWlnaHRSZW1haW5pbmdMZWZ0ID0g SU5UX01BWDsKICAgICAgICAgICAgIGludCBoZWlnaHRSZW1haW5pbmdSaWdodCA9IDE7CiAgICAg ICAgICAgICBmbG9hdExvZ2ljYWxMZWZ0ID0gbG9naWNhbFJpZ2h0T2Zmc2V0Rm9yTGluZShsb2dp Y2FsVG9wLCByaWdodE9mZnNldCwgZmFsc2UsICZoZWlnaHRSZW1haW5pbmdSaWdodCk7CiAgICAg ICAgICAgICB3aGlsZSAoZmxvYXRMb2dpY2FsTGVmdCAtIGxvZ2ljYWxMZWZ0T2Zmc2V0Rm9yTGlu ZShsb2dpY2FsVG9wLCBsZWZ0T2Zmc2V0LCBmYWxzZSwgJmhlaWdodFJlbWFpbmluZ0xlZnQpIDwg ZmxvYXRMb2dpY2FsV2lkdGgpIHsK