http://lxr.mozilla.org/seamonkey/ident?i=HasMoreThanOneCell belongs into the cellmap code below follows some email communication between Boris and me, 1.) Hi Boris, I just added a comment on the mozilla.org thread. Oh man HasMoreThanOneCell what is that???? see http://www.mozilla.org/newlayout/doc/table-cellmap.html the last section. This MUST move to the cellmap.cpp. This code sucks so endless. This code is bad because it calls nsTableCellmap which looksup the row group and then calls the nsCellmap, plus it comes probably with the bonus of trying to repair the cellmap, then inside the cellmap we look up the row and get the cellmap entry for the specified column. This is bad as we need to look up only the row elements (which might be zero for a yet empty row). And now imagine that we do that nsTableCellmap nsCellMap and so on stuff for every column if we have a empty row. I know how to rewrite it. :-) Bernd 2.) Bernd wrote: > I just added a comment on the mozilla.org thread. I saw. I'm very glad I started that thread. I wonder how long Brendan was planning to sit on that announcement? > Oh man HasMoreThanOneCell what is that???? Puuuure Eeeevil? ;) > http://www.mozilla.org/newlayout/doc/table-cellmap.html the last section. This MUST move to the cellmap.cpp. Agreed. How the cellmap implements that should be none of our concern. > I know how to rewrite it. :-) Great. Are you going to do that as part of the patch for that "50000 row" bug? -Boris 3.) >> I know how to rewrite it. :-) > > > > Great. Are you going to do that as part of the patch for that "50000 row" bug? > I just attached a raw patch to http://bugzilla.mozilla.org/show_bug.cgi?id=54542. If you could report back how that patch influences jprof results it would be great. Bernd 4.) Bernd wrote: > I just attached a raw patch to http://bugzilla.mozilla.org/show_bug.cgi?id=54542. If you could report back how that patch influences jprof results it would be great. Interesting. This has a much bigger effect than I would have thought. Analysis follows below, but why does this patch help this much? It's basically doing the same thing the old code was doing, no? Or is limiting ourselves to the known number of columns the big win? I tested this patch on the file at https://www.seven4sky.com/weblogs/index.php?view=list&show=file&logs=apachesave&file=seven4sky.com-access_log.08-19-2002 (which is just a really big table; about 46000 lines). Let me know whether there are other testcases you want me to run this on; the table bugs are a mess of useless noise and useless testcases. I tested builds both with and without the patch as follows: start the profiler and the pageload as close together as possible, stop the profiler 30 seconds later. The profile was non-realtime, so I was getting a hit once every 1ms of program time (I did some realtime profiles too, with very similar results, so these numbers will suffice). Mozilla was taking about 100% cpu during both profiles, so the total hit numbers are, not surprisingly close: Total hits without patch: 1469 Total hits with patch: 1564 But the time spent under CalculateRowHeights dropped a lot: Time under CalculateRowHeights without patch: 1112 (75.7% of total) Time under CalculateRowHeights with patch: 101 (6.5% of total) Another way to look at this is to compare how event handling worked with and without the patch: Without patch: 29569 0 1454 PL_HandleEvent 1301 HandlePLEvent(ReflowEvent*) 150 nsInputStreamReadyEvent::EventHandler(PLEvent*) With patch: 29569 0 1412 PL_HandleEvent 997 HandlePLEvent(ReflowEvent*) 411 nsInputStreamReadyEvent::EventHandler(PLEvent*) So without the patch, 89% of the time spent handling events was handling reflow events (that's all that lives under HandlePLEvent). With the patch, that percentage dropped to 70%. The nsInputStreamReadyEvent numbers correspond to the fraction of time spent in parser, DOM, frame construction, etc. A lot more of this happened without the patch, in the same period of wall-clock time. Most importantly, with this patch Mozilla is responsive as it loads the page, I can scroll up and down without it freezing up like it does without the patch, and the page actually finishes loading in a somewhat sane amount of time. -Boris 5.) Boris Zbarsky wrote: > Bernd wrote: > >> I just attached a raw patch to http://bugzilla.mozilla.org/show_bug.cgi?id=54542. If you could report back how that patch influences jprof results it would be great. > > > > Interesting. This has a much bigger effect than I would have thought. Analysis follows below, but why does this patch help this much? It's basically doing the same thing the old code was doing, no? Or is limiting ourselves to the known number of columns the big win? There are a few differences and the main idea is that I removed the cellmap repair. from http://www.mozilla.org/newlayout/doc/table-cellmap.html: The handling of zero spans introduces overhead as one can not mark in advance the corresponding cells as spanned by the zero spans. The current solution is to use nsCellmap::GetDataAt with a special argument aUpdateZeroSpan to repair the cellmap if it encounters a empty cell (nsnull), by looking for a origin of a zero row- or colspan that spans the queried place in the cellmap. This can produce enormous costs once the cellmap contains large holes that are not caused by zero spans, this is at least a O2(n) algorithm. What does that mean if you feed a empty row without the patch? you look at the first cell you see that it is not a real cell then you look at the second cell you see that it is not a real cell, but it might be a zero col or rowspan, so you look up the cell above and to the left if they are real. The cell above probably is, the cell to the left not. So you continue on the third. And so on ... O2(n). What this patch does it says, we dont need to repair afterwards, it has been done already. So the patch needs some regression testing and some guerilla zero span dom testing. I would even go without the second one if the patch passes the rtest, these 4 webpages that use zero spans should be fixed inside the cellmap code and not at such a high level. It might be worth to teach the parser to try to get rows complete and not these empty or half empty rows, this would significantly drop the number of incremental reflows. (I have no idea how this parser works) We should attach the conversation about this into bugzilla into a new bug with some technical description like chris waterson did, this will keep these performance groupies out of the bug. Bernd 6.) Bernd wrote: > There are a few differences and the main idea is that I removed the cellmap repair. Ah, right. I see. Excellent. > What does that mean if you feed a empty row without the patch? Are we really looking at empty rows here? More on that below. > you look at the first cell you see that it is not a real cell > then you look at the second cell you see that it is not a real cell [more looking snipped] Right. What I think is actually happening here is more like this. Say we have 1 column (like the testcase I was testing on), and we're looking at the n-th row. The pre-patch code gets the cellmap entry at (n,1) and sees that we have a cell there. To see whether we have more than one cell, it has to get the entry at (n,2), but there's nothing there so it tries to repair and what you described ensues. Note that the pre-patch code just increments the col till it gets null, instead of limiting itself to the "real" number of cols in the table. > What this patch does it says, we dont need to repair afterwards, it has been done already. Right. > So the patch needs some regression testing and some guerilla zero span dom testing. Hmmm... yeah, writing testcases for this could be fun.... > It might be worth to teach the parser to try to get rows complete and not these empty or half empty rows, this would significantly drop the number of incremental reflows. (I have no idea how this parser works) It tries to do this already, actually. <tr> is treated as a "monolithic" element; that means the sink will never voluntarily notify while there's an open <tr> that's half-parsed. Notifications can still happen if they're forced by someone else flushing, or doing some sorts of DOM access, or whatever, though. > We should attach the conversation about this into bugzilla into a new bug with some technical description like chris waterson did, this will keep these performance groupies out of the bug. Yes. Would you mind doing that? And marking it as a dependency (in whichever direction makes sense) of that cellmap tracker? -Boris 7.) >> So the patch needs some regression testing and some guerilla zero span dom testing. > > It doesnt pass the regression tests, so it looks like some more surgery is necessary. But it seems from your data that it is the right way. As there want be a quick solution it will go behind the col frame crash bug. Bernd 8.) Bernd wrote: > It doesnt pass the regression tests, so it looks like some more surgery is necessary. OK. Nice of the tests to catch it. ;) It actualy failed on one of the (col|row)span="0" tests, I hope? > But it seems from your data that it is the right way. Yeah. Perhaps we should reenable the repair (PR_TRUE for the last arg to GetDataAt)? Since we're only going up to maxColIndex, that should not break things too badly. On the other hand, if the last column of the table is a single rowspan="0" cell, won't maxColIndex be off by one in the code in question? > As there want be a quick solution it will go behind the col frame crash bug. Sounds like a plan. -Boris

the previous regression test failure was due to a coding error when converting the do while into a for loop. I have seen a few state mismatches as usual and some single pixel changes that I could not verify visually. So I would claim that this passes the rtest. Boris could you please reevaluate, as the previous patch was bogus and it could have influence on the timing.

Comment on attachment 145941 [details] [diff] [review] revised patch r+sr=bzbarsky. This has about the same effect on performance that the erroneous version had -- HasMoreThanOneCell all but disappears from the profile.

fix checked in, effect on tinderbox: 0

I wonder, might this impact Bug 121142?

certainly not