241599 - Table layout speedup

Status: RESOLVED FIXED

(Core :: Layout: Tables, enhancement)

Description

[jim_nance]

I am still trying to make the table layout code faster for the table given in
the URL above (its bonsi output).  We seem to be spending a lot of time under
nsTableFrame::GetCellInfoAt() which is called by
BasicTableLayoutStrategy::AssignPctColumnWidths().

AssignPctColumnWidths() makes two passes over the table.  Once to handle columns
with a colspan of 1, and once to handle columns with a colspan>1. 
GetCellInfoAt() is called for every table element in both of those passes.  I
modified the code so that it records the minimum and maximum columns which have
a colspan>1, so that it only has to loop over this range in the second pass. 
For the table above, and probably many others, no colums have a colspan>1, so we
cut our calls in half.  Jprof shows how much this helps.  These runs consist of
loading the page referenced above 5 times.  The page was on the local FS to
remove network interactions.

Old:
                112 BasicTableLayoutStrategy::AssignPctColumnWidths(nsHTML
                110 GetSortedFrames(nsTableFrame*, int, int, CellInfo*)
                100 BasicTableLayoutStrategy::CalcPctAdjTableWidth(nsHTMLR
                 57 BasicTableLayoutStrategy::AssignNonPctColumnWidths(int
 70593   5      379 nsTableFrame::GetCellInfoAt(int, int, int*, int*)
                370 nsTableCellMap::GetCellInfoAt(int, int, int*, int*)
                  2 nsCellMap::GetCellInfoAt(nsTableCellMap&, int, int, in
                  1 nsTableFrame::GetCellMap() const
                  1 nsSplittableFrame::GetFirstInFlow() const


New:

                 98 BasicTableLayoutStrategy::CalcPctAdjTableWidth(nsHTMLR
                 53 GetSortedFrames(nsTableFrame*, int, int, CellInfo*)
                 50 BasicTableLayoutStrategy::AssignNonPctColumnWidths(int
                 46 BasicTableLayoutStrategy::AssignPctColumnWidths(nsHTML
 70664   8      247 nsTableFrame::GetCellInfoAt(int, int, int*, int*)
                238 nsTableCellMap::GetCellInfoAt(int, int, int*, int*)
                  1 nsCellMap::GetCellInfoAt(nsTableCellMap&, int, int, in

Comment 1

[jim_nance]

Attachment: Patch to implement change described in initial comment

Comment 2

[jim_nance]

Another way to accomplish this would be to create a list of columns with
colspan>1 when we did the first loop.  It could be faster, but it is also more
complex as we would have to potentially allocate memory to hold the list.  If
someone thinks its better to make the list, I am willing to code it up.

Comment 3

[Bernd]

I think the table cell map would be a better place to hold this list. We have
already a function that does that nsCellMap::ColHasSpanningCells but it is slow
as it looks up the cell data in the cellmap every time  it is called.
Look for comparison at nsTableCellMap::ColIsSpannedInto(PRInt32 aColIndex).
Speeding ColHasSpanningCells up in a similiar way like ColIsSpannedInto would
also speed up the other callers.

Comment 4

[Bernd]

Could you please attach the jprof, I am just curious how it looks now.

Comment 5

[Bernd]

by the way is that patch for review? If yes, could you be more explicit about it
(setting the flags).

Comment 6

[jim_nance]

The patch is not for review, I was interested in collecting comments first.  I
am currently implementing a version that makes a list so we can compare them.

Comment 7

[jim_nance]

Attachment: prepatch jprof

Comment 8

[jim_nance]

Attachment: post patch jprof

Comment 9

[jim_nance]

Attachment: New patch using list method

Here is a patch implementing the same idea using a list built in the first
pass.  I like this a lot better.  It will provide speedups regardless of
whether the table has colspans or not.	And it make it so that we iterate
through the table only once, regardless of the number of spans.  We still do 3
passes, but we are only querying the elements once.  I used an arena so
building and tearing down the list should be light weight.  I would appreciate
comments, and if people like this I will request a review.  

There is one suggestion listed above for an alternate way to speed things up. 
I will look at doing that.  But I do not think it conflicts with this patch, so
I would like this included regardless of how the other one comes out

Comment 10

[jim_nance]

Attachment: jprof with the the second patch applied

Comment 11

[jim_nance]

Attachment: list patch with a couple of bugs fixed

The original list patch had 2 bugs.  There was an uninitalized mPrev field in
the list, and I had changed the direction we looped through the rows, and that
broke some pages.

Comment 12

[Bernd]

the  patch doesnt compile on winxp VC6

e:/moz_src/mozilla/layout/html/table/src/BasicTableLayoutStrategy.cpp(1426) : er
ror C2106: '=' : Linker Operand muss ein L-Wert sein
e:/moz_src/mozilla/layout/html/table/src/BasicTableLayoutStrategy.cpp(1512) : er
ror C2106: '=' : Linker Operand muss ein L-Wert sein
make: *** [BasicTableLayoutStrategy.obj] Error 2
It dies in
 
PL_ARENA_ALLOCATE((void*)spanned, &spanArena, sizeof(*spanned));

Comment 13

[jim_nance]

Attachment: Fix the PL_ARENA_ALLOCATE problem

Sorry Bernd, this one should compile.  I took a year of German in high school. 
Its fun to try and translate the error messages and see how much I remember!

Comment 14

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Comment on attachment 152357 [details] [diff] [review]
Fix the PL_ARENA_ALLOCATE problem

sr=dbaron, although I'm not sure a struct inside a function will work with all
our compilers.

Comment 15

[jim_nance]

Checked in