Better, faster, smaller Table layout patch

RESOLVED FIXED

Status

()

RESOLVED FIXED
15 years ago
15 years ago

People

(Reporter: jim_nance, Unassigned)

Tracking

(Blocks: 1 bug, {perf})

Trunk
x86
Linux
Points:
---
Dependency tree / graph

Firefox Tracking Flags

(Not tracked)

Details

(URL)

Attachments

(1 attachment, 3 obsolete attachments)

(Reporter)

Description

15 years ago
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.
(Reporter)

Comment 1

15 years ago
Created attachment 143156 [details] [diff] [review]
Reduce calls to GetDataAt() originating from the table layout code
Attachment #143156 - Flags: review?(bernd.mielke)
(Reporter)

Comment 2

15 years ago
Created attachment 143677 [details] [diff] [review]
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.
Attachment #143156 - Attachment is obsolete: true

Comment 3

15 years ago
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
Attachment #143677 - Flags: review+
(Reporter)

Comment 4

15 years ago
Created attachment 144126 [details] [diff] [review]
Incorporates requested changes

Here is the patch with the changes you suggested.  Who should I get to sr this?
Attachment #143677 - Attachment is obsolete: true

Comment 5

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

GetDataAt()-  Boris is a known fan of this function
Attachment #144126 - Flags: superreview?(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).
Blocks: 220997
(Reporter)

Comment 7

15 years ago
Still going to superreview?
Hopefully tomorrow, yes.
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!
Attachment #144126 - Flags: superreview?(bzbarsky) → superreview+
Comment on attachment 143156 [details] [diff] [review]
Reduce calls to GetDataAt() originating from the table layout code

removing obsolete review request
Attachment #143156 - Flags: review?(bernd.mielke)
(Reporter)

Comment 11

15 years ago
Created attachment 145919 [details] [diff] [review]
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.
Attachment #144126 - Attachment is obsolete: true
(Reporter)

Comment 12

15 years ago
Checked the code in
Status: NEW → RESOLVED
Last Resolved: 15 years ago
Resolution: --- → FIXED

Updated

15 years ago
Keywords: perf
You need to log in before you can comment on or make changes to this bug.