675417 - Firefox hangs while rendering a border-collapse table with many rows containing a cell with large colspan

Status: NEW

(Core :: Layout: Tables, defect, P3)

Description

[Esa Peuha]

User Agent: Mozilla/5.0 (Windows NT 5.1; rv:5.0) Gecko/20100101 Firefox/5.0
Build ID: 20110615151330

Steps to reproduce:

I visited the web page at http://www.kansalliskirjasto.fi/extra/linnea2/kirjastotunnukset.htm


Actual results:

Firefox became completely unresponsive to user input.


Expected results:

Firefox should let me go back to previous page or close Firefox.

Comment 1

[Thomas Ahlblom]

Thanks for reporting!

Reproduced: (Hangs forever?)
Mozilla/5.0 (X11; Linux x86_64; rv:5.0.1) Gecko/20100101 Firefox/5.0.1
Mozilla/5.0 (X11; Linux x86_64; rv:6.0) Gecko/20100101 Firefox/6.0
Mozilla/5.0 (X11; Linux x86_64; rv:7.0a2) Gecko/20110729 Firefox/7.0a2
Mozilla/5.0 (X11; Linux x86_64; rv:8.0a1) Gecko/20110730 Firefox/8.0a1

Hangs initially, but releases after a while:
Mozilla/5.0 (X11; U; Linux i686 (x86_64); en-US; rv:1.9.2.19) Gecko/20110707 Firefox/3.6.19
Opera/9.80 (X11; Linux x86_64; U; en) Presto/2.9.168 Version/11.50

WFM (no hang at all):
Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/534.30 (KHTML, like Gecko) Chrome/12.0.742.112 Safari/534.30

In Firefox it does not matter if I start in Safe Mode or if I disable JavaScript - it hangs anyway.

Comment 2

[Thomas Ahlblom]

This frame file has 38053 lines of code:
http://www.kansalliskirjasto.fi/extra/linnea2/kirjastotunnukset_files/sheet001.htm

35898 of the lines contain '<td' and a huge number of them look like this one:
<td width=64 style='width:48pt'></td>
Or like this one:
<td class="xl68" width="64" style="width:48pt"></td>


Maybe Firefox gets a little bit overwhelmed by the table?

Comment 3

[Thomas Ahlblom]

This is not an orthodox hang. Firefox is just a little bit slow. ;)

Firefox 7 needs about 9 minutes to render the page on a fast computer and then gives the browser control back to the user.

Chromium gives the control back within a fraction of a second and renders the page in something like 9 seconds.

So Firefox is approximately 60 times slower than Chromium.

Comment 4

[Mats Palmgren (inactive)]

It appears the slow path is:

nsCellMap::AppendCell (..., aRowIndex=107 ...
BCMapCellIterator::PeekBottom (...,, aColIndex=12880, ....
nsTableFrame::CalcBCBorders
nsTableFrame::GetIncludedOuterBCBorder
nsCSSOffsetState::InitOffsets
nsCSSOffsetState
nsBlockFrame::WidthToClearPastFloats
nsBlockReflowState::ComputeBlockAvailSpace
nsBlockFrame::ReflowBlockFrame

The table has 706 <tr>s, 5 <td>s per row, the 5th <td> has colspan=16380.

I suspect we do nsCellMap::AppendCell 16380 * 706 times...

Related to bug 357729?

Comment 5

[Mats Palmgren (inactive)]

Attachment: zipped testcase

Zipped the file containing the table for posterity.  Original URL:
http://www.kansalliskirjasto.fi/extra/linnea2/kirjastotunnukset_files/sheet001.htm

Comment 6

[Mats Palmgren (inactive)]

The table has style border-collapse:collapse; if I remove that then it renders
in a couple of seconds.

Comment 7

[Boris Zbarsky [:bzbarsky]]

Right; that makes us not enter the BCMapCellIterator code....

And yes, it sounds like we're appending a cell to the cellmap for each row*(logical column), which is generally correct conceptually.  Do we not end up appending those cells in the non-BC case at all?  Or is it just a matter of cellmap entries being much smaller and simpler when BC is not involved?

Comment 8

[Bernd]

I guess here kicks the colspan limit in first, then the cell does not span enough cells, it creates cellmap holes from 1000 to 16380. Under separated mode this is not of importance but under BC we fill the cell with dead cell map entries 15380 roughly for every row and that is slow.

Comment 9

[Boris Zbarsky [:bzbarsky]]

Oh, wait.  You mean we don't apply the colspan limit when deciding on the cellmap sizing???  That would be the bug, no?

Comment 10

[Bernd]

we apply the colspan limit and that later causes the necessity of repair

Comment 11

[Bernd]

http://mxr.mozilla.org/mozilla-central/source/content/html/content/src/nsHTMLTableCellElement.cpp#283

Comment 12

[Boris Zbarsky [:bzbarsky]]

I don't understand.  That code treats colspan="something really big" as colspan="1", right?  So why do we end up having to do cellmap repair or ending up with a big cellmap?

Comment 13

[Bernd]

ASCII paint

just imagine that the last cell needs to look up its lower neighbour

without  colspan clamp

cell cell    cell     cell      ...16000 times ... cell
cell colspan colspan  colspan   ...16000 times ... colspan

it will see a colspan goes to the left and finds the originating cell with its style information

with colspan clamp

cell cell    cell     cell      ...16000 times ... cell
cell 

it will see nothing, hmmm this might be a zero colspan lets walk left
it walks every entry until it finds that there is the first cell without a corresponding colspan

after BC repair

cell cell    cell     cell      ...16000 times ... cell
cell dead    dead     dead      ...16000 times ... dead      

now it will see a dead cell, OK, there is certainly no 0 colspan, lets do the computation without a neighbour.

from the html 5 spec

"The td and th elements may have a colspan content attribute specified, whose value must be a valid non-negative integer greater than zero."

so we might not need that repair mechanism anymore...

Comment 14

[Boris Zbarsky [:bzbarsky]]

I hadn't realized that the testcase actually had 16000-some cells in that first row.  That certainly explains the behavior!  That'll also teach me to actually look at the testcase.  So the colspan limit is actually breaking this layout (assuming it's not just broken to start with; it's trying to stick 16380 cells each one 48pt wide into a single <col> that's 48pt wide).  Fun.

We can certainly talk about removing zero colspans.  I'm not sure anyone else ever implemented them, and of course a browser that doesn't support zero colpans can do this particular testcase faster than we can.

Bernd, are you OK with getting rid of that feature, in general?  Seems like it would simplify things a bit.

Comment 15

[Bernd]

#define COL_SPAN_OFFSET  0xFFF80000 which is then shifted down
shows that we in principle handle only 13 bits of colspan information, that is 8190, which is also the max row span that we do correctly. 

While it hurts to see code go where a lot of effort has been spent to get it working I have to admit that I haven't seen a new table fan, so any code simplification is a strong argument.

To my knowledge the 0 colspan is Gecko only (webkit opera and ie certainly don't do this). I believe this was the reason to remove it from the html5 spec.

Comment 16

[Bernd]

The connection to 0 colspans is bogus. We need the dead cells because we might want to store BC information on them as those dead cells might border to real cells. We store only the left and upper border for each entry so a dead cell that is below a real cell will contain the information about the bottom border of the real cell above.

Comment 17

[Boris Zbarsky [:bzbarsky]]

Hmm.  I wonder whether we can somehow break up that colspan into individual cells lazily (i.e. if we discover that there are multiple cells that fall into the colspan in rows below) somehow...

Comment 18

[Bernd]

>somehow break up
I am not sure that putting a lot of effort into the current BC code is really a move in to the right direction, in principle the BC code needs a rewrite  but bug 452319 and bug 540256 haven't seen any real work other than my refactoring but a lot of broken promises.

Comment 19

[Sebastian Zartner [:sebo]]

The test case in comment #0 renders in less than a second for me using Firefox 33.1.1 on Win7 64-bit.
Is that still an issue?

Sebastian

Comment 20

[Alice0775 White]

Nightly became completely unresponsive with Attachment of Comment #5

Comment 21

[Sebastian Zartner [:sebo]]

You're right. That test case causes Firefox to hang. With e10s enabled the browser does not hang, though the page doesn't load.
Though also Chrome has its trouble with displaying that huge table. It's taking ~20s seconds to display it.

Sebastian

Comment 22

[Sebastian Zartner [:sebo]]

[Tracking Requested - why for this release]:

Just tested this with Nightly 57.0a1 (2017-08-24) with enabled Stylo and e10s and while the page doesn't hang the browser anymore, the page still doesn't load at all.

I've also tested it in Chrome Canary 62.0 and there it is now loaded super fast (like half a second).

Sebastian

Comment 23

[Jonathan Watt [:jwatt]]

Mass bug change to replace various 'parity' whiteboard flags with the new canonical keywords. (See bug 1443764 comment 13.)

Comment 24

[c.buhtz]

I am wondering what the current with the current Firefox version and ESR version is.

Can we close this?

Comment 25

[Sebastian Zartner [:sebo]]

For me, the attached test case now needs two to three minutes to load in Firefox 91.0.2 while in Chrome 92.0.4515.159 it still loads very fast. I.e. the DOMContentLoaded event is fired after about 1.5 seconds in Chrome in comparison to about 120-170 seconds in Firefox. This is with WebRender enabled, btw. I've also tried it in Nightly 93.0a1 (2021-08-27) with Fission enabled with basically no difference.

So Firefox's UI doesn't hang anymore like earlier comments indicated, though the slowness is definitely still a big issue.
I assume, this still waits for the rewrite of the related code mentioned in comment 18 / bug 540256.

Sebastian

Comment 26

[c.buhtz]

In the case that Firefox does not "hang" anymore I would take the bug as fixed recommend to close it.

Comment 27

[Boris Zbarsky [:bzbarsky]]

The UI process does not hang, but the renderer process still hangs, right?