Closed Bug 270392 Opened 20 years ago Closed 17 years ago

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

Categories

(Core :: Layout: Floats, defect)

x86
All
defect
Not set
critical

Tracking

()

RESOLVED FIXED
mozilla1.9alpha1

People

(Reporter: ervin.nemeth+org.mozilla.bugzilla, Assigned: bzbarsky)

References

(Blocks 1 open bug, )

Details

(Keywords: hang, perf)

Attachments

(4 files)

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:
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.
Component: General → Layout: Floats
OS: Linux → All
Product: Firefox → Browser
Version: unspecified → Trunk
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
Flags: blocking-aviary1.1?
unless this is widespread, I don't think we'd block on it.
Flags: blocking-aviary1.1? → blocking-aviary1.1-
Blocks: 267233
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"
*** Bug 267233 has been marked as a duplicate of this bug. ***
Keywords: hang
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. ***
WFM Mozilla/5.0 (Windows; U; Windows NT 5.0; en-US; rv:1.9a1) Gecko/20050828
Firefox/1.6a1
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.
Attached file 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
Flags: blocking1.9?
Whiteboard: [wanted-1.9]
Attached patch Proposed fixSplinter Review
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.
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
Closed: 17 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?
Summary: [FIX]Firefox hangs on this page → [FIX]Firefox hangs on a page that contains thousands of float:left images
Depends on: 368330
Flags: wanted1.9+
Whiteboard: [wanted-1.9]
You need to log in before you can comment on or make changes to this bug.