Conservative garbage collector

Question

I've seen garbage collectors labelled as a lot of things- generational, etc. But I've seen the Boehm GC labelled as "conservative". What exactly does that mean?

Answer 1

A garbage collector must scan all objects and invocations (execution stack) to identify all of the "live" addresses in the executing program and then "collect" objects that do not have "live" addresses. In some environments it's possible for the GC algorithm to be PRECISE and know exactly what is an object address and what is not. In other environments it must scan parts of storage (most notably the execution stack) where there are words of storage that MIGHT be an object address and make the CONSERVATIVE assumption that if it looks like a valid address, and there is an object that has that address, then the object should not be collected.

There are advantages to conservative collection, most notably that the code generator (if not interpreted) is freer to allocate variables where and when it needs them and it need not keep rigorous track of which are object pointers. (The need to keep track of object pointer locations can lead to less well optimized code, in addition to making the code generator considerably more complex. Also, a conservative collector stands some reasonable chance of being used with a compiler which was never intended to support garbage collection, while a precise collector would require that the compiler be radically altered.)

The major disadvantage of the conservative approach is that a full "copying" collector cannot be implemented. When copying is done the pointers to the copied objects must be updated, and if it's not clear whether a given bit value is an object pointer or just a numeric value, it cannot be safely determined whether or not it should be modified when the object is copied. There's also the disadvantage that some "dead" objects may end up not getting collected, due to random bit patterns that look like their addresses, though in practice this is not a serious concern.

Answer 2

A conservative garbage collector is one that does not know whether or not a given word is a pointer. If the word points into an allocated heap block then the garbage collector conservatively assumes that the word is a pointer and, therefore, does not recycle that heap block or anything considered to be reachable from it.

The main advantage of this approach is that it can collect unreachable values without having to work in harmony with the compiler. However, there are many disadvantages:

1. Values that happen to look like pointers cause memory leaks by preventing parts of the heap from being recycled. This is a much bigger problem with 32-bit address spaces because almost every int will point to a heap block if GBs of RAM have been allocated.

2. Determining whether or not a word points into an allocated heap block requires the heap to be searched which is slow and (objectively) unnecessary.

3. The GC cannot move heap blocks because it cannot update pointers because it does not know where they all are.

4. Code that hides pointers or uses pointers outside the heap block will crash a conservative GC. This problem arose with the Numerical Recipes code and Boehm GC, albeit because the NR C code violated the C spec.

These disadvantages are severe enough that production garbage collectors try not to be conservative whenever possible.