gc.dvi

Size: px

Start display at page:

Download "gc.dvi"

つねときなかきむら
5 years ago
Views:

1 Garbage Collection ( ) (endo@logos.t.u-tokyo.ac.jp) 6 : Jan 27, Garbage Collection? 2 (1) (2) ( 1) C C++, Pascal ML Java, Perl C malloc (allocate) free ( malloc Java/C++ ML tuple record ) C ( / free) 12 ML tuple record garbage collection(gc) GC UNIX (1995 ) emacs GC Java web Java 0.5 / ( )black box GC GC ( 1) Java Sun HotSpot VM (Ver ) GC 3 generational GC (6.2 ) ( ) copying GC (4.2 ) mark-compact GC (4.3 ) -Xincgc incremental GC (6.1 ) [7] [12] zlib LZW root

2 C malloc free C++ new, malloc delete, free Java new, (GC) ML tuple record (GC) Scheme pair vector (GC) Perl (GC) Table 1: i ÕÕÖ ÕÕÖ i ÕÕÖ (GC) ˆ i ÕÕÖ Tracing GC Mark-sweep GC Reference counting Escape Analysis Region inference Linear type Copying GC Mark-compact GC + Generational GC + Incremental GC Figure 1: Tracing GC GC 2

3 global variables registers heap stack Figure 2: 2 GC Java, ML, C A B (record record ) A B ( ) return / (C malloc) 2.2 ( tuple, record...) allocate(n)( ) n allocate () n n push 3

4 f() { r = new Object(...); // s = new Object(...); // (r, s ) return r; // r } f r s r f r r r GC (C/C++ ) ML Java GC (=garbage) GC f() ( GC ) r s GC / GC GC (1) reference counting (2) tracing GC allocate+ free GC 5 free(p) p (= allocate ) free () free p allocate(n) Allocate/free fragmentation( ) allocate free coalescing( ) fragmentation: fragmentation allocate coalescing: coalescing header: header Allocate/free 40 Wilson [13] 4 GC 5 copying GC allocate 4

5 segregated free lists allocate allocate 3 Reference Counting reference counting GC reference count() a ( / /) a Reference counting a a a 0 a a b b 1 b 0 b... Reference counting a b b a a, b a b 0 ML Java tracing GC (perl ) 1 defered reference counting [4] ( / / ) ( ) (1) reference counting tracing GC (2) trace (cycle detection ) 4 Tracing GC Reference counting o o Tracing GC tracing GC reference counting 5

6 allocate ()... ( GC ) GC reference counting reference counting tracing GC allocate/free 6 6 GC 8.2 ( ) Tracing GC mark-sweep GC (4.1 ) copying GC (4.2 ) mark-compact GC (4.3 ) Tracing GC GC 3 GC GC GC GC ( ) 4.1 Mark-Sweep GC tracing GC tracing GC mark-sweep GC Java Kaffe C GC Boehm GC 1 7 GC GC 0( ) 1 GC wave front( ) 8 6 allocate GC GC allocate 400MHz Ultra SPARC 20MB live 700ms (mark-sweep ) GUI 7 GC 8 6

7 ;;; mark-phase push all roots into mark-stack while (mark-stack is not empty) o =pop(mark-stack) for i = 0 to sizeof(o) c = ith field of o if (c is pointer) and (mark-bit(c) == 0) mark-bit(c) =1 push(c, mark-stack) ;;; sweep-phase p = heap-bottom while (p <heap-top) if (mark-bit(p) ==0) free(p) p=p+sizeof(p) Figure 3: mark-sweep GC 0 ( ) free free fragmentation 4.2 Copying GC Copying GC mark sweep reference counting fragmentation Scheme ML GC ( 4) from-space to-space 10 from-space GC to-space GC 2 to-space from-space b c d to space b c 3 11 (from-space ) from-space ( ) from-space 9 Mark-sweep GC 10 2 from-space/to-space 11 ( A A ) 7

8 roots roots f e a c b GC f e a c b a c d b g d g d fromspace tospace fromspace tospace Figure 4: Copying GC From-space to-space copying GC Cheney [3] O(1)! GC ( a ) to space a 2 scanned to-space Scanned unscanned (to-space ) +sizeof(a) Scanned unscanned unscanned GC Scanned o o unscanned (o ) unscanned o scanned (o ) Scanned unscanned GC from-space d d d forwarding tag ( ) forwarding pointer( ) Copying GC Copying GC fragmentation free (2 ) mark-sweep(4.1 ) allocation allocate linear allocation free ( free ) copy GC GC ( ) 8

9 free reference counting tracing GC or Table 2: 4.3 Mark-Compact GC Mark-compact GC mark-sweep GC fragmentation Mark phase mark-sweep GC compact phase live object 2 copy GC 1 mark-sweep GC copying GC GC live mark-sweep/copying GC GC reference counting tracing GC 2 Tracing GC 1. free/reference counting GUI free Tracing GC GUI Incremental GC (6.1 ) 5.1 Copying GC v.s. free copying GC free GC free live object L, M / free 1 free M,L f 12 Copying GC GC L cl (c ) cl M/2 L M/2 L cl M L free GC ( ) L 12 GC free 9

10 memory use allocate free time Figure 5: free ( ) Free memory use allocate GC time Figure 6: Tracing GC ( ) GC 10

11 Scheme ML (M/2 L ) GC 5.2 Mark-sweep v.s. copying mark-sweep GC copying GC copying mark-sweep 1 GC live object L M mark-sweep GC ml + sm copying GC live object L cl M mark-sweep L copying mark-sweep GC lazy sweeping Lazy sweeping allocate ( ) Lazy sweeping allocate (1)GC ml (2) m c mark-sweep GC( ml) copying GC( cl) Mark-sweep GC live object read 1 () push/pop 1 copying GC read 2 write 1 m<c mark-sweep 13 1 GC mark-sweep GC(+lazy sweeping) Allocate copying GC 6 Tracing GC tracing GC incremental GC generational GC Generational mark-compact GC Incremental generational copy GC 6.1 Incremental GC: GC Incremental GC GC allocate GC mark sweep GC incremental Incremental GC GC GC... GC 13 Copy GC (mark-sweep ) 3 11

12 GC (= ) ( 5 7 ) write barrier Incremental GC GC GC GC 8 a (b, c ) a c b c (NULL ) GC b c c GC GC ( ) write barrier 14 write barrier 2 (incremental-update) a c a c (Snapshot-at-beginning) b c c 15 incremental mark sweep GC incremental copying GC mark-compact GC incremental incremental GC GC incremental GC write barrier Incremental 6.2 Generational GC: GC (*) GC ( ) Generational GC ( GC) ( 9) Copying GC from/to 2 GC GC(minor collection) Minor collection ( GC n ) ( promote ) minor collection ( ) b minor collection 14 write barrier OS (UNIX mprotect() ) write write 15 write barrier [5] 12

13 memory use allocate GC(partially) time Figure 7: Incremental GC ( ) GC roots a b c Figure 8: Incremental GC write barrier a c b c 13

14 roots b a c d e f old generation new generation Figure 9: Generational GC c d, e f GC(major collection) Generational GC Minor collection GC major collection (*) 5.1 (*) () Generational GC Minor collection c d d GC c e minor collection (incremental GC ) write barrier 7 GC finalizer, weak reference Java 7.1 Conservative GC: C GC GC ( ) C GC Boehm GC[2] ( web w3m, gcc 3.x 14

15 ) 16 C/C++ mark-sweep GC (GC malloc()) GC (conservative GC( GC) ) GC (false pointer) 17 : copying GC Copying GC update(fromspace tospace ) GC copying GC (mostly copying GC [1]) GC ( malloc ) C/C GC GC GC 2 concurrent GC: GC GC (GC allocation ) Incremental GC write barrier parallel GC: GC GC Write barrier GC parallel concurrent GC Boehm GC [6, 5] GC write barrier 7.3 GC CORBA Java RMI ( ) (remote reference) GC GC 2 reference counting: remote reference reference counting(3 ) GC tracing GC Java RMI 16 w3m ( 17 consservative GC double double word false pointer 15

16 tracing GC: tracing GC GC Shapiro [10] GC 7.4 Escape analysis ([9] ) GC GC Region inference ([11] ) tracing GC ML kit linear type ([8] ) () 1 free 8 GC 8.1 GC GC Sun Java VM -Xms( ) -Xmx( ) 8.2 GC GC 1. ( GC) 2. (conservative GC ) 3. GC (tracing GC, reference counting ) 4. (tracing GC) 5. GC (tracing GC) 6., ( GC) 7. (write barrier) (reference counting, incremental GC ) 8. (reference counting, incremental GC) 16

17 1. allocate+ free allocate header 5., 6., 7., ( ) GC 1 =16bit 1bit 1 0 ( ) 15bit 2 ( +1) ( *2) r3 r1 r2 mul r1, r2, r3 1bit mul r1, r2, r3; shr r3, 1 (, char,boolean ) 2bit 3bit ( 16bit 19 ) ( ) 1 / Tracing GC 5.() GC ( ) GC 9 GC web GC Boehm/gc/ [2] [7] Boehm conservative GC GC Paul Wilson, [12][13] / GC 18 C GC (7.1 ) 19 Java 17

18 References [1] Joel F. Bartlett. Compacting garbage collection with ambiguous roots. Technical Report 88/2, DEC Western Researach Laboraory, February [2] Hans-Juergen Boehm and Mark Weiser. Garbage collection in an uncooperative environment. Software Practice and Experience, 18(9): , [3] C. J. Cheney. A nonrecursive list compacting algorithm. Communications of the ACM, 13(11): , [4] L. Peter Deutsch and Daniel G. Bobrow. An efficient incremental automatic garbage collector. Communications of the ACM, 19(7): , July [5] Toshio Endo and Kenjiro Taura. Reducing pause time of conservative collectors. In Proceedings of ACM SIGPLAN International Symposium on Memory Management (ISMM), pages 12 24, June [6] Toshio Endo, Kenjiro Taura, and Akinori Yonezawa. A scalable mark-sweep garbage collector on large-scale shared-memory machines. In Proceedings of ACM/IEEE Conference on High Performance Networking and Computing (SC97), November [7] Richard Jones and Rafael Lins. Garbage Collection, Algorithms for Automatic Dynamic Memory Management. Wiley & Sones, ISBN [8] Naoki Kobayashi. Quasi-linear types. In Proceedings of the 26st ACM Symposium on Principles of Programming Languages, pages 29 42, [9] Y. G. Park and B. Goldberg. Escape analysis on lists. In Proceedings of ACM SIGPLAN Conference on Programming Language Design and Implementation, pages , June [10] David Plainfossé and Marc Shapiro. A survey of distributed garbage collection techniques. In Proceedings of the 1995 SIGPLAN International Workshop on Memory Management, volume 986 of Lecture Notes in Computer Science, [11] Mads Tofte and Jean-Pierre Talpin. Implementation of the typed call-by-value λ -calculus using a stack of regions. In Proceedings of the 21st ACM Symposium on Principles of Programming Languages, pages ACM, [12] Paul R. Wilson. Uniprocessor garbage collection techniques. In Proceedings of the 1992 SIGPLAN International Workshop on Memory Management, volume 637 of Lecture Notes in Computer Science, [13] Paul R. Wilson, Mark S. Johnstone, Michael Neely, and David Boles. Dynamic storage allocation: A survey and critical review. In Proceedings of the 1995 SIGPLAN International Workshop on Memory Management, volume 986 of Lecture Notes in Computer Science,

IPSJ SIG Technical Report Vol.2016-ARC-221 No /8/9 GC 1 1 GC GC GC GC DalvikVM GC 12.4% 5.7% 1. Garbage Collection: GC GC Java GC GC GC GC Dalv

IPSJ SIG Technical Report Vol.2016-ARC-221 No /8/9 GC 1 1 GC GC GC GC DalvikVM GC 12.4% 5.7% 1. Garbage Collection: GC GC Java GC GC GC GC Dalv GC 1 1 GC GC GC GC DalvikVM GC 12.4% 5.7% 1. Garbage Collection: GC GC Java GC GC GC GC DalvikVM[1] GC 1 Nagoya Institute of Technology GC GC 2. GC GC 2.1 GC 1 c 2016 Information Processing Society of