Slide 1Garbage Collection – A ReviewLooking For Garbage In The Right PlaceWish ListBaker (Copying) ReviewBaker Review (2)Some Insights Towards A SolutionSome Insights Towards A Solution (graphic)Murphy’s Law: Forever With UsTracking Forward PointersOne, Two, ManyCondemnationConcurrent CondemnationsClarificationsDetails AboundReferences/Resources/AcknowledgementsSome interesting notes, Possible DiscussionDiscussionTerminology Review (From Baker to here)GENERATIONAL GARBAGE COLLECTIONA Real-Time Garbage Collector Based on the Lifetimes of ObjectsLieberman and Hewitt, CACM June 1983, pp 419-429Curtis DunhamCS 395T Memory Management, Spring 2011GARBAGE COLLECTION – A REVIEWPurpose:Obtain Memory by Reclaiming GarbageEffort expended with no garbage found is wastedTechniques covered so far are for whole heapCopying: O(live objects)Mark-Sweep: Mark also O(live objects), Sweep is O(allocated memory)Pesky non-garbage data continuously copied, marked/swept-over, or marked/compacted, etc.2LOOKING FOR GARBAGE IN THE RIGHT PLACEMost garbage comes from recently allocatedor “young” objectsProgramming intuition backed up by empirical dataExample: map-filter-reduce paradigm in LispVisual: pdf/cdf cartoons3WISH LISTGoal: efficiency in the face of “infant mortality”Pay-as-you-go: cheaper storage for short-lived objects than for long-lived objectsGoal: reclaim young, dead objects with minimal effort; i.e. without examining the whole heapStay away from O(heap size), O(heap objects) complexitiesShorter GC pause times!4BAKER (COPYING) REVIEW5New objectsEvacuated objectsTracedTospaceFromspaceUntraced“Scavenging”BAKER REVIEW (2)Semi-space is wasteful of spaceCopies whole heapAll objects treated the same,regardless of longevityBut it’s not all thorns…LocalityCompaction6SOME INSIGHTS TOWARDS A SOLUTIONNo Time Travel: Impossible to point to a newer object than oneself at object creationi.e. all pointers initially point “backwards in time”,or are nullA pointer must be updated to point “forward in time”, from older to newer.7SOME INSIGHTS TOWARDS A SOLUTION (GRAPHIC)8YoungstersFogiesRootsImagine no forward pointersWe only have to trace this space!Ignore the pointers to fogies.We allocated in here for awhile,until it filled up.Then we started allocating over here.RegionsMURPHY’S LAW: FOREVER WITH USPointers can be updatedPointers will be updatedPointers will inevitably point forward in time,across the region boundarySolution:Track these troublesome forward pointersWe expect (hope for) them to be rareGreat things become possible (pruned heap traces)9TRACKING FORWARD POINTERS10YoungstersFogiesRootsEntry tableHonorary roots(for this region)We still only have to trace this space!Still ignoring the pointers to fogies, too.ONE, TWO, MANY11YoungestOldestRootsOlderOldYoungerYoungAllows an arbitrary number of regions called “generations”CONDEMNATION12g0.v0 g1.v0 g2.v0 g3.v0 g4.v0 g5.v0g5.v1Like Bakers algorithm (Copying),space is reclaimed through evacuationGC is initiated by condemning a regionRegion keeps same generation number,but increments its version numbercondemn v.4. to judge or pronounce to be unfit for use or service: to condemn an old building.5. U.S. Law. to acquire ownership of for a public purpose, under the right of eminent domain: The city condemned the property.memory regionGCregionVMCONCURRENT CONDEMNATIONS13g0.v1 g1.v1 g2.v2 g3.v2 g4.v3 g5.v4g5.v5g4.v3CLARIFICATIONSThe heap structure is only time-based by practicality-driven convention; the real invariants revolve around pointer directionsCan put new objects anywhereGives system and user optimization opportunitiesRegion/Generation coalescing is possible14DETAILS ABOUNDGC of Entry tablesRecord generation/version of source pointerOrthogonality of forward pointers and intra-region collectionCollecting younger regions more oftenWeak pointersStore in Entry table with Forward pointersScavenging stacks, globals15REFERENCES/RESOURCES/ACKNOWLEDGEMENTS(other than this paper, cited on title slide)Richard Jones and Rafael Lins. Garbage Collection: Algorithms for Automatic Dynamic Memory Management. (Chapter 7) 1996.Previous slides by Rudy Depena (2009), Maria Jump (2003)Dictionary.comNUnabridgedNBasedNonNtheNRandomNHouseNDictionary,N2011.16SOME INTERESTING NOTES, POSSIBLE DISCUSSIONLanguages like Haskell also adopted another mitigating technique called deforestationOriginally called Listlessness by Wadler (1984)Escape analysis, a type of static extent analysisHas roots in call-graph reclamation schemes (Hudak 1981), closure allocation strategies (ORBIT paper, Kranz et al 1986)Even if we can’t prove that a new object will die quickly, it probably will anyway – and for that, we have generational GC!17DISCUSSIONEmpirical analysis??We think it should work…“… future research plans include … [testing] the behavior of real programs”“Judging [GC] algorithms is tricky”“… we expect good performance…”Heap reorganization“Pointer length”Region size – parallels with ImmixRelationship with incremental designs18TERMINOLOGY REVIEW (FROM BAKER TO HERE)Tracing → ScavengingSemi-spaces (fromspace, tospace) → Regions corresponding to generationsFlip (fromspace ↔ tospace) → Condemning a regionFromspace → Condemned
View Full Document
Unlocking...