Automatic storage reclamation, aka garbage collection, comes in two main families, sometimes cooperating: the reference count collectors and the tracing collectors. I may develop specifics of each family if there is demand for it but my question is about tracing collectors.

Tracing collectors, in their simpler form can be divided into mark-and-sweep (possibly with compaction) and copy collectors (that compact naturally). Historically, they seem to have been considered distinct families in the first 10 or 20 years of the development of garbage collection technology.

I am wondering when they started to become known as tracing collectors forming a single family. When was the expression tracing collectors first used to denote both mark-and-sweep and copy collection, and possibly collectors mixing both technologies (as is often the case with generational collectors).

Ideally, a reference to a paper introducing the terminology would be the best form for an answer. Reference to a book is good too, if you can give the printing where it first appears, as books often evolve with successive printings. Specifying the page or giving a quote would be nice too.

Added after accepting the answer.

I am accepting the answer given by Pseudonym, as it is a very clear answer, that seems to be as good as it will ever get (but who knows?). What I mean is that it seems unlikely that an earlier date will be found, sinve the Paul Wilson's 1992 survey is pretty thorough. As I recall, the previous survey by Cohen in 1981 does not allude to tracing or unification of copy and mark-and-sweep.

An interesting trivia is that the introduction of this concept is exactly half-way between the first garbage collection paper in 1960 (as far as I know) and now (early 2015), which give a kind of time measure of conceptual evolution.

This first GC papers, to my knowledge, used reference counting and were published in 1960. According to wikipedia, which cites Jones, Richard; Lins, Rafael (1996), Garbage collection: algorithms for automatic dynamic memory management, Wiley, p. 40, ISBN 9780471941484:

The first, though cumbersome and error-prone, reference counting technique was described by J. Gelertner, J.R. Hansen, and C.L. Gerberich [Gelernter et al, 1960] but the standard reference counting algorithm is due to George Collins [Collins, 1960].

To my knowledge, the first tracing GC is a mark-and-sweep implementation for LISP published in 1964 in, Notes on implementing LISP for the M-460 Computer, Timothy P. Hart and Thomas G. Evans, pp. 191-203 in The Programming Language LISP, its Operation and Applications, March 1964, published by Information International, and reprinted by MIT press (though they seemed to have lost all memory of it when I asked, a long time ago). It does use the name "garbage collector", but I do not know whether that is the first occurrence in the computer literature.


1 Answer 1


The terminology was introduced in Lang and Dupont, Incremental Incrementally Compacting Garbage Collection, SIGPLAN 87. This is the paper which consolidated several lines of enquiry into one common language.

The way I found this out was by consulting Paul Wilson's 1992 survey, Uniprocessor Garbage Collection Techniques, which is required reading if you need to know stuff like this.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.