advertisement

mostly oopsla03

40 %
60 %
advertisement
Information about mostly oopsla03
News-Reports

Published on September 19, 2007

Author: Haggrid

Source: authorstream.com

advertisement

Mostly Concurrent Garbage Collection Revisited:  Mostly Concurrent Garbage Collection Revisited Katherine Barabash - IBM Haifa Research Lab. Israel Yoav Ossia - IBM Haifa Research Lab. Israel Erez Petrank - Technion. Israel Outline:  Outline The mostly concurrent garbage collection (GC) Internals of the collector Write barrier and card table Incremental collection Our two improvements And their implications on performance Results Conclusions Mark Sweep Stop-The-World (STW) Garbage Collection:  Mark Sweep Stop-The-World (STW) Garbage Collection The basic method Mark all objects that are reachable from roots Sweep - reclaim all unmarked objects Done when Java mutation is suspended (STW) Pause time - the length of the STW phase Motivation for the mostly concurrent GC Reduce the pause time at acceptable throughput hit Mostly Concurrent GC - The Basic Method:  Mostly Concurrent GC - The Basic Method Perform marking concurrently with Java mutation Traditionally done by a separate thread While concurrent marking is active, record changes in objects Otherwise… When marking terminates do a short STW phase Re-trace from Roots Marked objects that were not traced yet Marked and changed objects Sweep Mostly Concurrent GC - Perspective:  Mostly Concurrent GC - Perspective Related Work Steele and Dijkstra et al - Concurrent GC. 1976 Baker - Incremental collection. 1977 Boehm at al - Mostly concurrent collection. 1991 Printezis and Detlefs - Mostly concurrent and generational GC. 2000 Many others… Ossia at al - Parallel, incremental and concurrent GC. 2002 Status Collector well accepted both in academic research and industry Used in many production JVMs: IBM, Sun, BEA JRockit Outline:  Outline The mostly concurrent garbage collection (GC) Internals of the collector Write Barrier and card table Incremental collection Our two improvements And their implications on performance Results Conclusions The Write Barrier and Object “cleaning” interaction:  The Write Barrier and Object 'cleaning' interaction Tracer: Marks and traces Java Mutator: Modifies Blue and Green objects Write barrier on objects Tracer: Traces rest of graph Tracer: Clean blue object Mostly Concurrent GC – Card Cleaning:  Mostly Concurrent GC – Card Cleaning Heap is logically divided into cards A card table is used, with a byte entry per each heap card A card-marking write barrier Whenever a reference field is modified, dirty the card table entry of the modified object Card cleaning Clean dirty mark Retrace all marked objects on card Card cleaning can be done concurrently While this is done, more cards will be dirtied Additional STW card cleaning phase must be done Incremental Mostly Concurrent GC:  Incremental Mostly Concurrent GC Marking done by the Java mutator threads When allocating Tracing Rate (TR) - configurable by user The ratio between requested allocation size and required tracing work Per every allocation request of K bytes, trace K* TR bytes of objects Allocation rate of application andamp; tracing rate of collector imply CPU percentage dedicated to the concurrent collection Starting the concurrent collector Must be done on time, to complete tracing when the heap is exhausted Concurrent Behavior Patterns :  Concurrent Behavior Patterns Higher tracing rate implies shorter concurrent cycle with smaller CPU share for Java Numbers below refer to SPECjbb STW GC 100% CPU for Java mutation Mostly Concurrent Tracing Rate 8 28% CPU for Java mutation Mostly Concurrent Tracing Rate 1 72% CPU for Java mutation CPU Utilization Time Java mutation Incremental Tracing Parallel STW Mostly concurrent GC – Summary of the Base Algorithm:  Mostly concurrent GC – Summary of the Base Algorithm Fast card marking write barrier always active (JITed) Kickoff concurrent tracing when free space reached kickoff point Reset the card table Trace (incrementally) all objects reachable from roots Do a single concurrent card cleaning pass on the card table Initiate final (short) STW phase Trace again the roots for new objects Do another card cleaning pass Trace all newly marked objects Sweep Outline:  Outline The mostly concurrent garbage collection (GC) Internals of the collector Write Barrier and card table Incremental collection Our two improvements And their implications on performance Results Conclusions The Repetitive Work Problem:  The Repetitive Work Problem Observations Suppose a card is dirtied while concurrent marking is executing Newly reached objects in this card are marked and traced by the collector All these objects will later be traced again in the card cleaning phase Outcome: repeated tracing Improvement: Don’t trace through dirty cards Don’t Trace Through Dirty Cards:  Don’t Trace Through Dirty Cards If an object resides in a dirty card, omit its tracing Only a single tracing will be done, in the concurrent card cleaning phase Advantages Less marking work Reduced floating garbage More later… Reduced cache miss rate More later… Thus, substantial throughput improvements Disadvantage Increased pause time Timing of Card Dirtying:  Timing of Card Dirtying Observations Card (and object) dirtying indicates that previous tracing may have been insufficient New objects may be reachable only from the dirtied object Dirtying information is needed only if tracing was already done Prior to tracing, card dirtying is irrelevant Improvement: Undirdy cards with no traced objects Undirtying via scanning Undirtying via local allocation caches Undirtying via Scanning:  Undirtying via Scanning Undirtying can be done periodically on the whole card table An indication of 'traced' cards is needed Mark bit vector A 'traced' card table (first traced object marks the card as traced) Method: scan the card table and undirty all cards with no traced objects Very effective in undirtying cards (cuts cleaning by 65%) Some extra cost of card table scan Should be done frequently Catch these cards before any marking or tracing occurs! Undirtying via Local Allocation Caches:  Undirtying via Local Allocation Caches Local allocation caches are used by most modern JVMs Most cards of active caches are dirty Objects usually have write barriers while (and shortly after) initializing Objects in active cache are (usually) not traced before the cache is replaced If no tracing in the active cache is guarantied, we can undirty its cards Method: cooperation between allocators and concurrent tracers Allocator (when replacing a local cache): Undirty all the cache’s inner cards Mark all cards as 'traceable' Take a new cache and mark all its cards as 'untraceable' Concurrent tracer Defer tracing of objects in 'untraceable' cards 'for a while' BTW, this hardly ever happens Cuts the amount of dirty cards by more than 35%, at no cost Undirdy Cards with No Traced Objects:  Undirdy Cards with No Traced Objects Advantages Without 'Don’t trace through dirty cards' – less work With it, reduces the STW card cleaning significantly Characteristics of Dirty Cards:  Characteristics of Dirty Cards We believe that a recently dirtied card is good indication for more modification of objects in the near future Change of references Other writing activities Indication applied to all the objects in the card A recently dirtied card is probably hot and active But we don’t trace through dirty cards! By the time we get to clean them they will probably become more stable and colder Reduced Floating Garbage:  Reduced Floating Garbage Floating garbage is created when tracing is done before the object modification Don’t trace through dirty cards! Will probably defer the tracing until the card gets stable Objects are no longer modified No floating garbage will be created as a result of this late tracing Reduced Cache Miss Rate:  Reduced Cache Miss Rate Reducing the tracing work affects the cache miss rate As tracing the object graph intensifies cache capacity misses But also cache coherency misses are reduced A write barriered card (hot and active) is probably modified by Java mutators If a concurrent tracer scans objects on such card, it will suffer coherency misses Don’t trace through dirty cards! Deferring the tracing of these objects to the card cleaning phase reduces cache coherency misses Our improved collector reduces L2 cache miss rate by 6.4% Out of which 3.7% is reduction in cache coherency misses Outline:  Outline The mostly concurrent garbage collection (GC) Internals of the collector Write Barrier and card table Incremental collection Our two improvements And their implications on performance Results Conclusions Implementation and Tests:  Implementation and Tests Implementation On top of the mostly concurrent collector that is part of the IBM production JVM 1.4.0. Platforms Tested on both an IBM 6-way pSeries server and an IBM 4-way Netfinity server Benchmarks The SPECjbb2000 benchmark and the SPECjvm98 benchmark suite Measurements Performance of the base collector Vs. the improved version The effect of each improvement separately, and more… Results - Throughput Improvement:  Results - Throughput Improvement SPECjbb. 6-way PPC. Heap size 448 MB 26.7% improvement (in tracing rate 1) Results - Floating Garbage Reduction:  Results - Floating Garbage Reduction SPECjbb. 6-way PPC. Heap size 448 MB 13.4% improvement in heap residency (in tracing rate 1) Almost all floating garbage eliminated Results - Pause Time Reduction:  Results - Pause Time Reduction SPECjbb. 6-way PPC. Heap size 448 MB 33.3% improvement in average pause 36.4% improvement in max pause Conclusions:  Conclusions Introducing two improvements to the mostly concurrent GC Reduces repetitive GC work (don’t trace through dirty cards) Reduces number of dirty cards (undirty cards with no traced objects) Substantial improvement of the mostly concurrent GC Improved throughput by 26% Almost eliminated floating garbage (heap residency reduced by 13%) Reduced average pause time by 33% Additional effects of not tracing into dirty cards Reduced floating garbage Reduced cache miss rate The improved algorithm has been incorporated into IBM's production JVM Slide28:  End Analyzing the Performance of Lower Tracing Rate:  Analyzing the Performance of Lower Tracing Rate Throughput hit rate Relative to MS STW GC Java utilization Relative to MS STW GC Live Rate Relative to heap size Floating Garbage Marked objects that become unreachable before the STW phase More objects to trace. Less free space (more GCs) Card cleaning rate Relative to total number of cards More work. Longer final STW phase Results - Throughput Improvement:  Results - Throughput Improvement SPECjbb. 6-way PPC. Heap size 448 MB 26.7% improvement in tracing rate 1 Results - Floating Garbage Reduction:  Results - Floating Garbage Reduction SPECjbb. 6-way PPC. Heap size 448 MB 13.4% improvement in tracing rate 1 Results - Average Pause Time:  Results - Average Pause Time SPECjbb. 6-way PPC. Heap size 448 MB Throughput Improvement for All Tracing Rates:  Throughput Improvement for All Tracing Rates Heap Residency Reduction for All Tracing Rates:  Heap Residency Reduction for All Tracing Rates Slide35:  Reduced floating garbage:  Reduced floating garbage Potential Floating garbage root – reachable object that de-reference its sub-graph and thus make it unreachable To become a floating garbage root, it must first be traced and then have a write barrier We believe that a freshly dirty card is good indication for more write barriers Deferring the tracing into a dirty card will defer the tracing to after the write barriers

Add a comment

Related presentations

Related pages

Mostly Concurrent Garbage Collection Revisited

Mostly Concurrent Garbage Collection Revisited Katherine Barabash Yoav Ossiay Erez Petrankz ABSTRACT The mostly concurrent garbage collection was presented in
Read more

Erez Petrank -- Publications - Computer Science Department ...

Erez Petrank, Madanlal Musuvathi, and Bjarne Steensgaard. ... Yoav Ossia, and Erez Petrank. Mostly Concurrent Garbage Collection Revisited.
Read more

Relaxed MultiJava: Balancing Extensibility and Modular ...

a virtually unrestricted form while still providing mostly-modular static typechecking and fully-modular compilation. In some cases,
Read more

How Java Programs Interact with Virtual Machines at the ...

benchmark suite, mostly SPECjvm98. In addition, some studies use a small input set, e.g., s1 for SPECjvm98, to limit the simulation time in their study.
Read more

xp123.com

Reflection in Action: A Pattern Language Bill Wake, 8-31-03 See http://www.xp123.com/oopsla03 Goals of retrospectives Safe environment Appreciate successes
Read more

"Relaxed MultiJava: Balancing Extensibility and Modular ...

... RMJ supports the new language features in a virtually unrestricted form while still providing mostly-modular static typechecking and fully-modular ...
Read more

Tick - Concurrent GC in Apache Harmony

Tick: Concurrent GC in Apache Harmony Xiao-Feng Li 2009-4-12 Acknowledgement: ... et al. OOPSLA03) ... MOSTLY_CON vs. SATB Care new values in execution Con
Read more

Richard Jones' Garbage Collection Bibliography

the Garbage Collection Bibliography ... Mostly parallel garbage collection. In PLDI 1991 , 1991, pages 157-164. Available here.
Read more

Richard Jones' Garbage Collection Bibliography

William Gerald O'Farrell. Garbage Collection Algorithms for the Connection Machine. PhD thesis, Syracuse University, 1991.
Read more

From text to touch - Alarming Development | Dispatches ...

I saw some interesting work on touch programming languages at Onward. You may already have seen Codify. That is still a mostly textual language, as the ...
Read more