book

The Garbage Collection Handbook

Name: The Garbage Collection Handbook
ISBN: 9781315388007

by Richard Jones, Antony Hosking, Eliot Moss

September 2016

Intermediate to advanced

511 pages

19h 34m

English

Chapman and Hall/CRC

Read now

Unlock full access

Cover
Half Title
Title Page
Copyright Page
Dedication
Table of Contents
List of Algorithms
List of Figures
List of Tables
Preface

Acknowledgements
Authors
1 Introduction
1.1 Explicit deallocation1.2 Automatic dynamic memory management1.3 Comparing garbage collection algorithmsSafetyThroughputCompleteness and promptnessPause timeSpace overheadOptimisations for specific languagesScalability and portability1.4 A performance disadvantage?1.5 Experimental methodology1.6 Terminology and notationThe heapThe mutator and the collectorThe mutator rootsReferences, fields and addressesLiveness, correctness and reachabilityPseudo-codeThe allocatorMutator read and write operationsAtomic operationsSets, multisets, sequences and tuples
2 Mark-sweep garbage collection
2.1 The mark-sweep algorithm2.2 The tricolour abstraction2.3 Improving mark-sweep2.4 Bitmap marking2.5 Lazy sweeping2.6 Cache misses in the marking loop2.7 Issues to considerMutator overheadThroughputSpace usageTo move or not to move?
3 Mark-compact garbage collection
3.1 Two-finger compaction3.2 The Lisp 2 algorithm3.3 Threaded compaction3.4 One-pass algorithms3.5 Issues to considerIs compaction necessary?Throughput costs of compactionLong-lived dataLocalityLimitations of mark-compact algorithms
4 Copying garbage collection
4.1 Semispace copying collectionWork list implementationsAn example4.2 Traversal order and locality4.3 Issues to considerAllocationSpace and localityMoving objects
5 Reference counting
5.1 Advantages and disadvantages of reference counting5.2 Improving efficiency5.3 Deferred reference counting5.4 Coalesced reference counting5.5 Cyclic reference counting5.6 Limited-field reference counting5.7 Issues to considerThe environmentAdvanced solutions
6 Comparing garbage collectors
6.1 Throughput6.2 Pause time6.3 Space6.4 Implementation6.5 Adaptive systems6.6 A unified theory of garbage collectionAbstract garbage collectionTracing garbage collectionReference counting garbage collection
7 Allocation
7.1 Sequential allocation7.2 Free-list allocationFirst-fit allocationNext-fit allocationBest-fit allocationSpeeding free-list allocation7.3 Fragmentation7.4 Segregated-fits allocationFragmentationPopulating size classes7.5 Combining segregated-fits with first-, best- and next-fit7.6 Additional considerationsAlignmentSize constraintsBoundary tagsHeap parsabilityLocalityWilderness preservationCrossing maps7.7 Allocation in concurrent systems7.8 Issues to consider
8 Partitioning the heap
8.1 Terminology8.2 Why to partitionPartitioning by mobilityPartitioning by sizePartitioning for spacePartitioning by kindPartitioning for yieldPartitioning for responsivenessPartitioning for localityPartitioning by threadPartitioning by availabilityPartitioning by mutability8.3 How to partition8.4 When to partition
9 Generational garbage collection
9.1 Example9.2 Measuring time9.3 Generational hypotheses9.4 Generations and heap layout9.5 Multiple generations9.6 Age recordingEn masse promotionAging semispacesSurvivor spaces and flexibility9.7 Adapting to program behaviourAppel-style garbage collectionFeedback controlled promotion9.8 Inter-generational pointersRemembered setsPointer direction9.9 Space management9.10 Older-first garbage collection9.11 Beltway9.12 Analytic support for generational collection9.13 Issues to consider9.14 Abstract generational garbage collection
10 Other partitioned schemes
10.1 Large object spacesThe Treadmill garbage collectorMoving objects with operating system supportPointer-free objects10.2 Topological collectorsMature object space garbage collectionConnectivity-based garbage collectionThread-local garbage collectionStack allocationRegion inferencing10.3 Hybrid mark-sweep, copying collectorsGarbage-FirstImmix and othersCopying collection in a constrained memory space10.4 Bookmarking garbage collection10.5 Ulterior reference counting10.6 Issues to consider
11 Run-time interface
11.1 Interface to allocationSpeeding allocationZeroing11.2 Finding pointersConservative pointer findingAccurate pointer finding using tagged valuesAccurate pointer finding in objectsAccurate pointer finding in global rootsAccurate pointer finding in stacks and registersAccurate pointer finding in codeHandling interior pointersHandling derived pointers11.3 Object tables11.4 References from external code11.5 Stack barriers11.6 GC-safe points and mutator suspension11.7 Garbage collecting code11.8 Read and write barriersEngineeringPrecision of write barriersHash tablesSequential store buffersOverflow actionCard tablesCrossing mapsSummarising cardsHardware and virtual memory techniquesWrite barrier mechanisms: in summaryChunked lists11.9 Managing address space11.10 Applications of virtual memory page protectionDouble mappingApplications of no-access pages11.11 Choosing heap size11.12 Issues to consider
12 Language-specific concerns
12.1 FinalisationWhen do finalisers run?Which thread runs a finaliser?Can finalisers run concurrently with each other?Can finalisers access the object that became unreachable?When are finalised objects reclaimed?What happens if there is an error in a finaliser?Is there any guaranteed order to finalisation?The finalisation race problemFinalisers and locksFinalisation in particular languagesFor further study12.2 Weak referencesAdditional motivationsSupporting multiple pointer strengthsUsing Phantom objects to control finalisation orderRace in weak pointer clearingNotification of weak pointer clearingWeak pointers in other languages12.3 Issues to consider
13 Concurrency preliminaries
13.1 HardwareProcessors and threadsInterconnectMemoryCachesCoherenceCache coherence performance example: spin locks13.2 Hardware memory consistencyFences and happens-beforeConsistency models13.3 Hardware primitivesCompare-and-swapLoad-linked/store-conditionallyAtomic arithmetic primitivesTest then test-and-setMore powerful primitivesOverheads of atomic primitives13.4 Progress guaranteesProgress guarantees and concurrent collection13.5 Notation used for concurrent algorithms13.6 Mutual exclusion13.7 Work sharing and termination detectionRendezvous barriers13.8 Concurrent data structuresConcurrent stacksConcurrent queue implemented with singly linked listConcurrent queue implemented with arrayA concurrent deque for work stealing13.9 Transactional memoryWhat is transactional memory?Using transactional memory to help implement collectionSupporting transactional memory in the presence of garbage collection13.10 Issues to consider
14 Parallel garbage collection
14.1 Is there sufficient work to parallelise?14.2 Load balancing14.3 Synchronisation14.4 Taxonomy14.5 Parallel markingProcessor-centric techniques14.6 Parallel copyingProcessor-centric techniquesMemory-centric techniques14.7 Parallel sweeping14.8 Parallel compaction14.9 Issues to considerTerminologyIs parallel collection worthwhile?Strategies for balancing loadsManaging tracingLow-level synchronisationSweeping and compactionTermination
15 Concurrent garbage collection
15.1 Correctness of concurrent collectionThe tricolour abstraction, revisitedThe lost object problemThe strong and weak tricolour invariantsPrecisionMutator colourAllocation colourIncremental update solutionsSnapshot-at-the-beginning solutions15.2 Barrier techniques for concurrent collectionGrey mutator techniquesBlack mutator techniquesCompleteness of barrier techniquesConcurrent write barrier mechanismsOne-level card tablesTwo-level card tablesReducing work15.3 Issues to consider
16 Concurrent mark-sweep
16.1 Initialisation16.2 Termination16.3 Allocation16.4 Concurrent marking and sweeping16.5 On-the-fly markingWrite barriers for on-the-fly collectionDoligez-Leroy-GonthierDoligez-Leroy-Gonthier for JavaSliding views16.6 Abstract concurrent collectionThe collector wavefrontAdding originsMutator barriersPrecisionInstantiating collectors16.7 Issues to consider
17 Concurrent copying & compaction
17.1 Mostly-concurrent copying: Baker’s algorithmMostly-concurrent, mostly-copying collection17.2 Brooks’s indirection barrier17.3 Self-erasing read barriers17.4 Replication copying17.5 Multi-version copyingExtensions to avoid copy-on-write17.6 SapphireCollector phasesMerging phasesVolatile fields17.7 Concurrent compactionCompressorPauseless17.8 Issues to consider
18 Concurrent reference counting
18.1 Simple reference counting revisited18.2 Buffered reference counting18.3 Concurrent, cyclic reference counting18.4 Taking a snapshot of the heap18.5 Sliding views reference countingAge-oriented collectionThe algorithmSliding views cycle reclamationMemory consistency18.6 Issues to consider
19 Real-time garbage collection
19.1 Real-time systems19.2 Scheduling real-time collection19.3 Work-based real-time collectionParallel, concurrent replicationUneven work and its impact on work-based scheduling19.4 Slack-based real-time collectionScheduling the collector workExecution overheadsProgrammer input19.5 Time-based real-time collection: MetronomeMutator utilisationSupporting predictabilityAnalysisRobustness19.6 Combining scheduling approaches: Tax-and-SpendTax-and-Spend schedulingTax-and-Spend prerequisites19.7 Controlling fragmentationIncremental compaction in MetronomeIncremental replication on uniprocessorsStopless: lock-free garbage collectionStaccato: best-effort compaction with mutator wait-freedomChicken: best-effort compaction with mutator wait-freedom for x86Clover: guaranteed compaction with probabilistic mutator lock-freedomStopless versus Chicken versus CloverFragmented allocation19.8 Issues to consider
Glossary
Bibliography
Index

Content preview from The Garbage Collection Handbook

Chapter 7

Allocation

There are three aspects to a memory management system: (i) allocation of memory in the first place, (ii) identification of live data and (iii) reclamation for future use of memory previously allocated but currently occupied by dead objects. Garbage collectors address these issues differently than do explicit memory managers, and different automatic memory managers use different algorithms to manage these actions. However, in all cases allocation and reclamation of memory are tightly linked: how memory is reclaimed places constraints on how it is allocated.

The problem of allocating and freeing memory dynamically under program control has been addressed since the 1950s. Most of the techniques devised over the decades are of ...

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.

Read now

Unlock full access

More than 5,000 organizations count on O’Reilly

O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.

Julian F.

Head of Cybersecurity

I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.

Addison B.

Field Engineer

I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.

Amir M.

Data Platform Tech Lead

I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.

Mark W.

Embedded Software Engineer

The Garbage Collection Handbook, 2nd Edition

Publisher Resources

ISBN: 9781315388007

Cloud Computing

Data Engineering

Data Science

AI & ML

Programming Languages

Software Architecture

IT/Ops

Security

Design

Business

Soft Skills

The Garbage Collection Handbook

by Richard Jones, Antony Hosking, Eliot Moss

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.