The Benefits of Garbage Collection Mark K. Gardner Brigham Young University Provo, UT 84602 (gardner@osm7.cs.byu.edu) 1.0 Introduction Traditionally, memory deallocation policies have been hard coded into applications by the implementer. However, extreme care must be taken not be deallocate memory that can still be referenced. This task is so difficult that most non-trivial applications exhibit aberrant behavior as the result of Òdangling pointersÓ. The increased complexity of modern applications only makes the problem more severe. The most promising solution is the adoption of automatic memory deallocation or Ògarbage collectionÓ. 2.0 Basic Techniques The process of garbage collection logically consists of two phases, detection and reclamation [Wilson 92]. Valid objects (also called live objects) are distinguished from invalid objects (also called garbage) during the detection phase. Subsequently, the storage occupied by the garbage is reclaimed during the reclamation phase. Although there are many variations possible, generally the reclamation phase is highly dependent on the detection phase. In the discussion below, a few of the more popular techniques will be discussed. The remainder of this section discusses different types of collectors based on the information presented in [Wilson 92]. 2.1 Reference Counting A reference counting system maintains a count of the number of references to each object that exist in the system. Each time another reference is made to the object, the reference count of the object is incremented. Each time a reference to an object is eliminated, the reference count of the object is decremented. An object becomes garbage when its reference count becomes zero. In spite of its simplicity, reference counting suffers from two main problems: it is difficult to make efficient and it fails to reclaim cyclic garbage. Some techniques, such as deferred reference counting, reduce the cost but do not enough to make it competitive with other garbage collection systems. 2.2 Mark and Sweep Collection Mark and sweep collectors remedy the problem of cyclic garbage by traversing the graph of pointers from a set of known live objects (called the root set) marking objects traversed as being alive. Memory is then re-examined (swept) to reclaim the dead objects. Since none of the objects involved in the cycle are accessible from the root set, the cycle is reclaimed. Mark and sweep collectors must trace the live objects and collecting the dead objects so the cost is proportional to the size of the heap. And the locality of reference is reduced (working set size increased) because live objects are scattered over many virtual memory pages. They also suffer from fragmentation. Current research is attempting to reduce the costs by clever implementations. 2.3 Mark and Compact Collection A variation of the mark and sweep collector which solves the fragmentation problem is the mark and compact collector. After the live objects have been marked, the objects are compacted by moving together at one end of the heap until all the live objects are contiguous. Fragmentation is eliminated and allocation is simplified. In addition, objects are clustered which reduces the size of the working set and improves the locality of reference over mark and sweep collection. However, the collector suffers from repeated passes over the heap as it marks the live objects, computes the new locations, moves the objects and updates pointers. Thus the algorithm may be significantly slower than the mark and sweep collector. 2.4 Copying Collection Copying collectors integrate the phases of the mark and compact collector so that only one pass over the live objects is needed. Live objects are copied from one location to another and the remaining memory is considered reclaimed. The cost of the algorithm is proportional to the amount of live data, since only the live objects are traversed and copied. Because only live objects are considered, some researchers avoid the term garbage collection in favor of the term scavenging. A simple stop and copy collector divides the heap into two semispaces. Memory is allocated in successive blocks from one semispace until a request cannot be satisfied. Then the program halts while the collector copies all the live objects (usually breadth first) from the current semispace (fromspace) to the other semispace (tospace). The roles of the two semispaces are reversed and program execution continues. A copying collector can be made more efficient by decreasing the frequency of collection. The most simple way to decrease the frequency of collection is to increase the size of the semispaces. Besides taking longer for the program to fill a semispace, the average age of an object increases and hence the probability of it not needing to be copied increases. 2.5 Variations Other variations deal with making the collector incremental for real-time applications or increasing its efficiency through generational collection. These will not be treated here but are covered extensively in [Wilson 92]. The important point is that garbage collection can be used in systems with stringent performance requirements by carefully designing the collection system. 3.0 Production Language Support of Garbage Collection ÒIf garbage collection has so many benefits, why is it not available for commercial systems?Ó First of all, garbage collection has long been a feature of languages such as Lisp and Smalltalk [Goldberg 83]. In addition, new languages have included it in their design [Meyer 92][Wirth 92]). It is the Òmore traditionalÓ languages with which most programmers are familiar that lack support for garbage collection. As an example, consider the issue of adding garbage collection to C or C++. In order for garbage collection systems to use tracing for garbage detection, the location of pointers needs to be known by the system [Bartlett 90]. Compilers for the newly designed languages make that information available to the collector. However, just modifying a C or C++ compiler to provide the required information will not solve the problem. Inherent in the design of C and C++ is a feature which makes it difficult (if not impossible) for a compiler to determine what is a pointer and what is not. I am referring to the pointer aliasing problem. C and C++ are weakly typed languages that allow the programmer to change the type of an item by a type cast. As an example, this technique can be used to change a pointer type into a long integer and back. The long integer is an alias for the pointer, but the compiler does not realize it is a pointer. Thus, it may be impossible for the compiler to provide accurate information about all pointers in C and C++ for all programs. There are two ways around the problem: eliminate tracing (i.e., use reference counting) or make conservative estimation of pointers. The first choice is undesirable for performance and implementation reasons [Bartlett 90]. As was discussed in section 2.1, the overhead is high for reference counting techniques and cyclic garbage will not be reclaimed. Additional memory must also be dedicated to the maintenance of the counts. And from an implementation perspective, reference counting is undesirable because it requires the inclusion of properly implemented constructors, destructors, and assignment operators necessary. The later makes it almost impossible to add reference counting to C programs easily. The second choice, conservative estimation of pointers, assumes that anything that looks like a pointer is a pointer. As a result, not all garbage may be collected, but all live objects are guaranteed to not be reclaimed. This technique has been successfully used to implement conservative mark and sweep copiers for C and C++ [Detlefs 93]. And if one is willing to modify oneÕs implementation style slightly, a form of mark and copy collection can be used [Bartlett 90]. It should be noted that all these problems can be avoided if languages were designed from the beginning to include garbage collection. For some languages, such as C or C++, designing garbage collection into the language would conflict with the basic philosophy of the language [Edelson 90]. However, I believe languages designed with garbage collection in mind can be flexible enough to allow the system to be tailored to the demands of the application. And the benefits of garbage collection in the ease of designing and implementing a system without memory deallocation problems makes its use imperative in todayÕs production environments. 4.0 Conclusions The use of garbage collection would eliminate the memory deallocation errors common in nearly all programs. The technology is mature and is being used in modern languages. Garbage collection can be used with current production languages, but for optimum results the languages need to be extended. Even so, implementers would benefit greatly by using garbage collection. References [Bartlett 90] J. Bartlett, A Generational, Compacting Garbage Collector for C++, paper for the OOPSLAÕ90 Workshop on Garbage Collection, 1990. [Detlefs 93] D. Detlefs, Empirical Evidence for using Garbage Collection in C and C++ Programs, paper for the OOPSLA'93 Workshop on Memory Management and Garbage Collection, 1993. [Edelson 90] D. Edelson, and I. Pohl, The Case for Garbage Collection in C++, paper for the OOPSLAÕ90 Workshop on Garbage Collection, 1990. [Goldberg 83] A. Goldberg, and D. Robson, Smalltalk-80: The Language and Its Implementation, Addison-Wesley, Reading, Mass., 1983. [Meyer 92] B. Meyer, Eiffel: The Language, Prentice-Hall, London, 1992. [Wilson 92] P. R. Wilson, Uniprocessor Garbage Collection Techniques, to appear in 1992 International Workshop on Memory Management (St. Malo, France, September 1992), Springer-Verlag Lecture Notes in Computer Science. [Wirth 92] N. Wirth, and J, Gutknecht, Project Oberon: The Design of an Operating System and Compiler, Addison-Wesley, New York, New York, 1992.