728460 - remove all childless nodes from the purple buffer before a CC

Status: RESOLVED FIXED

(Core :: XPCOM, defect)

Description

[Andrew McCreight [:mccr8] (PTO until 12-2)]

We could do this by doing a Traverse on everything in the buffer that returns false for CanSkip and using a custom callback to see if it reports any children.  Pretty heavyweight, but it would be interesting to see what the tradeoffs are.

Comment 1

[Andrew McCreight [:mccr8] (PTO until 12-2)]

One way to do this less would be to only do it when we've filled up the purple buffer, and we're just about ready to go.  This would be a last-ditch effort to delay a CC.  Maybe only bail out if you removed a huge number of things, and not just enough to get under the limit again.

Comment 2

[Andrew McCreight [:mccr8] (PTO until 12-2)]

I experimented with running it in every time slice.  Seems to remove a decent amount from the purple buffer.  Though if you remove it just to add it again that's not useful.

CC(T+75.2) Duration: 14ms, Suspected: 1141, Visited: 5491 RCed 6021 GCed, Collected: 2855 RCed 3708 GCed (3708 waiting for GC)
ForgetSkippable 17 times before CC, min: 0 ms, max: 4 ms, avg: 1 ms, total: 24 ms, removed: 17973
CC(T+101.8) Duration: 34ms, Suspected: 766, Visited: 11976 RCed 2463 GCed, Collected: 9658 RCed 887 GCed (887 waiting for GC)
ForgetSkippable 41 times before CC, min: 0 ms, max: 6 ms, avg: 1 ms, total: 51 ms, removed: 30893
CC(T+117.2) Duration: 32ms, Suspected: 1305, Visited: 12007 RCed 10837 GCed, Collected: 9298 RCed 8370 GCed (8370 waiting for GC)
ForgetSkippable 36 times before CC, min: 0 ms, max: 9 ms, avg: 2 ms, total: 78 ms, removed: 19638
CC(T+167.8) Duration: 15ms, Suspected: 1306, Visited: 2787 RCed 3653 GCed, Collected: 468 RCed 1002 GCed (1002 waiting for GC)
ForgetSkippable 73 times before CC, min: 0 ms, max: 6 ms, avg: 0 ms, total: 65 ms, removed: 16354
CC(T+225.2) Duration: 8ms, Suspected: 690, Visited: 3722 RCed 3209 GCed, Collected: 1437 RCed 36 GCed (36 waiting for GC)
ForgetSkippable 97 times before CC, min: 0 ms, max: 8 ms, avg: 1 ms, total: 101 ms, removed: 38536

cc: no childs left behind: 114
cc: no childs left behind: 63
cc: no childs left behind: 67
cc: no childs left behind: 61
cc: no childs left behind: 83
cc: no childs left behind: 60
cc: no childs left behind: 83
cc: no childs left behind: 130
cc: no childs left behind: 77
cc: no childs left behind: 65
cc: no childs left behind: 129
cc: no childs left behind: 120
cc: no childs left behind: 63
cc: no childs left behind: 74

Comment 3

[Andrew McCreight [:mccr8] (PTO until 12-2)]

Attachment: rude and crude

Comment 4

[Andrew McCreight [:mccr8] (PTO until 12-2)]

Running with this for a while, I have yet to see a CC that doesn't free any garbage.  It also makes it so that largest spike in CC_TIME_BETWEEN is 120.  The average time between CCs is 64 seconds.

Comment 5

[Andrew McCreight [:mccr8] (PTO until 12-2)]

I have a new version that only does the childless purge when we pass the threshold for the CC.  The results look like this:

cc: last ditch purging took us from 761 to 338 nodes in the buffer.
cc: last ditch purging took us from 531 to 339 nodes in the buffer.
cc: last ditch purging took us from 649 to 340 nodes in the buffer.
cc: last ditch purging took us from 602 to 338 nodes in the buffer.
cc: last ditch purging took us from 642 to 338 nodes in the buffer.
cc: last ditch purging took us from 766 to 338 nodes in the buffer.
cc: last ditch purging took us from 1309 to 339 nodes in the buffer.
cc: last ditch purging took us from 1159 to 340 nodes in the buffer.
cc: last ditch purging took us from 818 to 341 nodes in the buffer.

All of the last ditch purges took 1ms or less.  As you can see, a huge % of the stuff in the purple buffer is apparently childless.

In that session (just a bit of light browsing), it was the 5 minute timer that finally caused the CC to fire.

With this patch, we may want to decrease the threshold from 500...

Comment 6

[Andrew McCreight [:mccr8] (PTO until 12-2)]

Marking P2 because this makes the CC run waaaaaay less often.

Comment 7

[Olli Pettay [:smaug][[e-mail]]]

This sounds great.

Perhaps we could keep the 500 limit, but decrease NS_CC_FORCED.

Comment 8

[Olli Pettay [:smaug][[e-mail]]]

I guess the effectiveness of this depends on the case.
I'm testing the patch attached to this bug and CC does run still reasonable often.
But, I do have several tbpl pages open and tbpl does create plenty of garbage.
CC does seem to release something always.

Comment 9

[Andrew McCreight [:mccr8] (PTO until 12-2)]

Attachment: wait to run it, WIP

Basically the same, except that it waits until the purple buffer is large enough to trigger a full CC to remove childless nodes, in an attempt to be more efficient.

Comment 10

[Olli Pettay [:smaug][[e-mail]]]

Comment on attachment 598684 [details] [diff] [review]
wait to run it, WIP

># HG changeset patch
># User Andrew McCreight <[e-mail]>
># Date 1329681208 28800
># Node ID 19d732e3b92d8c100b32fa3f15fb6227ea62176e
># Parent  34f9384193ddae2e0c9cc4c1849ca27870f5442a
>[mq]: PurplePurge
>
>diff --git a/dom/base/nsJSEnvironment.cpp b/dom/base/nsJSEnvironment.cpp
>--- a/dom/base/nsJSEnvironment.cpp
>+++ b/dom/base/nsJSEnvironment.cpp
>@@ -3290,22 +3290,22 @@ nsJSContext::CycleCollectNow(nsICycleCol
> 
>   KillCCTimer();
> 
>   PRTime start = PR_Now();
> 
>   PRUint32 suspected = nsCycleCollector_suspectedCount();
> 
>   for (PRInt32 i = 0; i < aExtraForgetSkippableCalls; ++i) {
>-    nsCycleCollector_forgetSkippable();
>+    nsCycleCollector_forgetSkippable(false);
>   }
> 
>   // nsCycleCollector_forgetSkippable may mark some gray js to black.
>   if (!sCleanupSinceLastGC && aExtraForgetSkippableCalls >= 0) {
>-    nsCycleCollector_forgetSkippable();
>+    nsCycleCollector_forgetSkippable(false);
>   }
>   nsCycleCollectorResults ccResults;
>   nsCycleCollector_collect(&ccResults, aListener);
>   sCCollectedWaitingForGC += ccResults.mFreedGCed;
> 
>   // If we collected a substantial amount of cycles, poke the GC since more objects
>   // might be unreachable now.
>   if (sCCollectedWaitingForGC > 250) {
>@@ -3384,16 +3384,32 @@ GCTimerFired(nsITimer *aTimer, void *aCl
> void
> ShrinkGCBuffersTimerFired(nsITimer *aTimer, void *aClosure)
> {
>   NS_RELEASE(sShrinkGCBuffersTimer);
> 
>   nsJSContext::ShrinkGCBuffersNow();
> }
> 
>+#define NS_CC_PURPLE_BUFFER_LIMIT 500
>+
>+static
>+bool PurpleBufferTooBigAfterPurge()
>+{
>+    PRUint32 suspected1 = nsCycleCollector_suspectedCount();
>+    if (nsCycleCollector_suspectedCount() < NS_CC_PURPLE_BUFFER_LIMIT)
>+      return false;
>+    nsCycleCollector_forgetSkippable(true); // last ditch purging, with childless nodes
>+    // one bad thing about this is that the time for the forgetSkippable isn't recorded anywhere.
>+    PRUint32 suspected2 = nsCycleCollector_suspectedCount();
>+    printf("cc: last ditch purging took us from %u to %u nodes in the buffer.\n",
>+           suspected1, suspected2);
>+    return suspected2 > NS_CC_PURPLE_BUFFER_LIMIT;
>+}
>+
> // static
> void
> CCTimerFired(nsITimer *aTimer, void *aClosure)
> {
>   if (sDidShutdown) {
>     return;
>   }
>   if (sCCLockedOut) {
>@@ -3403,34 +3419,34 @@ CCTimerFired(nsITimer *aTimer, void *aCl
>   if (sCCTimerFireCount < (NS_CC_DELAY / NS_CC_SKIPPABLE_DELAY)) {
>     PRUint32 suspected = nsCycleCollector_suspectedCount();
>     if ((sPreviousSuspectedCount + 100) > suspected) {
>       // Just few new suspected objects, return early.
>       return;
>     }
>     
>     PRTime startTime = PR_Now();
>-    nsCycleCollector_forgetSkippable();
>+    nsCycleCollector_forgetSkippable(false);
>     sPreviousSuspectedCount = nsCycleCollector_suspectedCount();
>     sCleanupSinceLastGC = true;
>     PRTime delta = PR_Now() - startTime;
>     if (sMinForgetSkippableTime > delta) {
>       sMinForgetSkippableTime = delta;
>     }
>     if (sMaxForgetSkippableTime < delta) {
>       sMaxForgetSkippableTime = delta;
>     }
>     sTotalForgetSkippableTime += delta;
>     sRemovedPurples += (suspected - sPreviousSuspectedCount);
>     ++sForgetSkippableBeforeCC;
>   } else {
>-    sPreviousSuspectedCount = 0;
>     nsJSContext::KillCCTimer();
>-    if (nsCycleCollector_suspectedCount() > 500 ||
>+    if (PurpleBufferTooBigAfterPurge() ||
>         sLastCCEndTime + NS_CC_FORCED < PR_Now()) {
Is this really needed?
Pretty much always calling forgetSkippable synchronously
right before cycle collection might increase CC times.


>-void nsCycleCollector_forgetSkippable();
>+void nsCycleCollector_forgetSkippable(bool noChilds);
The parameter name isn't very clear.
I'd prefer something which either includes word "green",
for example "aNoGreenObjectOptimization", or
"noBlackChildOptimization" or "dontSkipChildlessObjects"

Comment 11

[Andrew McCreight [:mccr8] (PTO until 12-2)]

(In reply to Olli Pettay [:smaug] from comment #10)
> Is this really needed?
> Pretty much always calling forgetSkippable synchronously
> right before cycle collection might increase CC times.

That's true.  It will reduce them in some cases, because things that are removed don't have to be Traversed again.  One problem with the current patch is that it won't properly ascribe this pause to the full CC pause.  One hacky way around this would be to run this in the time slice before we see if we want to run the CC.  We wouldn't remove any childless nodes added in the last time slice, but maybe it would still help.

On the other hand, maybe it isn't a big deal.  The additional forgetSkippable rarely takes more than 1 ms.

> The parameter name isn't very clear.

Yeah, it is terrible, I just threw that in there to mess around with this.  Thanks for the suggestions.  I don't want to go with "green".  We already have a ton of other colors, and green isn't used anywhere else.  Additionally, this is only a very crude measurement of acyclicity.

Comment 12

[Andrew McCreight [:mccr8] (PTO until 12-2)]

Attachment: run the childless removal only in the slice before we check the purple buffer size, untested

I don't know if this even compiles.  I need to look into how much we lose by doing it in the second to last slice.  I'm going to do that by seeing how much we remove if we run an additional purging pass right before we run the CC.

Comment 13

[Andrew McCreight [:mccr8] (PTO until 12-2)]

Removing childless nodes in the slice before we decide whether to CC

extra purge before collection (suspected: 663)
  cc: number of childless nodes removed: 138
  suspected after purge: 453)
  --> would have skipped CC with last minute purge.

Sometimes it is due to the regular old remove skippable optimization.  In this particular instance, the childless node removal only gets rid of 228, but the normal remove skippable gets rid of around 3000 nodes:

extra purge before collection (suspected: 3495)
  cc: number of childless nodes removed: 228
  suspected after purge: 172)

So, I think I'll go back to running it right before we CC.  It could cause some slowdowns, but I think most of the time if remove skippable takes a long time, then I think the added cost is likely going to decrease CC times by more than the time the remove skippable takes.

Comment 14

[Olli Pettay [:smaug][[e-mail]]]

ok, sounds good.
Just make sure CC time telemetry records the possibly added time, so that we know if there is a 
regressions.

Comment 15

[Olli Pettay [:smaug][[e-mail]]]

Actually, perhaps better to add a new telemetry probe for this.
I don't want to change what CYCLE_COLLECTOR means.

Comment 16

[Andrew McCreight [:mccr8] (PTO until 12-2)]

Attachment: rebased on top of cleanup patch

The increase in pause time caused by the forget_skippable right before the CC is still not measured in telemetry.  I still kind of want to measure it as part of the full CC pause time, rather than a separate measure.  I think that will require moving the forget_skippable(true) and inner ShouldTriggerCC() into CycleCollectNow, then add a flag to CycleCollectNow that says whether we can bail out or not.  That will be false for all callers but CCTimerFired.  If we do bail out, we'll have to update the forget_skippable counters, so that process will probably have to be factored out into a function.

Comment 17

[Andrew McCreight [:mccr8] (PTO until 12-2)]

https://tbpl.mozilla.org/?tree=Try&rev=800e76f4d724

Comment 18

[Andrew McCreight [:mccr8] (PTO until 12-2)]

Attachment: part 2: avoid bloating the CC

Here's an approach to having the childless cleanup not make the CC pause longer.

In the 14th time slice, we have special behavior.  We check if we should trigger a CC (by having too many things in the purple node, or hitting the CC-forcing timer).  In that case, we do a full-blown childless removing forget_skippable.  If we still meet the condition to trigger a CC, we just return.  If we don't meet the condition to trigger a CC, then we do the normal thing for a time slice (run a forget skippable that doesn't remove children if there have been enough things added to the purple buffer).  In the cases where we didn't return, we kill the timer, preventing a CC from happening.

If we hit the 15th time slice, that means that we ended the previous time slice deciding we should run a CC.  We kill the timer as before for this time slice.  We then check the condition again (it is possible a bunch of things in the purple buffer went away, and so we no longer meet the condition).  If we meet the condition, we run the CC.  Otherwise, we run a forget skippable if needed.  The idea is to avoid going an entire time slice without any purple buffer cleanup.

Comment 19

[Andrew McCreight [:mccr8] (PTO until 12-2)]

Attachment: part 1: add remove childless option to forget skippable

Comment 20

[Andrew McCreight [:mccr8] (PTO until 12-2)]

Attachment: part 2: remove childless nodes and decide if we run CC in slice before CC may run

Cleaned up from the last version.  Still has debug print statements in it.

Comment 21

[Andrew McCreight [:mccr8] (PTO until 12-2)]

Comment on attachment 600986 [details] [diff] [review]
part 1: add remove childless option to forget skippable

I still need to see how bug 730753 interacts with CC scheduling before I decide how to finalize part 2, and if we need to tweak the triggers.

Comment 22

[Olli Pettay [:smaug][[e-mail]]]

Comment on attachment 600986 [details] [diff] [review]
part 1: add remove childless option to forget skippable


>     // RemoveSkippable removes entries from the purple buffer if
>     // nsPurpleBufferEntry::mObject is null or if the object's
>     // nsXPCOMCycleCollectionParticipant::CanSkip() returns true.
>-    void RemoveSkippable();
>+    void RemoveSkippable(bool removeChildlessNodes);
Could you document what childless means here. It is a bit
misleading parameter name, since the meaning is:
removeChildlessObjectOrObjectWhichHasOnlyBlackChildren


>+class ChildFinder : public nsCycleCollectionTraversalCallback
>+{
>+public:
>+    ChildFinder() : mMayHaveChild(false) {}
>+
>+    // The logic of the Note*Child functions must mirror that of their
>+    // respective functions in GCGraphBuilder.
>+    NS_IMETHOD_(void) NoteXPCOMChild(nsISupports *child);
The file is so far from Mozilla coding style. But I can't blame you.
No need to change the style here.

> NS_IMETHODIMP_(void)
>+ChildFinder::NoteXPCOMChild(nsISupports *child)
>+{
>+    if (!child || !(child = canonicalize(child)))
>+        return; 
>+    nsXPCOMCycleCollectionParticipant *cp;
>+    ToParticipant(child, &cp);
>+    if (cp && !cp->CanSkip(child, true))
>+        mMayHaveChild = true;
>+};
>+
>+NS_IMETHODIMP_(void)
> GCGraphBuilder::NoteNativeChild(void *child,
>                                 nsCycleCollectionParticipant *participant)
> {
>     nsCString edgeName;
>     if (WantDebugInfo()) {
>         edgeName.Assign(mNextEdgeName);
>         mNextEdgeName.Truncate();
>     }
>     if (!child)
>         return;
> 
>     NS_ASSERTION(participant, "Need a nsCycleCollectionParticipant!");
>     NoteChild(child, participant, nsIProgrammingLanguage::CPLUSPLUS, edgeName);
> }
> 
> NS_IMETHODIMP_(void)
>+ChildFinder::NoteNativeChild(void *child,
>+                             nsCycleCollectionParticipant *helper)
Could you not mix GCGraphBuilder and ChildFinder methods.
Keep the new methods in one place.

I'm not sure which mMayHaveChild handling we want.
If mMayHaveChild is already true, should we use CanSkip for other edges.
I guess that can be effective in some cases.
So ok, let's try this behavior.

Comment 23

[Andrew McCreight [:mccr8] (PTO until 12-2)]

(In reply to Olli Pettay [:smaug] from comment #22)
> >+    void RemoveSkippable(bool removeChildlessNodes);
> Could you document what childless means here. It is a bit
> misleading parameter name, since the meaning is:
> removeChildlessObjectOrObjectWhichHasOnlyBlackChildren

Good point.  The object may have children, but it won't have children in the CC graph.  I'll try to document that or come up with a better name.

> The file is so far from Mozilla coding style. But I can't blame you.
> No need to change the style here.

I can change it if you want.  No big deal.

> Could you not mix GCGraphBuilder and ChildFinder methods.
> Keep the new methods in one place.

So, the idea here was to place the related methods near each other so it is easy to tell that they have similar logic.  But I can split them up if you think that isn't a good enough reason.

> I'm not sure which mMayHaveChild handling we want.
> If mMayHaveChild is already true, should we use CanSkip for other edges.
> I guess that can be effective in some cases.
> So ok, let's try this behavior.

Oh, right, I didn't think about that.  I'll leave it as is then.

Comment 24

[Andrew McCreight [:mccr8] (PTO until 12-2)]

Attachment: part 1: add remove childless option to forget skippable

Review comments addressed.  Carrying forward smaug's review.  I also made the signature for nsCycleCollector_forgetSkippable match Mozilla style because the other functions nearby also seemed to adhere to it.

Comment 25

[Andrew McCreight [:mccr8] (PTO until 12-2)]

Attachment: part 2: remove childless nodes (and decide if we run CC) in slice before CC may run

Comment 26

[Andrew McCreight [:mccr8] (PTO until 12-2)]

I also reduced the forced-CC timer from 5 minutes to 2 minutes, and changed the purple buffer threshold from 500 to 250.

Comment 27

[Olli Pettay [:smaug][[e-mail]]]

Comment on attachment 602543 [details] [diff] [review]
part 2: remove childless nodes (and decide if we run CC) in slice before CC may run

The patch is a bit hard to read.
Could you add some comment what inLatePhase means.

Comment 28

[Andrew McCreight [:mccr8] (PTO until 12-2)]

(In reply to Olli Pettay [:smaug] from comment #27)
> The patch is a bit hard to read.
> Could you add some comment what inLatePhase means.
Good idea. Thanks for the review.

Comment 29

[Andrew McCreight [:mccr8] (PTO until 12-2)]

https://hg.mozilla.org/integration/mozilla-inbound/rev/d00e5203b958
https://hg.mozilla.org/integration/mozilla-inbound/rev/1448a8de40a8

Updated comments in the second part.

Comment 30

[Matt Brubeck (:mbrubeck)]

https://hg.mozilla.org/mozilla-central/rev/d00e5203b958
https://hg.mozilla.org/mozilla-central/rev/1448a8de40a8