Bug 13430 - Block and inline continuations are O(n^2)
: Block and inline continuations are O(n^2)
Status: NEW
Product: WebKit
Classification: Unclassified
Component: Layout and Rendering
: 523.x (Safari 3)
: Macintosh Mac OS X 10.4
: P2 Normal
Assigned To: Dave Hyatt
:
Depends on:
Blocks: 13351
  Show dependency treegraph
 
Reported: 2007-04-21 03:17 PDT by Dave Hyatt
Modified: 2015-03-31 12:15 PDT (History)
11 users (show)

See Also:


Attachments
Work in progress (44.75 KB, patch)
2007-04-21 03:19 PDT, Dave Hyatt
no flags Details | Formatted Diff | Diff
Patch that has been updated to ToT (54.34 KB, patch)
2009-08-19 19:18 PDT, Dave Hyatt
no flags Details | Formatted Diff | Diff
This patch fixes a bunch of bugs in margin collapsing and pref width calculations. (67.96 KB, patch)
2009-08-22 12:33 PDT, Dave Hyatt
no flags Details | Formatted Diff | Diff
This patch gets the position of self-collapsing blocks correct (up to 15 / 65 tests converted and passing) (68.15 KB, patch)
2009-08-22 14:04 PDT, Dave Hyatt
no flags Details | Formatted Diff | Diff
001-031.html now pass. (72.50 KB, patch)
2009-08-22 19:32 PDT, Dave Hyatt
no flags Details | Formatted Diff | Diff
001.html-033.html pass (79.16 KB, patch)
2009-08-22 21:24 PDT, Dave Hyatt
no flags Details | Formatted Diff | Diff
Clean up some layout test failures. No progress on margin-collapsing test suite, but fixed some errors and crashes in other layout tests. (80.71 KB, patch)
2009-08-23 01:06 PDT, Dave Hyatt
no flags Details | Formatted Diff | Diff
Patch updated to ToT (no logical changes, just keeping it merged) (81.30 KB, text/plain)
2010-02-08 12:27 PST, Dave Hyatt
no flags Details
Fix failing ruby layout tests. (81.34 KB, patch)
2010-02-08 13:03 PST, Dave Hyatt
no flags Details | Formatted Diff | Diff
Fix outside list markers. Fix repainting bugs with relpositioned inlines. (118.27 KB, patch)
2010-02-08 23:48 PST, Dave Hyatt
no flags Details | Formatted Diff | Diff
This patch fixes selection painting. (123.19 KB, patch)
2010-02-09 11:40 PST, Dave Hyatt
no flags Details | Formatted Diff | Diff
Fixes to hit testing and selection painting. (137.13 KB, patch)
2010-02-09 15:44 PST, Dave Hyatt
no flags Details | Formatted Diff | Diff
Patch that makes blocks work inside inlines with layers (149.47 KB, patch)
2010-02-10 13:10 PST, Dave Hyatt
no flags Details | Formatted Diff | Diff
Make hit testing work inside layers. Refine painting and hit testing to fix some glitches. (157.11 KB, patch)
2010-02-10 14:33 PST, Dave Hyatt
no flags Details | Formatted Diff | Diff
Smaller patch now that I landed the InlineIterator/BidiRun breakout. (129.37 KB, patch)
2010-02-11 13:22 PST, Dave Hyatt
no flags Details | Formatted Diff | Diff
Fix the line box culling issue and the box height issue. (140.45 KB, patch)
2010-02-11 17:00 PST, Dave Hyatt
no flags Details | Formatted Diff | Diff
Sync to ToT (140.45 KB, patch)
2010-02-12 09:08 PST, Dave Hyatt
no flags Details | Formatted Diff | Diff
Fix the determineStartPosition problem (146.50 KB, patch)
2010-02-15 11:57 PST, Dave Hyatt
no flags Details | Formatted Diff | Diff
Starting to update this to ToT (106.12 KB, patch)
2015-03-11 16:43 PDT, Dave Hyatt
no flags Details | Formatted Diff | Diff
More work to bring patch to ToT (about 75% merged) (129.34 KB, patch)
2015-03-12 11:32 PDT, Dave Hyatt
no flags 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:17:10 PDT
Continuations are too slow, since pathological nesting results in O(n^2) RenderObjects being made (and then our O(n^2) algorithms run on it to create a really horrible performance bottleneck).

They should be phased out in favor of a new approach that uses anonymous inline blocks to enable blocks to live inside inlines.
Comment 1 Dave Hyatt 2007-04-21 03:19:58 PDT
Created attachment 14120 [details]
Work in progress

Here is a first cut that demonstrates the gigantic performance gains.  On the tag nesting PLT, this patch cuts the time from 34 seconds down to 6 seconds.

Open issues abound though:
(1) Margin collapsing has to run on contiguous inline blocks.  This could complicate line layout a fair bit, as it would have to become even more of a hybrid.
(2) Floats need a lot more testing.  There is some concern that certain cases could get slower in DHTML scenarios if floats are present.
(3) Selection is kind of horked.
(4) Many editing tests fail.  Editing's typical fragility makes it unprepared for the use of inline blocks.
Comment 2 Dave Hyatt 2007-04-21 03:22:54 PDT
Another issue is that the line gets descent in strict mode.  This should be pretty easy to fix though.
Comment 3 Dave Hyatt 2009-08-19 19:17:37 PDT
Little test to remind myself of some other issues:

<!doctype html>
<div style="float:left; width:100px;height:100px;background-color:lime"></div>
<span style="border:5px solid red">Hello
<div style="border:1px solid black">world</div>
wow</span>

Paint stacking order is wrong.  The inline block has to pretend to be a block as far as stacking order and painting goes.  This means the float background should paint above the black border of the div block that is inside the inline.

Whitespace needs to be consumed at the end of the line preceding the anonymous inline block.
Comment 4 Dave Hyatt 2009-08-19 19:18:17 PDT
Created attachment 35178 [details]
Patch that has been updated to ToT
Comment 5 Dave Hyatt 2009-08-22 12:33:26 PDT
Created attachment 38435 [details]
This patch fixes a bunch of bugs in margin collapsing and pref width calculations.  

With this patch 001.html in fast/margin-collapsing passes (which is great given how complex the test is).  I'll be working to ensure that all 65 margin collapsing tests pass when every block is wrapped in a span.
Comment 6 Dave Hyatt 2009-08-22 14:04:44 PDT
Created attachment 38437 [details]
This patch gets the position of self-collapsing blocks correct (up to 15 / 65 tests converted and passing)
Comment 7 Dave Hyatt 2009-08-22 19:32:47 PDT
Created attachment 38441 [details]
001-031.html now pass.
Comment 8 Dave Hyatt 2009-08-22 21:24:22 PDT
Created attachment 38442 [details]
001.html-033.html pass

This patch fixes the paint stacking issue, the trailing whitespace issue, and a number of float issues.  It gets basic float positioning working.
Comment 9 Dave Hyatt 2009-08-22 22:12:09 PDT
More notes:

(1) Have to make determineStartPosition work.  This means rerunning as much of margin collapsing as is needed to get the right state for the next child and to have the right state at the top of the block.

(2) Not necessarily something that has to be fixed for landing, but need to teach line layout how to do multiple start/end positions since missing out on clean lines is lame.  If line 2 changes and line 10000 changes, throwing away all the clean lines in between is dumb.

(3) Have to make sure repainting is pretty smart, although this is also not super critical, since continuations don't do well when they split.  We should at least make the common case of appending into the same anonymous inline block work correctly.

(4) Selection painting is not good.

(5) Probably huge layout test failures still in other areas. :)
Comment 10 Dave Hyatt 2009-08-23 01:06:39 PDT
Created attachment 38448 [details]
Clean up some layout test failures.  No progress on margin-collapsing test suite, but fixed some errors and crashes in other layout tests.
Comment 11 Dave Hyatt 2010-02-08 12:27:48 PST
Created attachment 48351 [details]
Patch updated to ToT (no logical changes, just keeping it merged)
Comment 12 Dave Hyatt 2010-02-08 13:03:35 PST
Created attachment 48356 [details]
Fix failing ruby layout tests.
Comment 13 Dave Hyatt 2010-02-08 23:48:29 PST
Created attachment 48394 [details]
Fix outside list markers.  Fix repainting bugs with relpositioned inlines.
Comment 14 Dave Hyatt 2010-02-09 11:40:50 PST
Created attachment 48431 [details]
This patch fixes selection painting.
Comment 15 Dave Hyatt 2010-02-09 11:45:32 PST
Current issues:

(1) Have to make determineStartPosition work.  This means rerunning as much of
margin collapsing as is needed to get the right state for the next child and to
have the right state at the top of the block.

(2) Not necessarily something that has to be fixed for landing, but need to
teach line layout how to do multiple start/end positions since missing out on
clean lines is lame.  If line 2 changes and line 10000 changes, throwing away
all the clean lines in between is dumb.

(3) Have to make sure repainting is pretty smart, although this is also not
super critical, since continuations don't do well when they split.  We should
at least make the common case of appending into the same anonymous inline block
work correctly.

(4) Hit testing doesn't work yet in the margins of anonymous inline blocks.  Need to special case this in the line hit testing code.

(5) Floats will need lots of testing.
Comment 16 Dave Hyatt 2010-02-09 15:44:12 PST
Created attachment 48449 [details]
Fixes to hit testing and selection painting.
Comment 17 Dave Hyatt 2010-02-10 13:10:34 PST
Created attachment 48514 [details]
Patch that makes blocks work inside inlines with layers

And now for something totally awesome:

<span style="position:relative;left:100px; opacity:0.7"><i>Hello <div style="border:5px solid blue">world</div> goodbye</span>

This patch makes the above finally work in WebKit for the first time.  Blocks will now work when nested inside enclosing inlines with layers.

Even better, the inlines that enclose an anonymous inline block are only created if they have a layer or an outline.  Otherwise they don't get made.  This optimization will be applicable even to the normal line box tree eventually (e.g., don't make line boxes that don't paint anything or provide any useful info).
Comment 18 Dave Hyatt 2010-02-10 14:33:56 PST
Created attachment 48515 [details]
Make hit testing work inside layers.  Refine painting and hit testing to fix some glitches.
Comment 19 Dave Hyatt 2010-02-10 15:33:31 PST
Current notes:

(1) Have to make determineStartPosition work.  This means rerunning as much of
margin collapsing as is needed to get the right state for the next child and to
have the right state at the top of the block.

(2) Not necessarily something that has to be fixed for landing, but need to
teach line layout how to do multiple start/end positions since missing out on
clean lines is lame.  If line 2 changes and line 10000 changes, throwing away
all the clean lines in between is dumb.

(3) Have to make sure repainting is pretty smart, although this is also not
super critical, since continuations don't do well when they split.  We should
at least make the common case of appending into the same anonymous inline block
work correctly.

(4) Outline painting is messed up in the non-auto case.

(5) Empty inlines with borders/padding are no longer showing up.  Maybe they are being subsumed by the anonymous inline block line?

(6) Because of the culling of line boxes (in order to avoid O(n^2) behavior), methods on RenderInline like absoluteRects and linesBoundingBox don't know about the inline block lines.  Options are to disable the culling or to taint the RenderInline so that it has to grovel into descendants looking for the anonymous inline blocks.

(7) When line boxes don't get culled, they still need to have the dimensions of the anonymous inline block.  However right now because of height() on InlineFlowBox just returning the font's height, it isn't possible to customize the height of these boxes.  I will probably need to make a special subclass of InlineFlowBox with a height member to deal with this.
Comment 20 Dave Hyatt 2010-02-11 13:22:22 PST
Created attachment 48589 [details]
Smaller patch now that I landed the InlineIterator/BidiRun breakout.
Comment 21 Dave Hyatt 2010-02-11 17:00:05 PST
Created attachment 48597 [details]
Fix the line box culling issue and the box height issue.
Comment 22 Dave Hyatt 2010-02-12 09:08:37 PST
Created attachment 48648 [details]
Sync to ToT
Comment 23 Dave Hyatt 2010-02-15 11:57:16 PST
Created attachment 48766 [details]
Fix the determineStartPosition problem

This patch fixes the determineStartPosition issue and makes sure margin collapsing re-runs like it's supposed to.

The performance issues continue to be pretty complex though.

(1) If only an anonymous inline block is dirty, you end up repainting the whole block plus everything that follows it.

(2) If only an anonymous inline block is dirty, you end up extracting all the lines that follow and then re-attaching them.   This makes layout way more expensive if say images are loading in earlier blocks.

The "cars" pages on the nesting PLT is way way slower, mainly because 50% of the time is spent in attach/extractLine.   So this means determineStartPosition/EndPosition are working, but the problem is content is coming in to early anonymous blocks, causing the extraction/attachment to run over and over on all the later lines for each layout operation.
Comment 24 Oliver Hunt 2011-05-01 19:52:04 PDT
Did this ever get landed?
Comment 25 Dave Hyatt 2012-01-30 11:23:33 PST
Nope.
Comment 26 Eric Seidel 2012-05-14 15:02:34 PDT
I'm interested in this.  I'll see if I can take a whack at it next month.
Comment 27 Elliott Sprehn 2012-07-02 15:36:21 PDT
(In reply to comment #17)
> Created an attachment (id=48514) [details]
> Patch that makes blocks work inside inlines with layers
> 
> And now for something totally awesome:
> 
> <span style="position:relative;left:100px; opacity:0.7"><i>Hello <div style="border:5px solid blue">world</div> goodbye</span>
> 
> This patch makes the above finally work in WebKit for the first time.  Blocks will now work when nested inside enclosing inlines with layers.
> 
> Even better, the inlines that enclose an anonymous inline block are only created if they have a layer or an outline.  Otherwise they don't get made.  This optimization will be applicable even to the normal line box tree eventually (e.g., don't make line boxes that don't paint anything or provide any useful info).

This test renders identically in Firefox and Webkit now, did a fix get landed separately? Are they both wrong?
Comment 28 Dave Hyatt 2014-04-11 13:44:16 PDT
(In reply to comment #27)
> (In reply to comment #17)
> > Created an attachment (id=48514) [details] [details]
> > Patch that makes blocks work inside inlines with layers
> > 
> > And now for something totally awesome:
> > 
> > <span style="position:relative;left:100px; opacity:0.7"><i>Hello <div style="border:5px solid blue">world</div> goodbye</span>
> > 
> > This patch makes the above finally work in WebKit for the first time.  Blocks will now work when nested inside enclosing inlines with layers.
> > 
> > Even better, the inlines that enclose an anonymous inline block are only created if they have a layer or an outline.  Otherwise they don't get made.  This optimization will be applicable even to the normal line box tree eventually (e.g., don't make line boxes that don't paint anything or provide any useful info).
> 
> This test renders identically in Firefox and Webkit now, did a fix get landed separately? Are they both wrong?

There's a hack that made the positioning part work for continuations, so this is less about correctness now and more about better performance and code simplicity.
Comment 29 Dave Hyatt 2015-03-11 16:43:36 PDT
Created attachment 248464 [details]
Starting to update this to ToT

Just recording this work so I don't lose it. Doesn't compile.
Comment 30 Dave Hyatt 2015-03-12 11:32:03 PDT
Created attachment 248528 [details]
More work to bring patch to ToT (about 75% merged)

Does not compile.

One big new issue that will have to be dealt with is pagination. We're going to have to make sure that the anonymous inline-block line is not treated as unsplittable, and that pagination really will drill down into it and never move the line.
Comment 31 Dave Hyatt 2015-03-12 11:41:54 PDT
Recording thoughts:

We should add a special mode to line layout that can lay out anonymous inline blocks and not make them contribute to the repaint rect or to line dirtying. 

What we'd like to do is, as long as we hit anonymous inline blocks first when looking for dirty lines, try to lay it out and see if it moves.

If the anonymous inline block does not move or change size and does not have any overhanging floats, then we simply undirty the line and keep going.

If the anonymous inline block does move or change size but does not have overhanging floats, then we can move the lines that follow without extraction.

Another big thing to think about is pagination. Pagination came online after the 2010 patch. We have to make sure to drill into anonymous inline blocks and paginate them, and our line is irrelevant for pagination and should just be allowed to sit where it wants.

Pagination struts may need to be handled for contiguous inline blocks.

The dirty line optimizations mentioned above may need to turn off when pagination is involved.
Comment 32 WebKit Commit Bot 2015-03-12 11:51:11 PDT
Attachment 248528 [details] did not pass style-queue:


ERROR: Source/WebCore/rendering/InlineFlowBox.cpp:1136:  Weird number of spaces at line-start.  Are you using a 4-space indent?  [whitespace/indent] [3]
ERROR: Source/WebCore/accessibility/AccessibilityRenderObject.cpp:339:  This { should be at the end of the previous line  [whitespace/braces] [4]
ERROR: Source/WebCore/rendering/InlineElementBox.cpp:70:  Weird number of spaces at line-start.  Are you using a 4-space indent?  [whitespace/indent] [3]
ERROR: Source/WebCore/rendering/InlineElementBox.cpp:76:  Weird number of spaces at line-start.  Are you using a 4-space indent?  [whitespace/indent] [3]
ERROR: Source/WebCore/rendering/InlineElementBox.cpp:121:  Weird number of spaces at line-start.  Are you using a 4-space indent?  [whitespace/indent] [3]
ERROR: Source/WebCore/rendering/RenderInline.h:171:  Weird number of spaces at line-start.  Are you using a 4-space indent?  [whitespace/indent] [3]
ERROR: Source/WebCore/rendering/RenderBlock.cpp:2654:  Tests for true/false, null/non-null, and zero/non-zero should all be done without equality comparisons.  [readability/comparison_to_zero] [5]
ERROR: Source/WebCore/rendering/RenderBlock.cpp:3190:  Weird number of spaces at line-start.  Are you using a 4-space indent?  [whitespace/indent] [3]
ERROR: Source/WebCore/rendering/RenderBlock.cpp:3428:  Weird number of spaces at line-start.  Are you using a 4-space indent?  [whitespace/indent] [3]
ERROR: Source/WebCore/rendering/InlineBox.h:38:  This { should be at the end of the previous line  [whitespace/braces] [4]
ERROR: Source/WebCore/rendering/InlineBox.h:40:  Missing spaces around :  [whitespace/init] [4]
ERROR: Source/WebCore/rendering/InlineBox.h:40:  Wrong number of spaces before statement. (expected: 8)  [whitespace/indent] [4]
ERROR: Source/WebCore/rendering/InlineBox.h:42:  Weird number of spaces at line-start.  Are you using a 4-space indent?  [whitespace/indent] [3]
ERROR: Source/WebCore/rendering/InlineBox.h:47:  This { should be at the end of the previous line  [whitespace/braces] [4]
ERROR: Source/WebCore/rendering/InlineBox.h:49:  Missing spaces around :  [whitespace/init] [4]
ERROR: Source/WebCore/rendering/InlineBox.h:49:  Wrong number of spaces before statement. (expected: 8)  [whitespace/indent] [4]
ERROR: Source/WebCore/rendering/InlineBox.h:54:  Weird number of spaces at line-start.  Are you using a 4-space indent?  [whitespace/indent] [3]
ERROR: Source/WebCore/rendering/RenderBlockLineLayout.cpp:1023:  Should have only a single space after a punctuation in a comment.  [whitespace/comments] [5]
ERROR: Source/WebCore/rendering/RenderBlockLineLayout.cpp:1078:  Weird number of spaces at line-start.  Are you using a 4-space indent?  [whitespace/indent] [3]
ERROR: Source/WebCore/rendering/RenderBlockLineLayout.cpp:1566:  Should have only a single space after a punctuation in a comment.  [whitespace/comments] [5]
ERROR: Source/WebCore/rendering/RenderBlockLineLayout.cpp:1575:  Weird number of spaces at line-start.  Are you using a 4-space indent?  [whitespace/indent] [3]
ERROR: Source/WebCore/rendering/RenderBlockLineLayout.cpp:2080:  Should have only a single space after a punctuation in a comment.  [whitespace/comments] [5]
ERROR: Source/WebCore/rendering/RenderBlockLineLayout.cpp:2095:  Weird number of spaces at line-start.  Are you using a 4-space indent?  [whitespace/indent] [3]
ERROR: Source/WebCore/rendering/RenderBlockLineLayout.cpp:2099:  Weird number of spaces at line-start.  Are you using a 4-space indent?  [whitespace/indent] [3]
ERROR: Source/WebCore/rendering/RenderBlockLineLayout.cpp:2103:  More than one command on the same line in for  [whitespace/parens] [4]
ERROR: Source/WebCore/rendering/RenderBlockLineLayout.cpp:2104:  Weird number of spaces at line-start.  Are you using a 4-space indent?  [whitespace/indent] [3]
ERROR: Source/WebCore/rendering/RenderBlockLineLayout.cpp:2107:  Weird number of spaces at line-start.  Are you using a 4-space indent?  [whitespace/indent] [3]
ERROR: Source/WebCore/rendering/RenderBlockLineLayout.cpp:2112:  Weird number of spaces at line-start.  Are you using a 4-space indent?  [whitespace/indent] [3]
ERROR: Source/WebCore/rendering/InlineBox.cpp:29:  Alphabetical sorting problem.  [build/include_order] [4]
ERROR: Source/WebCore/rendering/RenderBlockFlow.cpp:2747:  Weird number of spaces at line-start.  Are you using a 4-space indent?  [whitespace/indent] [3]
ERROR: Source/WebCore/rendering/RenderBlockFlow.cpp:3103:  Boolean expressions that span multiple lines should have their operators on the left side of the line instead of the right side.  [whitespace/operators] [4]
ERROR: Source/WebCore/rendering/RenderBlockFlow.cpp:3103:  Multi line control clauses should use braces.  [whitespace/braces] [4]
ERROR: Source/WebCore/rendering/RenderBlockFlow.cpp:3372:  Boolean expressions that span multiple lines should have their operators on the left side of the line instead of the right side.  [whitespace/operators] [4]
ERROR: Source/WebCore/rendering/RenderBlockFlow.cpp:3372:  Multi line control clauses should use braces.  [whitespace/braces] [4]
ERROR: Source/WebCore/rendering/RenderBlockFlow.cpp:3377:  Weird number of spaces at line-start.  Are you using a 4-space indent?  [whitespace/indent] [3]
ERROR: Source/WebCore/rendering/InlineFlowBox.h:357:  This { should be at the end of the previous line  [whitespace/braces] [4]
ERROR: Source/WebCore/rendering/InlineFlowBox.h:360:  Wrong number of spaces before statement. (expected: 8)  [whitespace/indent] [4]
ERROR: Source/WebCore/rendering/RenderBlock.h:474:  Weird number of spaces at line-start.  Are you using a 4-space indent?  [whitespace/indent] [3]
ERROR: Source/WebCore/rendering/RootInlineBox.h:240:  This { should be at the end of the previous line  [whitespace/braces] [4]
ERROR: Source/WebCore/rendering/RootInlineBox.h:243:  Wrong number of spaces before statement. (expected: 8)  [whitespace/indent] [4]
ERROR: Source/WebCore/rendering/RootInlineBox.h:244:  Wrong number of spaces before statement. (expected: 8)  [whitespace/indent] [4]
ERROR: Source/WebCore/rendering/RootInlineBox.h:257:  Weird number of spaces at line-start.  Are you using a 4-space indent?  [whitespace/indent] [3]
Total errors found: 42 in 29 files


If any of these errors are false positives, please file a bug against check-webkit-style.
Comment 33 Dave Hyatt 2015-03-30 11:04:12 PDT
https://bugs.webkit.org/show_bug.cgi?id=143145 merged in concept of isAnonymousInlineBlock and the addChild code for RenderInline.
Comment 34 Dave Hyatt 2015-03-31 10:44:42 PDT
https://bugs.webkit.org/show_bug.cgi?id=143238 merged the preferred width calculation and the concept of a bit on RootInlineBoxes to know about anonymous inline blocks. Line construction was fixed up to set the bit and avoid intermediate boxes. Line layout was patched to make sure breaks occurred before and after the anonymous inline-block.
Comment 35 Dave Hyatt 2015-03-31 12:15:49 PDT
https://bugs.webkit.org/show_bug.cgi?id=143271 got the width of the inline-block correct.