Bug 13430 - Block and inline continuations are O(n^2)
: Block and inline continuations are O(n^2)
Status: NEW
: WebKit
Layout and Rendering
: 523.x (Safari 3)
: Macintosh Mac OS X 10.4
: P2 Normal
Assigned To:
:
:
:
: 13351
  Show dependency treegraph
 
Reported: 2007-04-21 03:17 PST by
Modified: 2014-04-11 14:33 PST (History)


Attachments
Work in progress (44.75 KB, patch)
2007-04-21 03:19 PST, Dave Hyatt
no flags Review Patch | Details | Formatted Diff | Diff
Patch that has been updated to ToT (54.34 KB, patch)
2009-08-19 19:18 PST, Dave Hyatt
no flags Review Patch | 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 PST, Dave Hyatt
no flags Review Patch | 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 PST, Dave Hyatt
no flags Review Patch | Details | Formatted Diff | Diff
001-031.html now pass. (72.50 KB, patch)
2009-08-22 19:32 PST, Dave Hyatt
no flags Review Patch | Details | Formatted Diff | Diff
001.html-033.html pass (79.16 KB, patch)
2009-08-22 21:24 PST, Dave Hyatt
no flags Review Patch | 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 PST, Dave Hyatt
no flags Review Patch | 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 Review Patch | 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 Review Patch | Details | Formatted Diff | Diff
This patch fixes selection painting. (123.19 KB, patch)
2010-02-09 11:40 PST, Dave Hyatt
no flags Review Patch | 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 Review Patch | 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 Review Patch | 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 Review Patch | 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 Review Patch | 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 Review Patch | Details | Formatted Diff | Diff
Sync to ToT (140.45 KB, patch)
2010-02-12 09:08 PST, Dave Hyatt
no flags Review Patch | Details | Formatted Diff | Diff
Fix the determineStartPosition problem (146.50 KB, patch)
2010-02-15 11:57 PST, Dave Hyatt
no flags Review Patch | Details | Formatted Diff | Diff


Note

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


Description From 2007-04-21 03:17:10 PST
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 From 2007-04-21 03:19:58 PST -------
Created an attachment (id=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 From 2007-04-21 03:22:54 PST -------
Another issue is that the line gets descent in strict mode.  This should be pretty easy to fix though.
------- Comment #3 From 2009-08-19 19:17:37 PST -------
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 From 2009-08-19 19:18:17 PST -------
Created an attachment (id=35178) [details]
Patch that has been updated to ToT
------- Comment #5 From 2009-08-22 12:33:26 PST -------
Created an attachment (id=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 From 2009-08-22 14:04:44 PST -------
Created an attachment (id=38437) [details]
This patch gets the position of self-collapsing blocks correct (up to 15 / 65 tests converted and passing)
------- Comment #7 From 2009-08-22 19:32:47 PST -------
Created an attachment (id=38441) [details]
001-031.html now pass.
------- Comment #8 From 2009-08-22 21:24:22 PST -------
Created an attachment (id=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 From 2009-08-22 22:12:09 PST -------
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 From 2009-08-23 01:06:39 PST -------
Created an attachment (id=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 From 2010-02-08 12:27:48 PST -------
Created an attachment (id=48351) [details]
Patch updated to ToT (no logical changes, just keeping it merged)
------- Comment #12 From 2010-02-08 13:03:35 PST -------
Created an attachment (id=48356) [details]
Fix failing ruby layout tests.
------- Comment #13 From 2010-02-08 23:48:29 PST -------
Created an attachment (id=48394) [details]
Fix outside list markers.  Fix repainting bugs with relpositioned inlines.
------- Comment #14 From 2010-02-09 11:40:50 PST -------
Created an attachment (id=48431) [details]
This patch fixes selection painting.
------- Comment #15 From 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 From 2010-02-09 15:44:12 PST -------
Created an attachment (id=48449) [details]
Fixes to hit testing and selection painting.
------- Comment #17 From 2010-02-10 13:10:34 PST -------
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).
------- Comment #18 From 2010-02-10 14:33:56 PST -------
Created an attachment (id=48515) [details]
Make hit testing work inside layers.  Refine painting and hit testing to fix some glitches.
------- Comment #19 From 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 From 2010-02-11 13:22:22 PST -------
Created an attachment (id=48589) [details]
Smaller patch now that I landed the InlineIterator/BidiRun breakout.
------- Comment #21 From 2010-02-11 17:00:05 PST -------
Created an attachment (id=48597) [details]
Fix the line box culling issue and the box height issue.
------- Comment #22 From 2010-02-12 09:08:37 PST -------
Created an attachment (id=48648) [details]
Sync to ToT
------- Comment #23 From 2010-02-15 11:57:16 PST -------
Created an attachment (id=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 From 2011-05-01 19:52:04 PST -------
Did this ever get landed?
------- Comment #25 From 2012-01-30 11:23:33 PST -------
Nope.
------- Comment #26 From 2012-05-14 15:02:34 PST -------
I'm interested in this.  I'll see if I can take a whack at it next month.
------- Comment #27 From 2012-07-02 15:36:21 PST -------
(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?
------- Comment #28 From 2014-04-11 13:44:16 PST -------
(In reply to comment #27)
> (In reply to comment #17)
> > Created an attachment (id=48514) [details] [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.