22
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ GC traverse all structures in more or less the same way, but only in a very abstract sense (see answer). The way they keep track of thing concretely is a lot more sophisticated than indicated by the elementary presentations you can find in textbooks. And they do not use recursion. Furthermore, with virtual memory, bad implementations show as GC slowdown, seldom as memory overflow. $\endgroup$ – babou Apr 21 '15 at 0:24
  • $\begingroup$ You worry about the space needed for tracing. But what about the space or structures needed to distinguish memory that has been traced and is known to be in use, from memory that is potentially reclaimable. This may have a significant memory cost, possibly proportional to the heap size. $\endgroup$ – babou Apr 21 '15 at 1:27
  • $\begingroup$ I figured it would be done with a bitvector on an object size larger than 16 or so bytes so the over head would be like 1000 times less at minimum. $\endgroup$ – Jake Apr 21 '15 at 1:30
  • $\begingroup$ There are many ways to do it (see answer), and they can also be used for tracing, which would then answer your question (bitvectors or bitmaps can be used for tracing, rather than the stack or queue you suggest). You cannot assume all objects are big, unless you intend to waste space on small objects, of which there can be many, and then you should not worry for space. If you are in virtual memory, space is often much less an issue and the problems are very different. $\endgroup$ – babou Apr 21 '15 at 1:39
13
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ The technique described in the last paragraph is often called "pointer reversal" . $\endgroup$ – Wandering Logic Apr 21 '15 at 12:39
  • $\begingroup$ @WanderingLogic Yes, pointer reversal is how I called it in my own answer. It is due to Deutsch, Schorr and Waite (1967). However, it is incorrect to state that it works in constant memory: it does require $\lceil\log_2 p\rceil$ extra bits for each cell with $p$ pointers, though this can be reduced by using bit stacks. The accepted answer you reference is not quite correct or complete either for the same reason. $\endgroup$ – babou Apr 21 '15 at 20:05
  • $\begingroup$ I have used pointer reversal in a custom GC without needing these extra bits; the trick was to use a special in-memory representation of objects in memory. Namely, the object "header" was in the middle, with pointer fields before the header, and non-pointer fields after; moreover, all pointers were aligned, and the header included a field with the least significant bit always set. Thus, during the pointer reversal backtrack, reaching the next pointer and noticing we had finished with an object could be done unambiguously without the extra bits. This layout also supported OOP inheritance. $\endgroup$ – Thomas Pornin Apr 22 '15 at 12:17
  • $\begingroup$ @ThomasPornin I think the bit information has to be somewhere. The question is where? Can we discuss this in chat? I have to leave now, but I would like to get to the bottom of this. Or is there a description reachable on the web? $\endgroup$ – babou Apr 22 '15 at 16:56
  • 1
    $\begingroup$ @babou and Thomas please $\endgroup$ – Gilles Apr 22 '15 at 23:52
11
$\begingroup$

In a nutshell: Garbage collectors do not use recursion. They just control tracing by keeping track of essentially two sets (that may combine). The order of tracing and cell processing is irrelevant, which gives considerable implementation freedom to represent the sets. Hence there are many solutions that are actually very cheap in memory usage. This is essential since the GC is called precisely when the heap runs out of memory. Things are a bit different with large virtual memories, as new pages can be easily allocated, and the ennemy is not lack of space, but lack of data locality.

I assume you are considering tracing garbage collectors, not reference counting for which your question does not seem to apply.

The question is focussing on the memory cost of tracing for keeping track of a set: the set $U$ (for untraced) of accessible memory cells that still contain pointers that have not yet been traced. This is only half the memory problem for garbage collection. The GC must also keep track of another set: the set $V$ (for visited) of all cells that have been found to be accessible, so as to reclaim all the other cells at the end of the process. Discussing one and not the other makes limited sense, as they may have similar cost, use similar solutions, and even be combined.

The first thing to note is that all tracing GC follow the same abstract model, based on systematic exploration of the directed graph of cells in memory accessible from the program, where memory cells are vertices and pointers are the directed edges. It uses for that the following sets:

  • the set $V$ (visited) of cells already found to be accessible by the mutator, i.e. the program or algorithm for which the GC is performed. The set $V$ is partitioned into two disjoint subsets: $V=U\cup T$;

  • the set $U$ (untraced) of visited cells with pointers that have not been followed yet;

  • the set $T$ (traced) of visited cells that had all their pointers traced.

  • we also note $H$ the set of all cells in the heap, whether or not in use.

Only $V$ and $U$, or $U$ and $T$, need to be represented somehow for the algorithm to work.

The algorithm starts from some roots pointers that are known to the run-time system (usually pointers in stack allocated memory), and puts all the cells they point in the untraced set $U$ (hence in $V$ too).

Then the collector takes cells in $U$ one by one, and checks for each cell $c$ all its pointers. For each pointer, if the pointed cell is in $V$, then nothing is done, else the pointed cell is added to $U$, since its pointers have yet to be checked. When all its pointers have been processed, the cell $c$ is transferred from the untraced set $U$ to the traced set $T$.

The tracing terminates when $U$ is empty. This is bound to happen, since no cell goes through $U$ more than once. At that points, $V=T$, and all cells in $V$ are know to be accessible to the program, thus not reclaimable. The complement $H-V$ of $V$ in the heap determines what cells are unreachable by the mutator program and can be reclaimed by the collector for future allocation to the mutator.

Of couse, details vary depending on how sets are implemented, and on whether it is $V$ and $U$, or $U$ and $T$, which are effectively represented.

I also skip details about what is a cell, whether they come in one size or many, how we find pointers in them, how they may be compacted, and a host of other technical issues which you can find in books and surveys on garbage collection.

You may have notice that this is an extremely simple algorithm. There is no recursion, but only a loop on the elements of the set $U$ that can grow as it is being processed, until it eventually empties. No a priori assumption about extra memory. Whatever allows identifying the sets, and doing cheaply enough the needed operations will do. Note that the order in which cells are processed is irrelevant (no specific need for a pushdown stack), which gives a lot of freedom for choosing the means to represent the sets efficiently.

Where known implementations differ is in the way these sets are actually represented. Many techniques have been actually used:

  • bit map: Some memory space is preserved for a map that has one bit for each memory cell, which can be found using the adress of the cell. The bit is on when the corresponding cell is in the set defined by the map. If only bit maps are used, you need only 2 bits per cell.

  • alternatively, you may have space for a special tag bit (or 2) in each cell to mark it.

  • list: you make a list of those cells that are in the set. You do not need a stack, or a specific data structure. In some system, astute pointer reversal technique allow building the list with very little extra memory, precisely $\log_2 p$ bits where $p$ is the number of pointers per cell, this being further reduced by means of stacks of bits.

  • you may test a predicate on the content of the cell, and its pointers.

  • you may relocate the cell in a free part of memory intended for all an only the cells belonging to the set represented.

  • one interesting special case is having the visited cell relocated in another contiguous area of memory (figuring the set $V$), and representing the set $T$ of traced cells by a single, but changing, boundary address that is greater than adresses of cells in $T$, and less than those in $U$.

  • you may actually combine these techniques, even for a single set.

As said, all of the above have been used by some implemented garbage collector, strange as some may seem. It all depends on the various constraints of the implementation. And they can be rather cheap in memory usage, possibly helped by processing order policies that can be freely chosen for that purpose, since they do not matter for the end result.

What may seem the strangest one, transfering cells in a new area, is actually very common: it is called copy collection. It is mostly used with virtual memory.

Clearly there is no recursion, and the mutator algorithm stack does not have to be used.

Another important point is that many modern GC are implemented for large virtual memories. Then getting space to implement and extra list or stack is not an issue as new pages can be easily allocated. However, in large virtual memories, the ennemy is not lack of space but lack of locality. Then, the structure representing the sets, and their use, must be geared towards preserving the locality of data structure and of GC execution. The problem is not space but time. Inadequate implementations are more likely to show unacceptable slowdown than memory overflow.

I did not give references to the many specific algorithms, resulting from various combinations of these techniques, as this seems long enough.

$\endgroup$
4
$\begingroup$

The standard way to avoid a stack overflow is to use an explicit stack (stored as a data structure in the heap). That works for these purposes too. Garbage collectors often have a worklist of items that need to be examined/traversed, which serves this role. For instance, your "Unscanned" queue is an example of exactly this sort of pattern. The queue can potentially get large, but it doesn't cause a stack overflow, because it is not stored in the stack segment. In any case it will never get larger than the number of live objects in the heap.

$\endgroup$
  • $\begingroup$ When the GC is called, the heap is usually full. Another point is that it happens that the stack and the heap grow from both ends of the same memory space.. $\endgroup$ – babou Apr 21 '15 at 0:33
4
$\begingroup$

In "classic" descriptions of garbage collection (e.g., Mark Wilson, "Uniprocessor Garbage Collection Techniques", Int'l Workshop on Memory Management, 1992, (alternate link), or the description in Andrew Appel's Modern Compiler Implementation (Cambridge University Press, 1998)), collectors are classified as either "Mark and Sweep" or "Copying".

Mark and Sweep collectors avoid needing extra space by using pointer-reversal, as described in @Gilles's answer. Appel says that Knuth attributes the pointer-reversal algorithm to Peter Deutsch, and to Herbert Schorr and W.M. Waite.

Copying garbage collectors use what is often called Cheyney's algorithm to perform a queue traversal without needing extra space. This algorithm was introduced in C.J. Cheyney, "A Nonrecursive List Compacting Algorithm", Comm. ACM, 13(11):677-678, 1970.

In a copying garbage collector you have a chunk of memory that you are trying to collect, called the from-space, and a chunk of memory that you are using for the copies called the to-space. The to-space is organized as a queue with a scan pointer pointing to the oldest copied-but-unscanned record, and a free pointer pointing to the next free position in to-space. The picture of this from Wilson's paper is:

Cheyney's algorithm example

As you scan each item in to-space you copy its children from from-space to the free pointer in to-space, and then change the pointer to the child from from-space to the new copy of the child in to-space. There's an extra trick you need to use when your data structures aren't trees (when a child can have more than one parent). In that case, when you copy a child from from-space to to-space you need to overwrite the old version of the child with a forwarding pointer to the new copy of the child. Then if you ever scan another pointer to the old version of the child you realize that it has already been copied, and don't copy again.

$\endgroup$
  • $\begingroup$ Actually, as explained in my answer, both Mark+Sweep and Copy collection are the same abstract graph algorithm. MS and Copy collection differ only in the way sets used by the abstract algorithm are implemented, and both families are included, with many variants, in some combination of the set implementation techniques I describe in my answer. Some GC variants actually mix MS and Copy in the same GC. Separating MS and Copy is seen by some as a convenient way to structure books, but it is an arbitrary, and I believe outdated, vision. $\endgroup$ – babou Apr 21 '15 at 20:17
  • $\begingroup$ @babou: If one is using a copying algorithm in which everything that is visited will be copied (slow, but may be useful on small platforms where the working set is never all that big), some algorithms may be somewhat simplified since one can use the memory formerly occupied by a relocated object as a scratchpad. One may also gain a limited ability to have other threads perform read-only accesses to objects during collection provided that one checks object validity before and after each read, and follows the forwarding pointer if an object has gotten moved. $\endgroup$ – supercat Apr 21 '15 at 22:51
  • $\begingroup$ @supercat I am not sure what you are trying to say, what is your intent. Some of your statements seem correct. But I do not understand how you can use from-space before the GC cycle is ended (it contains forwarding pointers). And it would be a scratchpad for what? Simplify the algoritm how? Regarding multiple mutator threads executed while GC is taking place, this is largely an orthogonal issue, though it may impact severely implementation. I would not attempt to address that in comments. It should raise less problems in read-only access, but the devil is in the details. $\endgroup$ – babou Apr 21 '15 at 23:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.