Closed Bug 85755 Opened 23 years ago Closed 22 years ago

nsCellMap::AppendCell has a O(n^2) algorithm

Categories

(Core :: Layout: Tables, defect)

defect
Not set
normal

Tracking

()

RESOLVED FIXED
mozilla1.1beta

People

(Reporter: bratell, Assigned: bernd_mozilla)

References

(Depends on 1 open bug)

Details

(Keywords: perf, Whiteboard: [awd:tbl])

Attachments

(2 files, 4 obsolete files)

I continued looking at the table stress case to find more performance things.

There I noted that nsCellMap::GetMapCellAt is called 500000 times for the table 
with 10000 cells. This is because every row is walked from the beginning looking 
for where to insert the cell. For a RxC table every row is at average C/2 
filled so the time to get the cell is O(C^2) where C is the width of the table.

Is there any better way to find the cell then linear search? Remember the last 
position? Binary search?

Right now this is ~1% of the time to display that page but I can easily 
construct a table where this would take a majority of the time (like a very wide 
table). No really big deal but every percent counts.
That should be O(RxC^2) (but we can say that I considered the height (R) to be 
constant).
Keywords: perf
Whiteboard: [awd:tbl]
Target Milestone: --- → mozilla0.9.6
I thought 0.9.6 was released some time ago? (Regarding yesterday's change of 
milestone)
0.9.6 is long gone. -> 0.9.7
Target Milestone: mozilla0.9.6 → mozilla0.9.7
chances to get this into 0.9.7 ?
I think we need more test cases and/or urls before investing effort in this bug. 
A 1% savings on an artifical test case is not much motiviation. Moving to m1.1.
Status: NEW → ASSIGNED
Target Milestone: mozilla0.9.7 → mozilla1.1
I wish I could remember the URL to soros' page that built an image with a table
cells. I think that one must be hurt by this bug, but I don't know how much.

I don't think this bug is very hard to fix, but I won't say that your priorities
aren't right. There's probably many performance bugs affecting more pages than this.
Blocks: 54542
Could be a testcase:
http://tite.cs.tut.fi/~ruffe/urlit/

I don't really know what exactly causes Mozilla to render this page so
slowly (~65 sec. on AMD 1000) compared to other browsers (Opera and
IE render it in 3-5 sec.)
~38% direct, 57% total are in FindFrameWithContent (called from
GetPrimaryFrameFor).  I hate GPFF.
Keywords: mozilla0.9.9
Tested http://tite.cs.tut.fi/~ruffe/urlit/ again with 0.9.8.
It now loads in 10 secs. Great improvement!
hm, the URL no longer exists - any backups somwhere?
Keywords: mozilla0.9.9mozilla1.1
Target Milestone: mozilla1.1alpha → mozilla1.1beta
Depends on: 115049
For the binary search suggestion; is the code to be replaced currently at line
1152 in nsCellMap.cpp? In that case I have a draft that does binary search
instead of that linear search.

Are we guaranteed that there will be no holes in the data cells in the table?
I tried this on http://www.mozilla.org/newlayout/testcases/stress/. It seems to
render things correctly. Could someone quantify this?
+  PRInt32 tmp = 0;

That should be |PRInt32 tmp;|, it gets initialized a few lines below. Sorry.
Keywords: review
This bug has a patch. The last comment is from July.
Is anybody still working on it?
Maybe we can get this into 1.3b ?
Keywords: mozilla1.1mozilla1.3
Comment on attachment 92104 [details] [diff] [review]
Use binary search instead of linear search.

>+  PRInt32 hi = origNumCols;
>+  PRInt32 lo = 0;
>+  PRInt32 tmp = 0;
>+  CellData* data;
>+
>+  // Find the first empty element. It will equal
>+  // origNumCols if there are none.
>+  while (lo < hi) {

Canonical binary search should use hi = origNumCols - 1 and loop while (lo <=
hi).  Otherwise (not that it matters here), searching [1,5,3,4] for 2 would
wrongly find 2 at index 1, when in fact 5 is there.

But can't we do even better here?  How does a data element become dead?  Could
we not maintain a low-watermark index of the first empty or dead element when a
data element dies?

>+    tmp = (lo + hi) / 2;
>+    data = GetDataAt(aMap, aRowIndex, tmp, PR_TRUE);
>+
>+    if ((!data) || data->IsDead()) {

Nit: don't overparenthesize !data.

>+      // We can insert here - cut right half.
>+      hi = tmp;

Note: hi = tmp - 1; in canonical binary search, but it's ok here.

/be
I wrote:

> Canonical binary search should use hi = origNumCols - 1 and loop while (lo <=
> hi).  Otherwise (not that it matters here), searching [1,5,3,4] for 2 would
> wrongly find 2 at index 1, when in fact 5 is there.

That's an error case, to be sure (the array isn't sorted), but replace 5 by 1.5
to get a valid input such a broken binary search would wrongly succeed in
"finding" 2 at index 1, without actually comparing 2 to 1.5 and failing.

/be
Status: ASSIGNED → RESOLVED
Closed: 22 years ago
Resolution: --- → FIXED
brendan: how did this bug magically without r/sr solved?
Status: RESOLVED → REOPENED
Resolution: FIXED → ---
The patch needs to be run through the regression tests, something I do not have
time to do at the moment. If anyone has the time to do so then feel free to.

As for the watermarking, I looked at that possibility when I did the patch, this
patch is less invasive than that though I believe. It is an improvement over
what we had in July (O(nlog(n)) instead of O(n^2)), whether it is worth the work
is not really my call. 
Sorry, I must have fat-fingered the FIXED option somehow.

/be
Status: REOPENED → ASSIGNED
The patch is not correct, there is no guarantee for a hole free cellmap. The
following table will create a hole after cell4.

<table border="1">
<tr><td>cell1</td><td>cell2</td><td rowspan="2">cell 3</td></tr>
<tr><td>cell4</td></tr>
</table>

I can't see how binary search will help you to find a zero in the following
sequence: 1111111011111

A real performance gain is only achievable when some sort of more intelligent
vectorizing is applied when adding whole rows to the cellmap. 

>The patch needs to be run through the regression tests.
This is only a necessary condition to get a review in the table code land,
because it says you guarantee that you looked after all possible regressions
that could have been prevented before checkin. Passing the regression tests does
not prove the correctness of a patch. 
->default owner
Assignee: karnaze → table
Status: ASSIGNED → NEW
Attached patch patch (obsolete) — Splinter Review
The attached patch uses a pointer to minimize the search. It reduces the number
of calls from 630000 to 130000 for the wbtbltxt.html testcase. The calling
count code is commented out. The saving of 0.5 Mio function calls gives a non
measurable performance boost in my debug build. In other words	Chris was
probably right with his prognose: "A 1% savings on an artifical test case is
not much motiviation." May be btek will recognize it.
Attachment #92104 - Attachment is obsolete: true
Comment on attachment 109933 [details] [diff] [review]
patch

chris/brendan could you please r/sr, I will certainly remove the debug code
before checking in
Attachment #109933 - Flags: superreview?(brendan)
Attachment #109933 - Flags: review?(karnaze)
Comment on attachment 109933 [details] [diff] [review]
patch

>@@ -1179,8 +1180,10 @@
> 
>   // get the first null or dead CellData in the desired row. It will equal origNumCols if there are none
>   CellData* origData = nsnull;
>-  PRInt32 startColIndex;
>-  for (startColIndex = 0; startColIndex < origNumCols; startColIndex++) {
>+  PRInt32 startColIndex =0;
>+  if(aStartIndex)
>+    startColIndex = *aStartIndex;

Please use prevailing style: if (, not if(.  Same comment applies to the later
if(aStartIndex), excerpted below.

>+  for (; startColIndex < origNumCols; startColIndex++) {
>     CellData* data = GetDataAt(aMap, aRowIndex, startColIndex, PR_TRUE);
>     if (!data) {
>       break;

There's an else after this break, which is a non-sequitur.  Please remove it.

>@@ -1190,7 +1193,8 @@
>       break; 
>     }
>   }
>-
>+  if(aStartIndex)
>+    *aStartIndex =  startColIndex + 1; 

What if the loop found no hole or dead data item?  startColIndex will be
origNumCols in that case.  Is it safe to return origNumCols + 1 in
*aStartIndex?

/be
Attached patch patch v1.1 (obsolete) — Splinter Review
The idea in this patch is that once we have appended a cell we know that there
is no hole before. It works together with the ExpandWithRows routine, where
cellframes are consecutively added to the row. When the first cell is added to
the row in the cellmap the search should begin at 0, once it is added the next
search should start only at 1 and so for. When a cell is added which would fill
the place at the last column of origNumCols then the next search would begin
behind origNumCols and the for loop would be a NOP, the necessary columns will
be created below with

  PRInt32 endColIndex = startColIndex + colSpan - 1;
  if (endColIndex >= origNumCols) {
    aMap.AddColsAtEnd(1 + endColIndex - origNumCols);
  }
Attachment #109933 - Attachment is obsolete: true
Attached patch patch v1.2 (obsolete) — Splinter Review
Attachment #110711 - Attachment is obsolete: true
Attachment #109933 - Flags: superreview?(brendan)
Attachment #109933 - Flags: review?(karnaze)
Attachment #110714 - Flags: superreview?(brendan)
Attachment #110714 - Flags: review?(karnaze)
How about a diff -wu?

/be
Attached patch patch diff -wuSplinter Review
Attachment #111147 - Flags: superreview?(brendan)
taking the bug
Assignee: table → bernd_mozilla
Comment on attachment 110714 [details] [diff] [review]
patch v1.2

Looks ok to me -- is karnaze still working on Mozilla?

/be
Attachment #110714 - Flags: superreview?(brendan) → superreview+
Attachment #111147 - Flags: review?(karnaze)
Attachment #110714 - Attachment is obsolete: true
Comment on attachment 111147 [details] [diff] [review]
patch diff -wu

Very good! aBeginSearchAtCol sounds like a boolean. Can you change it to
aColToBeginSearch.
Attachment #111147 - Flags: review?(karnaze) → review+
Attachment #110714 - Flags: review?(karnaze)
fix checked in, btek did not drop
Status: NEW → RESOLVED
Closed: 22 years ago22 years ago
Resolution: --- → FIXED
Attachment #111147 - Flags: superreview?(brendan)
You need to log in before you can comment on or make changes to this bug.

Attachment

General

Created:
Updated:
Size: