UniProcessor Garbage Collection Techniques
Paul R. Wilson University of Texas
Presented By Naomi Sapir Tel-Aviv University
Overall Goal Overall Goal
Introduction of garbage collectors for Introduction of garbage collectors for uniprocessors.
uniprocessors.
Clarify basic issues in the field.Clarify basic issues in the field.
Motivation Motivation
Modular programming.Modular programming.
Unreclaimed memory leads to slow memory Unreclaimed memory leads to slow memory leaks.
leaks.
Reclaiming too soon may cause Reclaiming too soon may cause unpredictable results.
unpredictable results.
GC should be built into a language GC should be built into a language implementation.
implementation.
Two Phase Abstraction Two Phase Abstraction
Distinguish live objects from garbage by Distinguish live objects from garbage by terms of
terms of root set.root set.
- reference counting - reference counting
- mark sweep - mark sweep
- copying - copying
Reclaim Garbage storage.Reclaim Garbage storage.
Root Set Root Set
Global variablesGlobal variables
local variables in the activation stack.local variables in the activation stack.
RegistersRegisters
• Live object: Any object reached from the Root Set.
• What is Garbage?
Reference Counting
Reference Counting
Unreclaimable Cycle
Unreclaimable Cycle
Cons Cons
Conservative approximation of true liveness.Conservative approximation of true liveness.
Efficiency cost proportional to the number of Efficiency cost proportional to the number of objects allocated in runtime.
objects allocated in runtime.
- a real pointer points to another object - a real pointer points to another object
- short lived stack variables - short lived stack variables
Fragmentation.Fragmentation.
Pros Pros
Used in distributed systems combined with Used in distributed systems combined with other techniques.
other techniques.
Mark-Sweep Collection
Mark-Sweep Collection
Root Page
Object
Mark-swept
Cons Cons
Fragmentation - difficult to allocate large Fragmentation - difficult to allocate large objects.
objects.
Locality of reference: interleave of different Locality of reference: interleave of different ages causes many page swaps.
ages causes many page swaps.
Cost: proportional to the heap size.Cost: proportional to the heap size.
Mark Compact Mark Compact
Collection Collection
Compact after mark Compact after mark
ProsPros
Solves fragmentation.Solves fragmentation.
Saves locality.Saves locality.
ConsCons
Cost: Several passes over the data:Cost: Several passes over the data:
Mark, compute new locations, Mark, compute new locations,
update pointers and move the objects.
update pointers and move the objects.
Copying Garbage Copying Garbage
Collection
Collection
Before garbage Before garbage
collection
collection
After garbage After garbage
collection
collection
Cheney breath-first Cheney breath-first
copying
copying
Efficiency of Copying Efficiency of Copying
Collection Collection
Proportional to the live data during collection.Proportional to the live data during collection.
Decrease of collection Decrease of collection frequencyfrequency, decreases , decreases collection effort.
collection effort.
Need increased Need increased heapheap memory. memory.
Objects that die before GC needn’t be copied.Objects that die before GC needn’t be copied.
Basic Techniques - Basic Techniques -
Conclusions Conclusions
High performance systems use High performance systems use hybridhybrid techniques.
techniques.
Copy collectors use a separate Copy collectors use a separate large objectslarge objects area.
area.
In-place collectors (mark-sweep, treadmill) In-place collectors (mark-sweep, treadmill) are conservative in respect to untyped
are conservative in respect to untyped objects, a
objects, a copyingcopying collector must collector must identify identify pointers.
pointers.
Problems with basic GC Problems with basic GC
Not large memory, causes excessive paging.Not large memory, causes excessive paging.
A copying collection might cause paging.A copying collection might cause paging.
Locality in cache memory is important.Locality in cache memory is important.
Time consuming, not usable for real time Time consuming, not usable for real time applications.
applications.
Incremental Tracing Incremental Tracing
Collectors
Collectors
Incremental Tracing Incremental Tracing
Collectors Collectors
Incremental tracing for garbage detection.Incremental tracing for garbage detection.
The running program may mutate the graph The running program may mutate the graph of reachable objects.
of reachable objects.
- keep track of changes.- keep track of changes.
- floating garbage.- floating garbage.
Tricolor Marking Tricolor Marking
Before After a violation D is not reachable
Incremental Incremental
Approaches Approaches
Coordinates the collector with the mutator.Coordinates the collector with the mutator.
Read barrierRead barrier
A mutator access a pointer to a white object, A mutator access a pointer to a white object,
colors the object grey.
colors the object grey.
Write barrier - Write barrier - a direct methoda direct method
- Traps the write of a white pointer into a black - Traps the write of a white pointer into a black
object.
object.
- Traps the death of a pointer before it is reached - Traps the death of a pointer before it is reached
by GC.
by GC.
Baker’s Incremental Baker’s Incremental
Copying Copying
The best known real-time garbage collector.The best known real-time garbage collector.
Free list(tospace), Live list (fromspace).Free list(tospace), Live list (fromspace).
Object: two pointers (next,prev) and a color (for Object: two pointers (next,prev) and a color (for the set).
the set).
Fast allocation: copying in Cheney fashion.Fast allocation: copying in Cheney fashion.
Read Barrier.Read Barrier.
Baker’s Incremental Baker’s Incremental
Copying (cont’) Copying (cont’)
Tricolors: Tricolors:
- Black:
- Black: Scanned area in tospace Scanned area in tospace - - GreyGrey: copied but not scanned.: copied but not scanned.
- - WhiteWhite: unreached objects in fromspace.: unreached objects in fromspace.
• Use scan-pointer on unscanned area of
tospace, and move referred-to objects from
fromspace.
Baker’s Incremental Baker’s Incremental
Copying (cont’) Copying (cont’)
Rule: Scanned objects in tospace(black) Rule: Scanned objects in tospace(black) cannot point to objects in fromspace(white).
cannot point to objects in fromspace(white).
If If a mutator tries to access a pointer from the a mutator tries to access a pointer from the fromspace (white), the referent is copied into fromspace (white), the referent is copied into
the tospace (grey) before the access.
the tospace (grey) before the access.
Allocation of new objects during GC is done Allocation of new objects during GC is done in tospace, they are live - black.
in tospace, they are live - black.
Baker’s Incremental Baker’s Incremental
Copying implementation Copying implementation
Rate of copy is tied to the rate of runtime Rate of copy is tied to the rate of runtime allocation.
allocation.
Read barrier: compiled in software orRead barrier: compiled in software or
implemented by hardware checks and/or implemented by hardware checks and/or
microcode routines (Lisp Machines) microcode routines (Lisp Machines)
Order of 20% time overheads.Order of 20% time overheads.
The Treadmill (Baker) The Treadmill (Baker)
Non-copying.Non-copying.
Doubly linked lists.Doubly linked lists.
The Treadmill (cont’) The Treadmill (cont’)
During allocation
The Treadmill The Treadmill
Conservatism Conservatism
Allocated objects are marked live, but might Allocated objects are marked live, but might die before the collection finishes.
die before the collection finishes.
Pre-existing object marked live, might die Pre-existing object marked live, might die after being reached.
after being reached.
• If the mutator destroys all the grey objects
that point to a white object, although the
white object will not be reachable by the
collector, its memory will be reclaimed.
Snapshot-at-Beginning Snapshot-at-Beginning
Write-Barrier (Yuasa) Write-Barrier (Yuasa)
CheaperCheaper then read barrier, as heap writes then read barrier, as heap writes are less common then heap reads.
are less common then heap reads.
The graph of reachable objects is The graph of reachable objects is fixedfixed from from the beginning.
the beginning.
AllAll objects are accessed by the GC during objects are accessed by the GC during collection (saves overwritten values).
collection (saves overwritten values).
more more conservativeconservative then Baker, then Baker, all pointers all pointers retained, no free during GC.
retained, no free during GC.
Tricolor Marking Tricolor Marking
Before D is reachable
Incremental Update
Incremental Update Write- Write- Barrier(Dijkstra)
Barrier(Dijkstra)
Heuristically retain live objects at the end of Heuristically retain live objects at the end of GC.GC.
Objects that die during GC and before Objects that die during GC and before reached by GC, may be reclaimed.
reached by GC, may be reclaimed.
Records a pointer that escapes into an already Records a pointer that escapes into an already reached object (black
reached object (black white) white) (grey (grey white)
white)
Incremental Update Incremental Update
Write-Barrier(Dijkstra) Write-Barrier(Dijkstra)
cont’
cont’
New objects are allocated New objects are allocated whitewhite: short lived : short lived objects will not be traversed early, but will be objects will not be traversed early, but will be
reclaimed quickly (advantage).
reclaimed quickly (advantage).
Comparison of Comparison of
Incremental GCs Incremental GCs
Write Barrier Read Barrier
incremental update
snapshot Treadmill
Efficiency heap writes heap writes heap reads Reclaim short
lived objects (80% - 98%)
quickly(allocate white)
longer(allocate black)
longer(allocate black)
Generational Garbage Generational Garbage
Collection Collection
(copying)
(copying)
Before GC
After GC
Generational Garbage Generational Garbage
Collection Collection
New objects are allocated in the New Gen.New objects are allocated in the New Gen.
When full, New Gen only is scavenged, then When full, New Gen only is scavenged, then old objects are copied to the Old Gen.
old objects are copied to the Old Gen.
Include a pointer Old Gen Include a pointer Old Gen New Gen in the New Gen in the Root Set
Root Set..
Does not copy all live data at a collection.
Does not copy old objects repeatedly.
Generational Garbage Generational Garbage
Collection Cont’
Collection Cont’
Copy CollectorCopy Collector: all pointers to moved objects : all pointers to moved objects are updated.
are updated.
Conservative true livenessConservative true liveness, not all pointers , not all pointers Old Gen
Old Gen New Gen are live, they will float New Gen are live, they will float until the Old Gen will be scavenged.
until the Old Gen will be scavenged.
Generational Garbage Generational Garbage
Collection Cont’
Collection Cont’
Newer generations are usually smaller then Newer generations are usually smaller then older, so scanning them is
older, so scanning them is fasterfaster..
Better locality.Better locality.
Record of intergenerational pointers is not Record of intergenerational pointers is not tied to the rate of object creation, but still tied to the rate of object creation, but still
might slow the program.
might slow the program.
Conclusions Conclusions
Generational techniques reduce cost as Generational techniques reduce cost as objects tend to die fast.
objects tend to die fast.
Generational techniques with write barrier Generational techniques with write barrier can support incremental update collection.
can support incremental update collection.
We studied several kinds of GCs.We studied several kinds of GCs.
Most important characteristics of GCs.Most important characteristics of GCs.
Constant factors of cost (locality effects).Constant factors of cost (locality effects).
Understanding current research.Understanding current research.
