The default bug view has changed. See this FAQ.

[FIX]Firefox hangs on a page that contains thousands of float:left images

RESOLVED FIXED in mozilla1.9alpha1

Status

()

Core
Layout: Floats
--
critical
RESOLVED FIXED
13 years ago
9 years ago

People

(Reporter: Ervin Németh, Assigned: bz)

Tracking

(Blocks: 1 bug, {hang, perf})

Trunk
mozilla1.9alpha1
x86
All
hang, perf
Points:
---
Dependency tree / graph
Bug Flags:
blocking-aviary1.5 -
wanted1.9 +
in-testsuite ?

Firefox Tracking Flags

(Not tracked)

Details

(URL)

Attachments

(4 attachments)

(Reporter)

Description

13 years ago
User-Agent:       Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.7.5) Gecko/20041116 Firefox/1.0
Build Identifier: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.7.5) Gecko/20041116 Firefox/1.0

The above URL makes Firefox eat 100% CPU. After 2 minutes I've given up that
Firefox will ever display it.

Both Linux and Windows versions affected.

Reproducible: Always
Steps to Reproduce:
Created attachment 166757 [details]
Zipped testcase (partly stripped down)

I've reduced the html of that page.
The url testcase consists of >12000 left floating images. I've reduced it to
something like 2000 left floating images. This is still slow in Mozilla.
So I think that a lot of floating images are slowing down the rendering of
Mozilla. Also resizing becomes very slow.
I've tried replacing the images with left floating divs (with a size common to
most images), but that doesn't seem quite as slow.

Updated

13 years ago
Component: General → Layout: Floats
OS: Linux → All
Product: Firefox → Browser
Version: unspecified → Trunk

Updated

13 years ago
Assignee: firefox → nobody
Keywords: perf
QA Contact: firefox.general → core.layout.floats
Profiling the original page, I get:

Total hit count: 319255
Count %Total  Function Name
179913   56.4     nsSpaceManager::GetNextBand(nsSpaceManager::BandRect const*) const
42424   13.3     nsSpaceManager::GetFrameInfoFor(nsIFrame*)
4771   1.5     nsSpaceManager::GetBandData(int, nsSize const&, nsBandData&) const
4105   1.3     __libc_calloc
3668   1.1     nsSpaceManager::InsertBandRect(nsSpaceManager::BandRect*)
3515   1.1     sem_unlink

etc.

The main callers of GetNextBand are:

 104808 nsSpaceManager::GetBandData
  68630 nsSpaceManager::InsertBandRect

The main caller of GetFrameInfoFor is nsSpaceManager::AddRectRegion, called from
nsBlockReflowState::RecoverFloats and nsBlockReflowState::FlowAndPlaceFloat.

The GetFrameInfoFor() call looks like it's just trying to catch an error on the
caller's part and bail out.  Perhaps it should become an assertion?  I'm not
sure what the state of the caller is (that is, whether we can sufficiently trust
caller to not screw up).

For GetNextBand(), I don't have good ideas offhand....  Are bands sorted in some
reasonable way?  If so, could we store some sort of "last band we looked at"
cursor similar to what we do to lines in blockframe and use that instead of the
linear walks we do now?
Status: UNCONFIRMED → NEW
Ever confirmed: true
(Reporter)

Updated

12 years ago
Flags: blocking-aviary1.1?

Comment 3

12 years ago
unless this is widespread, I don't think we'd block on it.
Flags: blocking-aviary1.1? → blocking-aviary1.1-

Updated

12 years ago
Blocks: 267233
(Reporter)

Comment 4

12 years ago
Just a new notice: it seems gcc 3.4.3 is like wonder. On my Gentoo box Firefox
shows the above page in less the 20 seconds.

Pentium M 1.8GHz, CXXFLAGS used: "-pipe -march=pentium-m -mmmx -msse -msse2
-mfpmath=sse -O2 -funroll-loops -funswitch-loops -fprefetch-loop-arrays
-finline-functions -finline-limit=24 -frename-registers -fweb
-maccumulate-outgoing-args -fno-align-jumps -fno-align-loops -fno-align-labels
-fomit-frame-pointer -fmove-all-movables -ftracer -funit-at-a-time
--param=max-unrolled-insns=16 --param=max-unswitch-insns=24
--param=max-reload-search-insns=256 -fconserve-space"

Comment 5

12 years ago
*** Bug 267233 has been marked as a duplicate of this bug. ***

Updated

12 years ago
Keywords: hang

Updated

12 years ago
No longer blocks: 267233
*** Bug 304040 has been marked as a duplicate of this bug. ***
*** Bug 304837 has been marked as a duplicate of this bug. ***

Comment 8

12 years ago
WFM Mozilla/5.0 (Windows; U; Windows NT 5.0; en-US; rv:1.9a1) Gecko/20050828
Firefox/1.6a1

Comment 9

12 years ago
I can reproduce this using Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US;
rv:1.9a1) Gecko/20050828 Firefox/1.6a1. It loads under 10sec in ie on my
machine.  Maybe Michael Stolovitzsky just has a very fast machine!? 
Blocks: 305045
Things have definitely improved. In current trunk build, the page is hanging Mozilla appr. 10 seconds, while in a 1.8.1 build it is hanging Mozilla more like 1 minute.
Created attachment 249077 [details]
ZIP of original page

I took out the <link> and <script> that pointed to 404s...
So I reprofiled that original page.  I get 91% of the time spent in nsSpaceManager::GetNextBand.  Again, the main callers are InsertBandRect and nsSpaceManager::GetBandData (mostly the former).

So I bet the issue here is that all the band rects involved have the same mTop, or close enough, so every call to GetNextBand has to walk the entire list... In particular, every call to InsertBandRect() walks the entire list, so building up the list is O(N^2).

David, Robert, band rects are doubly-linked... would it make more sense for us to walk the list backwards instead of forwards in nsSpaceManager::InsertBandRect?  I'd think during pageload insertion at the end would be the common thing to do, and at other times it's equally bad no matter which direction we go unless we do some sort of binary search thing.
Flags: blocking1.9?
Blocks: 350228
Sounds reasonable.
Flags: blocking1.9?
Whiteboard: [wanted-1.9]
Created attachment 252488 [details] [diff] [review]
Proposed fix

So I tried doing the "start at end" thing, and that helps with nsSpaceManager::InsertBandRect, but not with nsSpaceManager::GetBandData.

Then I recalled comment 2, and tried doing the cursor thing.  That helps a lot!

For comparison purposes, with this page the full pageload takes 258905 hits.  Of those, 235 are in nsSpaceManager::GetNextBand.  There are 3249 hits under nsSpaceManager::InsertBandRect and 889 hits under nsSpaceManager::GetBandData.

Without this patch, a partial pageload (I got tired of waiting) takes 1477391 hits, with 1193649 of them in nsSpaceManager::GetNextBand.
Assignee: nobody → bzbarsky
Status: NEW → ASSIGNED
Attachment #252488 - Flags: superreview?(roc)
Attachment #252488 - Flags: review?(roc)
Summary: Firefox hangs on this page → [FIX]Firefox hangs on this page
Target Milestone: --- → mozilla1.9alpha
Comment on attachment 252488 [details] [diff] [review]
Proposed fix

This looks good, but I can't help feeling that nsSpaceManager needs to be rewritten to be simpler.
Attachment #252488 - Flags: superreview?(roc)
Attachment #252488 - Flags: superreview+
Attachment #252488 - Flags: review?(roc)
Attachment #252488 - Flags: review+
... since I think we don't really need a lot of its functionality. For what we currently use it for, I think we could get by with a list of available-space rectangles which are do not overlap vertically and are in fact vertically contiguous. Even with a very large number of floats in the page, this list would normally only have a few rectangles in it.
Created attachment 252502 [details] [diff] [review]
With some minor tweaks

The previous version didn't maintain the "beginning of band" invariant correctly on some insertions.
Attachment #252502 - Flags: superreview?(roc)
Attachment #252502 - Flags: review?(roc)
Comment on attachment 252502 [details] [diff] [review]
With some minor tweaks

Like if you insert a new rect at the start of a band?
Attachment #252502 - Flags: superreview?(roc)
Attachment #252502 - Flags: superreview+
Attachment #252502 - Flags: review?(roc)
Attachment #252502 - Flags: review+
Yeah, precisely.  ;)
Checked in.
Status: ASSIGNED → RESOLVED
Last Resolved: 10 years ago
Resolution: --- → FIXED
I should note that we still take some time to load the page ('cause it's pretty big), but we never hang.   And "some time" is about 15-20 seconds on my pretty slow machine.
Flags: in-testsuite?

Updated

10 years ago
Summary: [FIX]Firefox hangs on this page → [FIX]Firefox hangs on a page that contains thousands of float:left images

Updated

10 years ago
Depends on: 368330
Flags: wanted1.9+
Whiteboard: [wanted-1.9]
Duplicate of this bug: 305045
You need to log in before you can comment on or make changes to this bug.