I ? A
r ? A ? . i ■ . . ? * * r
1
i'
r ? w *
) I -
? f r w^
?. CRC Press
Taylor Si Francis Grou ?
A CHAPMAN & HALL BOOK
THE
GARBAGE COLLECTION
HANDBOOK
The Art of Automatic Memory Management
Chapman & Hall/CRC
Applied Algorithms and Data Structures Series
Series Editor
Samir Khuller
University of Maryland
Aims and Scopes
The design and analysis of algorithms and data structures form the foundation of computer
science. As current algorithms and data structures are improved and new methods are
introduced, it becomes increasingly important to present the latest research and applications
to professionals in the field.
This series aims to capture new developments and applications in the design and analysis
of algorithms and data structures through the publication of a broad range of textbooks,
reference works, and handbooks. The inclusion of concrete examples and applications is
highly encouraged. The scope of the series includes, but is not limited to, titles in the
areas of parallel algorithms, approximation algorithms, randomized algorithms, graph
algorithms, search algorithms, machine learning algorithms, medical algorithms, data
structures, graph structures, tree data structures, and other relevant topics that might be
proposed by potential contributors.
Published Titles
A Practical Guide to Data Structures and Algorithms Using Java
Sally A. Goldman and Kenneth J. Goldman
Algorithms and Theory of Computation Handbook, Second Edition - Two Volume Set
Edited by Mikhail J. Atallah and Marina Blanton
Mathematical and Algorithmic Foundations of the Internet
Fabrizio Luccio and Linda Pagli, with Graham Steel
The Garbage Collection Handbook: The Art of Automatic Memory Management
Richard Jones, Antony Hosking, and Eliot Moss
THE
GARBAGE COLLECTION
HANDBOOK
The Art of Automatic Memory Management
Richard Jones
Antony Hosking
Eliot Moss
CRC Press
Taylor &. Francis Group
Boca Raton London New York
CRC Press is an imprint of the
Taylor & Francis Group an informa business
A CHAPMAN & HALL BOOK
The cover image logo concept was created by Richard Jones, and the rights to the logo belong solely to him.
CRC Press
Taylor & Francis Group
6000 Broken Sound Parkway NW, Suite 300
Boca Raton, FL 33487-2742
? 2012 by Richard Jones, Antony Hosking, and Eliot Moss
CRC Press is an imprint of Taylor & Francis Group, an Informa business
No claim to original U.S. Government works
Printed in the United States of America on acid-free paper
Version Date: 20110726
International Standard Book Number: 978-1-4200-8279-1 (Hardback)
This book contains information obtained from authentic and highly regarded sources. Reasonable efforts have been
made to publish reliable data and information, but the author and publisher cannot assume responsibility for the
validity of all materials or the consequences of their use. The authors and publishers have attempted to trace the copyright
holders of all material reproduced in this publication and apologize to copyright holders if permission to publish in this
form has not been obtained. If any copyright material has not been acknowledged please write and let us know so we may
rectify in any future reprint.
Except as permitted under U.S. Copyright Law, no part of this book may be reprinted, reproduced, transmitted, or
utilized in any form by any electronic, mechanical, or other means, now known or hereafter invented, including
photocopying, microfilming, and recording, or in any information storage or retrieval system, without written permission from the
publishers.
For permission to photocopy or use material electronically from this work, please access www.copyright.com (http://
www.copyright.com/) or contact the Copyright Clearance Center, Inc. (CCC), 222 Rosewood Drive, Danvers, MA 01923,
978-750-8400. CCC is a not-for-profit organization that provides licenses and registration for a variety of users. For
organizations that have been granted a photocopy license by the CCC, a separate system of payment has been arranged.
Trademark Notice: Product or corporate names may be trademarks or registered trademarks, and are used only for
identification and explanation without intent to infringe.
Visit the Taylor & Francis Web site at
http://www.taylorandfrancis.com
and the CRC Press Web site at
http://www.crcpress.com
To
Robbie, Helen, Kate and William
Mandi, Ben, Matt, Jory and K
Hannah, Natalie and Casandra
Contents
List of Algorithms xv
List of Figures xix
List of Tables xxi
Preface xxiii
Acknowledgements xxvii
Authors xxix
1 Introduction 1
1.1 Explicit deallocation 2
1.2 Automatic dynamic memory management 3
1.3 Comparing garbage collection algorithms 5
Safety 6
Throughput 6
Completeness and promptness 6
Pause time 7
Space overhead 8
Optimisations for specific languages 8
Scalability and portability 9
1.4 A performance disadvantage? 9
1.5 Experimental methodology 10
1.6 Terminology and notation 11
The heap 11
The mutator and the collector 12
The mutator roots 12
References, fields and addresses 13
Liveness, correctness and reachability 13
Pseudo-code 14
The allocator 14
Mutator read and write operations 14
Atomic operations 15
Sets, multisets, sequences and tuples 15
vn