240318 - move HasMoreThanOneCell into the cellmap code

Status: RESOLVED FIXED

(Core :: Layout: Tables, defect)

Description

[Bernd]

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

Comment 1

[Bernd]

Attachment: revised patch

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 2

[Boris Zbarsky [:bzbarsky]]

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.

Comment 3

[Bernd]

fix checked in, effect on tinderbox: 0

Comment 4

[Greg K.]

I wonder, might this impact Bug 121142?

Comment 5

[Bernd]

certainly not