Status

()

Core
Layout: Tables
--
enhancement
RESOLVED FIXED
14 years ago
13 years ago

People

(Reporter: jim_nance, Unassigned)

Tracking

(Blocks: 1 bug, {perf})

Trunk
Points:
---
Dependency tree / graph

Firefox Tracking Flags

(Not tracked)

Details

(URL)

Attachments

(5 attachments, 2 obsolete attachments)

(Reporter)

Description

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

Comment 1

14 years ago
Created attachment 146947 [details] [diff] [review]
Patch to implement change described in initial comment
(Reporter)

Comment 2

14 years ago
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

14 years ago
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

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

Comment 5

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

Comment 6

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

Comment 7

14 years ago
Created attachment 147036 [details]
prepatch jprof
(Reporter)

Comment 8

14 years ago
Created attachment 147037 [details]
post patch jprof

Updated

14 years ago
Keywords: perf
(Reporter)

Comment 9

14 years ago
Created attachment 147153 [details] [diff] [review]
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
(Reporter)

Comment 10

14 years ago
Created attachment 147154 [details]
jprof with the the second patch applied
(Reporter)

Comment 11

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

Updated

14 years ago
Attachment #147278 - Flags: superreview?(bernd_mozilla)
Attachment #147278 - Flags: review?(bernd_mozilla)

Updated

14 years ago
Flags: blocking1.8a1?

Updated

14 years ago
Flags: blocking1.8a1?

Comment 12

14 years ago
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));

(Reporter)

Comment 13

14 years ago
Created attachment 152357 [details] [diff] [review]
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!
Attachment #147278 - Attachment is obsolete: true

Updated

14 years ago
Attachment #152357 - Flags: superreview?(dbaron)
Attachment #152357 - Flags: review+

Updated

14 years ago
Attachment #147278 - Flags: superreview?(bernd_mozilla)
Attachment #147278 - Flags: review?(bernd_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.
Attachment #152357 - Flags: superreview?(dbaron) → superreview+
(Reporter)

Comment 15

14 years ago
Checked in
Status: NEW → RESOLVED
Last Resolved: 14 years ago
Resolution: --- → FIXED
You need to log in before you can comment on or make changes to this bug.