Automatic memory management allows the developer to focus on application logic (e.g., payroll, solving math problems) instead of innate details, such as memory allocation. However, popular computing languages like C and C++ didn’t have a standardized method for supporting automatic memory management until very recently. Popularity and standardization occurred with the emergence of governed virtual machines that execute intermediate languages, such as the virtual machines used to run Java or the .NET languages.

A deceptively difficult, yet interesting problem to solve is in the area of automatic memory management. Half of the problem, the act of allocating memory to a program, is relatively trivial—the hard part is discovering when a program is truly finished with a piece of memory. Memory that is no longer needed, garbage memory, is collected by a garbage (memory) collector. The goal is to free unused memory as soon as it becomes garbage, so it can be reused later in the program if needed.

Many different types of algorithms have surfaced to handle memory management. Yet, there still is no best solution for all cases. This article discusses some of most popular garbage collector (GC) algorithms used today in the Java and .NET virtual machines. Garbage collecting algorithms work either on the fly while objects are being referenced and dereferenced, or in snapshot mode as if periodically the memory picture of the application is frozen while the collection runs and finds the garbage.

Reference counting
Probably the most intuitive automatic memory management algorithm is reference counting. If you keep track of which objects the program is referencing, those objects must still be needed. Implementing the algorithm requires that each object has a data field that is updated as to how many other program objects reference (i.e., point to) it. Any references of the object pointing to itself are ignored. If that count ever goes to zero, the object in question is considered garbage. After all, if no one references an object, it is, in effect, orphaned in memory. In terms of memory and performance, this is the most efficient way to collect garbage memory.

Unfortunately, computer scientists face an impossible problem with this algorithm. If two objects or a large chain of objects point to each other, and that set of objects is orphaned from the system, there is no obvious way to see the cycle. Since all objects involved have a reference count of at least 1, they preserve their nongarbage status.

Because of this problem, reference counting isn’t often used in modern VMs with any fervor. In fact, Java only uses reference counting with distributed objects (i.e., remote method invocation), which is borrowed from Modula-3’s Network Objects. Distributed memory management imposes new constraints on garbage collections. Things like slow object access and references that can disappear at the drop of a network must be dealt with. Even though reference counting can leave cyclical garbage object sets alive, for performance and practicality reasons, it is more suitable for garbage collecting than other algorithms.

Mark and sweep
Mark and sweep garbage collecting seems to always be the first try when developers of new systems implement garbage collection. It is theoretically easier to implement than other systems, but keep in mind that easy is relative. This algorithm was used in many Java VMs in early versions and is still used as a subalgorithm in advanced garbage collectors today.

Mark and sweep starts by traversing all pointers from some canonical system object. That object is key to the VM, as in: If that object were to not exist, the VM is going down (i.e., the program has finished execution). Each object encountered via the pointer traversal is marked as being visited. Recursively, all pointers from all encountered objects are then traversed. In effect, this operation traverses the entire pointer reference tree rooted at the system canonical object, marking all objects marked along the way.

Once this stage is complete, the algorithm looks at its complete list of known objects in existence. If any objects are found unmarked, they are considered to be disconnected from the system (garbage).

This algorithm is clean and simple but suffers from some nagging issues. First, it requires all program execution to halt while it performs a job. Changes to the reference tree, while it is in midtraversal, compromise the algorithm. This algorithm was responsible for the pauses in execution that Java was famous for in its early days. Also, repeated sweeps cause memory fragmentation, which makes the job harder on the allocator. Eventually, a memory defrag must be run to clear up the fragmentation, causing even more pauses in execution.

Stop and copy
A cousin to mark and sweep is stop and copy collection. Stop and copy solves the defragmentation problems of mark and sweep at the expense of higher memory requirements (or a smaller object pool that induces more frequent collections). This algorithm is present in the Microsoft Java VM, which at introduction was one of the fastest VMs around.

Stop and copy works by creating two memory pools for objects but only uses one of those pools. As you allocate objects, it simply gives you the next available space in its active memory pool. If that pool fills up—or if the system decides it is time to collect—it performs the same traversal phase as mark and sweep, following all pointers from a system object through your program. But instead of just marking the objects, it copies them from the current memory pool to the inactive one.

The copy ends up nestling the live objects one after the other in the new pool. Once complete, it switches active memory pools. Since it only copies active objects, garbage objects are simply left behind. They aren’t so much collected as abandoned. The copying inherently defragments the new pool since one object is placed right after the other.

Stop and copy still must stop the running program to collect objects and move them into the memory pool. While it’s running, the application that it’s cleaning up after is not running, and this manifests as choppy behavior for some applications.

Profiles of active garbage collection revealed some fundamental flaws in how GC algorithms worked versus how garbage needed to be collected. Most objects in a running application only live for a short while and a select few live the entire life of the application. The algorithms outlined above treat all objects equally. Unfortunately, every active object requires some work upon it (e.g., shuffling, marking), which negatively affects performance. Objects that live a long time are continuously—and needlessly—shuffled around as they survive collection to collection.

Contemporary garbage collectors like the one in the latest Java Hotspot VM create separate pools for younger and older objects called generations. If an object survives a specific number of collections (sometimes just one, but it depends on the collector), it is moved from a younger pool to an older pool. The older pool is, by nature, collected less often in hopes that, since these objects have lived awhile, they’re likely to live awhile longer.

The effect is a greatly reduced load upon the garbage collector. Short-lived objects that die inside a collection cycle have less impact on the collector since collectors mostly deal only with live objects. Older generations are collected far less often, reducing the needless shuffling of old objects.

Different generations can even have different algorithms used within them. For example, a stop and copy is suitable for the young object pool since it is assumed most young objects die quickly (stop and copy has a linear performance cost in respect to the number of nongarbage objects). Older generations can take extra steps towards exacting algorithms since performance is less of an issue.

Put garbage collection to good use
For all its merits, garbage collection still takes CPU cycles away from a running program. The best way to minimize that impact is to simply create fewer objects. Fewer objects provide fewer collections, which theoretically improves performance.

Garbage collection is a solid step toward taking away some nasty details from everyday programming. It was a hot topic of research in years past and most of the technology used today is quite old (in computing terms anyway). It is about time you put garbage collection to good use.