Generational CollectionGenerational Collectionldots Generational Collectionldots Generational Collectionldots Generational Collection -- After GC($G_0$)Generational Collectionldots Remembering Back PointersRemembering Back PointersRemembering Back PointersRemembering Back Pointersldots Remembering Back Pointersldots Remembering Back Pointersldots Cost of Garbage CollectionCost of Garbage CollectionCost of GC --- Generational CollectionCost of GC --- Generational Collectionldots Readings and References520 —Spring 2008 — 10CSc 520Principles of ProgrammingLanguages10 : Garbage Collection — GenerationalCollectionChristian [email protected] of Computer ScienceUniversity of ArizonaCopyrightc 2008 Christian Collberg[1]520 —Spring 2008 — 10Generational CollectionWorks best for functional and logic languages (LISP,Prolog, ML, ...) because1. they rarely modify allocated cells2. newly created objects only point to older objects((CONS A B) creates a new two-pointer cell withpointers to old objects),3. new cells are shorter lived than older cells, and oldobjects are unlikely to die anytime soon.[2]520 —Spring 2008 — 10Generational Collection...Generational Collection therefore1. divides the heap intogenerations, G0is theyoungest, Gnthe oldest.2. allocates new objects in G0.3. GC’s only newer generations.We have to keep track of back pointers (from oldgenerations to new).[3]520 —Spring 2008 — 10Generational Collection...Functional Language:(cons ’a ’(b c))mt1: x ← new ’(b c);t2: y ← new ’a;t3: return new cons(x, y)A new object (created at time t3) points to older objects.Object Oriented Language:t1: T ← new Table(0);t2: x ← new Integer(5);t3: T.insert(x);A new object (created at time t2) is inserted into an older object, whichthen points to the news object.[4]520 —Spring 2008 — 10Generational Collection...Remembered Set:Roots:G0G1G2[5]520 —Spring 2008 — 10Generational Collection – After GC(G0)Remembered Set:Roots:G1G2G′0[6]520 —Spring 2008 — 10Generational Collection...Since old objects (in Gn· · · G1) are rarely changed (topoint to new objects) they are unlikely to point into G0.Apply the GC only to the youngest generation (G0),since it is most likely to contain a lot of garbage.Use the stack and globals as roots.There might be some back pointers, pointing from anolder generation into G0. Maintain a special set of suchpointers, and use them as roots.Occasionally GC older (G1· · · Gk) generations.Use either mark-and-sweep or copying collection to GCG0.[7]520 —Spring 2008 — 10Remembering Back Pointers[8]520 —Spring 2008 — 10Remembering Back PointersRemembered ListAfter each pointer update x.f := · · · , the compiler addscode to insert x in a list of updated memory locations:x↑.f := · · ·⇓x↑.f := · · · ;insert(UpdatedList, x);[9]520 —Spring 2008 — 10Remembering Back PointersRemembered SetAs above, but set a bit in the updated object so that it isinserted only once in the list:x↑.f := · · ·⇓x↑.f := · · · ;IF NOT x↑.inserted THENinsert(UpdatedList, x);x.↑inserted := TRUE;ENDIF[10]520 —Spring 2008 — 10Remembering Back Pointers...Card markingDivide the heap into “cards” of size 2k.Keep an array dirty of bits, indexed by card number.After a pointer update x↑.f := · · · , set the dirty bit forcard c that x is on:x↑.f := · · ·⇓x↑.f := · · · ;dirty[x div 2k] := TRUE;[11]520 —Spring 2008 — 10Remembering Back Pointers...Page marking ISimilar to Card marking, but let the cards be virtualmemory pages.When x is updated the VM system automatically setsthe dirty bit of the page that x is on.We don’t have to insert any extra code![12]520 —Spring 2008 — 10Remembering Back Pointers...Page marking IIThe OS may not let us read the VM system’s dirty bits.Instead, we write-protect the page x is on.On an update x↑.f := · · · a protection fault isgenerated. We catch this fault and set a dirty bitmanually.We don’t have to insert any extra code![13]520 —Spring 2008 — 10Cost of Garbage Collection[14]520 —Spring 2008 — 10Cost of Garbage CollectionThe size of the heap is H, the amount of reachablememory is R, the amount of memory reclaimed isH − R.HeapHeapsize=HReachable=R Reclaimed=H − Ramortized GC cost =time spent in GCamount of garbage collected=time spent in GCH − R[15]520 —Spring 2008 — 10Cost of GC — Generational CollectionHeaptofromHeapsize=HReachable=RReclaimedG0G2G1Assume the youngest generation (G0) has 10% livedata, i.e. H = 10R.Assume we’re using copying collection for G0.GC costG0=c3RH2− R=c3R10R2− R≈10R4R= 2.5[16]520 —Spring 2008 — 10Cost of GC — Generational Collection...HeaptofromHeapsize=HReachable=RReclaimedG0G2G1GC costG0=c3RH2− R=c3R10R2− R≈10R4R= 2.5If R ≈ 100 kilobytes in G0, then H ≈ 1 megabyte.In other words, we’ve wasted about 900 kilobytes, to get2.5 instruction/word GC cost (for G0).[17]520 —Spring 2008 — 10Readings and ReferencesRead Scott, pp.
View Full Document
Unlocking...