653019 - switch cycle collector graph builder from BFS to DFS

Status: RESOLVED INCOMPLETE

(Core :: XPCOM, defect)

Description

[Andrew McCreight [:mccr8]]

Currently, the cycle collector builds the graph using a breadth first search, using the node pool as the queue.  This is nice because it means that the root nodes are all lined up so they can be easily traversed.  It is bad because we cannot prune the graph while we traverse it: when we see a node, it gets allocated, and we don't examine it until much later.  On the other hand, if we do a depth first search, we can throw avoid allocating nodes as we go.

I believe there are a lot of opportunities for reducing the size of the cycle collector graph during traversal, for instance by dynamically detecting acyclic structures and by collapsing strongly connected components of JS objects.  This will not improve the performance of the first traversal, but should greatly speed up later traversals, as well as reducing memory usage.  From my reading of Jones and Lins's GC book, this may also improve locality.

We will probably need to do something similar to Bug 616666 to avoid exploding the call stack.  In one experiment I did, a depth of 55 or so was sufficient, but I'm sure it can get much worse.

Another problem is that we won't be able to store the set of root nodes in the node pool any longer.  The straightforward solution to this is a separate array of root pointers.  We could also look into treating every node in the cycle collector graph as a root.  In my observation, almost every DOM node in the cycle collector graph is a root anyways, so if we can collapse together most of the JS heap, then we should be able to do this without too much wasted time compared to the current setup.

Comment 1

[Andrew McCreight [:mccr8]]

Doesn't seem like this really needs a separate bug.