Bug 13432

Summary:

determineSpacingForFlowBoxes is O(n^2)

Product:

WebKit

Reporter:

Dave Hyatt <hyatt>

Component:

Layout and Rendering

Assignee:

Dave Hyatt <hyatt>

Status:

RESOLVED FIXED

Severity:

Normal

CC:

mitz

Priority:

Version:

523.x (Safari 3)

Hardware:

Mac

OS:

OS X 10.4

Bug Depends on:

Bug Blocks:

13351

Attachments:

Description	Flags
Avoid edge testing if there's no need.	mitz: review-
Add a cache for nextOnLine/prevOnLine existence	hyatt: review+

Dave Hyatt

Reported 2007-04-21 03:56:29 PDT

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.

Attachments
Avoid edge testing if there's no need. (4.76 KB, patch) 2007-04-21 05:18 PDT, Dave Hyatt	mitz: review-	Details Formatted Diff Diff
Add a cache for nextOnLine/prevOnLine existence (2.29 KB, patch) 2007-04-21 14:54 PDT, Dave Hyatt	hyatt: review+	Details Formatted Diff Diff
Show Obsolete (1) View All Add attachment proposed patch, testcase, etc.

Dave Hyatt

Comment 1 2007-04-21 05:18:34 PDT

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

mitz

Comment 2 2007-04-21 05:34:16 PDT

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.

mitz

Comment 3 2007-04-21 05:38:21 PDT

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.

mitz

Comment 4 2007-04-21 05:40:03 PDT

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

mitz

Comment 5 2007-04-21 05:59:56 PDT

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

Comment 6 2007-04-21 14:23:03 PDT

Yeah, good point. I forgot about negative margins.

Dave Hyatt

Comment 7 2007-04-21 14:23:30 PDT

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

Dave Hyatt

Comment 8 2007-04-21 14:41:54 PDT

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

Comment 9 2007-04-21 14:54:54 PDT

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 10 2007-04-21 14:59:35 PDT

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

Adam Roben (:aroben)

Comment 11 2007-04-21 15:00:29 PDT

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 12 2007-04-21 15:31:24 PDT

Comment on attachment 14126 [details] Add a cache for nextOnLine/prevOnLine existence Fails some layout tests. Investigating.

Dave Hyatt

Comment 13 2007-04-21 15:41:16 PDT

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

Comment 14 2007-04-21 15:50:44 PDT

Fixed.

Note You need to log in before you can comment on or make changes to this bug.