350228 - Using floats to paint pictures is slow

Status: NEW

(Core :: Layout: Floats, defect)

Description

[Imre Péntek]

User-Agent:       Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.8.0.6) Gecko/20060809 Firefox/1.5.0.6
Build Identifier: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.8.0.6) Gecko/20060809 Firefox/1.5.0.6

firefox hangs when trying to load this page

Reproducible: Always

Comment 1

[Mats Palmgren (inactive)]

The URL is 7.5Mbyte big and the bandwidth I get from the site is
on average 15Kbyte/s (the problem is not on my side - I have a
100Mbit/s connection). So to see the problem, the first step is
to download the page to disk.

The page consists of 300 <div> blocks each containing 300 floats
(1px x 1px), totalling 90000 floats. (It reminds me of Hixie's
cat image painted with table cells IIRC).
This page renders the Mandelbrot set if you have the patience.

When loading the page from disk it took about 35 minutes for it
to render on a (rather crappy) IBM X31 laptop, Firefox 2.0b2 Linux.
This is too slow IMO. The memory consumption was about 190MB.
Starting Firefox with about:blank takes about 70MB so 120MB
seems to be what it took to render the page, which I guess is ok
(~1.33kB per float).

Comment 2

[Boris Zbarsky [:bzbarsky]]

Attachment: Testcase as zip file containing test.html

Comment 3

[Boris Zbarsky [:bzbarsky]]

Attachment: Profile

Comment 4

[Boris Zbarsky [:bzbarsky]]

The part of the profile that screams O(N^2) to me is this:

Total hit count: 1311396
Count %Total  Function Name
694792   53.0     nsSpaceManager::GetNextBand(nsSpaceManager::BandRect const*) const
264613   20.2     nsSpaceManager::GetFrameInfoFor(nsIFrame*)

The GetFrameInfoFor part will go away in bug 349113.

The GetNextBand part is called from nsSpaceManager::GetBandData, ultimately called from nsBlockBandData::GetAvailableSpace, and from nsSpaceManager::InsertBandRect, called ultimately from nsBlockReflowState::FlowAndPlaceFloat.  Same thing on reflow branch, basically.

Comment 5

[Boris Zbarsky [:bzbarsky]]

I bet in this case the whole thing is one band.  Would it make sense to keep a pointer to the next band around or something?

Comment 6

[Tony Spencer]

Attachment: Another, Smaller Testcase as a zip file

I ran into what looks like the same problem. This page loaded in this test case isn't nearly as large as the first, only about 500Kb. 

The only difference between the two files is that in tescase_broken.html, there is a float:left CSS rule around the image blocks, and in testcase.html that line is commented out. They both render the same, but testcase.html takes 2-3 seconds while testcase_broken.html takes about 3.5 minutes to load. 

My User Agent:
Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.8.1) Gecko/20060601 Firefox/2.0 (Ubuntu-edgy) ... but also always reproducible with Firefox 2.0 on OSX and Windows

Comment 7

[Boris Zbarsky [:bzbarsky]]

The original bug here is very similar (to the point of probably being a duplicate) to bug 270392.

Tony, the testcase you attached doesn't show the same problem at all; it looks like a completely different issue.  I'd file a separate bug on it and cc me on the new bug.

Comment 8

[Boris Zbarsky [:bzbarsky]]

OK, I did a profile now that bug 270392 has landed.

13% of the time is spent in nsSpaceManager::AddRectToBand.  I bet if we did the "search from the end" thing that I was considering doing in bug 270392 this would be faster.  But it might be better to just redesign the space manager, as roc was suggesting.

10% of the time is spent under __libc_malloc.  The callers are about evenly split between nsScannerBufferList::AllocBuffer (filed bug 368015) and allocation of frameinfos and band rects in nsSpaceManager.  Again, we might want to just simplify space manager.

About 10% of the time is spent parsing "style" attributes.  I'm not going to worry about it, since the page is being pretty silly about the CSS -- it should use just two rules and classes and it would be _much_ faster.

From a higher level, about 50% of the time is spent under reflow (that's including the nsSpaceManager::AddRectToBand stuff), about 30% in parsing and frame construction, about 5% in painting.  Filed bug 368018 on painting being slow even once the page finishes loading.

Comment 10

[Mats Palmgren (inactive)]

Attachment: Testcase from bug 371885

Comment 11

[Jingshao Chen]

I updated the testcase page from bug 371885. 

Comment 12

[Jingshao Chen]

Attachment: an updated version of a small testcase from bug 371885.

I found last attachment of the testcase from 371885 is not working under IE. I revised it and attached a more up to date one here. 

You can easily reproduce the performance problem I saw with this small testcase.

Comment 13

[Boris Zbarsky [:bzbarsky]]

Actually, bug 371885 is pretty different from this bug.  A trunk profile shows almost all the time being spent under nsBlockBandData::GetAvailableSpace; flat profile top is:

Total hit count: 190553
Count %Total  Function Name
122635   64.4     nsSpaceManager::GetPrevBand(nsSpaceManager::BandRect const*) const
40490   21.2     nsSpaceManager::GetNextBand(nsSpaceManager::BandRect const*) const

That's the sort of thing that doesn't come up in the testcase in this bug at all; it was fixed in bug 270392.  The reason you get this sort of behavior is because of all the gaps in the bands; something that really will not happen in a "paint images using floats as pixels" scenario, which is what this bug is about.

I'm going to reopen bug 371885.

Comment 14

[Thorin [:thorin]]

boris: ... aaaand 14 years later, the test takes approx 2 seconds for me

Comment 15

[Thorin [:thorin]]

(In reply to Simon Mainey from comment #14)

boris: ... aaaand 14 years later, the test takes approx 2 seconds for me

should have mentioned that is on Nightly 88, windows, on a 10yr old PC