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

Status: RESOLVED DUPLICATE of bug 109428

(Core :: Layout, defect)

Description

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

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.

Comment 1

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

See bug 63890.

Comment 2

[Randell Jesup [:jesup] (needinfo me)]

*** Bug 94890 has been marked as a duplicate of this bug. ***

Comment 3

[Randell Jesup [:jesup] (needinfo me)]

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.

Comment 4

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

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...

Comment 5

[Randell Jesup [:jesup] (needinfo me)]

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

Comment 6

[Cathleen]

-> dbaron for 0.9.7

Comment 7

[Randell Jesup [:jesup] (needinfo me)]

Note in bug 54542, loading a large table is spending 58%(!!!) of it's time in
GetPrimaryFrameFor().

Comment 8

[Chris Waterson]

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.

Comment 9

[Kevin McCluskey (gone)]

*** Bug 108951 has been marked as a duplicate of this bug. ***

Comment 10

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

*** This bug has been marked as a duplicate of 109428 ***