438509 - Major performance regression on deeply nested tables with height=100%

Status: RESOLVED FIXED

(Core :: Layout: Tables, defect, P2)

Description

[Boris Zbarsky [:bzbarsky]]

This came up in bug 363698, but has nothing to do with that bug.  See bug 363698 comment 29 through bug 363698 comment 32.

I tried some old builds, and loading the page takes under 10 seconds on my slow machine up through the 2007-06-18-01 build.  Builds later than that (starting 2007-06-19-01) take at least a minute (I never bothered to run it to completion).    Given the checkin range:

http://bonsai.mozilla.org/cvsquery.cgi?treeid=default&module=MozillaTinderboxAll&branch=HEAD&branchtype=match&dir=&file=&filetype=match&who=&whotype=match&sortby=Date&hours=2&date=explicit&mindate=2007-06-18+01&maxdate=2007-06-19+01&cvsroot=%2Fcvsroot

I suspect this is a regression from bug 381507.

I profiled in Shark, and it showed that we're just doing very deeply nested table reflow.  The bottom-up profile shows us getting style structs, invalidating, etc.  All very fast operations, so we're doing a _lot_ of them.  Given the changes bug 381507 and that this web page has very deeply nested tables with 100% heights, I bet we're doing two reflow passes at each level, giving a number of passes at the deepest level that grows exponentially with depth.

Comment 1

[Boris Zbarsky [:bzbarsky]]

Attachment: zipped-up testcase

Comment 2

[j.j.]

Attachment: testcase 2

Reduced from the reported file in bug 363698 comment 29.
Loads locally ~3 min in Fx3, 1 sec in Fx2 for me.

Mozilla/5.0 (Windows; U; Windows NT 5.1; de; rv:1.9) Gecko/2008051206 Firefox/3.0

Comment 3

[j.j.]

Attachment: testcase 3

More reduced
Fx 3   ~15 sec
Fx 2    ~0 sec

Comment 4

[Mike Schroepfer]

I'd be in favor of this blocking, not wanted for 1.9.1...

Comment 5

[Florin]

I'm seeing this one with reports generated by MS (SQL Server) Reporting Services with AsyncRendering=True => nested tables. When I have a big report the CPU goes to 100% when scrolling and the scrolling is not smooth.

Comment 6

[Mike Schroepfer]

Given the regression from FF2->FF3 I'm moving this to blocking status - please reset if you disagree

Comment 7

[j.j.]

(In reply to comment #5)
> the CPU goes to 100% when scrolling and the scrolling is not smooth.

This bug is about loading time, not scrolling behaviour.

(Summary changed, added "with height=100%")

Comment 8

[Vincent Vandenschrick]

We are using an AJAX framework that heavily relies on tables (and table nesting) for its components layout. This bug is really a show stopper for us since it makes our applications almost unusable with FF3. +1 for the blocking status.

Comment 9

[Bernd]

Attachment: reflow counts

we reflow the inner tables up to 4096 times

Comment 10

[Bernd]

Comment 1 is exactly to the point we reflow each level with two times so there tables that get 8192 reflows. this is for attement 324846 I only added some padding to get the numbers apart. The display of reflow counts can be triggered by setting the flag in the layout debugger.

Comment 11

[Bernd]

just to make it obvious: I will not work on this in the 1.9.1 time frame. dbaron and dholbert have a understanding how this works, but I do not. And there are more than enough table bugs for me left.

Comment 12

[Daniel Holbert [:dholbert]]

Attachment: testcase 4 (displays load time)

This simplified testcase displays the time that it takes to load.

Here are the results for these builds:
 mozilla-central debug build:       6.47 sec
 mozilla-central nightly build:     1.59 sec
 Firefox 3.0.3 official build:      1.43 sec
 Firefox 2.0.0.17 official build:   0.03 sec

Also: as mentioned in the testcase's source, each successive layer of <table><td> seems to exactly double the load time, for Firefox 3+ builds.

Comment 13

[Bernd]

> seems to exactly double the load time, for Firefox 3+ builds.

thats what comment 10 says.

https://bugzilla.mozilla.org/attachment.cgi?id=268284&action=diff

schedules another resize  reflow before a special  height reflow without checking that the reflow is premature (http://mxr.mozilla.org/mozilla1.8/source/layout/tables/nsTableFrame.cpp#1802) The check got removed but would probably have prevented this.

Comment 14

[Robert O'Callahan (:roc) (email my personal email if necessary)]

dbaron's probably the best person for this.

Comment 15

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Attachment: patch 1: remove a write-only variable

This removes a write-only variable and thus makes the code a little less likely to confuse me.

Comment 16

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Attachment: patch 2: some optimizations that make things fast

I'm not sure that these three optimizations are all valid, but they seemed valid to me when I wrote them.  I haven't run reftests yet; I'll do that shortly.

I wrote them in 1-3-2 order relative to how they appear in the patch.  I was actually expecting to need to do more to fix things in quirks mode because I was expecting that nsHTMLReflowState.:mFlags.mVResize would still be set.in quirks mode because of the percent-height-quirks code in the nsHTMLReflowState constructor.

If this approach doesn't work, the alternative is probably to do the following two things (the second depends on the first):
http://hg.mozilla.org/mozilla-central/annotate/55f801c97764/layout/tables/nsTableFrame.cpp#l1889
http://hg.mozilla.org/mozilla-central/annotate/55f801c97764/layout/tables/nsTableFrame.cpp#l1924
(though the condition for the latter could just be if-not-dirty-or-dirty-children rather than if-in-special-height-reflow)

Comment 17

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

(In reply to comment #16)
> I wrote them in 1-3-2 order relative to how they appear in the patch.  I was
> actually expecting to need to do more to fix things in quirks mode because I
> was expecting that nsHTMLReflowState.:mFlags.mVResize would still be set.in
> quirks mode because of the percent-height-quirks code in the nsHTMLReflowState
> constructor.

... and I also haven't tested that they're all still needed.

Comment 18

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

So, it turns out the write-only variable was actually used, pre-reflow-branch, by a function called nsTableFrame::IsPrematureSpecialHeightReflow, which might actually be another useful optimization here -- except I think it may have actually been testing for whether it was an extra (after-the-needed-one) special height reflow... though actually I think it's close to equivalent to what I did in the optimization patch.

Comment 19

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Well, it caused exactly 2 reftest failures:
!	layout/reftests/bugs/234964-1.html
!	layout/reftests/bugs/234964-2.html

Comment 20

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Attachment: patch 2: some optimizations that make things fast

This weakens one of the three added optimizations, as described, and thus passes reftests.

I still need to add comments describing these better, though...

Comment 21

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Attachment: patch 3: simplify condition, part 1

Comment 22

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Attachment: patch 4: simplify conditions, part 2

Comment 23

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Attachment: patch 4: simplify conditions, part 2

Oops, I meant to keep the || that was outside the () rather than substituting the && that was inside!

Comment 24

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Attachment: combination of patches 2, 3, and 4

Comment 25

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Comment on attachment 348372 [details] [diff] [review]
combination of patches 2, 3, and 4

I'm not sure whether this is going to make more sense as the three separate patches or as this one patch.  I tend to think it makes more sense as three separate patches.  However, I'm requesting reviews on the combined patch to reduce review-request-spam.

This does pass reftests, although I should perhaps try to think up some additional ones to add.

Comment 26

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Comment on attachment 348372 [details] [diff] [review]
combination of patches 2, 3, and 4

Actually, hold a bit on that; I can simplify things further.

Comment 27

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Comment on attachment 348372 [details] [diff] [review]
combination of patches 2, 3, and 4

Actually, no, I don't think I can simplify it further.  I got confused by the second sentence comment in the patch header of patch 4, which isn't actually true.

Comment 28

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Comment on attachment 348367 [details] [diff] [review]
patch 3: simplify condition, part 1

>Simplify condition, part 1, since mVResize already implies IsGeometryDirty.

to be clear, that's true because of the code immediately above (which is then moved by patch 4, whose patch header is in turn partly lying).

Comment 29

[Daniel Holbert [:dholbert]]

/me is looking over the patch...

One initial thing -- to regression-test this, I'd suggest adding a simple check-for-hangs crashtest along the lines of "testcase 4", but with more nesting.  (i.e. with 30 levels of <table height="100%"><td>, which I think would take on the order of 24 hours to load on unpatched optimized builds, based on comment 12)

Comment 30

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Attachment: patch 5: test

Good idea.

Here's a patch for the test as described by dholbert.

Comment 31

[Daniel Holbert [:dholbert]]

Great! Patch & test look good to me.  I can confirm that the crashtest hangs on an unpatched build, and loads quickly on a patched build.

Comment 32

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Fixed in mozilla-central (and thus also on mozilla-1.9.1):
http://hg.mozilla.org/mozilla-central/rev/1f5aa404ea30
http://hg.mozilla.org/mozilla-central/rev/3a8d00537a89
http://hg.mozilla.org/mozilla-central/rev/ede1fa2c79a9
http://hg.mozilla.org/mozilla-central/rev/7a9d1fe1cab5
http://hg.mozilla.org/mozilla-central/rev/356407d18ef3