Copying CollectionCopying Collectionldots Copying Collectionldots Copying Collectionldots Copying Collectionldots Copying Collection AlgorithmCopying Collection Exampleldots (A)Copying Collection Exampleldots (B)Readings and References520—Spring 2005—40CSc 520Principles of ProgrammingLanguages40: Garbage Collection — Copying CollectionChristian [email protected] of Computer ScienceUniversity of ArizonaCopyrightc 2005 Christian Collberg[1]520—Spring 2005—40Copying CollectionEven if most of the heapspace is garbage, a mark andsweep algorithm will touch the entire heap. In suchcases it would be better if the algorithm only touchedthe live objects.Copying collection is such an algorithm. The basic ideais:1. The heap is divided into two spaces, thefrom-spaceand the to-space.2. We start out by allocating objects in thefrom-space.3. Whenfrom-space is full, all live objects are copiedfromfrom-space to to-space.4. We then continue allocating in to-space until it fillsup, and a new GC starts.[2]520—Spring 2005—40Copying Collection...An important side-effect of copying collection is that weget automatic compaction – after a collectionto-spaceconsists of the live objects in a contiguous piece ofmemory, followed by the free space.This sounds really easy, but · · ·:We have to traverse the object graph (just like inmark and sweep), and so we need to decide theorder in which this should be done, depth-first orbreadth-first.DFS requires a stack (but we can, of course, usepointer reversal just as with mark and sweep), andBFS a queue. We will see later that encoding aqueue is very simple, and hence mostimplementations of copying collection make use ofBFS.[3]520—Spring 2005—40Copying Collection...This sounds really easy, but · · ·An object in from-space will generally have severalobjects pointing to it. So, when an object is movedfromfrom-space to to-space we have to make surethat we change the pointers to point to the new copy.[4]520—Spring 2005—40Copying Collection...Mark-and-sweep touches the entire heap, even if most of it isgarbage. Copying collection only touches live cells.Copying collection divides the heap in two parts: from-space andto-space.to-space is automatically compacted.How to traverse object graph: BFS or DFS?How to update pointers to moved objects?Algorithm:1. Start allocating in from-space.2. Whenfrom-space is full, copy live objects to to-space.3. Now allocate into-space.[5]520—Spring 2005—40Copying Collection...Traversing the Object Graph:Most implementations use BFS.Use the to-space as the queue.Updating (Forwarding) Pointers:When an object is moved its new address is stored firstin the old copy.Example:roots:from−spaceto−spaceroots:from−spaceto−spaceGC[6]520—Spring 2005—40Copying Collection Algorithm1. scan := next := ADDR(to-space)[scan · · · next] hold the BFS queue.Objects above scan point into to-space. Objects between scanand next point into from-space.2. Copy objects pointed to by the root pointers to to-space.3. Update the root pointers to point toto-space.4. Put each object’s new address first in the original.5. Repeat (recursively) with all the pointers in the newto-space.(a) Updatescan to point past the last processed node.(b) Updatenext to pointe past the last copied node.Continue whilescan < next.[7]520—Spring 2005—40Copying Collection Example...(A)rootsrootsACDEFfrom−spaceBfrom−spaceto−spaceABCDEFDBnextscan[8]520—Spring 2005—40Copying Collection Example...(B)rootsto−spaceDBnextscanfrom−spaceABCDEFrootsto−spaceDBscannextEfrom−spaceABCDEF[9]520—Spring 2005—40Readings and ReferencesRead Scott, pp.
View Full Document
Unlocking...