Why we need automatic memory management

We argue that a programming language meant for writing applications (i.e. end-user applications, as opposed to low-level systems code) must have automatic memory management in order for such applications to be maintainable and modular.

Uniform reference semantics

We have already argued elsewhere that uniform reference semantics is a prerequisite for modular and maintainable code. If you don't know what that means, you should first look at that text and come back only when you are convinced that that argument is correct.

Multiple references to objects

The key argument to needing automatic memory management is that it is impossible, or at least very hard, for a program to know when an object can be safely deleted, or equivalently, when an object is about to have its last reference removed. Let us use the same example that we use elsewhere. Suppose a program contains two containers, one containing all the staff of the company, and another containing all the people with parking permits. For that program to be modular, the part that manipulates parking permits must be independent of the part that manipulates staff members. Suppose someone quits his or her job, thus no longer begin a staff member. That person is then removed from the corresponding container. Should we delete the object representing the person as well, or should we just remove that object from the container? If that person is also in some other container, then we should not delete the object, but if that person is only in the container representing staff members, we should delete the object. For instance, if the person also has a parking permit, then the object is also referenced from the container of holders of parking permits, and we absolutely must not delete the object. Doing so anyway will either result in a core dump or, worse, in some mysterious bug in which a person without a parking permit still is in the container for parking permits. But making such a decision requires the part of the program (module) that manages staff members to know about all other modules, in particular about parking permits. Needless to say, such global knowledge would completely ruin modularity and any hope for producing a maintainable program.

Complication of code dues to manual memory management

Some code is much more complicated than it ought to be because of lack of automatic memory management. Let us suppse we have som C function concat that concatenates two strings by allocating a new string the size of the two arguments, and copying the characters to the newly allocated space. Now suppose we want to concatenate three strings , x, y, and z. We could do something like this: 
  w = concat(concat(x, y), z);
However, this code has a memory leak. The inner call to concat allocates memory that is never deallocated. A simple idea like this must be expressed this way instead to avoid memory leaks: 
  temp = concat(x, y);
  w = concat(temp, z)
  free(temp);

How does automatic memory management solve the problem?

Automatic memory management solves the problem by detecting objects and groups of objects that cannot possibly be referenced by a program, and deleting them. With automatic memory management, we can safely remove the (reference to the) object contained in the container of staff members without deleting the object itself. Should it be the case that doing so will make that object inaccessible, for instance if it is contained in no other container, then the automatic memory management system (the garbage collector) will eventually detect it and delete it. Conversely, if the object is still referenced from a container (that itself is accessible), then the garbage collector will preserve the object intact.

How does garbage collection work?

To do its work, the garbage collector needs to know which objects cannot be accessed. It does so by directly applying the definition of `accessible':
  1. Any object referenced from a machine register is accessible.
  2. Any object referenced from a global variable is accessible.
  3. Any object referenced from the stack is accessible.
  4. Any object referenced from an accessible object is accessible.
  5. Any object not accessible according to the previous definition can be deleted.
Usually, the garbage collector traces all the accessible objects starting with the registers, the global variables, and the stack. While tracing these objects, it inserts them in a set (for instance by marking them). When all accessible objects are traced, the remaining ones (the ones not members of the set) are deleted.

But isn't garbage collection slow?

Not really. But it is hard to evaluate the exact cost of it, since not having it means writing your program differently. If not having a garbage collector means lots of duplications of objects, then having it is probably cheaper. Also, if not having a garbage collector means having a buggy program, you can argue that the cost of not having one is infinite.

To get an estimation, you may consider that the execution time of a typical garbage collector is less than 15% of total execution time of the program. But without the garbage collector, at least part of that time would have to be devoted to explicit calls to `free'.

So it isn't slow, but doesn't it have these unacceptable pauses?

Some garbage collectors do, especially old ones. For batch programs such pauses are not a problem, and garbage collectors of that sort are usually very efficient.

For interactive programs, pauses can be annoying. More recent garbage collectors, such as generational collectors, only scan a small part of all objects during each collection, making the pauses hard or impossible to detect.

Incremental collectors go one step further and interleave their execution with that of the application so that no pauses remain, only a minor slowdown of the application. Such collectors can even be used in real-time systems with hard requirements on response times.

So can't we use reference counters?

A common trick, often used in languages such as C or C++ with no automatic memory management is to use reference counters. The idea is that each object contains an additional field that indicates how many other objects refer to it. Each time another reference is created (for instance when the object is inserted into another container), the reference counter is incremented. Each time a reference to the object is lost (for instance when the object is removed from a container), the reference counter is decremented and checked. If its value is zero, then no references to the object remain and the object can be removed.

Reference counters can be much more costly than automatic memory management, as the reference counter needs to be updated fairly often, usually much more often that a garbage collector would scan the object.

Worse, reference counters fail to detect some inaccessible objects, thus potentially creating memory leaks. The reason is the presence of cycles of references. Objects in such a cycle will have their reference counters all greater than zero, despite the possibility of none of the objects being accessible. All of them are accessible from each other, but non of them from the registers, from the global variables, or from the stack, neither directly nor indirectly. By the definition of accessibility, they are thus not accessible. Despite that, their reference counters are greater than zero, making it impossible to delete them.

The only situation in which reference counters work, is when one can guarantee that no object participate in a cycle, which for some applications is possible. But even then, reference counters represent a greater cost than that of automatic memory management.

Languages with automatic memory management

From the explanation above, we must conclude that automatic memory management is a necessity for programming applications. Many languages that were created for that purpose therefore directly support automatic memory management, in particular Simula, Eiffel, Lisp, Scheme, Java, and Smalltalk.

What does it mean that the language `supports' automatic memory management? First, it means that all implementations are required to have it. But it also means that the language is designed so as to make it easy for a garbage collector to precisely detect live (accessible) objects.

This is not the right forum to go into a deep discussion as to how languages might make it easy for the garbage collector. For those who are interested, there is a large body of literature on automatic memory management. It is also a very active research topic.

What if the language does not have automatic memory management?

Some very popular languages, in particular C and C++ (and Ada?) do not support automatic memory management. The best solution is of course to avoid these languages for writing applications. Sometimes, however, that is not an option.

In those cases, for C and C++, the best solution is to use a so called conservative garbage collector. A conservative garbage collector does not need the support from the compiler or the language in order to do its job. It is called `conservative' because it may erroneously declare an object as `live' even though in fact it is not, whereas it can never (provided the programmer follow some elementary precautions such as respecting the language definition) erroneously declare an accessible object as inaccessible.

In theory, a conservative collector (by the very fact that it is conservative) can still create memory leaks. In practice, it almost never does.

The most popular conservative garbage collector for C and C++ was written by Hans Boehm and is freely distributable as a library to link with the application. It is quite easy to use for applications with few requirements, and allows sophisticated tuning for better performance in more important applications.

We recommend you always use the Boehm collector when writing applications in C or C++.