548733 - use a self-terminating edge list for the cycle collector

Status: RESOLVED WONTFIX

(Core :: XPCOM, defect)

Description

[Andreas Gal :gal]

We currently use pool-allocated chunked lists in the cycle collector that have a begin and end pointer. Chunk transition can only occur at 64k allocation unit (block) boundaries.

I suggest switching this to self-terminated lists. Based on the observation that pointers are always 4-byte aligned (jsvals say hello), we implement 2 tags: GOTO and STOP. GOTO(label) is inserted to transition to a new block. STOP(value) labels the last element in the list and replaces the end pointer.

A couple advantages:
- We save a word per PtrInfo. We expect to make millions of those, so we should save some respectable amount of memory.
- We can inject GOTO markers at arbitrary points, not just at block boundaries. This can be used to inject additional edges later on. This might come in handy for weak pointer scanning.

The patch is completely untested and I am uploading it to discuss the idea.

Comment 1

[Andreas Gal :gal]

Attachment: patch

Comment 2

[Andreas Gal :gal]

Note: a null pointer is used to represent the empty list, since the shortest list we can build is [ STOP(0th entry) ].

Comment 3

[Andreas Gal :gal]

On a somewhat related note, we could eliminate mParticipant from PtrInfo and save another word, making it 4 words instead of 5 (currently 6) by stealing another bit from mInternalRefs. We only have 2 participants, realistically :)

Comment 4

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

The basic idea seems reasonable.  I didn't look all that closely, though.

(In reply to comment #3)
> On a somewhat related note, we could eliminate mParticipant from PtrInfo and
> save another word, making it 4 words instead of 5 (currently 6) by stealing
> another bit from mInternalRefs. We only have 2 participants, realistically :)

I think we have one participant for everything in JS, and then another one for each class of XPCOM object or non-XPCOM C++ object that participates in cycle collection.  That's a lot more than two.

Comment 5

[Andreas Gal :gal]

Attachment: patch

Iteration was broken for lists of length 1. Invoke the magic of the pre-processor to make things a bit more readable and consistent.

Comment 6

[Andreas Gal :gal]

Attachment: patch

And this time the right patch.

Comment 7

[Andreas Gal :gal]

Oh. Ok. I must have confused that with nsCycleCollectionLanguageRuntime.

Comment 8

[Andreas Gal :gal]

Attachment: patch

Make bulk insertion into an existing list more efficient and maintain the order of list entries.

Comment 9

[Andreas Gal :gal]

Attachment: patch

Working patch (passes some simple xpcshell tests and I seem to be able to browse with it).

Comment 10

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

Why do we need insertion into an existing list?

Is there a good way to make the emptiness check more similar to the has-more-elements check so that we wouldn't need the macro?

Comment 11

[Andreas Gal :gal]

- We are trying to cycle collect ephemeron tables, and those contain additional edges in the graph, which we don't see until we actually get to the table (a row [a,b] in the table means that b is live if a is live, so we have to insert an edge a->b while marking the table). The method is only there as proof that this data structure allows insertion. I will remove it and land the rest separately until we need it, since even without this option its beneficial.

- Its NULL vs ->methodCall(), so to make those match I have to check for NULL in every iteration or waste an array entry as sentinel. How dare you insult my macro, I like it ;)

Comment 12

[Andreas Gal :gal]

Attachment: patch

Comment 13

[Andreas Gal :gal]

Patch ready for review, with lots of help from peterv debugging it.

Comment 14

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

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

Please call EdgePool::current mLastBlock instead of current.

Please call EdgePool::Block::next mPrev instead of next.

(Alternatively, you could update comments in various places to say that iterators can have GOTOs that go into the previous block, but I think it makes more sense to talk about the blocks in the order we create them.)

Given your changes to make the list linked in backwards order,
  Block **mNextBlockPtr;
can just become:
  Block *mNextBlock;

>+    EdgePool() :
>+        current(nsnull)

>+        Block() :
>+            next(nsnull)

Local style puts the : on the second line in both of these cases, i.e.,:

EdgePool()
    : mCurrent(nsnull)

Block()
    : next(nsnull)


Does gcc give any aliasing warnings?  If so, the switch to uintptr_t
should probably be a union of uintptr_t and PtrInfo*.

>+        uintptr_t *End() { // Point past the last element
>+            return &mPointers[BlockSize - 1];
>+        }

This seems like the comment and the code are inconsistent.  If not, I
think a bit more of a comment is needed to explain why the last element
of mPointers[] is not actually an element..

I think I'd tend to prefer fixing the code, which would also involve
changing:
>+            if (mCurrent+1 >= mBlockEnd) {
to the more standard:
>+            if (mCurrent >= mBlockEnd) {
and perhaps looking through other uses of mBlockEnd.

Also, on the same topic, the comment:
>         // mBlockEnd points to space for null sentinel
is now wrong, and you should adjust it to match whatever you do above.


>+#define foreach_edge(list, e, block) \
>+    if (!list.isEmpty()) {           \
>+        EdgePool::Iterator e = list; \
>+        while (true) {               \
>+            { block; }               \
>+            if (!e.hasMore())        \
>+                break;               \
>+            ++e;                     \
>+        }                            \
>+    }

This should use PR_BEGIN_MACRO and PR_END_MACRO, and should put
parenthesis around uses of (list) inside the macro.


I'm a little skeptical of the |Append| methods you've added; they look
rather inefficient (iterating the whole list) and I wonder if they're
really what you'll end up needing if you really want to append in the
middle.  Feel free to remove them if you agree, although I'm also ok
with leaving them.  (It looks like they're unused.)

>+                // Emit a goto marker in the outgoing block
>+                if (mCurrent) {
>+                    NS_ASSERTION(mCurrent < mBlockEnd, "no room to write goto marker");
>+                    if (mCurrent == mBegin) {
>+                        mBegin = mCurrent = b->Start();
>+                    } else {
>+                        *mCurrent = uintptr_t(b->Start()) | GOTO;
>+                    }
>+                }

Maybe worth emitting the marker so the blocks are all linked even if no
node's edge list needs the linkage?

>+                NS_ASSERTION(!(*mPointer & GOTO), "goto marker targeting goto marker");

Can't this assertion be violated by use of Append?  (As I said, I'm a
little skeptical of the Append methods.)  I think if you want to keep
Append you need to turn this (GOTO-dereferencing code) into a while loop.

>-            for (EdgePool::Iterator e = ppi->mFirstChild, e_end = ppi->mLastChild;
>-                 e != e_end; ++e) {
>+            foreach_edge(pp->mFirstChild, e,

Should be ppi, not pp.  (You should probably try compiling with DEBUG_CC
to check for other compilation errors.)

>-            debugInfo.mLastChild = pi->mLastChild;
>             debugInfo.mCurrentChild = pi->mFirstChild;
>-            for (EdgePool::Iterator child = pi->mFirstChild,
>-                                child_end = pi->mLastChild;
>-                 child != child_end; ++child, debugInfo.mCurrentChild = child) {
>-                sCollector->mGraph.mEdges.CheckIterator(child);
>+            foreach_edge(pi->mFirstChild, child,
>                 aQueue.Push(*child);
>-            }
>+                debugInfo.mCurrentChild = child;
>+            );

This sets mCurrentChild differently from the current code.  You should
move the assignment you move ou tof the loop to before the aQueue.Push()
call, and then remove the assignment of pi->mFirstChild to mCurrentChild
before the loop.


There are a whole bunch of 80th column violations in the patch.  If it's
really ugly to avoid them, then I suppose it's ok, but please at least
fix the:
 * multiline wrapped comments
 * NS_ASSERTION where the assertion text could easily be on a second line


r=dbaron with those things fixed

Comment 15

[Andreas Gal :gal]

Thanks. I will post a new patch for final stamping due to the volume of changes.

Comment 16

[Andrew McCreight [:mccr8]]

Bug 658386 implemented the elimination of mLastChild, and the separation of the GC and CC has enabled a more elegant approach to CCing weak pointers, so I think the patch in this bug isn't needed any more.