Closed Bug 77114 Opened 19 years ago Closed 19 years ago
Primary Frame For has O(N) search -> Content Appended O(N^2)
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.
See bug 63890.
*** 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.
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.