One of the defining features of a high-level language like Scheme, Perl, PHP or almost any other recent language is that they have built-in garbage collection (GC), which makes the programmers life much easier because they don’t have to worry about memory management too much. However there are different GC strategies, and costs and benefits depending on the choices you make. I’d like to talk a little about the common GC strategies here, so you can see what the trade-offs are.

Reference Counting Garbage Collection

Unfortunately for both Perl and PHP they made a bad choice of garbage collector; they both opted for the simplest possible mechanism, that is reference counting. Why it is a bad choice I hope to demonstrate.

Reference counting is simple. Each object being memory-managed has a reference-count field which is incremented whenever a new variable refers to the object, and decremented when a variable stops referring to that object. If the reference count reaches zero, nothing can be referring to that object and it can be immediately returned to the free store, decrementing the reference counts of any objects it may contain in turn.

Now this is initially quite attractive: one of the very attractive features, beyond its simplicity, is that garbage collection happens in tiny little steps, and does not usually interfere with the flow of the program, in contrast to Mark-and-Sweep GC discussed below. The real problem with it is that it doesn’t work, at least not in all cases.

The cases where it doesn’t work are where there are circular references between structures. If we imagine a situation where A refers to B, B to C and C back to A, and we have an additional reference X also referring to A, and nothing else, then A will have a reference count of 2 (one from X, one from C), and B and C a reference count of 1. Now when X stops referring to A, A’s reference count will be decremented to 1, but now that entire cyclic structure of A, B and C is cut adrift: since nothing external refers to it, no reference counts can ever be decremented again, and A B and C all still have reference counts of 1.

There are some fancy tricks in Perl to try to work around the problem, specifically weak references which are references that do not disturb the reference counts, but they are probably more difficult to reason about than simple memory management in low-level languages and so are not a valid solution. Another solution is to have a “guard” object acting as a wrapper around the cyclic structure. If the guard object’s reverence count goes to zero its DESTROY method will be invoked, and it then explicitly tells the cyclic structure to remove the circular references so that the components can be recovered. Again this is making memory management the programmers concern.

Mark and Sweep Garbage Collection

This is a strategy that at least works in all cases, but has significant drawbacks. With mark and sweep, a “Free List” of objects is maintained that can be used for their space. A normal request for memory will retrieve an object from the free list and put it on to an “in Use” list. If there are no objects available on the free list, then Mark and Sweep Garbage collection is invoked. Mark and Sweep, as its name suggests, proceeds in two stages. The first is to follow all pointers from the current execution context, recursively, and to “mark” all objects found as “in use”. The next phase, the “Sweep” phase, traverses the “In Use” list and moves any objects not marked as in use to the free list (also resetting the “mark” on all objects).

The problem is that in a typical application the majority of the objects on the “In Use” list will not be actually in use, and the sweep phase will use a lot of resources moving unused objects back to the free list. This can produce a pronounced “stutter” in interactive programms, where they appear to hang for seconds at a time. This behaviour was a common failing of early Lisp implementations, and one solution there was to provide a (gc) command that the programmer could sprinkle around the code in order that the number of unused objects on the used list never got too big. Again this is passing memory management back to the programmer, albeit at a higher level.

Copying Garbage Collection

The realisation that most supposedly in-use objects actually are not in use is a clue to a more time efficient (but not space-efficient) garbage collection strategy.

To get it to work we have to drop the high-level notion of lists, and instead get down to the machine level and consider free pools and in-use pools, where a pool is just a contiguous region of memory on the heap.

Basically, instead of moving everything that isn’t in use from the in-use pool to the free pool, we move what is in use, as we find it during the mark phase, to the “free pool” then we swap the ponters to the two pools: so the free pool becomes the in-use pool and vice versa. We know that the free pool was initially empty otherwise garbage collection would not have been invoked. Of course that means we can no longer have an explicit (gc) command, but that’s not a bad thing. It also means we can dispose of the Sweep phase altogether.

The remaining details are fairly simple: when moving an object from the in-use pool to the free pool, we must leave a note behind to say that it has been moved, and where it has been moved to. We replace the old copy of the object with a “forwarding pointer” with a flag to say that it has been forwarded. That way any further encounters of the object during garbage collection merely update their pointers to refer to the new copy and then stop, because the object and its contents have already been moved.

Generational Garbage Collection

Another observation about the memory usage of typical applications provides a more time efficient variation on Copying Garbage Collection. That observation is “the longer an object has persisted, the longer it is likely to persist”.

To leverage that observation, we divide our heaps into “generations”. The most recent generation being the objects that have not yet been through a garbage collection. Generational Garbage collection inspects the most recent generation of in-use objects first, and if it can reclaim enough space there its job is done. It moves objects still in use to the next generation, and so on (the choice of the number of generations is presumably configurable, and the oldest generation falls back to standard Copying Garbage collection behaviour.)

More details needed, later…