Unified Theory of Garbage Collection

Seminar Talk by Yoshimi Takano

1. A Unied Theory of Garbage CollectionDavid F. Bacon Perry Cheng V.T. Rajan
IBM Watson Research CenterSeminar Talk by Yoshimi Takano, ETH Zurich
A Unied Theory of Garbage Collection (Bacon et al.)Seminar Talk by Yoshimi Takano 1

2. “He who loves practice without theory is like the sailor
who boards ship without a rudder and compass and
never knows where he may cast.”
– Leonardo da Vinci
A Unied Theory of Garbage Collection (Bacon et al.)Seminar Talk by Yoshimi Takano 2

3. A Unied Theory of Garbage CollectionDavid F. Bacon Perry Cheng V.T. Rajan
IBM Watson Research Center
A Unied Theory of Garbage Collection (Bacon et al.)Seminar Talk by Yoshimi Takano 3

4. Summary
ITracing and reference counting aredualsIAll high-performance garbage collectors arehybridsof
tracing and reference counting
IThistaxonomycan be used
ITo develop a uniform cost-modelIAs an algorithm design frameworkITo generate collectors dynamically. . .
A Unied Theory of Garbage Collection (Bacon et al.)Seminar Talk by Yoshimi Takano 4

5. Outline
Introduction
Garbage CollectionMotivation
Duality of Tracing and Reference Counting
Qualitative ComparisonAbstract Garbage CollectionConvergence
Collection as Tracing and Reference Counting
Single HeapSplit Heap
Uniform Cost Model
A Unied Theory of Garbage Collection (Bacon et al.)Seminar Talk by Yoshimi Takano 5

6. IntroductionGarbage Collection
Garbage Collection and Liveness (Recap)
IAutomaticstorage reclamation ofunreachableobjectsIRoots:IGlobals
ILocals in stack framesRootsLiveDead
A Unied Theory of Garbage Collection (Bacon et al.)Seminar Talk by Yoshimi Takano 6

7. IntroductionMotivation
Picking a Garbage Collector for your VM
ILots and lotsof garbage collector algorithms
State of the Art
IImplementnalgorithmsIMeasure and compare formbenchmarksIUse algorithm with best mean performance
Problems
ILimited exploration of design space (“no compass”)IStatic selection can sacrice performance
A Unied Theory of Garbage Collection (Bacon et al.)Seminar Talk by Yoshimi Takano 7
[Slide from OOPSLA presentation]

8. IntroductionMotivation
Picking a Garbage Collector for your VM
ILots and lotsof garbage collector algorithms
State of the Art
IImplementnalgorithmsIMeasure and compare formbenchmarksIUse algorithm with best mean performance
Problems
ILimited exploration of design space (“no compass”)IStatic selection can sacrice performance
A Unied Theory of Garbage Collection (Bacon et al.)Seminar Talk by Yoshimi Takano 7
[Slide from OOPSLA presentation]

9. Duality of Tracing and Reference CountingQualitative Comparison
Two Fundamental Garbage Collection Techniques
Tracing
[McCarthy, 1960]IStopthe worldITraceforward from rootsIEverything touched is live, all else is garbage
Reference Counting
[Collins, 1960]IEach object hascount of incoming pointersIAdjust count in case of mutations(write barrier)IWhen counter reacheszero, object is garbage and count
of all children is decremented
A Unied Theory of Garbage Collection (Bacon et al.)Seminar Talk by Yoshimi Takano 8

10. Duality of Tracing and Reference CountingQualitative Comparison
Two Fundamental Garbage Collection Techniques
Tracing
[McCarthy, 1960]IStopthe worldITraceforward from rootsIEverything touched is live, all else is garbage
Reference Counting
[Collins, 1960]IEach object hascount of incoming pointersIAdjust count in case of mutations(write barrier)IWhen counter reacheszero, object is garbage and count
of all children is decremented
A Unied Theory of Garbage Collection (Bacon et al.)Seminar Talk by Yoshimi Takano 8

11. Duality of Tracing and Reference CountingQualitative Comparison
Diametrical Opposites?
TracingReference Counting
Collection Style
BatchIncremental
Pause Times
LongShort
Real Time?
NoYes
Delayed Reclamation?
YesNo
Cost per Mutation
NoneHigh
Collects Cycles?
YesNo
111
A Unied Theory of Garbage Collection (Bacon et al.)Seminar Talk by Yoshimi Takano 9
[Table from paper]

12. Duality of Tracing and Reference CountingQualitative Comparison
How Different Really?
IBoth types have been implemented by the authorsIVery different starting pointIBut with optimizations,similaritiesincrease:
IBoth trace rootsIBoth are semi-incrementalIBoth have oating garbageIBoth have write barriersIWhy?
A Unied Theory of Garbage Collection (Bacon et al.)Seminar Talk by Yoshimi Takano 10

13. Duality of Tracing and Reference CountingAbstract Garbage Collection
Abstract Garbage Collection
Denition
An
object graphis a tripleG= (V;E;R)with
Vthe set of vertices (objects)
Ethe multiset of directed edges (pointers)
Rthe multiset of roots
Multiset notation:[a;b]][b] = [a;b;b]
Denition
A function:V!N0is a
reference count functionfor an object
graphG= (V;E;R)iff
8x2V:
(x)=j[(u;x)2E:(u)>0]j+1x2R
I“# in-edges from vertices with a non-zero RC (+1)”
A Unied Theory of Garbage Collection (Bacon et al.)Seminar Talk by Yoshimi Takano 11
RootsR
|
{z}
V

14. Duality of Tracing and Reference CountingAbstract Garbage Collection
Abstract Garbage Collection
Denition
An
object graphis a tripleG= (V;E;R)with
Vthe set of vertices (objects)
Ethe multiset of directed edges (pointers)
Rthe multiset of roots
Multiset notation:[a;b]][b] = [a;b;b]
Denition
A function:V!N0is a
reference count functionfor an object
graphG= (V;E;R)iff
8x2V:
(x)=j[(u;x)2E:(u)>0]j+1x2R
I“# in-edges from vertices with a non-zero RC (+1)”
A Unied Theory of Garbage Collection (Bacon et al.)Seminar Talk by Yoshimi Takano 11
RootsR
|
{z}
V

15. Duality of Tracing and Reference CountingAbstract Garbage Collection
Abstract Garbage Collection, cont'd
Denition
A
garbage collection algorithmtakes an object graphGas input
and computes a
reference count functionforG.
Objectsxwith
(x) =0are thenreclaimed.ICommon abstract model, whereanyalgorithm computes
reference counts
IFor a given object graph, there can bemanysuch
functions, as will be seen later
A Unied Theory of Garbage Collection (Bacon et al.)Seminar Talk by Yoshimi Takano 12

16. Duality of Tracing and Reference CountingAbstract Garbage Collection
Abstract Garbage Collection, cont'd
Denition
A
garbage collection algorithmtakes an object graphGas input
and computes a
reference count functionforG.
Objectsxwith
(x) =0are thenreclaimed.ICommon abstract model, whereanyalgorithm computes
reference counts
IFor a given object graph, there can bemanysuch
functions, as will be seen later
A Unied Theory of Garbage Collection (Bacon et al.)Seminar Talk by Yoshimi Takano 12

17. Duality of Tracing and Reference CountingConvergence
Tracing Revisited
Let's consider a version of tracing that
computes reference
counts
instead of simply setting mark bits:
initialize-for-tracing():
W R
scan-by-tracing():
whileW6=;
removewfromW
(w) (w) +1if
(w) =1
for eachx2children(w)
W W][x]
RootsLiveDead00000000000000
A Unied Theory of Garbage Collection (Bacon et al.)Seminar Talk by Yoshimi Takano 13
[Pseudo-code snippets from paper]

18. Duality of Tracing and Reference CountingConvergence
Tracing Revisited
Let's consider a version of tracing that
computes reference
counts
instead of simply setting mark bits:
initialize-for-tracing():
W R
scan-by-tracing():
whileW6=;
removewfromW
(w) (w) +1if
(w) =1
for eachx2children(w)
W W][x]
RootsLiveDead00000000000000
A Unied Theory of Garbage Collection (Bacon et al.)Seminar Talk by Yoshimi Takano 13
[Pseudo-code snippets from paper]

19. Duality of Tracing and Reference CountingConvergence
Tracing Revisited
Let's consider a version of tracing that
computes reference
counts
instead of simply setting mark bits:
initialize-for-tracing():
W R
scan-by-tracing():
whileW6=;
removewfromW
(w) (w) +1if
(w) =1
for eachx2children(w)
W W][x]
RootsLiveDead22114100000000
A Unied Theory of Garbage Collection (Bacon et al.)Seminar Talk by Yoshimi Takano 13
[Pseudo-code snippets from paper]

20. Duality of Tracing and Reference CountingConvergence
Tracing Revisited
Let's consider a version of tracing that
computes reference
counts
instead of simply setting mark bits:
initialize-for-tracing():
W R
scan-by-tracing():
whileW6=;
removewfromW
(w) (w) +1if
(w) =1
for eachx2children(w)
W W][x]
RootsLiveDead22114100000000
A Unied Theory of Garbage Collection (Bacon et al.)Seminar Talk by Yoshimi Takano 13
[Pseudo-code snippets from paper]

21. Duality of Tracing and Reference CountingConvergence
Reference Counting Revisited
Let's consider a version of RC in which the
decrement
operations are
batchedinstead of performed immediately:
mutate(old,new):
W W][old](new) (new) +1
scan-by-counting():
whileW6=;
removewfromW
(w) (w)1if
(w) =0
for eachx2children(w)
W W][x]
Anti-rootsDeadCyclic12134221112111
A Unied Theory of Garbage Collection (Bacon et al.)Seminar Talk by Yoshimi Takano 14

22. Duality of Tracing and Reference CountingConvergence
Reference Counting Revisited
Let's consider a version of RC in which the
decrement
operations are
batchedinstead of performed immediately:
mutate(old,new):
W W][old](new) (new) +1
scan-by-counting():
whileW6=;
removewfromW
(w) (w)1if
(w) =0
for eachx2children(w)
W W][x]
Anti-rootsDeadCyclic12134221112111
A Unied Theory of Garbage Collection (Bacon et al.)Seminar Talk by Yoshimi Takano 14

23. Duality of Tracing and Reference CountingConvergence
Reference Counting Revisited
Let's consider a version of RC in which the
decrement
operations are
batchedinstead of performed immediately:
mutate(old,new):
W W][old](new) (new) +1
scan-by-counting():
whileW6=;
removewfromW
(w) (w)1if
(w) =0
for eachx2children(w)
W W][x]
Anti-rootsDeadCyclic22134221112121
A Unied Theory of Garbage Collection (Bacon et al.)Seminar Talk by Yoshimi Takano 14

24. Duality of Tracing and Reference CountingConvergence
Reference Counting Revisited
Let's consider a version of RC in which the
decrement
operations are
batchedinstead of performed immediately:
mutate(old,new):
W W][old](new) (new) +1
scan-by-counting():
whileW6=;
removewfromW
(w) (w)1if
(w) =0
for eachx2children(w)
W W][x]
Anti-rootsDeadCyclic22124201001001
A Unied Theory of Garbage Collection (Bacon et al.)Seminar Talk by Yoshimi Takano 14

25. Duality of Tracing and Reference CountingConvergence
Reference Counting Revisited
Let's consider a version of RC in which the
decrement
operations are
batchedinstead of performed immediately:
mutate(old,new):
W W][old](new) (new) +1
scan-by-counting():
whileW6=;
removewfromW
(w) (w)1if
(w) =0
for eachx2children(w)
W W][x]
Anti-rootsDeadCyclic22124201001001
A Unied Theory of Garbage Collection (Bacon et al.)Seminar Talk by Yoshimi Takano 14

26. Duality of Tracing and Reference CountingConvergence
Not So Different After All...
initialize-for-tracing():
W R
scan-by-tracing():
whileW6=;
removewfromW
(w) (w)
+1
if(w) =
1
for eachx2children(w)
W W][x]
mutate(old,new):
W W][old]
(new) (new) +1
scan-by-counting():
whileW6=;
removewfromW
(w) (w)
1
if(w) =
0
for eachx2children(w)
W W][x]
A Unied Theory of Garbage Collection (Bacon et al.)Seminar Talk by Yoshimi Takano 15

27. Duality of Tracing and Reference CountingConvergence
Duality
TracingReference Counting
Starting Point
RootsAnti-roots
Graph Traversal
Fwd. from rootsFwd. from anti-roots
Objects Traversed
LiveDead
Initial RC
Low (zero)High
RC Reconstruction
AdditionSubtraction
2211410000000022124201001001
A Unied Theory of Garbage Collection (Bacon et al.)Seminar Talk by Yoshimi Takano 16
[Table from paper]

28. Collection as Tracing and Reference Counting
Tracing/Counting Hybrids
Fundamentals
IDivisionof storage:ISingle heap(=1)
ISplit heap(=2)IMulti-heap(>2)IAssignment of eithertracingorreference countingto the
different divisions
Trade-offs
IRemaining choices are implementation details andspace-time trade-offs
A Unied Theory of Garbage Collection (Bacon et al.)Seminar Talk by Yoshimi Takano 17

29. Collection as Tracing and Reference Counting
Tracing/Counting Hybrids
Fundamentals
IDivisionof storage:ISingle heap(=1)
ISplit heap(=2)IMulti-heap(>2)IAssignment of eithertracingorreference countingto the
different divisions
Trade-offs
IRemaining choices are implementation details andspace-time trade-offs
A Unied Theory of Garbage Collection (Bacon et al.)Seminar Talk by Yoshimi Takano 17

30. Collection as Tracing and Reference CountingSingle Heap
Single Heap Algorithms
IRoot references vs. intra-heap referencesRootsHeap
A Unied Theory of Garbage Collection (Bacon et al.)Seminar Talk by Yoshimi Takano 18

31. Collection as Tracing and Reference CountingSingle Heap
Single Heap Algorithms
IRoot references vs. intra-heap referencesRootsHeap
A Unied Theory of Garbage Collection (Bacon et al.)Seminar Talk by Yoshimi Takano 18
[Schematics from paper]

32. Collection as Tracing and Reference CountingSingle Heap
Algorithm 1: Tracing
IBoth root and intra-heap references aretracedRootsHeapTT
A Unied Theory of Garbage Collection (Bacon et al.)Seminar Talk by Yoshimi Takano 19

33. Collection as Tracing and Reference CountingSingle Heap
Algorithm 2: Reference Counting
IBoth root and intra-heap references arecountedRootsHeapCC
A Unied Theory of Garbage Collection (Bacon et al.)Seminar Talk by Yoshimi Takano 20

34. Collection as Tracing and Reference CountingSingle Heap
Algo. 3: Deferred Reference Counting
[Deutsch/Bobrow, '76]ITo avoid high mutation overhead root references arenot
counted
(i.e. write barrier ignores root pointers)IObjects with reference count 0 are maintained in azero
count table(ZCT)
IRoot references aretracedat collection time
mutate(old,new):
if
:is-root-pointer
. . .
RootsHeapZCTTC
A Unied Theory of Garbage Collection (Bacon et al.)Seminar Talk by Yoshimi Takano 21

35. Collection as Tracing and Reference CountingSingle Heap
Algo. 3: Deferred Reference Counting
[Deutsch/Bobrow, '76]ITo avoid high mutation overhead root references arenot
counted
(i.e. write barrier ignores root pointers)IObjects with reference count 0 are maintained in azero
count table(ZCT)
IRoot references aretracedat collection time
mutate(old,new):
if
:is-root-pointer
. . .
RootsHeapZCTTC
A Unied Theory of Garbage Collection (Bacon et al.)Seminar Talk by Yoshimi Takano 21

36. Collection as Tracing and Reference CountingSingle Heap
Algo. 3: Deferred Reference Counting
[Deutsch/Bobrow, '76]ITo avoid high mutation overhead root references arenot
counted
(i.e. write barrier ignores root pointers)IObjects with reference count 0 are maintained in azero
count table(ZCT)
IRoot references aretracedat collection time
mutate(old,new):
if
:is-root-pointer
. . .
RootsHeapZCTTC
A Unied Theory of Garbage Collection (Bacon et al.)Seminar Talk by Yoshimi Takano 21

37. Collection as Tracing and Reference CountingSingle Heap
Single Heap Collector Family
TT
(Pure) Tracing
[McCarthy, 1960]CT
“Partial Tracing”
CC
(Pure) Reference Counting
[Collins, 1960]TC
Deferred Reference Counting
[Deutsch/Bobrow, 1976]
A Unied Theory of Garbage Collection (Bacon et al.)Seminar Talk by Yoshimi Takano 22

38. Collection as Tracing and Reference CountingSplit Heap
Generational Garbage Collection
[Ungar, 1984]IHeap is split up in 2 regions: anurseryand amature spaceICollect nurseryindependentlyINursery objects pointed to by mature references are
maintained in a
remembered set(RS)by a write barrier,
i.e. reference
countedRootsNurseryMatureRSTTTTC
A Unied Theory of Garbage Collection (Bacon et al.)Seminar Talk by Yoshimi Takano 23

39. Collection as Tracing and Reference CountingSplit Heap
Generational Garbage Collection
[Ungar, 1984]IHeap is split up in 2 regions: anurseryand amature spaceICollect nurseryindependentlyINursery objects pointed to by mature references are
maintained in a
remembered set(RS)by a write barrier,
i.e. reference
countedRootsNurseryMatureRSTTTTC
A Unied Theory of Garbage Collection (Bacon et al.)Seminar Talk by Yoshimi Takano 23

40. Collection as Tracing and Reference CountingSplit Heap
Generational Garbage Collection
[Ungar, 1984]IHeap is split up in 2 regions: anurseryand amature spaceICollect nurseryindependentlyINursery objects pointed to by mature references are
maintained in a
remembered set(RS)by a write barrier,
i.e. reference
countedRootsNurseryMatureRSTTTTC
A Unied Theory of Garbage Collection (Bacon et al.)Seminar Talk by Yoshimi Takano 23

41. Collection as Tracing and Reference CountingSplit Heap
Generational Traced-Root Collector Family
TTTTC
Generational
[Ungar, 1984]TTCCC
“Redundant Reference Counting”
TTTCC
Ulterior Reference Counting
[Blackburn/McKinley, 2003]TTCTC
“Inferior Reference Counting”
A Unied Theory of Garbage Collection (Bacon et al.)Seminar Talk by Yoshimi Takano 24

42. Uniform Cost Model
Enabling Quantitative Comparison
ICharacterizeobject graphandprogramINumber of objectsIAllocation rate
IMutation rateIetc.IDevelopspace/time cost formulasfor each collectorIDon't “cheat” by ignoring collectormetadataICoefcientscifor each parameter are left unspecied
ISee paper for detailsISimple example:
time-per-collection
Tracing
=c1jRj+c2jVlivej+c3jElivej+c4jVj
A Unied Theory of Garbage Collection (Bacon et al.)Seminar Talk by Yoshimi Takano 25

43. Uniform Cost Model
Enabling Quantitative Comparison
ICharacterizeobject graphandprogramINumber of objectsIAllocation rate
IMutation rateIetc.IDevelopspace/time cost formulasfor each collectorIDon't “cheat” by ignoring collectormetadataICoefcientscifor each parameter are left unspecied
ISee paper for detailsISimple example:
time-per-collection
Tracing
=c1jRj+c2jVlivej+c3jElivej+c4jVj
A Unied Theory of Garbage Collection (Bacon et al.)Seminar Talk by Yoshimi Takano 25

44. ConclusionBenets
Conclusion
Benets
IDeeper theoreticalinsightinto garbage collectionIDesign of collectors can be made moremethodicalIMay help enabledynamicconstruction of collectors tuned
to particular applications
A Unied Theory of Garbage Collection (Bacon et al.)Seminar Talk by Yoshimi Takano 26

45. ConclusionFuture Work/Outlook
Conclusion, cont'd
Future Work/Outlook
IRene(unrealistic) assumptions:IFixed-size objects (no fragmentation)
INo concurrent collectors
IApplication in steady stateITakeallocationcost andlocalityissues into accountIMeasurecoefcientsfor cost parametersITheory looks promising, butpracticalrelevance still needs
to emerge
A Unied Theory of Garbage Collection (Bacon et al.)Seminar Talk by Yoshimi Takano 27

46. “Theory without practice cannot survive and dies as
quickly as it lives.” – Leonardo da Vinci
A Unied Theory of Garbage Collection (Bacon et al.)Seminar Talk by Yoshimi Takano 28

47. Sources
Sources
David F. Bacon, Perry Cheng, V.T. Rajan
A Unied Theory of Garbage Collection(Paper and Presentation atOOPSLA 2004, Vancouver)
Paul R. Wilson
Uniprocessor Garbage Collection Techniques
A Unied Theory of Garbage Collection (Bacon et al.)Seminar Talk by Yoshimi Takano 29

48. Additional MaterialFix-point Formulation
Fix-point Formulation
Denition
A function:V!N0is a
reference count functionfor an object
graphG= (V;E;R)iff
8x2V:
(x)=j[(u;x)2E:(u)>0]j+1x2R
I“# in-edges from vertices with a non-zero RC+const.”I=x:j[(u;x)2E:(u)>0]j+1x2R
|
{z}
=:
F()
=)is a
x-point
A Unied Theory of Garbage Collection (Bacon et al.)Seminar Talk by Yoshimi Takano 30
RootsR
|
{z}
V

49. Additional MaterialPartial Tracing
Algorithm 4: Partial Tracing
INew (inefcient?) algorithmIOnly root references arecountedIIntra-heap references aretraced, starting from the
dynamically maintained root setR
mutate(old,new):
if
is-root-pointer
R R][new]
R R[old]
RootsHeapCT
A Unied Theory of Garbage Collection (Bacon et al.)Seminar Talk by Yoshimi Takano 31

50. Additional MaterialPartial Tracing
Algorithm 4: Partial Tracing
INew (inefcient?) algorithmIOnly root references arecountedIIntra-heap references aretraced, starting from the
dynamically maintained root setR
mutate(old,new):
if
is-root-pointer
R R][new]
R R[old]
RootsHeapCT
A Unied Theory of Garbage Collection (Bacon et al.)Seminar Talk by Yoshimi Takano 31

51. Additional MaterialPartial Tracing
Algorithm 4: Partial Tracing
INew (inefcient?) algorithmIOnly root references arecountedIIntra-heap references aretraced, starting from the
dynamically maintained root setR
mutate(old,new):
if
is-root-pointer
R R][new]
R R[old]
RootsHeapCT
A Unied Theory of Garbage Collection (Bacon et al.)Seminar Talk by Yoshimi Takano 31

52. Additional MaterialTrain Algorithm
Multi-Heap Collectors: Train Algorithm
[Hudson/Moss, 1992]RootsTrain 1Train 2TTTTTCCC
A Unied Theory of Garbage Collection (Bacon et al.)Seminar Talk by Yoshimi Takano 32

53. Additional MaterialTrade-Offs
Trade-Offs
IUsingsemi-spaceswith a copying collector (linear
space-time trade-off: half the heap space vs. sweep time)
ITraversal(recursive or with pointer reversals?)IMemorycompactionIImplementation ofremembered sets
A Unied Theory of Garbage Collection (Bacon et al.)Seminar Talk by Yoshimi Takano 33

54. Additional MaterialCycle Collection
Cycle Collection
Backup Tracing
IOccasionally perform atracingcollection
Trial Deletion
IWanted: vertex setShavingno live external in-edgesICandidatevertexx,S:=x

ISubtract internal references and remove vertices withexternal count>022124201001001
A Unied Theory of Garbage Collection (Bacon et al.)Seminar Talk by Yoshimi Takano 34