241796 - Painting large tables requires linear walk over all rows (slow table scrolling)

Status: RESOLVED FIXED

(Core :: Web Painting, defect)

Description

[Boris Zbarsky [:bzbarsky]]

This is basically the table analogue of bug 51938.  Now that we've fixed bug
240275, scrolling a page with a large table is still rather painful due to this
issue.  The solution would be to do what blocks do -- store a cursor, etc.

For a table, the .ys for rows should be nondecreasing, so we only have to worry
about YMosts.  I'm not sure whether we want to take exactly the same approach as
for blocks (since that will effectively turn off the optimization on any table
with a cell that has a rowspan greater than 2); maybe we can handle those cases?

Comment 1

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

> For a table, the .ys for rows should be nondecreasing

No, because we're talking about the overflow area.

> I'm not sure whether we want to take exactly the same approach as
> for blocks (since that will effectively turn off the optimization on any table
> with a cell that has a rowspan greater than 2)

We could boost the height of the overflow area of a row to at include the bottom
of any rowspanning cells that cover the row. Then we could use the same
technique as for blocks. Bernd, would that be hard?

Comment 2

[Bernd]

>  I'm not sure whether we want to take exactly the same approach as
for blocks 
So does that mean we add the same code twice for blocks and for tables? Shouldnt
that then go the HTMLContainer?
I would like to avoid adding special code to the tables. What I have done over
the past months is just the opposite. Remove as much as possible special
handling, make table frames nice citizens of the frame land. This is necessary
as in a foreseeable future the amount of engineer hours spend in the
layout-table will be limited.
We have some cellmap functions like
http://lxr.mozilla.org/seamonkey/ident?i=RowIsSpannedInto
and 
http://lxr.mozilla.org/seamonkey/ident?i=RowHasSpanningCells
They are of course potential performance bombs especially in the case when you
dont have rowspans.
I have strong feelings about horking the row overflow area.
Returning to the first point I dont see why a large nubmer of blocks with
vertical overflow wouldn't pose the same problem.

Comment 3

[Boris Zbarsky [:bzbarsky]]

> So does that mean we add the same code twice for blocks and for tables?

We sorta have to do it anyway, since blocks have this line iterator funkiness
going on, so in blocks the basic child is not a frame but a nsLineBox, while in
tables it is in fact a frame (table row frame, in fact)....

> They are of course potential performance bombs especially in the case when you
> dont have rowspans.

Yeah, calling those on every Paint() or worse yet GetFrameForPoint() operation
would be moderately unpleasant...  Let's not.

> I have strong feelings about horking the row overflow area.

Reasonable sentiment.

> I dont see why a large nubmer of blocks with vertical overflow wouldn't pose
> the same problem

They would.  I posit (perhaps incorrectly?) that having a large number of block
kids at least one of which overflows is rarer than having a large number of rows
and at least one row-spanning cell.

But both should be rare, so maybe we just want to start with a basic impl a la
blocks and not deal with the hard and rare cases for now.

Comment 4

[Bernd]

speaking of GetFrameForPoint it seems that bug 219147 matures for prime time.

Comment 5

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

> So does that mean we add the same code twice for blocks and for tables?
> Shouldnt that then go the HTMLContainer?

Like bz said ... it's the same general concept but quite different code. The
invariant will probably be different, what we think of as children will be
different, how you iterate over them will be different.

The block cursor doesn't handle all cases. The idea is to handle common cases
well with a small amount of maintainable code, and make the solution more
general (and more complex) only when we can see a very clear need.

Actually I think I have worked out a general solution that's not too complex :-)

Comment 6

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

here's the idea:

check that the sequences of row frame .y and .YMost values are both
non-decreasing (that's the regular frame rect, not the overflow area).

compute maxOverflowAbove = max over row frames (-overflowArea.x)
        maxOverflowBelow = max over row frames (overflowArea.XMost - rect.XMost)

now, the first row frame that can overlap a given vertical y is the first row
frame whose rect includes y - maxOverflowAbove. the last row frame that can
overlap a given vertical y is the last row frame whose rect includes y +
maxOverflowBelow.

Comment 7

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

Ooh, I just realized one thing: for the cursor stuff to work, we have to be able
to find the preceding row of a table row frame in constant time. Can we do that?
(In blocks we have a doubly-linked list of lines.)

Comment 8

[Bernd]

no table frames are just nice frames and live in frame lists.
see: nsTableFrame::GetFrameAtOrBefore
http://lxr.mozilla.org/seamonkey/source/layout/html/table/src/nsTableFrame.cpp#4267

just as a side note imagine that you pass  as  nsLayoutAtoms::tableColFrame
aChildType and then hit line 4276  or 4289 

Comment 9

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

Yickity. Well, how hard would it be to keep the rows in a linked list? Do normal
tables have one row group per row or one row group per table?

Comment 10

[Boris Zbarsky [:bzbarsky]]

One row group per table.  So we're interested in nsRowGroupFrame::Paint and
nsRowGroupFrame::GetFrameForPoint, not in nsTableFrame.

Comment 11

[Bernd]

http://bugzilla.mozilla.org/show_bug.cgi?id=233463#c25
isnt point 6 the way to go?

Comment 12

[Boris Zbarsky [:bzbarsky]]

Only if we also implement an (efficient) prev() like blocks do.

Comment 13

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

Sure, we could abstract out an iterator for rows, but I think that wouldn't buy
us much. The line iterators just confuse me. I think a mPrev field in
nsTableRowFrame and an mLastRow field in nsTableRowGroupFrame would be just fine.

Comment 14

[Boris Zbarsky [:bzbarsky]]

Who'd maintain that mPrev? Especially in the context of the changes I think we
need to make in bug 233463?

Comment 15

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

nsTableRowGroupFrame would maintain it, I guess.

Comment 16

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

If we want to use this as an opportunity to prototype an nsReversibleFrameList
for later use elsewhere, I'd be for that.

Comment 17

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

I think I can just use GetPrevInFlow() to get the previous row in the rowgroup, plus a check to make sure we're still in the same rowgroup.

Comment 18

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

Never mind, I'm stupid.

If we do have to go back above the current row then I'll just build a temporary row array. So this would be O(N) in the number of rows, but with a small constant.

Comment 19

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

Actually I can keep an array of frame pointers alongside the cursor. We'll clear the cursor anyway anytime something happens that could change the array.

Comment 20

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

Attachment: fix

This patch adds cursor support to nsTableRowGroupFrame. It seems to work, but I don't have any testcases that show a measurable performance improvement...

Comment 21

[Boris Zbarsky [:bzbarsky]]

Damn.  I wish I'd saved the original testcase.  Let me see whether I can create a testcase for this.

Comment 22

[Boris Zbarsky [:bzbarsky]]

Attachment: Simple testcase -- zip containing test.html; extracts to 19MB file.

With this testcase, and without this patch, I see a good chunk (30+%) of the time spent in (not under) nsIFrame::BuildDisplayListForChild.  Applying this patch drops that to more like 0.3%.  The next hotspot is nsTableRowFrame::GetNextRow() called from TableBackgroundPainter::PaintRowGroup()... which does a loop over all rows.  It should probably make use of the cursor too.  In all, with this patch applied about 75% of the time is spent in non-painting stuff (GetNextRow and TableBackgroundPainter::TableBackgroundData::SetFrame() under PaintRowGroup.

Comment 23

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

Do you think this is worth taking, then?

Comment 24

[Boris Zbarsky [:bzbarsky]]

I think so; actual performance on the testcase I attached (and on any other table with tens of thousands of rows) is a lot better (probably 2-3 times as fast).  We could do a followup for PaintRowGroup, I guess.

Comment 25

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

Comment on attachment 235872 [details] [diff] [review]
fix

okay then!

Comment 26

[Boris Zbarsky [:bzbarsky]]

I should get to this early next week.

Comment 27

[Boris Zbarsky [:bzbarsky]]

Comment on attachment 235872 [details] [diff] [review]
fix

>Index: layout/tables/nsTableFrame.h
>+   * @param aCursorFrame if non-null, this is the frame to start with, and we

This should be documentation for aTraversal, right?

>Index: layout/tables/nsTableRowGroupFrame.cpp

>+DisplayRows(nsDisplayListBuilder* aBuilder, nsFrame* aFrame,

After you finish setting up the row cursor, do you want to call Compact() on its mFrames?  nsTArray uses a doubling algorithm for EnsureCapacity, so we could have a lot of wasted space in the array.

>+void nsTableRowGroupFrame::ClearRowCursor() {

Linebreaks after the |void| and before the '{', please.

>+nsTableRowGroupFrame::FrameCursorData* nsTableRowGroupFrame::SetupRowCursor() {

Similar here.

>+  if (GetStateBits() & NS_ROWGROUP_HAS_ROW_CURSOR)
>+    return nsnull;

Curly braces around the if body, please, and same elsewhere in the patch.  And add a comment explaining that if someone's asking for a cursor when we already have one it's because they shouldn't be using it anyway, so we return null?  Or something along those lines?  Just so some kind soul doesn't decide to "fix" this.

>+nsIFrame* nsTableRowGroupFrame::GetFirstRowContaining(nscoord aY, nscoord* aOverflowAbove) {

Again, linebreaks after the return type and before the curly.

>+  while (cursorIndex > 0 &&
>+         cursorFrame->GetRect().YMost() + property->mOverflowBelow > aY) {

So I assume there's a reason we don't need the IsEmpty() check on the rect here because we perform it in AppendFrame, right?

Also, how come we use mOverflowBelow here and not just the cursorFrame's overflow YMost()?  I assume this is to handle a case where some row doesn't reach down to aY, but a row above it with a rowspanning cell does?  If so, we should document that...

>Index: layout/tables/nsTableRowGroupFrame.h
>+    FrameCursorData()
>+      : mCursorIndex(0), mOverflowAbove(0), mOverflowBelow(0) {}

You know you'll have at least MIN_ROWS_NEEDING_CURSOR frames, right?  Might as well toss in |mFrames(MIN_ROWS_NEEDING_CURSOR)| and avoid some allocations.


>+  void ClearRowCursor();
>+  /**

Put a linebreak in there?

>+   *  Get the first row that might contain y-coord 'aY', or nsnull if you must search

Extra space before "Get".

>+   * overflowArea.ys and overflowArea.yMosts are non-decreasing.

So this is only the case because the caller of AppendFrame enforces it, right?

>+   * You can stop when you reach a row whose GetRect().y - aOverflowAbove is

*aOverflowAbove, right?  And "stop" means "stop looking for rows that contain aY"?

>+  nsIFrame* GetFirstRowContaining(nscoord aY, nscoord* aOverflowAbove);
>+  /**

Again, put in a linebreak.

r+sr=bzbarsky with those nits picked.

Comment 28

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

(In reply to comment #27)
> >Index: layout/tables/nsTableFrame.h
> >+   * @param aCursorFrame if non-null, this is the frame to start with, and we
> 
> This should be documentation for aTraversal, right?

Er, right.

> >Index: layout/tables/nsTableRowGroupFrame.cpp
> 
> >+DisplayRows(nsDisplayListBuilder* aBuilder, nsFrame* aFrame,
> 
> After you finish setting up the row cursor, do you want to call Compact() on
> its mFrames?  nsTArray uses a doubling algorithm for EnsureCapacity, so we
> could have a lot of wasted space in the array.

Good idea

> >+  if (GetStateBits() & NS_ROWGROUP_HAS_ROW_CURSOR)
> >+    return nsnull;
> 
> Curly braces around the if body, please, and same elsewhere in the patch.

I thought we were allowing bare returns, breaks and continues to not have their own block.

> And add a comment explaining that if someone's asking for a cursor when we
> already have one it's because they shouldn't be using it anyway, so we return
> null?  Or something along those lines?  Just so some kind soul doesn't decide
> to "fix" this.

OK. The idea is that if someone calls SetupRowCursor while we already have one, we let them go ahead but we prevent them from messing with the existing cursor. This can happen when GetStateBits() & NS_FRAME_FORCE_DISPLAY_LIST_DESCEND_INTO is set (when we are forced to traverse all rows looking for placeholders of absolutely or fixed positioned elements that need to be painted).

> >+  while (cursorIndex > 0 &&
> >+         cursorFrame->GetRect().YMost() + property->mOverflowBelow > aY) {
> 
> So I assume there's a reason we don't need the IsEmpty() check on the rect here
> because we perform it in AppendFrame, right?

Exactly. I'll add a comment.

> Also, how come we use mOverflowBelow here and not just the cursorFrame's
> overflow YMost()?  I assume this is to handle a case where some row doesn't
> reach down to aY, but a row above it with a rowspanning cell does?  If so, we
> should document that...

Right. It's essential that the sequence of thresholds we test aY against be monotonic, otherwise we can't know when to stop.

> >Index: layout/tables/nsTableRowGroupFrame.h
> >+    FrameCursorData()
> >+      : mCursorIndex(0), mOverflowAbove(0), mOverflowBelow(0) {}
> 
> You know you'll have at least MIN_ROWS_NEEDING_CURSOR frames, right?  Might as
> well toss in |mFrames(MIN_ROWS_NEEDING_CURSOR)| and avoid some allocations.

Good idea.
 
> >+   * overflowArea.ys and overflowArea.yMosts are non-decreasing.
> 
> So this is only the case because the caller of AppendFrame enforces it, right?

Actually this comment is wrong, it's a leftover from the nsBlockFrame regime. There is no such guarantee. The only relevant guarantee is that you can start from the returned frame, traversing the sibling chain, and stop when reach a row whose GetRect().y - aOverflowAbove is >= the YMost() of the vertical region you're interested in, and be sure that you have seen all the frames whose overflow area intersects with your vertical region.

> >+   * You can stop when you reach a row whose GetRect().y - aOverflowAbove is
> 
> *aOverflowAbove, right?

Right

> And "stop" means "stop looking for rows that contain aY"?

Stop looking for rows that intersect your vertical region. I'll clean this up to make it a lot more precise.

Thanks!

Comment 29

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

(In reply to comment #28)
> OK. The idea is that if someone calls SetupRowCursor while we already have one,
> we let them go ahead but we prevent them from messing with the existing cursor.
> This can happen when GetStateBits() & NS_FRAME_FORCE_DISPLAY_LIST_DESCEND_INTO
> is set (when we are forced to traverse all rows looking for placeholders of
> absolutely or fixed positioned elements that need to be painted).

This is actually an optimization, BTW. It means we don't eat the cost of reconstructing the cursor if we already have a perfectly good one.

Comment 30

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

checked in.

Comment 31

[Boris Zbarsky [:bzbarsky]]

So I'm not following this comment in nsTableFrame.h:

268    * @param aTraversal if non-null, this is the frame to start with, and we
269    * can stop as soon as we find a frame whose overflowRect has y-coordinate
270    * below the dirty rect and is non-empty

And I just realized that the SetProperty in nsTableRowGroupFrame::SetupRowCursor can fail and that we should handle that, probably with a NS_UNLIKELY check...

Also, is the stuff about YMost in the comments on SetupRowCursor correct?  Similar wording was removed from the GetFirstRowContaining docs...


aTraversal seems to be a function...

Comment 32

[Boris Zbarsky [:bzbarsky]]

> aTraversal seems to be a function...

This was supposed to be after the quote from nsTableFrame.h and before the other comments in comment 31.

Comment 33

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

(In reply to comment #31)
> Also, is the stuff about YMost in the comments on SetupRowCursor correct? 
> Similar wording was removed from the GetFirstRowContaining docs...

It is, because we're talking about the frame Y and YMost, not the overflowArea.

I'll post a patch to address the other issues.

Comment 34

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

Attachment: fix outstanding issues

Fixes comment, handles SetProperty failure.

Comment 35

[Boris Zbarsky [:bzbarsky]]

Comment on attachment 239292 [details] [diff] [review]
fix outstanding issues

Looks good

Comment 36

[K Carter]

Should this bug be resolved fixed?  I don't see a checkin for the attachment 239292 [details] [diff] [review] 'fix outstanding issues'.  Sorry if I just overlooked it.

Comment 37

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

The bug is fixed. The remaining patch just cleans up some stuff. I'll check it in today.

Comment 38

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

checked in.