with a chapter on Distributed Garbage Collection by Rafael Lins
John Wiley & Sons, Ltd, ISBN 0-471-94148-4
403 pages, hardback
This book is about garbage collection:
the automatic reclamation of heap-allocated storage after its last use by a
Memory is and has always been a scarce and precious resource.
In the early days of computing,
before the advent of very large scale integrated circuits,
memory was expensive and
even a time-sharing operating system like Unix was expected to run in just one
although SIMM memory modules are comparatively cheap to buy and easy to install,
programs are increasingly profligate in their consumption of this resource.
an operating system for a single-user personal computer,
needs more than twelve megabytes of RAM
to operate optimally.
Thus main memory alone may account for half the cost of a PC.
As with all precious resources,
memory needs to be carefully managed and recycled when no longer needed.
The storage requirements of many computer programs are simple and predictable.
Allocation and deallocation of memory
for such programs
can be handled by the programmer
or the compiler,
and indeed is best done so.
Other programs have grown enormously in size and complexity.
Languages like Lisp and Prolog
typically manipulate large data structures
with complex inter-dependencies.
Functional and logic languages have complex patterns of execution.
The result is that the useful lifetimes of many data structures can no longer be
determined before execution,
either by programmer or by compiler.
Automatic storage reclamation is essential.
One reflection of the growing importance of garbage collection is
the level of debate on this subject within the computer science community.
As well as individual papers in journals and conferences,
there have been workshops on garbage collection at the
1990, 1991 and 1993
Object-Oriented Systems, Languages and Applications OOPSLA conferences,
as well as international workshops exclusively devoted to the topic
in 1992 and 1995.
Garbage collection is also a perennially popular subject for extended argument on
Usenet news groups.
the strongest growing area of interest in analysis, design and programming today.
The key to good software engineering is the control of complexity.
One of the ways that object-oriented design achieves this goal
is the encapsulation of abstractions into objects
that communicate through clearly defined interfaces.
Programmer-controlled storage management inhibits this modularity.
For this reason,
most modern object-oriented languages,
such as Smalltalk, Eiffel, Java and Dylan,
are supported by garbage collection.
even languages used in part for systems programming,
such as Modula-3 and Oberon,
provide garbage collection for these sound but pragmatic reasons.
Garbage collecting libraries are even available for
such uncooperative languages as C and C++.
The literature on garbage collection is enormous.
Well over a thousand
chapters in books,
presentations to conferences,
and postgraduate theses
have been written on the subject.
Despite this many myths about garbage collectors prevail.
`They are only necessary for Lisp and functional languages;
they can only be used with interpreters rather than for compiled code;
they place an intolerable overhead on programs'
- and doubtless they have cloven hooves and forked tails as well!
Two corollaries follow.
garbage-collected solutions are often ignored where they could profitably be applied.
where the complexities of the data structures involved demand garbage collection,
the experience provided in the literature is often unfamiliar so
a wheel is reinvented.
The aim of this book is to draw this wealth of experience together
into a single, accessible and unified framework.
State of the art techniques are described and compared
for declarative and imperative programming styles,
and distributed architectures.
Each of the most important algorithms is explained in detail,
often with illustrations of its characteristic features and animations of its use.
Its complexity, performance, applicability and relationship with other related
algorithms is also discussed.
We believe that this survey should prove useful to postgraduate students and
researchers working in
Functional, Logic and
Object-oriented Programming and Design;
The book should also be of interest to students taking advanced courses in
We hope that
professionals developing programs
- from simple software tools to complex real-time systems -
will find this book valuable.
the rapid growth in popularity of object-oriented systems over the past few years
makes a thorough understanding of garbage collection methods essential
for any programmer in this area.
Organisation of the book
The first chapter
begins with the evolution of computer memory management
and the need for automatic storage reclamation.
We then describe the representation of objects in our heap,
and discuss the yardsticks by which
different strategies of garbage collection may be measured.
The chapter ends with a description of our pseudo-code notation.
Chapter 2 introduces the three `classical'
techniques for garbage collection:
and copying collection.
Readers with some experience of these techniques may wish to skip this chapter.
The next four chapters cover these styles of collection
- and mark-compact collection -
in more detail.
introduces generational garbage collection,
a paradigm that has proved effective at reducing garbage collection pause times and
overall costs in a wide range of applications,
Chapter 8 describes how garbage collection
can be finely interleaved with the rest of a computation.
Chapters 9 and 10 extend garbage collection
to environments in which there is no support from the
language compiler, C and C++ respectively.
The next chapter of the book discusses a relatively new research area,
the interaction of garbage collection with
hardware data caches.
Chapter 12 briefly surveys
garbage collection for distributed systems.
We have included a summary of issues to consider
at the end of each chapter.
These summaries are intended to offer guidelines to the reader
on the questions that should be answered
about the collectors,
the client program
and the operating system and architecture
before a garbage collector is chosen.
These questions are designed as prompts to the reader.
The summaries are certainly not a substitute for reading the appropriate chapter,
and we have not attempted to provide `pat' solutions.
strategies of garbage collection
(such as reference counting, mark-sweep or copying)
introduced in earlier chapters are revisited in later ones.
The characteristics and performance of naive implementations
should not be mistaken for those of state of the art implementations of
the same garbage collection strategy.
we hope that these summaries will provide,
rather than a `cook book',
a focus for further analysis.
We should also declare what is missing from the book.
The most effortless form of memory management is to do none at run-time.
A considerable amount of research has gone into
compile-time techniques to discover when objects can be discarded or reused.
Most of this work has been theoretic and,
we believe that
there has been little evidence of substantial performance gains.
We have omitted this material.
Some techniques and tricks are language specific.
While we have chosen to cover C++ because of its increasing popularity
and growing realisation by many of its practitioners that
garbage collection is sorely needed,
we have concentrated in the main on generally applicable methods.
Techniques that are specific
to certain styles of programming,
for example pure functional programming or logic programming,
are only mentioned briefly.
energetic researchers who trawl through on-line bibliographic
databases will discover papers on other garbage collection techniques and issues
in their catch.
We were intrigued by, but chose to ignore,
burying garbage in landfills,
and dumping it at sea.
The question of public health and garbage collection is also often raised
- but language wars are another ball game altogether!
The Bibliography and the World-Wide Web
We mentioned earlier that over a thousand papers have been published on this topic.
The bibliography at the end of this book is considerably shorter.
However a comprehensive
is available electronically.
This bibliography also contains
and URLs for electronically available papers.
Richard Jones will endeavour to keep his bibliography up to date
and would be most grateful to receive further entries
(preferably in BibTeX format)
as well as URLs for existing papers
(and any corrections).
We have endeavoured to eradicate any errors
from the code fragments
presented in the book.
While not having the courage to repeat Donald Knuth's offer of cash
for errors reported,
list of any errors
found will be maintained at this web site.
Reports should be sent to
Richard Jones either
The Computing Laboratory,
University of Kent at Canterbury,
This book would never have been completed with the encouragement,
assistance and patience of many people.
I would like to thank the Theoretical Computer Science research group
at the University of Kent at Canterbury for cheering from the side-lines.
In particular I am indebted to
Simon Thompson for patiently reading and commenting on drafts of this
and for all his encouragement.
I would also like to thank
for their comments and suggestions.
I would also like to thank
for their advice on how to wrestle LaTeX into submission.
The two term study leave granted to me by the University of Kent
and visits to the Federal University of Pernambuco, Recife, Brazil
(and the caipirinha), funded by the British Council
and CNPq-Brazil, were invaluable.
I am also grateful to Rafael Lins
who originally conceived the idea for the book
and wrote the chapter on Distributed garbage collection,
as well as contributing to some other chapters.
Acknowledgement must also be paid to all those
- too numerous to mention -
who have worked on garbage collection over the last thirty-six years.
Finally, and above all, I must thank Robbie, Helen, Kate and William
without whose support and forbearance none of this would have been possible.
For more than two years
you have put up with me occupying the dining room claiming that it was my study;
you have forgiven my bad temper;
and you have graciously accepted that I could not come out to play.
I thank you from the bottom of my heart.
I am most grateful to the many people who contributed in many different ways
to make this book possible,
and in particular to
and Marcia Correia.
I am grateful to the Universidade Federal de Pernambuco,
Recife, Brazil, for granting sabbatical leave, funded by CAPES-Brazil,
and several visits to the University of Kent,
funded by CNPq-Brazil and the British Council.
The many friends at Kent made those visits ever so pleasant!
I am also grateful for all the support and love I have received from
Carmo, Gilka, Maria Teresa, Rilane and Silvia.
Copyright ©1996, Richard Jones