236703 - Better, faster, smaller Table layout patch

Status: RESOLVED FIXED

(Core :: Layout: Tables, defect)

Description

[jim_nance]

I was doing jprof runs to determine why the URL above loads so slowly (about 30
seconds, even when loading from a file rather than via http).  It seems that the
following methods are making calls down to nsCellMap::GetDataAt() where the
actual time is spent:
 
                 85
BasicTableLayoutStrategy::AssignPctColumnWidths(nsHTMLReflowState const&, int,
int, float)
                 59
BasicTableLayoutStrategy::CalcPctAdjTableWidth(nsHTMLReflowState const&, int)
                 29
BasicTableLayoutStrategy::ComputeNonPctColspanWidths(nsHTMLReflowState const&,
int, float, int*)
                 27 BasicTableLayoutStrategy::AssignNonPctColumnWidths(int,
nsHTMLReflowState const&)
 69041   5      200 nsTableFrame::GetCellInfoAt(int, int, int*, int*)
                189 nsTableCellMap::GetCellInfoAt(int, int, int*, int*)
                  5 nsTableFrame::GetCellMap() const
                  1 nsCellMap::GetCellInfoAt(nsTableCellMap&, int, int, int*, int*)

I did a little optimization the the BasicTableLayoutStrategy methods in an
attempt to reduce the number of calls to GetCellInfoAt() which they made.  It
turns out that the code I changed actually does not get excercised with the URL
above, so my changes do not make that testcase run faster.  However, they reduce
the number of lines of source code and the size of the executable:

tricia> diffstat tttt
 BasicTableLayoutStrategy.cpp |  163 ++++++++++++++++++-------------------------
 BasicTableLayoutStrategy.h   |   25 +-----
 2 files changed, 78 insertions(+), 110 deletions(-)

tricia> size layout/html/table/src/BasicTableLayoutStrategy.o{,.old}
   text    data     bss     dec     hex filename
  14774      60       0   14834    39f2
layout/html/table/src/BasicTableLayoutStrategy.o
  15324      60       0   15384    3c18 layout/html/table/src/BasicTableLayoutSt

I also feel like the code is cleaner after my changes.  So given these benifits
I would like to check this patch into the code.

Comment 1

[jim_nance]

Attachment: Reduce calls to GetDataAt() originating from the table layout code

Comment 2

[jim_nance]

Attachment: updated patch. Removes some dead code

I found some unnecessary code that I have removed and added to the patch.  One
place was a loop over the columns to calculate a value that was never used. 
The other was a call to RoundToPixel() whose return value was never used.  I
just deleted the RoundToPixel() call, but I suspect that might not be the right
fix.  It does preserve the current behavior though so I felt that it was the
safest.  If someone would take a look at that and comment I would appreciate
it.

Comment 3

[Bernd]

Comment on attachment 143677 [details] [diff] [review]
updated patch.  Removes some dead code

+
+static PRInt32
+GetSortedFrames(nsTableFrame *TableFrame,
+		 PRInt32       colX,
+		 PRInt32       numRows,
+		 CellInfo     *cellInfo)
+{

It would be nice to have a description of the function, similiar to the
description 
that was removed from BasicTableLayoutStrategy.h for RowSort().

+    PRInt32 index = GetSortedFrames(mTableFrame, colX, numRows, cellInfo);

please rename the variable in something more descriptive.

-	 nsTableFrame::RoundToPixel(propTotal, pixelToTwips);

please change this to, 

   propTotal = nsTableFrame::RoundToPixel(propTotal, pixelToTwips);

this is an omission.

With those changes r=bernd

Comment 4

[jim_nance]

Attachment: Incorporates requested changes

Here is the patch with the changes you suggested.  Who should I get to sr this?

Comment 5

[Bernd]

Comment on attachment 144126 [details] [diff] [review]
Incorporates requested changes

GetDataAt()-  Boris is a known fan of this function

Comment 6

[Boris Zbarsky [:bzbarsky]]

I won't be able to get to this for about a week and a half (I'll be out of the
country), but at first glance this looks very nice... gotta love those O(N^2)
sorts being removed.  This should help in the testcase in bug 220997 (if that
still exists).

Comment 7

[jim_nance]

Still going to superreview?

Comment 8

[Boris Zbarsky [:bzbarsky]]

Hopefully tomorrow, yes.

Comment 9

[Boris Zbarsky [:bzbarsky]]

Comment on attachment 144126 [details] [diff] [review]
Incorporates requested changes

>Index: layout/html/table/src/BasicTableLayoutStrategy.cpp

>+static int RowSortCB(const void *a, const void *b, void *)
>+{
>+  const CellInfo *aa = (CellInfo*)a;
>+  const CellInfo *bb = (CellInfo*)b;

Make those NS_STATIC_CAST, please.

>+    PRInt32 SpannedRows = GetSortedFrames(mTableFrame, colX, numRows, cellInfo);

interCaps, please (spannedRows).

> BasicTableLayoutStrategy::ComputeNonPctColspanWidths(PRInt32           

>+    PRInt32 SpannedRows = GetSortedFrames(mTableFrame, colX, numRows, cellInfo);

Again.

With those nits, sr=bzbarsky.  Thanks a ton for killing off that O(N^2) sort!

Comment 10

[Christian :Biesinger (don't email me, ping me on IRC)]

Comment on attachment 143156 [details] [diff] [review]
Reduce calls to GetDataAt() originating from the table layout code

removing obsolete review request

Comment 11

[jim_nance]

Attachment: Final patch, incorporating sr requests

I put in the changes you asked for.  As soon as the tree opens again, I will
check this in.

Comment 12

[jim_nance]

Checked the code in