1CS553 Lecture Garbage Collection 1Garbage Collection Last time– Compiling Object-Oriented Languages Today– Motivation behind garbage collection– Garbage collection basics– Garbage collection performance– Specific example of using GC in C++ Acknowledgements– These slides are based on Kathryn McKinley’s slides on garbagecollection as well as E Christopher Lewis’s slidesCS553 Lecture Garbage Collection 2Background Static allocation: variables are bound to storage at compile-time– pros: easy to implement– cons: no recursion, data structure sizes are compile-timeconstants, data structures cannot be dynamic Stack allocation: dyn. alloc. stack frame for each proc. invocation– pros: recursion is possible, data structure sizes may depend onparameters– cons: stack allocated data is not persistent, stack allocated datacannot outlive the procedure for which it is defined Heap allocation: arbitrary alloc. and dealloc. of objects in *heap*– pros: solves above problems: dynamic, persistent data structures– cons: very difficult to explicitly manage heap2CS553 Lecture Garbage Collection 3Memory Management Ideal– deallocate all data that will not be used in the future (not possible) What is garbage? Manual/Explicit– programmer deallocates with free or delete Automatic/Implicit– garbage collectionCS553 Lecture Garbage Collection 4Explicit versus Automatic Explicit+ efficiency can be very high+ gives programmers “control”– more code to maintain– correctness is difficult– core dump if an object is freed too soon– space is wasted if an object is freed too late– if never free, at best waste space, at worst fail Automatic+ reduces programmer burden+ eliminates sources of errors+ integral to modern OOP languages (ie. Java, C#)– can not determine all objects that won’t be used in the future– may or may not hurt performance3CS553 Lecture Garbage Collection 5Key Issues For both– Fast allocation– Fast reclamation– Low fragmentation (wasted space) For Garbage Collection– How to discriminate between live objects and garbage Basic approaches to garbage collection– reference counting– reachabilityCS553 Lecture Garbage Collection 6Reference Counting Idea– for each heap allocated object, maintain count of # of pointers to it– when creating object x, rc[x] = 0– when creating new reference to object x, rc[x]++– when removing reference to object x, rc[x]--– if ref count goes to zero, free object (i.e., place on free list) ExampleNode x, y;x = new Node (3, null);y = x;x = null;y = x; Complication– what if freed object contains pointers?xyNoderc =12 10null4CS553 Lecture Garbage Collection 7Reference Counting Analysis How it handles key issues– allocation is expensive because searching a freelist– reclamation is local and incremental– fragmentation is high Further analysis+ relatively simple+ very simple run-time system– cannot reclaim cyclic data structures (shifts burden to programmer)– high runtime overhead (must manipulate ref counts for every referenceupdate)– space cost– complicates compilationCS553 Lecture Garbage Collection 8Trace Collecting Observation– rather than explicitly keep track of the number of references to each objectwe can traverse all reachable objects and discard unreachable objects Details– start with a set of root pointers (program vars)– global pointers– pointers in stack and registers– traverse objects recursively from root set– visit reachable objects– unvisited objects are garbage– we might visit an object even if it's dynamically dead (ie, we are onlyconservatively approximating dead object discovery) When do we collect?– when the heap is full5CS553 Lecture Garbage Collection 9Mark-Sweep Collecting Simple trace collector– trace reachable objects marking reachable objects– sweep through all of heap– add unmarked objects to free list– clear marks of marked objects ExamplexyTTTTFFCS553 Lecture Garbage Collection 10Mark-Sweep Collecting Analysis How it handles the key issues– allocation is expensive because searching a freelist– reclamation can result in the “embarrassing pause” problem– poor memory locality when tracing– fragmentation is high Further analysis– collects cyclic structures– simple– must be able to dynamically identify pointers in vars and objects– more complex runtime system– space overhead is only one bit per data object6CS553 Lecture Garbage Collection 11Mark-Compact Collecting or Copy Collecting Idea– move objects to “new” heap while tracing Details– divide heap in half (prog. allocs. in from-space, to-space is empty)– when from-space is full...– copy non-garbage from from-space to to-space (to-space iscompact) when visiting object during tracing– copy from from-space to to-space– leave forwarding pointer in from-space version of object– if revisit this object, redirect pointer to to-space copyCS553 Lecture Garbage Collection 12Copying Garbage Collection‘from space’‘to space’ ‘from space’‘to space’‘to space’ ‘to space’‘from space’ ‘from space’‘to space’‘to space’ ‘to space’‘from space’7CS553 Lecture Garbage Collection 13Mark-Compact Collecting Analysis How it handles the key issues– allocation is very fast since there is no free list to search– reclamation can result in the “embarrassing pause” problem– poor memory locality when tracing– copying data from one heap to another– changing pointers because objects are being moved– no fragmentation Further Analysis+ collects cyclic structures– requires twice the (virtual) memory– breadth-first traversal means to-space objects could have poor localityCS553 Lecture Garbage Collection 14Hybrid Collectors Idea– different collection techniques may be combined Example: Mark-Sweep/Copy collector– big objects managed with mark-sweep (avoids copy time)– small objects managed with copy collector Analysis+ may be more efficient– more complex8CS553 Lecture Garbage Collection 15Generational Collecting Observation– "young" objects are most likely to die soon, while "old“ objects are morelikely to live on Idea– exploit this fact by concentrating collection on "young" objects Details– divide heap in generations (G0, G1, ...; G0 for youngest objects)– collect G0 most frequently, G1 less frequently, etc.– object is “tenured” from one gen. to next after surviving several GCs Result– usually only have