Advanced Compilers M. LamLecture 15Advanced Garbage CollectionI Break Up GC in Time (Incremental)II Break Up GC in Space (Partial)Readings: Ch. 7.6.4 - 7.7.4Advanced Compilers 2 L15: Advanced Garbage CollectionTrace-Based GC: Memory Life-CycleunreachedfreeMutator runsnewGCTracingunreachedfreescanned unscannedfound to bereachedobjects scannedfor new reachable objectsreachedGCDone tracingunreachedfreescannedRepeat untilunscanned = ∅unreachedAdvanced Compilers 3 L15: Advanced Garbage CollectionI. Incremental GC• Interleaves GC with mutator action to reduce pause timeIdeal = (R ∪ New) − Lost(R ∪ New) − Lost ⊆ Answer ⊆ (R ∪ New) kinds of data scannedunscannedunreachedafter the mutator newunreachableR (reachable)ideallostresumeshas runbefore mutator Advanced Compilers 4 L15: Advanced Garbage CollectionEffects of Mutation• Reachable set changes as mutator runs• R: set of reachable objects before the mutator runs• Ideal: set of reachable objects at the end of the GC cycle• New: set of newly created objects• Lost: set of objects that become unreachable in the interim• Ideal = (R ∪ New) − Lost• Ideal: Very expensive• Conservative Incremental GC:May misclassify some unreachable as reachable • should not include objects unreachable before GC starts • guarantees that garbage will be eliminated in the next roundIdeal = (R ∪ New) − Lost ⊆ Answer ⊆ (R ∪ New)Advanced Compilers 5 L15: Advanced Garbage CollectionAlgorithm Proposal 1• Initial condition • Scanned, Unscanned lists from before• To resume GC• Find root sets• Place newly reached objects in “unscanned list”• Continue to trace reachability without redoing “scanned” objects• Did we find all reachable objects? Advanced Compilers 6 L15: Advanced Garbage CollectionMissed Reachable Objects• All reaching pointers are found in “scanned objects”• Requires the occurrence of a 3-step sequence in the mutator: ScannedUnscanned / UnreachedUnreached0. after a stage of GCA B C1. Load p = ptr from B to C3. Store new pointer in B, 2. Store p in Aoverwriting value p pppAdvanced Compilers 7 L15: Advanced Garbage CollectionSolution• Intercept p in any of the three-step sequence• Treat pointee of p as “unscanned” ScannedUnscanned / UnreachedUnreached0. after a stage of GCA B C1. Load p = ptr from B to C3. Store new pointer in B, 2. Store p in Aoverwriting value p pppRead barrier: remember all loads of pointers from B → C Write barrier: remember all stores of pointers A → C Overwrite barrier: remember all overwrites of pointer B → C Advanced Compilers 8 L15: Advanced Garbage CollectionEfficiency of Different Barriers• Most efficient: Write barrier • less instances than read barrier• includes less unreachable objects than over-write barriersAdvanced Compilers 9 L15: Advanced Garbage CollectionII. Partial GC• Reduces pause time by collecting only objects in the target area:• Algorithm• New “root set” = original root set + pointers from Stable to Target set• Change program to intercept all writes to Stable set• Never misclassify reachable as unreachable• May misclassify unreachable as reachable Stable setTarget setignore used in tracingignore include in root setAdvanced Compilers 10 L15: Advanced Garbage CollectionGenerational GC• Observation: objects die young• 80-98% die within a few million instructions or before 1 MB has been allocated• Generational GC: collect newly allocated objects more often• ith generation• new root set = original root set + all pointers from generations j to i (j > i)• When 1st generation fills up, GC copies reachable objects into 2nd generation,and so on.targetstable1st 2nd 3rd 4thrememberedsetsAdvanced Compilers 11 L15: Advanced Garbage CollectionProperties• Never misclassify reachable as unreachable• Misclassify unreachable as reachable • when pointers in earlier generations are overwritten• eventually collect all garbage as generations get larger• Effective: time spent on objects that are mostly garbage• GC of mature objects takes longer• Size of target set increases • Eventually a full GC is performedAdvanced Compilers 12 L15: Advanced Garbage CollectionConclusions• Trace-based GC: find all reachable objects, complement to get unreachable• 4 states: free, unreached, unscanned, scanned• break up reachability analysis• in time (incremental)• in space (partial: