How do garbage collectors avoid stack overflow?

Problem Detail: 

So I was thinking about how garbage collectors work and I thought of an interesting issue. Presumably garbage collectors have to traverse all structures in the same way. They can't know weather they are traversing a linked list or a balanced tree or whatever. They also can't use up too much memory in their search. One possible way, and the only way I can think to traverse ALL structures, might be just to traverse them all recursively the way you would a binary tree. This however would give a stack overflow on a linked list or even just a poorly balanced binary tree. But all the garbage collected languages that I have ever used seem to have no problem dealing with such cases.

In the dragon book it uses a "Unscanned" queue of sorts. Basically rather than traversing the structure recursively it just adds things that need to be marked too a queue and then for each thing not marked at the end it is deleted. But wouldn't this queue get very large?

So, how do garbage collectors traverse arbitrary structures? How does this traversal technique avoid overflow?

Asked By : Jake

Answered By : Gilles

Note that I am not a garbage collection expert. This answer only gives examples of techniques. I do not claim that it is a representative overview of garbage collection techniques.

An unscanned queue is a common choice. The queue can get large — potentially as large as the deepest data structure. The queue is typically stored explicitly, not on the stack of the garbage collection thread.

Once all but one of the children of a node have been scanned, the node can be removed from the unscanned queue. This is basically a tail call optimization. Garbage collectors can include heuristics to attempt to scan the deepest child of a node last; for example a GC for Lisp should scan the car of a cons before the cdr.

One way to avoid keeping an unscanned queue is to modify pointers in place, making the child temporarily point to the parent. This is a constant-memory tree traversal technique that's used in contexts other than garbage collectors. The downside of this technique is that while the GC is traversing a data structure, the data structure is invalid, so the GC has to stop the world. This isn't a deal breaker: many garbage collectors do include a phase that stops the world, in addition to phases that don't but can miss garbage as a result.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/41616