Ulterior Reference Counting Fast GC Without The WaitOutlineThroughput/Responsiveness Trade-offThe Ulterior approachPure Reference CountingSlide 6Slide 7Slide 8RC OptimizationsDeferred Reference Counting Goal: Ignore RCM(p) for stacks & registersClassic Deferral In deferral phase: Ignore RCM(p) for stacks & registersClassic Deferral Ignore RCM(p) for stacks & registersClassic Deferral (Bacon et al.)Slide 14Slide 15Slide 16Slide 17Ulterior Reference CountingBG-RC Bounded Nursery Generational - RCView of heap in Ulterior RCBringing it TogetherBG-RC Write BarrierBG-RC Mutation PhaseSlide 24Slide 25Slide 26Slide 27Slide 28Slide 29BG-RC Nursery Collection: Scan RootsSlide 31Slide 32BG-RC Nursery Collection: Process Object BufferBG-RC Nursery Collection: Reclaim NurseryBG-RC RC Collection: Process Decrement BufferBG-RC RC Collection: Recursive DecrementSlide 37BG-RC Collection Complete!Controlling Pause TimesExperimental evaluationThroughput/Pause time Moderate Heap SizeThroughput & ResponsivenessConclusionUlterior Reference CountingFast GC Without The WaitSteve Blackburn – Kathryn McKinleyPresented by: Dimitris PrountzosSlides adapted from presentation by Steve BlackburnOutline•Throughput-Responsiveness problem•Reference counting & optimizations•Ulterior in detail•BG-RC in action•Experimental evaluation•Conclusion•GC and mutator share CPU–Throughput: net GC/mutator ratio–Responsivness: length of GC pausesGCmutatorCPU Utilization (time)mutator poor responsivenessmaximum pauseThroughput/Responsiveness Trade-ofThe Ulterior approach•Match mechanisms to object demographics–Copying nursery (young space)•Highly mutated, high mortality young objects•Ignores most mutations•GC time proportional to survivors, space efficient–RC mature space•Low mutation, low mortality old objects•GC time proportional to mutations, space efficient•Generalize deferred RC to heap objects–Defer fields of highly mutated objects & enumerate them quickly–Reference count only infrequently mutated fieldsPure Reference Counting•Tracks mutations: RCM(p)RCM(p) generates a decrement and an increment for the before and after values of p:RCM(p) RC(pbefore)--, RC(pafter)++•If RC==0, FreeRC spaceb1a1Pure Reference Counting•Tracks mutations: RCM(p)RCM(p) generates a decrement and an increment for the before and after values of p:RCM(p) RC(pbefore)--, RC(pafter)++•If RC==0, FreeRC spaceb0a1c1Pure Reference Counting•Tracks mutations: RCM(p)RCM(p) generates a decrement and an increment for the before and after values of p:RCM(p) RC(pbefore)--, RC(pafter)++•If RC==0, FreeRC spaceb0a1c1Pure Reference Counting•Tracks mutations: RCM(p)RCM(p) generates a decrement and an increment for the before and after values of p:RCM(p) RC(pbefore)--, RC(pafter)++•If RC==0, FreeRC spacea1c1RCM(p) for every mutation is very expensiveRC Optimizations•Buffering: apply RC(p)--, RC(p)++ later•Coalescing: apply RCM(p) only for the initial and final values of p (coalesce intermediate values):{RCM(p), RCM(p1), ... RCM(pn)} RC(pinitial)--, RC(pfinal)++•Deferral of RCM eventsDeferred Reference CountingGoal: Ignore RCM(p) for stacks & registers•Deferral of p–A mutation of p does not generate an RCM(p)–Correctness: •For all deferred p: RCR(p) at each GC•Retain Event: RCR(p)–po temporarily retains o regardless of RC(o)•Deutsch/Bobrow use a Zero Count Table•Bacon et al. use a temporary incrementClassic DeferralIn deferral phase: Ignore RCM(p) for stacks & registersRC spaceb1a0Stacks & RegsClassic DeferralIgnore RCM(p) for stacks & registersRC spaceb0a0c1Stacks & RegsBreaks RC==0 InvariantClassic Deferral (Bacon et al.)•Divide execution in epochs•Store information in bufers•Root bufer (RB): Store 1st level objects •Increment bufer (IB): Store increments to 1st level objects•Decrement bufer (DB): Store decrements to 1st level objects•At GC time do:–Look at RB and apply temporary increments to all objects there–Process IB of this epoch–Look at RB of previous epoch and apply decrements to all objects there–Process DB of previous epoch•During DB processing recycle o if RC(o)=0•Avoid race conditions by•Processing IB before DB•Processing DB of one epoch behindClassic Deferral (Bacon et al.)RC spaceb1a1c1Stacks & Regs root bufdec bufbaAt GC time, RCR(p)for root pointersapplies temporaryincrements.RC spaceb1a1c1Stacks & Regs root bufdec bufbaAt next GC,apply decrementsClassic Deferral (Bacon et al.)RC spaceb1a1c1Stacks & Regs root bufdec bufbaAt next GC,apply decrementsClassic Deferral (Bacon et al.)Key: Efficient enumeration of deferred pointersRC spaceb1a1c1Stacks & Regs root bufdec bufClassic Deferral (Bacon et al.)Better, but not good enough!Ulterior Reference Counting•Idea: Extend deferral to select heap pointers–e.g. All pointers within nursery objects•Deferral is not a fixed property of p–e.g. A nursery object gets promotedIntegrate Event I(p)–Changes p from deferred to not deferredBG-RCBounded Nursery Generational - RC•Heap organization–Bounded copying nursery•Ignore mutations to nursery pointer fields–RC old space•Object remembering, coalescing, bufering•Collection–Process roots–Nursery phase promotes live p to old space and I(p)–RC phase processes object bufer, dec buferView of heap in Ulterior RCStacks RegsRC spacenon-RC spaced1a1b1e1str•How can we efficiently•Enumerate all deferred pointer fields ?•Remember old to young pointers ?rememberdeferdeferBringing it Together•Deferral:–Defer nursery & roots–Perform I(p) on nursery promotion•Piggyback on copying nursery collection•Coalescing:–Remember mutated RC objects•Upon first mutation, dec each referent•At GC time, inc each referent•Piggyback remset onto this mechanismBG-RC Write Barrier10 private void writeBarrierSlow(VM_Address srcObj)11 throws VM_PragmaNoInline {12 if (attemptToLog(srcObj)) {13 modifiedBuffer.push(srcObj);14 enumeratePointersToDecBuffer(srcObj); // trade-off for sparsely15 setLogState(srcObj, LOGGED); // modified objects16 }17 }1 private void writeBarrier(VM_Address srcObj,2 VM_Address srcSlot,3 VM_Address tgtObj)4 throws VM_PragmaInline { 5 if (getLogState(srcObj) != LOGGED) 6 writeBarrierSlow(srcObj);7 VM_Magic.setMemoryAddress(srcSlot, tgtObj);8 }9 }// unsync check for uniquenessBG-RCMutation PhaseStacks Regs root bufRC spaceobj buf dec bufnon-RC
View Full Document
Unlocking...