Unobrusive Garbage CollectionUnobrusive Garbage CollectionIncremental GCIncremental GCldots Incremental GCldots Cost of Garbage CollectionCost of Garbage CollectionCost of GC --- Mark-and-SweepCost of GC --- Mark-and-Sweepldots Cost of GC --- Copying CollectionCost of GC --- Copying Collectionldots Cost of GC --- Generational CollectionCost of GC --- Generational Collectionldots Exam ProblemExam Problem Ildots Exam Problemldots Readings and ReferencesReadings and Referencesldots520—Spring 2005—43CSc 520Principles of ProgrammingLanguages43: Garbage Collection — DiscussionChristian [email protected] of Computer ScienceUniversity of ArizonaCopyrightc 2005 Christian Collberg[1]520—Spring 2005—43Unobrusive Garbage Collection[2]520—Spring 2005—43Unobrusive Garbage CollectionGC Requirements:batch programs: We want short total GC time.interactive programs: We want unnoticable GCs.Unobtrusive GC:Incremental CollectionDo a little GC-work every time an object is allocated,or a pointer is changed.Concurrent CollectionRun the collector and the program in differentprocesses, or on different processors.[3]520—Spring 2005—43Incremental GCUse copying collection, but rather than stop when yourun out of memory and then do all the GC work in oneshot, do a little bit whenever a pointer variable isreferenced or when a new object is allocated.We start out by forwarding (copying) the objects pointedto by global variables.Then, instead of continuing forwarding recursively, weresume the program.Every time a pointer is referenced we check to seewhether it is pointing into from-space. If it is, weforward that object too.[4]520—Spring 2005—43Incremental GC...Even objects which are not explicitly referenced have tobe checked, to see if they have become garbage.Therefore, every time we allocate a new object weforwardk pointers.A good value for k has to be determined byexperimentation.Eventually scan will catch up with next and we switchfrom-space and to-space and start an new cycle.Baker’s algorithm (on the next slide) is a variant ofcopying collection.[5]520—Spring 2005—43Incremental GC...1. Copy and update objects pointed to by global pointersto to-space.2. Resume program.3. When an object infrom-space is referenced, first copyit to to-space.p := x ↑.next;⇓ (implemented as)IF x ∈ from − space THENcopy x to to-space;updatex, scan, and next;x := x’s new address in to-space;END;p := x ↑.next;4. Every time NEW is called, k pointers are forwarded.[6]520—Spring 2005—43Cost of Garbage Collection[7]520—Spring 2005—43Cost of Garbage CollectionThe size of the heap is H, the amount of reachablememory is R, the amount of memory reclaimed isH − R.What is the cost of the different GC algorithms?HeapReachable=R Reclaimed=H − RHeapsize=Hamortized GC cost =time spent in GCamount of garbage collected=time spent in GCH − R[8]520—Spring 2005—43Cost of GC — Mark-and-SweepHeapReachable=R Reclaimed=H − RHeapsize=HThe mark phase touches all live nodes. Hence, it takestime c1H, for some constant c1. c1≈ 10?The sweep phase touches the whole heap. Hence, ittakes time c2R, for some constant c2. c2≈ 3?GC cost=c1R + c2HH − R≈10R + 3HH − R[9]520—Spring 2005—43Cost of GC — Mark-and-Sweep...HeapReachable=R Reclaimed=H − RHeapsize=HGC cost =c1R + c2HH − R≈10R + 3HH − RIf H ≈ R we reclaim very litte, and the cost of GC goesup. In this case the GC should grow the heap (increaseH).[10]520—Spring 2005—43Cost of GC — Copying CollectionHeapReachable=R Reclaimed=H − RHeapsize=HThe breadth first search phase touches all live nodes.Hence, it takes time c3R, for some constant c3. c3≈ 10?The heap is divided into a from-space and a to-space,so each collection reclaimsH2− R words.GC cost=c3RH2− R≈10RH2− R[11]520—Spring 2005—43Cost of GC — Copying Collection...GC cost =c3RH2− R≈10RH2− RIf there are few live objects (H R) the GC cost is low.If H = 4R, we getGC cost=c3R4R2− R≈ 10.This is expensive: 4 times as much memory asreachable data, 10 instruction GC cost per objectallocated.[12]520—Spring 2005—43Cost of GC — Generational CollectionHeapReachable=R Reclaimed=H − RHeapsize=HAssume 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[13]520—Spring 2005—43Cost of GC — Generational Collection...HeapReachable=R Reclaimed=H − RHeapsize=HGC 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 (forG0).[14]520—Spring 2005—43Exam Problem1. Why is generational collection more appropriate forfunctional and logic languages (such as LISP andProlog), than for object-oriented languages (such asEiffel and Modula-3)?2. The heap in the figure on the next slide holds 7 objects.All objects have one integer field and one or two pointerfields (black dots). The only roots are the three globalvariablesX, Y, and Z. Free space is shaded. Show thestate of To-Space after a copying garbage collectionhas been performed onFrom-Space. Note that severalanswers are possible, depending on the visit strategy(Depth-First or Breadth-First Search) you chose.[15]520—Spring 2005—43Exam Problem I...YXZRoots:SpaceFrom−57 13101286[16]520—Spring 2005—43Exam Problem...1. Name five garbage collection algorithms!2. Describe theDeutsch-Schorr-Waite algorithm! When isit used? Why is it used? How does it work?3. What are the differences betweenstop-and-copy,incremental and concurrent garbage collection? Whenwould we prefer one over the other?[17]520—Spring 2005—43Readings and ReferencesRead Scott, pp. 395–401.Apple’s Tiger book, pp. 257–282Topics in advanced language implementation, Chapter4, Andrew Appel, Garbage Collection. Chapter 5, DavidL. Detlefs, Concurrent Garbage Collection for C++.ISBN 0-262-12151-4.Aho, Hopcroft, Ullman. Data Structures and Algorithms,Chapter 12, Memory Management.[18]520—Spring 2005—43Readings and References...Nandakumar Sankaran, A Bibliography on GarbageCollection and Related Topics, ACM SIGPLAN Notices,Volume 29, No. 9, Sep 1994.J. Cohen. Garbage Collection of Linked DataStructures, Computing Surveys, Vol. 13, No. 3,
View Full Document
Unlocking...