Bug 13432 – determineSpacingForFlowBoxes is O(n^2)

• Status: RESOLVED
• Resolution: FIXED
• Component: Layout and Rendering

[Dave Hyatt]

determineSpacingForFlowBoxes does a bunch of work to try to figure out if the left/right edges should be included for a given inline's line box.  If the inline has no borders, no margins and no padding, then this work is unnecessary and can just be avoided completely.

[Dave Hyatt]

Created attachment 14121 [details]
Avoid edge testing if there's no need.

Comment on attachment 14121 [details]
Avoid edge testing if there's no need.

+        int marginBorderPadding = marginBorderPaddingLeft() + marginBorderPaddingRight();

These guys will always return 0 since includeLeftEdge and includeRightEdge are false when you call them.

Also, their actual values can add up to 0 even if they're not both 0, so I think it's best to check each side separately.

(In reply to comment #2)
> These guys will always return 0 since includeLeftEdge and includeRightEdge are
> false when you call them.
> 

Bah, I overlooked the setEdges() calls before and after.

Comment on attachment 14121 [details]
Avoid edge testing if there's no need.

Actually, even testing each side separately isn't enough. It will fix

<span style="border-left: 5px solid; margin-right: -5px;">foo</span>

which is the example I had in mind for comment #3, but not

<span style="border-left: 5px solid; margin-left: -5px;">foo</span>

I think the setEdges(false, false) is unnecessary.

[Dave Hyatt]

Yeah, good point.  I forgot about negative margins.

[Dave Hyatt]

I think I may explore just making the edge determination faster rather than trying to turn it off completely.

[Dave Hyatt]

A better fix here is to add bits to line boxes that indicate whether nextOnLineExists and prevOnLineExists.  The O(n^2) behavior arises from a lack of caching, since the methods go back up to parents over and over and over again.

This should allow edge computations to still be performed but still be efficient.

[Dave Hyatt]

Created attachment 14126 [details]
Add a cache for nextOnLine/prevOnLine existence

This patch is much better, since it will be fast even when spans do use borders, margins and padding, etc.

[Adam Roben (:aroben)]

Comment on attachment 14126 [details]
Add a cache for nextOnLine/prevOnLine existence

r=me

[Adam Roben (:aroben)]

For future reference, Hyatt has assured me that InlineBoxes are destroyed whenever these cached values would change, so we don't need to worry about recalculating them after the first time.

[Dave Hyatt]

Comment on attachment 14126 [details]
Add a cache for nextOnLine/prevOnLine existence

Fails some layout tests.  Investigating.

[Dave Hyatt]

Comment on attachment 14126 [details]
Add a cache for nextOnLine/prevOnLine existence

AH, no big deal.  Just didn't patch the other InlineBox constructor.

[Dave Hyatt]

Fixed.