Bug 13432 - determineSpacingForFlowBoxes is O(n^2)
Summary: determineSpacingForFlowBoxes is O(n^2)
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: Layout and Rendering (show other bugs)
Version: 523.x (Safari 3)
Hardware: Mac OS X 10.4
: P2 Normal
Assignee: Dave Hyatt
URL:
Keywords:
Depends on:
Blocks: 13351
  Show dependency treegraph
 
Reported: 2007-04-21 03:56 PDT by Dave Hyatt
Modified: 2007-04-21 15:50 PDT (History)
1 user (show)

See Also:


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

Note You need to log in before you can comment on or make changes to this bug.
Description Dave Hyatt 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.
Comment 1 Dave Hyatt 2007-04-21 05:18:34 PDT
Created attachment 14121 [details]
Avoid edge testing if there's no need.
Comment 2 mitz 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.
Comment 3 mitz 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.
Comment 4 mitz 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.
Comment 5 mitz 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.
Comment 6 Dave Hyatt 2007-04-21 14:23:03 PDT
Yeah, good point.  I forgot about negative margins.
Comment 7 Dave Hyatt 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.
Comment 8 Dave Hyatt 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.
Comment 9 Dave Hyatt 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.
Comment 10 Adam Roben (:aroben) 2007-04-21 14:59:35 PDT
Comment on attachment 14126 [details]
Add a cache for nextOnLine/prevOnLine existence

r=me
Comment 11 Adam Roben (:aroben) 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.
Comment 12 Dave Hyatt 2007-04-21 15:31:24 PDT
Comment on attachment 14126 [details]
Add a cache for nextOnLine/prevOnLine existence

Fails some layout tests.  Investigating.
Comment 13 Dave Hyatt 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.
Comment 14 Dave Hyatt 2007-04-21 15:50:44 PDT
Fixed.