Introduction

“One of LISP’s most lasting contributions is a non-language feature namely the term and technique garbage collection, which refers to the system’s method of automatically dealing with storage.”

Jean E. Sammet

Programming Languages: History and Fundamentals, 1969

Over the last dozen years, garbage collection has come of age. Whereas it was once confined to realm of Lisp and functional languages, today garbage collection is an important part of the memory management system of many modern programming languages, imperative as well as declarative. Although garbage collection has had a reputation for sloth and for disrupting interactive programs, modern implementation techniques have reduced its overheads substantially, to the point where garbage collected heaps are a realistic option even for traditional languages like C.

Despite the rapid growth in memory sizes of even the most modest computers, the supply of storage is not inexhaustible. Like all limited resources it requires careful conservation and recycling. Many programming languages tiday allow the programmer to allicate and reclaim memory for data whose lifetimes are not determined by lexical scope. Such data is said to be dynamically allocated. Dynamic memory may be managed explicity by the programmer through invocations of built-in or library prcedures that allocate storage and that dispose or free that storage when it is no longer needed.

Manual reclamation of dynamically managed storage is often unsatisfactory. The alternative is to devolve ressponsibility for dynamic memory management to the program’s runtime system. The programmer must still request dynamically allocated storage to be reserved but no longer needs to determine when that memory is no longer required: it is recycled automatically. Garbage collection is precisely this – the automatic management iof dynamically allocated storage. Some authors prefer to distinguish between direct techniques, such as reference counting, and indirect, tracing techniques. However the term garbage collection is widely used to refer to all forms of automatic management of dynamically allocated storage, and we shall use it to refer to both reference counting and tracing methods. We shall need to distinguish between the garbage collcetor and the part of the program that does ‘useful’ work. Following Dijkstra’s terminology, we shall call the user program the mutator since, as far as the collector is concerned, its sole role is to chanhe or mutate the connectivity of the graph of active data structures in the heap.

In this introduction we seel to answer three questions. What problem does garbage collection solve? How costly is garbage collection? By which parameters may different garbage collection algorithms ne compared? We also outline a taxonomy of garbage collection techniques and explain the notation used in the rest of the book. Let us first briefly review the history of programming languages, and in particular the implemetation of storage management, from the 1940s to the present day.