Programmer Musings

Other Resource Recovery Approaches

In The Semantics of Garbage Collection, I explained why I don't like the term garbage collection. I also introduced the term resource recovery, and suggested that this change in naming could generate a useful change in viewpoint.

In the next article, More Thoughts on Resource Recovery, I traced some of the history and side effects of the main current approach to garbage collection. I also pointed out where I think this approach makes a wrong turn.

Now, I'd like to turn to alternative approaches. Some that exist, and some that don't (yet).

The simplest and easiest to understand form of memory management is stack-based, local variables. The life-time of the variables matches the scope in which they are declared. Memory is automatically cleaned up when execution leaves the scope. If we could limit our use of memory to the current scope and any functions called from that scope, the memory problem would vanish. Unfortunately, this approach is too restrictive for most programming projects. At the very least, the lifetime of data in an object must persist beyond the scope of the constructor.

C++ has a very clean system for dealing with memory or any other resource. By defining both a constructor and a destructor, you can guarantee that memory is allocated when an object is created and freed when the object is destroyed. In the same way, you can allocate or acquire any resource at construction time and release or free it at destruction time. C++ programmers refer to this as the resource acquisition is initialization (RAII) idiom. Using this idiom consistently with only stack-based or member-data objects will also prevent resource leaks.

Unfortunately, this is still not the whole story. Sometimes, there is the need to share the same object between two places in the code or objects. There is also sometimes the need to have objects that live outside the particular scope in which they are created. Although, there are still special cases that can be handled simply, there is no way to always be able to recognize every way in which the programmer might want to deal with memory. For this reason, many computer scientists gave up and went the garbage collection route.

As I said in my last entry, the simplest case of automatic memory management uses reference counting. In this approach, every object carries with it a count of the number of references to it that currently exist. Many systems have relied on this relatively simple form of resource recovery. It has been re-implemented for use in many objects over time. There are a few subtleties to the implementation, but in general this approach works surprisingly well.

Reference counting has two problems, one minor and one major. The minor problem is the extra overhead of dealing with the count. For a small object, the count could be a significant increase in the size of the object. Dealing with the reference counts adds a small amount of effort when a new reference is made or an old one goes away. However, the real killer is circular references. A references B, that references A. Even if the last external reference to A or B goes away, these two items still have non-zero reference counts.

This issue is the result of a fundamental flaw in the reference counting approach. Reference counting mixes up life-time with ownership. These two concepts are strongly related, but they are not the same. In the C++ world, this problem has been explored in the Boost C++ Libraries. In this library, different programmers have designed a set of smart pointers with different semantics. You might wonder what kinds of semantics a pointer could have.

In many cases, the lifetime of an object is only really tied to one of it's references. That reference can be considered the owner of the object. The only time that reference counting makes any sense is when more than one reference must be the owner. So, let's look at ownership a little more closely. How do we define the ownership of an object? If an object is only referenced once, that reference is the owner. This includes objects on the stack. The only owner is the "reference" on the stack. Temporaries created by the compiler also only have one owner, the temporary reference that goes away at the next sequence point. Member or instance data usually only has one owner, the object it resides in. As much as we try to ignore them, globals and class data also only have one owner.

All of those kinds of references make up the easiest case. When the owner reaches the end of its life so does every object that it owns. The C++ destructor concept handles this very well for member data. Most languages handle it well for local objects. The C++ compiler handles this for temporaries. This is the easy case that everyone pretty much understands without thinking. It's also relatively easy to prove correctness for this case. Unfortunately, the whole world does not fit in this category.

Only slightly more complicated is assignment of ownership. This is when the old owner gives up it's ownership when making a new reference. The Standard C++ std::auto_ptr embodies this concept. This is often seen when a method or function returns an object. The old owner, the called method, gives ownership of the object to the calling method. Then the old reference ceases to exist. This sometimes also happens when putting items into a collection. The final case is when an object reference is copied to a new reference and the original reference is pointed to a new object. (Think manipulation of a linked list.)

The next level of complexity involves temporary shared access. This is the kind of sharing that happens when a temporary reference is made to an object but the original reference remains the owner. The most obvious example of this is passing an object to a function or method by reference. The function has a temporary reference to the object, but the object is owned by the calling code.

The interesting thing about all of these is that the compiler actually could determine the owner of the object fairly reliably in each case. By replacing the normal references with specialized references that either do or don't take control as needed, the compiler could convert each of these cases into something very close to the simple single owner, stack-based approach described earlier.

In these cases, we could get timely resource recovery and useful object lifetime semantics without resorting to a full-blown garbage collection system.

Unfortunately, that's not the whole story. The rest of the story will need to wait for later.