Closed Bug 77114 Opened 19 years ago Closed 19 years ago

GetPrimaryFrameFor has O(N) search -> ContentAppended O(N^2)

Categories

(Core :: Layout, defect)

x86
Linux
defect
Not set

Tracking

()

RESOLVED DUPLICATE of bug 109428
mozilla0.9.7

People

(Reporter: dbaron, Assigned: dbaron)

References

(Blocks 2 open bugs, )

Details

(Keywords: perf)

In bug 56432, waterson wrote:
> - In FrameManager::GetPrimaryFrameFor(), beware that nsIContent::IndexOf()
>   does a linear scan through children. This may cause grief; e.g., on LXR
>   pages where there is high fan-out.

I just profiled loading of 
http://lxr.mozilla.org/seamonkey/source/layout/html/style/src/nsCSSFrameConstructor.cpp
and that call to IndexOf was 1617/4670 (about one third) of the time spent
loading the page.  The calls were from PresShell::ContentAppended, which is
presumably called a number of times proportional to the length of the content.
*** Bug 94890 has been marked as a duplicate of this bug. ***
From bug 94890:

In looking through jprof's of loading large pages, I found that one hotspot was
that we are calling GetPrimaryFrameFor() a lot from within ContentAppended in
order to possibly restore frame positions, etc if this is a Back (or forward I'd
guess).  However, we seem to be doing it even when we're not going back and
forward, and GetPrimaryFrameFor is somewhat expensive to call this much due to
use of IndexOf.  Avoiding calling it except on back/forward would be good, and
finding a way to call it less often when we do need it would be good (on
reflows?)

Note the comments in nsPresShell::ContentAppended() about how this applies if
session history exists.  I _think_ (correct me if we're wrong) that this does
nothing unless there's back/forward state to restore, so perhaps there's an
early out?

This hits performance all over the place, especially on large documents, and
apparently also on activations, etc.
Blocks: 71874
I didn't realize this was for session history.  It's yet another reason we
should be storing form control state in the content model...
See the attachment to bug 86947; GetPrimaryFrameFor() (and IndexOf) ended up
using around 30% of the CPU time to load a 3.3MB jprof file.

http://bugzilla.mozilla.org/attachment.cgi?id=49342&action=view
-> dbaron for 0.9.7
Assignee: karnaze → dbaron
Target Milestone: --- → mozilla0.9.7
Note in bug 54542, loading a large table is spending 58%(!!!) of it's time in
GetPrimaryFrameFor().
But the whole problem here is that we ought not be restoring frame state anymore
(whoever added this code didn't understand how the laziness in the PF map
works). Work done to move form control state into the DOM should obviate the
need to GPFF on ContentAppended. See bug 109428.
*** Bug 108951 has been marked as a duplicate of this bug. ***

*** This bug has been marked as a duplicate of 109428 ***
Status: NEW → RESOLVED
Closed: 19 years ago
Resolution: --- → DUPLICATE
You need to log in before you can comment on or make changes to this bug.