Last Comment Bug 438509 - Major performance regression on deeply nested tables with height=100%
: Major performance regression on deeply nested tables with height=100%
Status: RESOLVED FIXED
: fixed1.9.1, perf, regression, testcase
Product: Core
Classification: Components
Component: Layout: Tables (show other bugs)
: Trunk
: All All
: P2 normal with 4 votes (vote)
: mozilla1.9.1b3
Assigned To: David Baron :dbaron: ⌚️UTC-7 (review requests must explain patch)
:
Mentors:
Depends on:
Blocks: 511234 381507
  Show dependency treegraph
 
Reported: 2008-06-10 23:12 PDT by Boris Zbarsky [:bz] (Out June 25-July 6)
Modified: 2009-09-28 09:07 PDT (History)
24 users (show)
mtschrep: blocking1.9.1+
See Also:
Crash Signature:
(edit)
QA Whiteboard:
Iteration: ---
Points: ---
Has Regression Range: ---
Has STR: ---


Attachments
zipped-up testcase (35.31 KB, application/zip)
2008-06-10 23:13 PDT, Boris Zbarsky [:bz] (Out June 25-July 6)
no flags Details
testcase 2 (55.33 KB, text/html)
2008-06-12 11:35 PDT, j.j.
no flags Details
testcase 3 (5.50 KB, text/html)
2008-06-12 12:46 PDT, j.j.
no flags Details
reflow counts (38.25 KB, image/png)
2008-09-03 12:20 PDT, Bernd
no flags Details
testcase 4 (displays load time) (2.34 KB, text/html)
2008-10-20 12:58 PDT, Daniel Holbert [:dholbert]
no flags Details
patch 1: remove a write-only variable (4.31 KB, patch)
2008-11-13 18:07 PST, David Baron :dbaron: ⌚️UTC-7 (review requests must explain patch)
roc: review+
roc: superreview+
Details | Diff | Review
patch 2: some optimizations that make things fast (3.68 KB, patch)
2008-11-13 18:12 PST, David Baron :dbaron: ⌚️UTC-7 (review requests must explain patch)
no flags Details | Diff | Review
patch 2: some optimizations that make things fast (4.07 KB, patch)
2008-11-14 16:54 PST, David Baron :dbaron: ⌚️UTC-7 (review requests must explain patch)
no flags Details | Diff | Review
patch 3: simplify condition, part 1 (1.54 KB, patch)
2008-11-15 12:41 PST, David Baron :dbaron: ⌚️UTC-7 (review requests must explain patch)
no flags Details | Diff | Review
patch 4: simplify conditions, part 2 (3.93 KB, patch)
2008-11-15 12:41 PST, David Baron :dbaron: ⌚️UTC-7 (review requests must explain patch)
no flags Details | Diff | Review
patch 4: simplify conditions, part 2 (3.93 KB, patch)
2008-11-15 13:20 PST, David Baron :dbaron: ⌚️UTC-7 (review requests must explain patch)
no flags Details | Diff | Review
combination of patches 2, 3, and 4 (4.75 KB, patch)
2008-11-15 13:43 PST, David Baron :dbaron: ⌚️UTC-7 (review requests must explain patch)
dholbert: review+
roc: superreview+
Details | Diff | Review
patch 5: test (3.03 KB, patch)
2008-11-17 11:45 PST, David Baron :dbaron: ⌚️UTC-7 (review requests must explain patch)
no flags Details | Diff | Review

Description Boris Zbarsky [:bz] (Out June 25-July 6) 2008-06-10 23:12:24 PDT
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 [:bz] (Out June 25-July 6) 2008-06-10 23:13:47 PDT
Created attachment 324585 [details]
zipped-up testcase
Comment 2 j.j. 2008-06-12 11:35:53 PDT
Created attachment 324838 [details]
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. 2008-06-12 12:46:46 PDT
Created attachment 324846 [details]
testcase 3

More reduced
Fx 3   ~15 sec
Fx 2    ~0 sec
Comment 4 Mike Schroepfer 2008-06-24 11:19:39 PDT
I'd be in favor of this blocking, not wanted for 1.9.1...
Comment 5 Florin 2008-07-08 11:05:15 PDT
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 2008-07-08 11:13:58 PDT
Given the regression from FF2->FF3 I'm moving this to blocking status - please reset if you disagree
Comment 7 j.j. 2008-07-08 15:57:46 PDT
(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 2008-07-30 09:45:35 PDT
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 2008-09-03 12:20:06 PDT
Created attachment 336689 [details]
reflow counts

we reflow the inner tables up to 4096 times
Comment 10 Bernd 2008-09-03 12:24:19 PDT
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 2008-10-06 06:11:19 PDT
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] 2008-10-20 12:58:43 PDT
Created attachment 343956 [details]
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 2008-10-26 07:42:26 PDT
> 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) (Exited; email my personal email if necessary) 2008-11-11 18:45:00 PST
dbaron's probably the best person for this.
Comment 15 David Baron :dbaron: ⌚️UTC-7 (review requests must explain patch) 2008-11-13 18:07:17 PST
Created attachment 348120 [details] [diff] [review]
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-7 (review requests must explain patch) 2008-11-13 18:12:20 PST
Created attachment 348121 [details] [diff] [review]
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-7 (review requests must explain patch) 2008-11-13 18:12:49 PST
(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-7 (review requests must explain patch) 2008-11-13 21:42:18 PST
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-7 (review requests must explain patch) 2008-11-13 21:46:55 PST
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-7 (review requests must explain patch) 2008-11-14 16:54:31 PST
Created attachment 348281 [details] [diff] [review]
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-7 (review requests must explain patch) 2008-11-15 12:41:18 PST
Created attachment 348367 [details] [diff] [review]
patch 3: simplify condition, part 1
Comment 22 David Baron :dbaron: ⌚️UTC-7 (review requests must explain patch) 2008-11-15 12:41:47 PST
Created attachment 348368 [details] [diff] [review]
patch 4: simplify conditions, part 2
Comment 23 David Baron :dbaron: ⌚️UTC-7 (review requests must explain patch) 2008-11-15 13:20:52 PST
Created attachment 348371 [details] [diff] [review]
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-7 (review requests must explain patch) 2008-11-15 13:43:44 PST
Created attachment 348372 [details] [diff] [review]
combination of patches 2, 3, and 4
Comment 25 David Baron :dbaron: ⌚️UTC-7 (review requests must explain patch) 2008-11-15 13:46:27 PST
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-7 (review requests must explain patch) 2008-11-15 13:50:17 PST
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-7 (review requests must explain patch) 2008-11-15 13:56:46 PST
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-7 (review requests must explain patch) 2008-11-15 14:00:36 PST
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] 2008-11-17 11:10:37 PST
/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-7 (review requests must explain patch) 2008-11-17 11:45:01 PST
Created attachment 348607 [details] [diff] [review]
patch 5: test

Good idea.

Here's a patch for the test as described by dholbert.
Comment 31 Daniel Holbert [:dholbert] 2008-11-17 11:50:26 PST
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.

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