mostly oopsla03

Information about mostly oopsla03

Published on September 19, 2007

Author: Haggrid

Source: authorstream.com

Content

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

Related presentations


Other presentations created by Haggrid

makyaj
18. 06. 2007
0 views

makyaj

2407224601
22. 04. 2008
0 views

2407224601

0616PVR76491
17. 04. 2008
0 views

0616PVR76491

DART Slideshow
17. 04. 2008
0 views

DART Slideshow

AdvFin 2008 01 Introduction
10. 04. 2008
0 views

AdvFin 2008 01 Introduction

dept revenue presentation
09. 04. 2008
0 views

dept revenue presentation

het607 m06a01
07. 04. 2008
0 views

het607 m06a01

20061116 intl ops
30. 03. 2008
0 views

20061116 intl ops

2004 AMCHAM Doorknock
27. 03. 2008
0 views

2004 AMCHAM Doorknock

pdhpe moderate
18. 06. 2007
0 views

pdhpe moderate

Where the Red Fern Grows
03. 10. 2007
0 views

Where the Red Fern Grows

tutorial 1
19. 09. 2007
0 views

tutorial 1

Future Law Enforcement ppt
19. 09. 2007
0 views

Future Law Enforcement ppt

231B 2006 Suetterlin Lec1
12. 10. 2007
0 views

231B 2006 Suetterlin Lec1

Crocodile
12. 10. 2007
0 views

Crocodile

VLSI Symp 2 10 2007
09. 10. 2007
0 views

VLSI Symp 2 10 2007

2003 08 27 Schelle Wolff Carola
24. 10. 2007
0 views

2003 08 27 Schelle Wolff Carola

875 PERL 06 mini
02. 11. 2007
0 views

875 PERL 06 mini

Where the Sidewalk Ends
26. 10. 2007
0 views

Where the Sidewalk Ends

CNV
22. 10. 2007
0 views

CNV

pfit
07. 11. 2007
0 views

pfit

scholz
16. 11. 2007
0 views

scholz

DDR Frog Licking
17. 11. 2007
0 views

DDR Frog Licking

The Suffering of Jesus
17. 08. 2007
0 views

The Suffering of Jesus

lecture5
28. 11. 2007
0 views

lecture5

ontology
11. 12. 2007
0 views

ontology

predationmurray
01. 01. 2008
0 views

predationmurray

academy mission vision
03. 01. 2008
0 views

academy mission vision

Maldives presentation
07. 08. 2007
0 views

Maldives presentation

mood disorders
07. 08. 2007
0 views

mood disorders

Loh Verma Michalowski CPS04
07. 08. 2007
0 views

Loh Verma Michalowski CPS04

Karen Middleton
07. 08. 2007
0 views

Karen Middleton

Linkage ordinal data hm
07. 08. 2007
0 views

Linkage ordinal data hm

modern Day Slavery
07. 08. 2007
0 views

modern Day Slavery

MOA Presentation Mandsager final
07. 08. 2007
0 views

MOA Presentation Mandsager final

oct15 insurance reinsurance RGA
07. 08. 2007
0 views

oct15 insurance reinsurance RGA

maldives khaleel
07. 08. 2007
0 views

maldives khaleel

peters HTC BlueGene CondorWeek
19. 09. 2007
0 views

peters HTC BlueGene CondorWeek

2005 Loftus Introduced Fish
19. 11. 2007
0 views

2005 Loftus Introduced Fish

UNTITLED
07. 08. 2007
0 views

UNTITLED

knoblock
23. 10. 2007
0 views

knoblock

India US Dual Use Goldman
17. 08. 2007
0 views

India US Dual Use Goldman

RedSquare Bike Ride Eng
27. 09. 2007
0 views

RedSquare Bike Ride Eng

Financing EFA Maldives
07. 08. 2007
0 views

Financing EFA Maldives

Languages Models Factories
14. 11. 2007
0 views

Languages Models Factories

Ge11cDIfferentiation
20. 02. 2008
0 views

Ge11cDIfferentiation

1950s
24. 02. 2008
0 views

1950s

Dual Language Posterboard 2
24. 02. 2008
0 views

Dual Language Posterboard 2

200792013611855
10. 10. 2007
0 views

200792013611855

as2007 aviation careers brief
28. 02. 2008
0 views

as2007 aviation careers brief

BiodieselFuelQuality pt1
29. 02. 2008
0 views

BiodieselFuelQuality pt1

2005 Inflammation
04. 03. 2008
0 views

2005 Inflammation

MI 2006 final 11 9
07. 08. 2007
0 views

MI 2006 final 11 9

figuerola lucifer
15. 10. 2007
0 views

figuerola lucifer

TOXICVB
05. 01. 2008
0 views

TOXICVB

GENIe ISA
10. 03. 2008
0 views

GENIe ISA

Pretty Blue Planet
19. 09. 2007
0 views

Pretty Blue Planet

AM1 DTV China EN
11. 10. 2007
0 views

AM1 DTV China EN

2007RoyalEurope consumer
01. 11. 2007
0 views

2007RoyalEurope consumer

YTBv4
12. 03. 2008
0 views

YTBv4

SevenBrochure
26. 03. 2008
0 views

SevenBrochure

babar
15. 10. 2007
0 views

babar

memphis
23. 10. 2007
0 views

memphis

NASBE Asthma Policies
07. 08. 2007
0 views

NASBE Asthma Policies

Apache Harmony Short Talk
19. 09. 2007
0 views

Apache Harmony Short Talk

DSF
07. 01. 2008
0 views

DSF

Module 10 C Older Adults
07. 08. 2007
0 views

Module 10 C Older Adults

CEC 999 2006 018
11. 10. 2007
0 views

CEC 999 2006 018

NNER MAGAZIN neu
18. 06. 2007
0 views

NNER MAGAZIN neu

kids slide show
18. 06. 2007
0 views

kids slide show

Inco Present1
18. 06. 2007
0 views

Inco Present1

nifty fifty thrifty 2
18. 06. 2007
0 views

nifty fifty thrifty 2

Navigator
18. 06. 2007
0 views

Navigator

mudancas internas2 lila
18. 06. 2007
0 views

mudancas internas2 lila

MMC Selection271006
18. 06. 2007
0 views

MMC Selection271006

MD Rhythm Software
18. 06. 2007
0 views

MD Rhythm Software

Experian
19. 09. 2007
0 views

Experian

urb1
27. 11. 2007
0 views

urb1

presentation reunion cnds clubs
18. 06. 2007
0 views

presentation reunion cnds clubs

PMA Veri Sign Hot Trends
18. 06. 2007
0 views

PMA Veri Sign Hot Trends

Phys Act2 Ron Johnston
18. 06. 2007
0 views

Phys Act2 Ron Johnston

cdp 8 12 06
19. 09. 2007
0 views

cdp 8 12 06

cdp 12 06
19. 09. 2007
0 views

cdp 12 06

061101 Panofsky
17. 08. 2007
0 views

061101 Panofsky

Saints or Sinners
17. 08. 2007
0 views

Saints or Sinners

memoria
18. 06. 2007
0 views

memoria

00021386
19. 09. 2007
0 views

00021386

peso fall protection w
04. 01. 2008
0 views

peso fall protection w

irony
15. 06. 2007
0 views

irony

HOUSE HOLDER
15. 06. 2007
0 views

HOUSE HOLDER

god you are looking for
15. 06. 2007
0 views

god you are looking for

generadio7
15. 06. 2007
0 views

generadio7

friendship cinquain
15. 06. 2007
0 views

friendship cinquain

foreign words in english
15. 06. 2007
0 views

foreign words in english

FME UC 2006 Opening Session
15. 06. 2007
0 views

FME UC 2006 Opening Session

First fun in the afternoon
15. 06. 2007
0 views

First fun in the afternoon

feml fool 2006
15. 06. 2007
0 views

feml fool 2006

FATE AND CHANCE WEEK I 2006
15. 06. 2007
0 views

FATE AND CHANCE WEEK I 2006

FATE AND CHANCE WEEK 2 2006
15. 06. 2007
0 views

FATE AND CHANCE WEEK 2 2006

faq remarriage
15. 06. 2007
0 views

faq remarriage

faq commitment
15. 06. 2007
0 views

faq commitment

Fabulously Funny Facts
15. 06. 2007
0 views

Fabulously Funny Facts

NEW MEMBERS
18. 06. 2007
0 views

NEW MEMBERS

FOL and Prolog
15. 06. 2007
0 views

FOL and Prolog

mouton
18. 06. 2007
0 views

mouton

NPR
18. 06. 2007
0 views

NPR

NOWARonIran
16. 10. 2007
0 views

NOWARonIran

maendsregler
18. 06. 2007
0 views

maendsregler

Les arts figuratives al s XIX
01. 10. 2007
0 views

Les arts figuratives al s XIX

Kirkpatrick
07. 08. 2007
0 views

Kirkpatrick

texas emission
26. 02. 2008
0 views

texas emission

NFI Pact presentation copy 2
07. 08. 2007
0 views

NFI Pact presentation copy 2

casestudy
22. 10. 2007
0 views

casestudy

Thankyou Lord
17. 08. 2007
0 views

Thankyou Lord

megagreen
18. 06. 2007
0 views

megagreen

SRaha
17. 08. 2007
0 views

SRaha

Glasgow Anand
15. 11. 2007
0 views

Glasgow Anand

2 day training slideshow
07. 08. 2007
0 views

2 day training slideshow

Finch
15. 11. 2007
0 views

Finch