Comparison of Compacting Algorithms for Garbage CollectionAlgorithms for Garbage CollectionBy Jacques Cohen & Alexandru NicolauPresented by Sam HarwellMark/Sweep/Compact Collection• Garbage collection is performed in two stages– Identify objects in memory that are live (mark)– Make dead-object memory locations available to the allocator by compacting live objectsthe allocator by compacting live objects• We are focusing on the compaction algorithmAllocator Fundamentals• Memory is allocated for cells:– Variable sized– Each may hold pointers and/or datareservedsize cnpcPointersDatasize cnpcIncoming pointers may only point to the first element in the cellAlgorithms• Classical– Lisp 2• D.E. Knuth, 1973–Table Compactor–Table Compactor• Modified algorithm based on Waite and Haddon, 1967• Modern (at the time)– Morris’ algorithm, 1978– Jonkers’ algorithm, 1979Lisp 2• Requires additional space in each cell for a pointer• Three passes:–Compute new address of each active cell–Compute new address of each active cell– Update pointer fields of each active cell– Relocate active cellsLisp 2 CompactorTable Compactor• Stores relocation data in garbage cells• Fundamental: cells are moved forward by the total size of holes preceding the cell•Pointers are updated similarly•Pointers are updated similarlyHolesThreading• An elegant way to answer, “Where are all the pointers to cell X?”– Threading the root:XYZroot node AXYZroot node AThreading• An elegant way to answer, “Where are all the pointers to cell X?”XYZroot node Anode Bnode BXYZroot node Anode BMorris’ Algorithm• Three-passes: one forward and two backward• Two tag bits per field overhead (one if single cells cannot hold both pointers and data)Morris’ AlgorithmJonkers’ Algorithm• Improved on Morris’:– Only two passes, both forward– One bit per cell overhead•Added assumptions:•Added assumptions:– No pointer-to-members– A cell containing data is always large enough to store a pointerJonkers’ AlgorithmTime-Formulas• Create optimized versions of each algorithm• Describe each procedure with a formula from the type and number of operations performed•Replace unknowns in the formula with •Replace unknowns in the formula with machine-specific constants, leaving the following variables:– α: Marked cell ratio (NMC/NC)– β: Live pointer ratio (NAP-1)/(NPC*NMC)Feature ComparisonLisp 2 Table compact Morris’ Jonkers’Age Classical (1973) Classical (1967) Modern (1978) Modern (1979)Space 1 pointer/cell None 2 bits/field 1 bit/cellPasses 3 3 3 2Member ptr No No Yes NoPerformance ResultsEffects of Increased Sorting in the Table CompactorEffects of Cell
View Full Document
Unlocking...