Closed Bug 655084 Opened 13 years ago Closed 13 years ago

Teardown of pages with large number of form controls is O(n^2) due to weakFrames

Categories

(Core :: Layout, defect)

Product:
Core
Component:
Layout
Type:
defect
Priority:
Not set
Severity:
normal

Tracking

()

Status:
RESOLVED FIXED

People

(Reporter: jesup, Assigned: jesup)

References

Details

(Keywords: perf, testcase, topperf)

Attachments

(3 files, 2 obsolete files)

weakFrame patch - rough - NOT ready for checkin
11.17 KB, patch
Details | Diff | Splinter Review
Working patch-in-progress for the Frame Properties-based approach
11.39 KB, patch
Details | Diff | Splinter Review
Final (I hope) patch using a property for EditorInitializer
17.09 KB, patch
ehsan.akhgari
: review+
Details | Diff | Splinter Review 
Spinoff of bug 352367

On pages with large numbers of form controls, all the nsWeakFrame objects end up in one big list in the PresShell.  Then, when an element is removed, it first searches the list to invalidate weakframes referencing the frame, then it removes the weakFrames when they're destroyed, and because of the tail linking this normally requires walking the entire list on each removal.

Each of these operations ends up being O(n^2).  In the really-huge form case (b6b.html) from bug 352367, there are circa 46000 nsWeakFrames in that list - or well over 2 billion node walks to tear it down.  In b6a.html (large, but not totally unreasonable) it's around 6500 (over 32M node walks).
Assignee: nobody → rjesup
Blocks: 352367
Keywords: perf, testcase, topperf
Patch cloned from bug 352367 - see discussion there
So I guess in this point we have long-lived weakframes from editor state or something?

I wonder whether it would be safe to just do a linear walk over all weakframes, invalidate them, and then clear the list when doing shutdown of the frame tree....

But in general, you could hit this with just DOM mutations on large pages.  We should probably detect non-stack nsWeakFrame and put them in a hashtable or something.
Yes, they're coming from the editor:
                          3142 (14.0%) nsTextControlFrame::DestroyFrom(nsIFrame*)
 89277      3 (0.0%)      3142 (14.0%) nsTextEditorState::UnbindFromFrame(nsTextControlFrame*)
                          3069 (13.7%) nsWeakFrame::InitInternal(nsIFrame*)

(which ends up doing RemoveWeakFrameInternal)

The thing about putting them in a hashtable (which was an initial thought of mine) is that you doing a lot of work to optimize access for something that is typically only accessed to delete it (perhaps more often to invalidate any possible weakframes, which normally don't exist). 

Complexity of implementation has a cost as well (and I'm someone who fights for bytes of footprint).  That said - a hash in the PresShell may well make sense if the footprint cost in Frames is too much, and it wouldn't be that much more complex.  

Too bad there isn't a hash-of-typed-objects (or list of typed objects) we could use to collapse a number of these sorts of occasionally-used items/lists in frames, with a query along the lines of frame->GetTypedHash(type, key) or "mWeakFrames = frame->GetTypedValue(TYPE_WEAKFRAMES)".  This would let you collapse a bunch of optional items into a single head pointer in high-use-count data structures like Frames.
Status: NEW → ASSIGNED
A thought I had to kludge this would be to invert the list before teardown, but that's an ugly hack and as mentioned DOM manipulations wouldn't be helped (and there's still ClearFrameRefs() that walks the entire list anyways).
Hmm.  The specific case of editor state could be hacked to be smarter, since in that case the frame _can_ reach the relevant nsWeakFrame.
So, what really uses weakFrames and causes them to be sitting in the PresShell?  Eliminating them (or virtually so) is even better.  :-)

Though I kindof like the frame->GetOptionalValue(type) idea - slightly more overhead than a pointer in the frame (or whatever) when it's there, and slightly more overhead to access it but no overhead when it's not (just one pointer shared by all these uses).  ((Much) less access overhead than putting it in the PresShell!)
> So, what really uses weakFrames and causes them to be sitting in the PresShell?

Those are separate questions.

We use weakFrames on the stack all over to deal with someone blowing away the world.

To sit in the presshell, they have to be on the heap; there should be fewer consumers there.
Non-stack users should (generally) be in structures/classes, so a little rooting around...

Note: just because these are in a class/struct doesn't mean they end up living in the PresShell!  These are just candidates.  Some of these are in subclasses of nsIReflowCallback.


These are pruned of obvious stack uses like "nsWeakFrame weakframe(aFrame);"

hfind nsWeakFrame
./content/base/src/nsObjectLoadingContent.h:    nsWeakFrame                 mPrintFrame;
/content/events/src/nsEventStateManager.h:  nsWeakFrame mCurrentTarget;
./content/events/src/nsEventStateManager.h:  nsWeakFrame mLastMouseOverFrame;
./content/events/src/nsEventStateManager.h:  nsWeakFrame mLastDragOverFrame;
./layout/forms/nsTextControlFrame.h:    nsWeakFrame mWeakFrame;
./layout/forms/nsFileControlFrame.h:    nsWeakFrame mFrame;
./layout/base/nsLayoutUtils.h:  nsWeakFrame mWeakFrame;
./layout/xul/base/src/nsListBoxBodyFrame.h:  nsWeakFrame mTopFrame;

cfind nsWeakFrame
./content/html/content/src/nsTextEditorState.cpp:  nsWeakFrame mFrame;
./content/events/src/nsEventStateManager.cpp:  static nsWeakFrame sTargetFrame;
./layout/generic/nsSubDocumentFrame.cpp:  nsWeakFrame mFrame;
./layout/xul/base/src/nsTextBoxFrame.cpp:    nsWeakFrame mWeakFrame;
./layout/xul/base/src/nsMenuFrame.cpp:  nsWeakFrame       mFrame;
./layout/xul/base/src/tree/src/nsTreeBodyFrame.cpp:  nsWeakFrame mFrame;

If we can make these go away, great, but I'm not seeing a simple way to do so.  (But I'm far from an expert on that currently.)

We could mass-clear the entire list at the start of destroying the PresShell - then the deletes and ClearFrameRefs would be fast - but other operations (DOM manipulation, etc) might still be very slow.
> We could mass-clear the entire list at the start of destroying the PresShell -

"maybe".  Might lead to correctness bugs.

Looking at your list, the ESM has a few weakframes and is a singleton per presshell, so should not be a problem.  The layout utils use is an nsReflowFrameRunnable; not sure how many of those can be pending.

The text and file and listbox uses there can be lots of on a page, I bet.  Same for editor state.  Same for treebody, menu, subdocument, textbox.

On the other hand, all those consumers may be able to explicitly clear the backlink.  At least in common cases.
I would prefer to focus on reducing the usage of nsWeakFrame.

(In reply to comment #10)
> Looking at your list, the ESM has a few weakframes and is a singleton per
> presshell, so should not be a problem.  The layout utils use is an
> nsReflowFrameRunnable; not sure how many of those can be pending.

Only used by XUL progress meters, i.e. not a problem.

> The text and file and listbox uses there can be lots of on a page, I bet.  Same
> for editor state.  Same for treebody, menu, subdocument, textbox.

In practice I think we can ignore the XUL-related ones and subdocuments ... if you have thousands of IFRAMEs on a page you have other problems. I think thousands of file input controls is also likely to be rare. That actually only leaves the editor state RestoreSelectionState script-runner and the nsTextControlFrame::EditorInitializer script-runner.

> On the other hand, all those consumers may be able to explicitly clear the
> backlink.  At least in common cases.

Yes. For both of those, I think we can make them nsIFrame* references and arrange to have nsTextControlFrame::DestroyFrom locate the pending runnables and clear out their frame references. A simple way to do that would to be store two more nsRevocableEventPtrs in nsTextControlFrame. Instead of having three rarely-used pointers in that class, we might be better off putting them in frame properties. If they were frame properties, we would use the property destruction function to clear out the runnables' frame references.

Another option would be for those runnables to store nsRefPtrs to the underlying elements and use GetPrimaryFrame to find the nsTextControlFrame when they run. However, that might cause issues if the wrong frame is found after frame recreation.
OK; the primary testcase issue here (large form pages) can be resolved by (as mentioned) dealing with the editor state nsWeakFrames.  That would seem to be the way to go.  

I don't think the 3-pointer footprint hit for TextControlFrames would be a big deal - even my way-beyond-reasonable testcase had circa 46000 such objects, for ~500KB (32-bit build) footprint hit.  I doubt even with 500 tabs of "normal" pages that the footprint hit would be easily measurable, though we could check.  If they averaged 10 text input boxes per tab (probably high), you're talking around 50KB total hit for 500 tabs.  Given a basic 500-tab profile normally boots up (even with almost all the tabs unloaded) at 600MB-1GB, this is in the noise.  Still, overall footprint is the result of a lot of little decisions too.

You could also chain them in a list when they exist, cutting the base object overhead to 1 pointer.  Obviously if there's a solution with no fixed overhead that doesn't add a lot of code or risk of errors that's even better.
Adding a few words to nsTextControlFrame is fine.
As roc indicated, look at frame properties (actually this is rather like the suggestion I made in comment 7 - I hadn't noticed the new-to-me FrameProperties existed).  Seems like the LayerActivity property works a bit like this.

We could add a Frame Property which is a pointer to an nsWeakFrame-like object (without the hooks into PresShell), and a separate state bit to tell us to get the property on DestroyFrom() and Clear the references in the property.  Effectively this lets us store the weakframe objects in the frame without burning a pointer to do it (or any real processing overhead).  This can be extended to any additional classes that need it.  "nsWeakFrameProperty"?  "nsLongWeakFrame"

I'm starting to code this up.
(In reply to comment #11)
> Another option would be for those runnables to store nsRefPtrs to the
> underlying elements and use GetPrimaryFrame to find the nsTextControlFrame when
> they run. However, that might cause issues if the wrong frame is found after
> frame recreation.

I'm pretty sure that this could happen in the real world, so let's not do this (although this doesn't seem to be the direction in which the bug is heading, fortunately.)
This is a working, close to done patch that implements the Frame Property-based approach to put certain Weak references in the Frame instead of the PresShell, to avoid the O(n^2) problem.

In jprof tests, the code for handling weak reference properties runs under 1% (in b6b.html we were around 30% before).

This patch should have no footprint impact.

I should note I moved nsWeakFrame within nsIFrame.h to make things easier.  I can move it back if needed; it will take a bit more effort.

While jprofs clearly show the improvement, times reported by the JS code don't appear to - they're *highly* variable on Firefox (0.3 to 4.8s for b6a.html), though not on IE.  This is probably caused by other aspects of bug 352367, or some deferred processing in the editor elements perhaps - I'll need to take runs with external triggering.

(Note bene: I'm still getting used to Mercurial; I hand-edited out some unrelated changes from the patch, so if it doesn't work for you please let me know ASAP.  I'll have the correct procedure/sequence down soon.)
I don't think we need nsLongWeakFrame. Instead nsTextControlFrame can just track its active scriptrunners, which hold direct nsTextControlFrame* pointers, and ask them to clear out their frame pointers when the nsTextControlFrame is destroyed.
roc: Even better.  Without having a good understanding of the constraints surrounding nsTextControlFrame and the scriptrunners, I was working from the direction of keeping the external interactions the same or equivalent, to minimize any chance of a regression while I come back up to full speed on the codebase.
roc: how does this patch look - is this a reasonable approach to tracking and clearing runnables?  It adds one pointer to nsTextEditorState.  Note: work-in-progress, not complete; review not intended for checkin.
Attachment #533574 - Flags: review?(roc)
Comment on attachment 533574 [details] [diff] [review]
work-in-progress patch for tracking and clearing runnables

Review of attachment 533574 [details] [diff] [review]:
-----------------------------------------------------------------

Otherwise looks OK.

::: content/html/content/src/nsTextEditorState.cpp
@@ +103,5 @@
>      return NS_OK;
>    }
>  
> +  // Let the text editor tell us we're no longer relevant - avoids use of nsWeakFrame
> +  void UnbindFromFrame() {

We usually call this Revoke().

@@ +1392,5 @@
>    if (mTextListener)
>      newEditor->AddEditorObserver(mTextListener);
>  
>    // Restore our selection after being bound to a new frame
> +  if (mSelState && !mRestoringSelection) { // paranoia

If there's already an mRestoringSelection you probably want to revoke the old one and launch a new one.
(In reply to comment #11)
roc wrote:
> > The text and file and listbox uses there can be lots of on a page, I bet.  Same
> > for editor state.  Same for treebody, menu, subdocument, textbox.
> 
> In practice I think we can ignore the XUL-related ones and subdocuments ...
> if you have thousands of IFRAMEs on a page you have other problems. I think
> thousands of file input controls is also likely to be rare. That actually
> only leaves the editor state RestoreSelectionState script-runner and the
> nsTextControlFrame::EditorInitializer script-runner.

Actually, I found the real culprit is the nsTextInputListener created at BindToFrame() time (though I've fixed both script-runners).
So, if nsTextEditorState disconnects the nsTextInputListener in nsTextEditorState::UnbindFromFrame() (and it does), is the nsWeakFrame in nsTextInputListener actually needed?  Looks to me to be "no", but I very may well be missing something - my head isn't yet into when and how frames can get destroyed - it's not, shall we say, simple.  :-)  Comments like this in nsTextInputListener::EditAction() make me suspicious:

  // mFrame may be dead after this, but we don't need to check for it, because
  // we are not uisng it in this function any more.

nsTextEditorState::UnbindFromFrame() was the same place we were revoking the selection scriptrunner.

roc?  (bz?)  Comments?
Comment on attachment 533574 [details] [diff] [review]
work-in-progress patch for tracking and clearing runnables

>-  if (mSelState) {
>-    nsContentUtils::AddScriptRunner(new RestoreSelectionState(this, mBoundFrame, mSelState->mStart, mSelState->mEnd));
>-    mSelState = nsnull;
>+  if (mSelState && !mRestoringSelection) { // paranoia

What roc said.

>+  if (mRestoringSelection)
>+  {
>+    mRestoringSelection->UnbindFromFrame();
>+    mRestoringSelection = nsnull; // probably not needed, paranoia

Hmm, why do you think this is not needed?  I think it is.

>+  void ClearRestoring() { mRestoringSelection = nsnull; }

Please rename this to something better, like FinishedRestoringSelection, make it private, and make RestoreSelectionState a friend of nsTextEditorState.
Attachment #533574 - Flags: review?(roc) → review+
(In reply to comment #22)
> So, if nsTextEditorState disconnects the nsTextInputListener in
> nsTextEditorState::UnbindFromFrame() (and it does), is the nsWeakFrame in
> nsTextInputListener actually needed?  Looks to me to be "no", but I very may
> well be missing something - my head isn't yet into when and how frames can
> get destroyed - it's not, shall we say, simple.  :-)  Comments like this in
> nsTextInputListener::EditAction() make me suspicious:
> 
>   // mFrame may be dead after this, but we don't need to check for it,
> because
>   // we are not uisng it in this function any more.
> 
> nsTextEditorState::UnbindFromFrame() was the same place we were revoking the
> selection scriptrunner.

It seems to me that we don't need the weak frame member variable for nsTextInputListener.  We do need to check whether the frame is alive in NotifySelectionChanged and EditAction, and this can be done with a local nsWeakFrame member.
Attached patch Working fix for review (obsolete) — — Splinter Review 
I haven't run it through the jst simulator yet, but it should pass
Attachment #533574 - Attachment is obsolete: true
Attachment #533778 - Flags: review?(ehsan)
The JST simulator is good with it outside of a few "keep existing style" nits
Comment on attachment 533778 [details] [diff] [review]
Working fix for review

I think you should remove mInitializer and use a frame property to store it.  Since this value is only ever used once per frame (if at all), it's not worth paying the storage cost on the frame for the whole duration of its lifetime.
Attachment #533778 - Flags: review?(ehsan) → review-
Now uses a property for holding the EditorInitializer.  

Note that I've found (with or without this change) that the time to run varies a lot depending on whether you leave the window focused or send it to the back (which can greatly increase the time to load b6b.html, though the jprof graph looks very similar).  But that's not a comment on this patch/bug; I think that's an event/timers/content-construction issue.
Attachment #533778 - Attachment is obsolete: true
Attachment #533937 - Flags: review?(ehsan)
Comment on attachment 533937 [details] [diff] [review]
Final (I hope) patch using a property for EditorInitializer

Review of attachment 533937 [details] [diff] [review]:
-----------------------------------------------------------------

r=me with the below nits fixed.

::: layout/forms/nsTextControlFrame.cpp
@@ +204,5 @@
> +  FrameProperties props = Properties();
> +  EditorInitializer* initializer = (EditorInitializer*) props.Get(TextControlInitializer());
> +  if (initializer) {
> +    initializer->Revoke();
> +    props.Delete(TextControlInitializer());

Here, and elsewhere, please do:

Properties().foo(bar)

instead of declaring a local FrameProperties object.

@@ +457,5 @@
> +    if (initializer) {
> +      initializer->Revoke();
> +    }
> +    initializer = new EditorInitializer(this);
> +    if (initializer) {

No need to check for null, new cannot fail.

@@ +458,5 @@
> +      initializer->Revoke();
> +    }
> +    initializer = new EditorInitializer(this);
> +    if (initializer) {
> +      props.Set(TextControlInitializer(),initializer);

Can you just move this to after checking the result of AddScriptRunner?  This way, the props.Delete call below would be unnecessary.

@@ +466,5 @@
> +        props.Delete(TextControlInitializer());
> +        return NS_ERROR_OUT_OF_MEMORY;
> +      }
> +    } else {
> +      props.Delete(TextControlInitializer());

As per above, this is not necessary.

::: layout/generic/nsIFrame.h
@@ +903,5 @@
>    NS_DECLARE_FRAME_PROPERTY(ScrollLayerCount, nsnull)
>  
> +  // Temp reference to scriptrunner
> +  // We could make these auto-Revoking via the "delete" entry for safety
> +  NS_DECLARE_FRAME_PROPERTY(TextControlInitializer, nsnull)

Please move this to nsTextControlFrame.h, it doesn't need to live in nsIFrame.h.
Attachment #533937 - Flags: review?(ehsan) → review+
>> +      initializer->Revoke();
>> +    }
>> +    initializer = new EditorInitializer(this);
>> +    if (initializer) {
>> +      props.Set(TextControlInitializer(),initializer);
>
>Can you just move this to after checking the result of AddScriptRunner?  This >way, the props.Delete call below would be unnecessary.

Is there any chance that the scriptrunner can run (or might someday) before we get to the Properties().Set()?  If so, deferring the Set() is not valid.  I usually feel safer not to set up something that makes assumptions about the ordering of operations elsewhere, not guaranteed by the API.  (For example, could there someday be some optimization that might allow a scriptrunner to run at Add time?)

That said - I have no problem changing it per your comment, since you're the expert here.
Fixed, with nits fixed per ehsan

Checked in as changeset http://hg.mozilla.org/mozilla-central/rev/52f72d71dc59
Status: ASSIGNED → RESOLVED
Closed: 13 years ago
Resolution: --- → FIXED
(In reply to comment #30)
> >> +      initializer->Revoke();
> >> +    }
> >> +    initializer = new EditorInitializer(this);
> >> +    if (initializer) {
> >> +      props.Set(TextControlInitializer(),initializer);
> >
> >Can you just move this to after checking the result of AddScriptRunner?  This >way, the props.Delete call below would be unnecessary.
> 
> Is there any chance that the scriptrunner can run (or might someday) before we
> get to the Properties().Set()?  If so, deferring the Set() is not valid.  I
> usually feel safer not to set up something that makes assumptions about the
> ordering of operations elsewhere, not guaranteed by the API.  (For example,
> could there someday be some optimization that might allow a scriptrunner to run
> at Add time?)

I think we should have a script blocker every time we hit this code.  More importantly, this can only be a problem if the frame is destroyed right after creation before script blockers, which also shouldn't happen.  *However*, on the second thought, I think it's not a good idea for us to rely on these magics, so would you mind filing a followup bug and revert this change?  Sorry about that!
Blocks: 669767
No longer blocks: 669767
Depends on: 669767
Depends on: 682684
You need to log in before you can comment on or make changes to this bug.

Attachment

General

Creator:
Created:
Updated:
Size: