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.

More Thoughts on Resource Recovery

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.

Many programmers have been indoctrinated with the belief that garbage collection is the solution to all memory problems, and that any language that does not use garbage collection is destined to be full of memory leaks. I disagree. But to really understand why I think otherwise will require a little history.

In the Beginning

Well, at least in the beginning of my programming career was Fortran. In the first dialect of Fortran I ever used, all memory was global memory. Even local variables in a subroutine were allocated as global memory; they just weren't visible outside the subroutine. There was no allocation of memory. Therefore, there were no memory leaks. There was also no recursion, because calling a subroutine from itself would wipe out the current values of its "local" variables.

These conditions no longer apply to Fortran, but they were the state of Fortran when I started. (Or at least the state of Fortran as I understood it then.)

The Stack and the Heap

Later in my career, I began to work in more modern languages. The first of these was C. In C, there were two types of memory besides the static memory I knew from Fortran. There was the stack and the heap. (I had actually seen these before, but I'll ignore that detail for now.)

The stack had the wonderful property that it would grow as you needed it and automatically be reclaimed at the end of the function (or block). It also allowed multiple copies of a function to have its own local variables, giving the possibility of recursion. Most of the time, stack memory is easy to use and is recovered automatically. As long as you didn't try to put a huge amount of stuff on the stack or recurse too deeply, everything worked out fine.

The heap had another wonderful property. I could allocate as much of it as I wanted (within reason) and give it back when I was finished. This allowed me to work with different amount of data without guessing the biggest size I could deal with ahead of time. However, this feature came with a dark side: the memory leak.

Objects

Then I discovered Object Oriented Programming. One of the most wonderful features of objects for me was the whole concept of the object lifetime. I could have an object that allocated memory as part of its construction and that would free that memory at destruction time. No more memory leaks! I could make allocated memory act like the stack memory that I had always liked. Well, of course things did not really work like that. People can allocate objects as well and automate the whole process of leaking memory.

Perl and Memory Management

At about the same time I found C++ and OOP, I also discovered Perl. Now Perl did not have objects at the time, but it did do automatic handling of memory in many cases. Over time, Perl developed real local variables (called my variables) and objects. Perl supported a simple garbage collection system called reference counting. Unlike the more popular mark and sweep garbage collection, reference counting has two really important virtues: it's simple to understand and it preserves object lifetime.

In a reference counting scheme, every object keeps count of the number of references pointing to it. As a reference goes away, the count of the references is decremented. When the count reaches 0, the object is really destroyed. This happens at a well-defined time, when the last reference is removed. This method is simple to understand and works very well in general. In fact, to my knowledge, reference counting has only one flaw: circular references. If object A references object B and object B references object A, and no other references point to either of them, we have a memory leak. These two objects are not referenced anywhere, but they cannot be reclaimed.

Reference counting works particularly well when objects are only referenced once or twice. This covers the simple object creation case and many uses of temporary objects created by the compiler. These objects are created and destroyed exactly the way you would expect.

Mark and Sweep

The great flaw of reference counting is one of the reasons that the mark and sweep approach was developed. Since mark and sweep starts from known references and works through all memory to find any that is referenced, circular references are not a problem. Unfortunately, mark and sweep suffers from a few problems of its own.

• The garbage collector can not be allowed to delete or move memory that is part of the stack.
• The time taken to garbage collect is a function of the amount of currently allocated memory, not the amount of memory to reclaim.
• The garbage collector does not usually respect object lifetimes.

The first point is why Java does not allow objects to be created locally on the stack. Otherwise, objects on the stack would need to be cleaned up differently than objects on the heap. With mark and sweep, this would require recognizing what parts of the objects are in which locations and treating them accordingly. The easiest solution was to define the problem away and only allow heap-allocated objects.

In order to perform the mark portion of the algorithm, we will need to touch each reference to every object to verify what is still in use. In order to perform the sweep portion of the algorithm, all referenced objects need to be moved so that the old memory can be reclaimed. More advanced versions of the system partition objects in different ways (new and old objects, etc.) to reduce this overhead to some extent.

For me, the worst effect of mark and sweep is the loss of object lifetime. An object's lifetime should run from the point where it is created to the last place it can be referenced or when it is explicitly killed. With the mark and sweep system, there is a period of time when the object is left in a kind of limbo. It cannot be referenced, but it hasn't been cleaned up. It's like a ghost of an object.

The Wrong Turn

Although I understand the purpose of garbage collection, it seems to me that we've taken a wrong turn. There was a time when we had stack-based data that was cleaned up automatically and was easy to deal with, and we had heap-based data that was more powerful, but could be misused. Now we've added garbage collection to reduce the chance of misusing the heap-based data, but to make the garbage collection simpler, we've thrown out stack-based objects and defined object lifetimes.

In the quest to stop memory leaks, we've made every object creation a memory leak and provided an automatic system to clean up the leaks we've made. Moreover, the loss of a defined time for the object to die has resulted in the loss of the destructor concept. We cannot be guaranteed that the object's cleanup/destructor/finalizer method will ever be called (even in normal operation).

This is why I have been thinking that maybe a new approach is needed. Next time, I plan to explore a possible new approach.

The Semantics of Garbage Collection

I have a confession to make. I've never really been comfortable with garbage collection.

Now, before you dismiss me as a Luddite who has obviously never worked with an advanced programming language, let me explain.

I'm familiar with many different forms of garbage collection. I have worked in languages with and without garbage collection. I've worked with Java, Lisp, and Perl; each with its own concept and implementation of garbage collection. I have seen well-done garbage collection free programmers from the drudgery of dealing with their own memory management.

But, despite all of that, I don't really like garbage collection. Strangely enough, when I finally examined why I didn't like garbage collection, I realized that my problem was more semantic than anything else. I don't like the name and what it implies. I don't think of used memory as garbage to be collected. I think of it as a resource to be recovered. The funny thing is that this shift in viewpoint results in a whole new set of assumptions about how resource recovery should work.

Timeliness of Recovery

The first consequence of this change in terminology is a change in timeliness.

Garbage is something we don't want to think about. Taking out the garbage is something we tend to put off until we have to deal with it. (The trash can is full, it's starting to smell, others in the house are complaining, etc.) This philosophy shows itself in the current crop of garbage collection systems. Most of the garbage collectors I've seen follow some variation of the mark and sweep algorithm. In this algorithm, a background task walks through memory marking all referenced objects. Then, it sweeps out the unused objects, freeing up their memory.^*

Unfortunately, running this algorithm uses CPU cycles that we obviously want to make use of elsewhere in our code. So most systems put it on a low priority thread; one that only gets called when there is nothing else to do (or when we begin running low on memory). Since this thread is just picking up our garbage, it doesn't need to be high priority. As long as the garbage is picked up before it gets in our way, we don't really care.

If you think of memory as a resource, things shift subtly. Resources are not things I'm ignoring, they are something I want. In fact, if it is a scarce (but renewable) resource, I want to make sure it is recycled or recovered as soon as possible. That way it will be available the next time I need it. It is no longer an issue of trying to put off this nasty chore off as long as possible. Now I want to try to handle it as soon as possible, without adversely impacting my other work.

Other Resources

Another advantage of thinking of memory as a resource, is that this puts it in the same category as other resources that we need to deal with. Most operating systems have limits on the numbers of certain resources. If a program tries to use too many without returning them to the system, it risks failure. Some kinds of scarce resources include:

• File handles
• Database handles
• TCP/IP sockets
• Process slots
• Address space
• Mutexes and semaphores
• Window handles
• Communications bandwidth

But, for some reason, we tend to treat memory as fundamentally different than these other resources. We tend to try to close/release each of the items in the list above as soon as we can. Because each is scarce and we know we will need it later. But, the current wisdom in garbage collection is to recover memory only when we have no choice or nothing better to do.

I find this approach disagrees with me on a gut-level.

*Okay, it usually involves copying the live objects around and doing some other maintenance work. But the simple description is enough for the purposes of the discussion.

Troubleshooting and Optimization

In LinuxDevCenter.com: Tales of Optimization and Troubleshooting [Jun. 03, 2004], Howard Feldman presents three examples of troubleshooting and fixing bottlenecks.

One thing I really like about this article is the methodical way the author goes about solving these problems. Having tried to teach troubleshooting to entry-level programmers, I know that it is very hard to get them to walk through the problem. Most inexperienced developers (and some experienced ones), want to jump immediately to a solution without doing the drudge work described here.

The author does a great job of showing how you measure the problem, and then think about the problem to solve it. Too many people try to make a quick fix based on too little information.