640853 - nsFrameSelection/mDomSelections/nsTypedSelection form a ton of cycles

Status: RESOLVED WORKSFORME

(Core :: Layout, defect)

Description

[Andreas Gal :gal]

Andrew is working on visualizing our heap structure (pdf attached). You can see that a ton of the cycles the collector is considering look like stars with one reference counted object in the middle, and 9 other reference counted objects centered around it. The object in the middle references all 9 objects around it, all 9 reference the object as well.

We looked up the type of the object in the middle and its a nsFrameSelection object. The outgoing edges are via mDomSelection. Lo and behold, you can see the cycle being formed right in the constructor:

nsFrameSelection::nsFrameSelection()
  : mDelayedMouseEvent(PR_FALSE, 0, nsnull, nsMouseEvent::eReal)
{
  PRInt32 i;
  for (i = 0;i<nsISelectionController::NUM_SELECTIONTYPES;i++){
    mDomSelections[i] = new nsTypedSelection(this);
    if (!mDomSelections[i])
      break;

And then nsTypedSelection:

nsTypedSelection::nsTypedSelection(nsFrameSelection *aList)
  : mFrameSelection(aList)   <=== here
  , mCachedOffsetForFrame(nsnull)
  , mDirection(eDirNext)
  , mType(nsISelectionController::SELECTION_NORMAL)
{
}

...

  nsCOMPtr<nsIRange> mAnchorFocusRange;
  nsRefPtr<nsFrameSelection> mFrameSelection;
  nsWeakPtr mPresShellWeak;

...

In case you wonder where the magic number 9 is coming from:

/content/base/public/nsISelectionController.idl
    line 66 -- const short NUM_SELECTIONTYPES=9;

As you can see from the graph quite a few of these cycles are being collected (nodes with an address in them).

Creating these cycles seems unnecessary and it creates pressure on the CC. We should avoid creating this and use a weak pointer on one side.

Comment 1

[Andreas Gal :gal]

And of course:

nsFrameSelection.h:  nsRefPtr<nsTypedSelection> mDomSelections[nsISelectionController::NUM_SELECTIONTYPES];

Comment 2

[Andrew McCreight [:mccr8]]

Attachment: graph of cycle collected heap

Circles are refcounted DOM objects, while squares are GC'ed JS objects.  Filled in circles are objects the cycle collector has determined are reachable from roots, while filled in squares are objects the GC has determined are reachable from a root.

Triangles are objects the cycle collector has determined are garbage.  All of the garbage except for a single mutually recursive pair in this particular collection are in the distinctive mutually recursive 9-pointed star.

This is just the slice of the heap that the CC collection that has 10 components.  Some of these structures are live, and some are dead.

Comment 3

[Andrew McCreight [:mccr8]]

Attachment: dot file of most of heap dump

Here's a dot file of the full graph of the heap that the CC visits.  You can turn it into a pdf using sfdp, which comes with GraphViz.  I collapsed some of the single and dual node chunks, but otherwise it is all there.

Comment 4

[Boris Zbarsky [:bzbarsky]]

> We should avoid creating this and use a weak pointer on one side.

On which side?  Arbitrary consumers can hold references to the nsTypedSelection objects, I believe.  And nsFrameSelection is the thing that something that want's "a selection" will typically own...

What we _could_ do if we want is to treat all this gunk as a single object, since it effectively is anyway, for refcounting purposes.  But would that make CC any happpier?

Comment 5

[Brendan Eich [:brendan]]

(In reply to comment #4)
> What we _could_ do if we want is to treat all this gunk as a single object,
> since it effectively is anyway, for refcounting purposes.  But would that make
> CC any happpier?

Yes!

Do we need to traverse these edges if they are (always/sometimes) self-cycles?

/be

Comment 6

[Andreas Gal :gal]

I am weary of misreporting the true heap graph to the CC. We had a number of cycles the CC couldn't break because it wasn't able to see the real structure, on the "reported" structure.

Comment 7

[Boris Zbarsky [:bzbarsky]]

> Do we need to traverse these edges if they are (always/sometimes) self-cycles?

In theory, no, if the self-cycles are permanent.

Andreas, was that an argument against the suggestion in comment 4?  If so, I agree with you; the complexity of faking the object graph is a bad thing...

But then we're left with the fact that we _will_ have tight cycles in the object graph.  In fact, once DOM nodes hold strong refs to their parents the entire DOM will be a tight cycle.  If CC can't handle that well, we should fix that...

Comment 8

[Andreas Gal :gal]

bz, yeah, I am against misreporting ownership relationships in the CC.

And yes, I think we should see if we can teach the CC to treat these constructs more efficiently. Andrew just filed a bug about quickly excluding non-cycling garbage. Similar, we could quickly try to identify garbage and immediately dispose of it, without even having to build a graph for that portion.

Andrew, what do you think?

Comment 9

[Andrew McCreight [:mccr8]]

Well, if node A points to B, B points to A, and A has a ref count of 1, then the CC doesn't have to add A to the cycle collector's graph.  If B gets freed by the CC, then A will too.  I don't know if checking for that situation is better or worse than just adding the tiny loop to the graph.

Comment 10

[Andrew McCreight [:mccr8]]

I wrote up a little script to compute how many of the tiny loops there are in the CC graph (eg an XPCOM node N1 with a refcount of 1 that points only to a node N2, and N2 points to N1).  This will get rid of all the trivial instances of these stars (but isn't limited to the stars).  In some tests I did, this eliminates 1% to 13% of nodes in the graph.

Comment 11

[Andrew McCreight [:mccr8]]

Update: Death Stars now have 11 nodes in them, instead of 10.  (NUM_SELECTIONTYPES is now 10)  This was changed in Bug 451833.  I have no real point here, I was just amused to notice that.

Comment 12

[Andrew McCreight [:mccr8]]

Bug 714162 should end the scourge of death stars.  I'll look at some logs next week when I get back and close this if so.

Comment 13

[Andrew McCreight [:mccr8]]

Looks fixed to me.  I looked at a random CC graph and saw only dead death stars.