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: 2014-04-11 14:33 PDT (History)
10 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

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.