348805 - Hang with <mtd> with large rowspan and columnspan

Status: RESOLVED WORKSFORME

(Core :: Layout: Tables, defect)

Description

[Jesse Ruderman]

Steps to reproduce:
1. Load the testcase.

Result: Firefox hangs for about 15 seconds while it allocates 300 MB.  (I don't know if this is one big allocation, or too many reallocs, or what.)

2. Close the window.

Result: Firefox hangs for about 15 seconds while it gives back about 50 MB.  About 250 MB appears to have leaked.

With more complicated testcases, I think this can easily hang for more than 15 seconds.

Comment 1

[Jesse Ruderman]

Attachment: MathML table testcase

Comment 2

[Jesse Ruderman]

Attachment: HTML table testcase

With multiple cells, HTML tables can trigger a similar hang.  I guess this isn't MathML-specific after all.

Comment 3

[Bernd]

This creates a table with 22 * 1000 = 22000 colframes a gigantic cellmap with 22*22000 = 484000 entries. of them only ca 30000 are valid cells the reminder are dead cells. There is some reason to believe that the cellmap repair mechanism is involved.

Comment 4

[Bernd]

Boris, now that the cellmap repair is gone this still hangs. Could you please profile the second testcase? If we could even determine what is leaked it would be very cool.

Comment 5

[Boris Zbarsky [:bzbarsky]]

OK, so just starting the app and loading the testcase spends a while at 100% CPU. When it's done, Mozilla is using about 600MB of RAM.  The flat jprof looks like:

Total hit count: 355908
Count %Total  Function Name
60498   17.0     memcpy
56379   15.8     __libc_malloc
50516   14.2     _int_malloc
41027   11.5     nsCellMap::SetDataAt(nsTableCellMap&, CellData&, int, int)
22316   6.3     nsCellMap::AppendCell(nsTableCellMap&, nsTableCellFrame*, int, int, nsRect&, int*)
15183   4.3     operator new(unsigned int)
13115   3.7     nsVoidArray::ReplaceElementAt(void*, int)
12515   3.5     CellData::CellData(nsTableCellFrame*)
12191   3.4     nsVoidArray::InsertElementAt(void*, int)
12004   3.4     nsTableCellMap::GetColInfoAt(int)
11178   3.1     nsCellMap::GrowRow(nsVoidArray&, int)
10606   3.0     nsCellMap::AllocCellData(nsTableCellFrame*)

Looking at the hierarchical profile, of the 355908 total hits, 351006 are under  nsTableFrame::SetInitialChildList.  Of those, 349127 are under nsCellMap::InsertRows.  Of those, 343712 are under nsCellMap::AppendCell.

AppendCell is about evenly split between nsCellMap::AllocCellData and nsCellMap::SetDataAt.  The former is basically all inside |operator new|. The latter spends about half its time under nsCellMap::GrowRow, most of that under InsertElementAt.

About as expected given that we're doing tons of tiny allocations.  :(

At a guess, the memory growth Jesse saw was heap fragmentation, not a leak.  But I'm not sure how he measured memory usage.

Comment 6

[Boris Zbarsky [:bzbarsky]]

Attachment: Profile

Comment 7

[Boris Zbarsky [:bzbarsky]]

Patch in bug 356335 helps here a little bit... The time needed goes down by about 15%.

If we could somehow allocate the celldata in bigger chunks too, that would help...  Is there any way to move from storing celldata pointers to storing actual structs?  I guess BCCellData gets in the way of that, eh?

Comment 8

[Boris Zbarsky [:bzbarsky]]

Though if we cared we could possibly handle BCCellData by simply templatizing nsCellMap on the celldata type and using the right template as needed.

If we could switch away from allocating CellData per se, we should be able to get to the point where this testcase allocates on the order of 1,000 blocks of memory instead of on the order of 24,000,000 blocks.  Granted, the 1,000 blocks will be pretty large.  But still....

The other thing to think about is an arena allocator or something for the celldata structs, maybe.

Comment 9

[Bernd]

If we could somehow allocate the celldata in bigger chunks too, that would
help...

We could allocate all cellmap entries that are caused by a single content cell and then distribute those entries to the cell map. I am very skeptical that this will not hurt for the general <td> with row- and colspan = 1. I am not convinced that we should trade typical performance for this case. 

Comment 10

[Boris Zbarsky [:bzbarsky]]

> We could allocate all cellmap entries that are caused by a single content cell
> and then distribute those entries to the cell map.

Yeah, that doesn't seem worth it...

Comment 11

[Boris Zbarsky [:bzbarsky]]

OK, so I made a simple change as a test -- instead of allocating CellData structs with |operator new| I tried allocating them via AllocateFromShell() on the prescontext of the row group.  That cuts memory usage by about 50% and time by about 40% on the testcase.  That makes sense -- AllocateFromShell() doesn't have to store the memory chunk size with the chunk, while malloc does.  For CellData structs, storing the size doubles the memory needed, since the whole struct is the size of a void*.

That might be a way to go in general, but I'm still tempted to try to switch to nsTArray<CellData> instead of nsTArray<CellData*> so we don't have to allocate celldatas separately.  That should save even more space, since right now we're using at least 2*sizeof(void*) per cell, whereas we could just use sizeof(void*).  I might need to steal a bit from somewhere to mark celldatas as "null" or something, and I'd need to figure out what to do with BCCellData.  Maybe templatize nsCellMap?  That'd double the codesize, probably...

Comment 12

[Boris Zbarsky [:bzbarsky]]

So switching to not heap-allocating CellData seems like more work than I'm willing to take on right now.  It'd be good to have it happen, though... Filed bug 357729 on it.

Comment 13

[Bernd]

the test case is more or less wfm which I think is a result of bug 443089

Comment 14

[Jesse Ruderman]

The HTML testcase still hangs for a few seconds, but sure.