Age-Based Garbage CollectionOutlineScavengingYoungest-Only (YO)Runtime OverheadsRuntime Overheads: Early Tenuring (Promotion)Why Generational Collection Works WellOlder-First Garbage CollectionSlide 9The Sweet SpotDesign DecisionsWrite Barrier: Pointer Filtering for Older-FirstTrace Based MeasurementsTotal Cost JavaBYTEmarkTotal Cost Richards (Smalltalk)Total Cost Bloat-BloatContributionsCitation StatisticsResourcesYoungest Only GCGenerational GC with 2 GenerationsAge-Based Garbage CollectionDarko Stefanović, Kathryn McKinley, J. Eliot B. MossOOPSLA ‘99CS395T: Hadi EsmaeilzadehFebruary 2009OutlineScavengingGenerational Copying Collection (YO)Runtime OverheadsOlder-First (OF)Write Barrier and Heap OrganizationContributionsStatisticsScavengingU={regions not collected}; assumed liveC={regions collected}S={Survivors}G={Garbage}; copied/compactedWork proportional to |S|CopyingPointer-trackingWhat is the ideal case?What is the best heuristic?Youngest-Only (YO)Intuition: Mortality rate is higher among young objects :((! Let C={Young objects}Objective: Minimize |S|Fewer survivorsCopy lessTrack lessQuickTime™ and a decompressorare needed to see this picture.Runtime OverheadsCopying the survivorsTracking the pointers crossing the boundariesIn this case, only old-to-young pointersWrite barrier (interleaving pointer-tracking with program execution)Cache: The place program and GC collide!Where is the trade-off?QuickTime™ and a decompressorare needed to see this picture.Runtime Overheads: Early Tenuring (Promotion)Newly objects are promoted… What a shame! They die!Waste of time, space, …What else?QuickTime™ and a decompressorare needed to see this picture.Why Generational CollectionWorks WellYoung objects die more quickly than old objects “generational hypothesis” [Unger’84,Hayes’91]Most pointers are from younger to older objects [Appel’89, Zorn’90]Do they apply to object oriented programs?Kathryn’sOlder-First Garbage CollectionMany objects die when they are middle age!Give the poor young objects a chance to live!Older-First Garbage CollectionOldestYoungestHeap windowCollection 1Collection 2Collection 3 survivorswindowwindow survivors survivorsKathryn’sThe Sweet SpotDesign DecisionsSliding window determines C (Collection region)What is the design decision?What is the trade-off?Other alternatives?Window hits the allocation pointCollect/compact objectsReset the window to the oldest objectsWhat is the design decision?What is the trade-off?Other alternatives?Degree of freedom or added complexity?Who can help?Write Barrier: Pointer Filtering for Older-FirstRuntime pointer direction filteringDo not record Pointers within the same blockPointers with source collected before targetHow can architecture help?allocationoldest youngestnext collectionstored pointer, no storeKathryn’sTrace Based MeasurementsFully accurate tracesAll pointers between objectsPrecise object life times (collect after every allocation)Measured costsCopying Write barrierRemembered set processingUnmeasured effectsCache / locality interactionsStartupWhat is the net speedup?Kathryn’sTotal Cost JavaBYTEmark00.511.522.5200,000 260000 330000 390000Heap size (words)Total cost (cycles x 10^7)Older-First 2 GenerationalKathryn’sTotal Cost Richards (Smalltalk)01234562,5002500 3000 3500 5200 6200 7800 9300Heap size (words)Total cost (cycles x 10^7)Older-first 2 GenerationalTotal Cost Bloat-Bloat00.511.522.5325000030000039000045000056000066000082000010000001300000Heap size (words)Total cost (cycles x 10^8)Older-first 2 GenerationalKathryn’sContributionsMore accurate explanations of generational collection (My favorite :))!Significant reduction in copying cost, by trading off pointer maintenance costsNew write barrier mechanismsNew promising algorithmKathryn’sCitation StatisticsACM portal: 28Google scholar: 61Narendran Sachindran , J. Eliot , B. Moss, Mark-copy: fast copying GC with less space overhead, ACM SIGPLAN Notices, v.38 n.11, November 2003Feng Xian , Witawas Srisa-an , Hong Jiang, Allocation-phase aware thread scheduling policies to improve garbage collection performance, Proceedings of the 6th international symposium on Memory management, October 21-22, 2007, Montreal, Quebec, CanadaSebastien Marion , Richard Jones , Chris Ryder, Decrypting the Java gene pool, Proceedings of the 6th international symposium on Memory management, October 21-22, 2007, Montreal, Quebec, CanadaWilliam D. Clinger , Fabio V. Rojas, Linear combinations of radioactive decay models for generational garbage collection, Science of Computer Programming, v.62 n.2, p.184-203, 1 October 2006Feng Xian , Witawas Srisa-an , Hong Jiang, Garbage collection: Java application servers' Achilles heel, Science of Computer Programming, v.70 n.2-3, p.89-110, February, 2008ResourcesBen Wiedermann’s presentation in 2003 classImproving Memory Performance for Java, Kathryn McKinley, CRA-W Distinguished Lecture, ECE CMU, 2000, http://amp.ece.cmu.edu/eceseminar/2000/Fall/Abstract/F00_McKinley.htmYoungest Only GCOldestYoungestHeap windowCollection 1Collection 2 survivors survivorswindowuncollecteduncollectedGenerational GC with 2 GenerationsOldestYoungestHeap windowCollection 1Collection 2 survivors survivorswindowreserveuncollectednurseryfreed fromreservefreed fromreserveuncollectedCollection
View Full Document
Unlocking...