378514 - record and play back cycle collection traversal to avoid repeating it

Status: RESOLVED FIXED

(Core :: XPCOM, defect)

Description

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

The cycle collection algorithm requires traversing the graph twice.  Since some of our traversal methods are slow, we should essentially record their output the first time through and then play that output back the second time so that we don't need to call all the methods on the traversal API twice.

PtrInfo currently represents a node in the graph.  This means we'll also store the edges.

I propose storing the edges (as PtrInfo*) in a linked list of big buffers (say, 32K of edges at a time) and the nodes (PtrInfo) in a similar linked list of big buffers.  Storing the PtrInfo in a buffer has the advantages that the PtrInfo will have stable addresses, so we can put them in mQueue (saving the Lookup call at the start of the loop in GraphWalker::Walk) and in the edge buffer, and also that we'll shrink the wasted space in the hash table mapping pointers to PtrInfo (which we'll now only need during the first traversal).  This should give the graph replay pretty good memory locality (since it will walk forward with one cursor through each of the two buffers, or, if the walker looks at children, with two cursors through the node buffer).

I'll be removing MarkGreyWalker (replacing it with something less generic) and removing NoteChild from the GraphWalker class.

Comment 1

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

(In reply to comment #0)
> or, if the walker looks at
> children, with two cursors through the node buffer).

Er, that's only true in the edge case of each child having only one parent.  With more than one, walkers that look at children (which appears to be only the graphVizWalker) would cause jumping around in memory.

Comment 2

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

Er, and flooding black doesn't have very good memory locality either since it's a sub-traversal.

Comment 3

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

Attachment: patch

1 file changed, 641 insertions(+), 503 deletions(-)

Still need to do some performance measurement.

Comment 4

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

Attachment: patch

1 file changed, 644 insertions(+), 512 deletions(-)

I cleaned up a few issues in the previous patch before doing performance tests.

I did the following test.  I created a clean profile, opened 30 Firefox windows with the default Firefox/Google start page, changed the homepage preference to restore my session, quit, and backed up the sessionstore.js.

Then, for the test, I restored the sessionstore.js from the backup, started Firefox (so session restore restored the 30 windows), and then closed the windows one window at a time until the cycle collection times increased (which indicates the first set of pointers was aged enough to be collected).  I then recorded the times (in milliseconds, based on PR_IntervalNow()-based printfs in nsCycleCollector_collect) of the times taken by the collection preceding the increase and the three collections following.  I repeated this test twice without the patch and then twice with the patch.  The times I got were (note that this patch shouldn't affect the first time):

Without patch (ms):
  263, 1448, 987, 919
  255, 1503, 1027, 952
With patch (ms):
  255, 978, 717, 671
  258, 976, 722, 669

I think comment 0 is still a pretty good description of the basic approach in this patch.

Comment 5

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

I'd also note that we shouldn't need the safety callback for debugging anymore since we canonicalize() earlier now.

Comment 6

[Peter Van der Beken [:peterv]]

Comment on attachment 262705 [details] [diff] [review]
patch

Looks great. I only have some nits:

>+        Builder(EdgePool &aPool)
>+          : mCurrent(&aPool.mSentinelAndBlocks[0])
>+          , mBlockEnd(&aPool.mSentinelAndBlocks[0])
>+          , mNextBlockPtr(&aPool.Blocks())

Nit: style in the file is to put commas at the end.

>+        void Add(PtrInfo* aEdge) {
>+            if (mCurrent == mBlockEnd) {
>+                EdgePool::Block *b = new EdgePool::Block();
>+                if (!b) {
>+                    // This means we just won't free things.

I'd say s/free things/collect cycles/ to avoid confusion.

>+struct PtrToNodeEntry : public PLDHashEntryHdr {

Nit: brace on its own line.

>+static PLDHashTableOps PtrNodeOps = {
>+    PL_DHashAllocTable,
>+    PL_DHashFreeTable,
>+    PL_DHashVoidPtrKeyStub,
>+    PtrToNodeMatchEntry,
>+    PL_DHashMoveEntryStub,
>+    PL_DHashClearEntryStub,
>+    PL_DHashFinalizeStub,
>+    NULL

Nit: nsnull

>@@ -872,20 +1172,16 @@ GraphWalker::NoteXPCOMChild(nsISupports 
>     scanSafe &= !nsCycleCollector_shouldSuppress(child);
> #endif
>     if (scanSafe) {
>-        PtrInfo *childPi = mGraph.Add(child);
>+        PtrInfo *childPi = AddNode(canonicalize(child));

Why do we need to canonicalize again? I guess we can rewrite this as:

{
    if (nsCycleCollector_isScanSafe(child) &&
        (child = canonicalize(child)) {

#ifdef DEBUG_CC
        if (!nsCycleCollector_shouldSuppress(child))
            return;
#endif

        PtrInfo *childPi = AddNode(child);
        if (!childPi)
            return;
        mEdgeBuilder.Add(childPi);
        ++childPi->mInternalRefs;
    }
}

(I haven't tested this).

I think removing the canonicalize calls is ok, though I'm still looking at those. I don't think you really changed when we canonicalize?

Comment 7

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

(In reply to comment #6)
> Nit: style in the file is to put commas at the end.

I'd prefer to switch the style here -- it makes the DEBUG_CC ifdefs much cleaner.  (I suppose if I want to be consistent I should change nsCycleCollectorParams, nsPurpleBuffer, and nsCycleCollector as well.)

> Why do we need to canonicalize again? I guess we can rewrite this as:

Oh, right, the canonicalize call was always in NoteXPCOMChild, which means the safety callback was unneeded since we added canonicalize.

And you're right that I added an extra call, although I do seem to remember moving it from somewhere else.  I suppose I was imagining that.  I think I was moving it around in MarkRoots and ended up searching for AddNode callers and making sure they all called canonicalize().

I'll just remove the unneeded call; I don't see a need to reorganize otherwise.

Comment 8

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

Attachment: patch

This addresses peterv's review comments.

And I did switch back to file style for member initializers.

Comment 9

[Graydon Hoare :graydon]

Comment on attachment 262774 [details] [diff] [review]
patch

looks good.

Comment 10

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

Checked in to trunk.

Comment 11

[[e-mail]]

Comment on attachment 262774 [details] [diff] [review]
patch

>+        EdgePool::Iterator Mark() { return EdgePool::Iterator(mCurrent); }

>+        EdgePool::Block **mNextBlockPtr;

Was there any particular reason for these EdgePool:: prefixes?
(We're still in the class EdgePool { } scope here...)

Comment 12

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

No.  I should probably remove them.