コンカレントGCの実装その１
イプシロンではMostly-Concurrent Mark & Sweep GCを実装しています。このアルゴリズムにつきましては、こちらのページの解説がわかりやすくてお勧めです。
http://www.nminoru.jp/~nminoru/java/cms/concurrent_mark_sweep.html
イプシロンでの実装方法の解説を行う前に、GCで管理されているヒープの状態を見る方法を紹介しておきます。
起動直後のヒープをみる
Ypsilon 0.9.6-trunk/r198 Copyright (c) 2008 Y.Fujita, LittleWing Company Limited. > (display-heap-statistics) |PPsossSOOOSsOSPOPOOPOOOP-OPPOOOOOOOOOOOOOOOPOOOOOOOOOOOOOOOOOOOO| |OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO| |OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOsOOOOOP| |---OOOPOOOOOOOOSPPPOOOOOOOP---OOsPPOPOOOOOPPOOOOOOOOOOOOOOOOOOOO| |OOOOOOOOOOOOOOOOOOPP-OOP-OOOOOOOOOOOOOOPOOOOP-OOOOOP-OOOOOOOOOOO| |OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO| |OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOPoOOP---OOOOSOOOOPOOO| |P---OPPPPSOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOoOPPoPP-OOOoOOoP---| |----Sos | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | object:441 static:14 page:64 free:1529 watermark:2048 limit:8192
しばらくプログラムを動かしてからもう一度見てみる
: : : > (display-heap-statistics) |PPsosssOOoSsOsPO.OO ooo oPPoooooo oooOoOOooooOoOooooooooooOo...| |ooooooooooooooooooOooOooooooooooOOoooooooOooooooooooooooOoooOooo| |ooooooooooooooooooooooooooooooooooooooooooOoooooooooooooo ooooOP| |---oo Poooooo o o o os o ooo o o oo o oo. o..o..| | oo..oo.o.oooo.ooO ..OO..o..o O.... oo. oooP-oooOoOoOOOo| |o.ooo.ooooooooooooooOooooooooooooooooooooooooooooooooooooooooooo| |ooooooooooooooooooooooooooooooooooooooooooo oooo.o.oo.os ooo oo| |P---o P oo .o ..o oP---ooo .Oo.o..o.. .oooOOoP---| |----.oP.oo.oo .oooo.. .o o. . o.. . .. o.ooo.....o..| |P o o o oo.. .o oo oooo ooo. oo. . .o. s o . . ...o.| |.... .. .o... .......o .. . o.oo.o.... .........o . o o.o. .. | | .. . .... ........o..... ......o............oo....o......o....o| |..oo..........o............o....o.......o.. o . o . .. . | | o. .o ......... ..... ...... ..............................o.| |ooooooooo.oooo...o.ooooo. ......o.oo....oo.P--o.o..o.o....ooo.o.| |.o....o....oo..ooooo.oo.ooo.ooo..o.ooOo..oOoOO..O.Oo.O.Oo..ooooo| |oo ooo oP-oo.oooo oo.ooo oo ooo oo... o.o o. o ooo . o | |o.o.o o. .o o oooo. o . P.o .o . .o o ooPo Poo .o o| | . o ooo oo oso oooS o ooooo ooo o | |oo . o o ooo oo o. o.o oo o oo o .oo o.o o o .oo oo| | .o .o .o o.P------- P------- . . . . .| | . . . . .| | . o. o . . . . . ... . . o o.. . ... . .. | | . . . . . .... .. . . .. . o. o. | | .o . . o. o .o. .o o o..o . . .o .o . oo . | |o o o . o . o o. . . . . | | .. . . . .o o.o. o ooo .o o o .o . oo .| |o . . o o o o. o. . . .o . oo o oo. o.| | . o . .o o.o | | o . . . . o.. o.o o . . . . . . . | |. . . . . . . . . . . . .. . . . | | . . . . . . . | |. . . . . . . . . . . . . . . . . | |. .o .o o . o o . . . ... . . | | . . . . . o . o . . . . . | | . . . . . . . . . . . o .| | o . . . . o . o o . . . | | . . . . . . . . . . . . .o o o | | . o . . o . . | | . o o. o o.. . .. .. ... .o .. o oo o.o ooo. o .o ..o | | . . o o . . o .o. . ooo oo. o oo.o | |ooo .o .. .oo o.o o.o o.... . ....o...o.oooo...oo.o.oooo.ooooo| |oooo. ooo..oooooooooooooooooooooo.oooooooo.o.ooooooo. | | | | | | | | o ooo oooo| | .oo.oooo ooo o o .oo oooo oooo oooooooo ooooooo oo.o . . | |. . o . . . . . . . . O o o o o o o o o | |o o o o o o o o o o o o o o o oo o o o o o o o| | o o oo P| object:1508 static:12 page:56 free:1634 watermark:3210 limit:8192
slabに発生したフラグメンテーションの解消を行ってみる
> (import (time)) > (time (collect)) ;; 0.019193 real 0.020002 user 0.0 sys
- 注：この動作はコンカレントには行われません。この例では19.2msほどVMが停止することになります。
> (display-heap-statistics) |PPsosssOOossOS OOOOSOOOOOOPPOoOOOOOOOOOOOOOOOOOOOOOOOOoooOOOOOOo| |OOOOOOOOOoOo O O OO O O O | | O O OP| |--- OP O O OO OOOOO OOOOO sOO O O OO O OOO OO OO OO O | |O OO OO OO O OOOOOOO O P- O O OOO | | O | | O sO OO | |P--- OOOPO O O OOOOOOOOOO OOOO OOOOO O O OO P---| |---- P O O O OOOOO OO O O OO OO | |POO OOOOO O O O O O O O OO O OOsOO O OOOOO O | | O O O O OO O O O OO O O| |O O O O O | | OOOO O O OOOO O O | |O O O OO | | O O O OOOOO O OOO P-- O OO O O OO O O| | O OO OOO OO O O O | | O P- O O O O O O O O OO OO O O OOOOOOOO OO| | O O OOO O O OOO OOOPO O OO OO O OO P OO P O | | OOOOO OO O OO S | | | | P------- P------- | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | P| object:331 static:12 page:51 free:2816 watermark:3210 limit:8192
- オブジェクトの局所性が上がっています。
さらに全体を圧縮してみます
> (time (collect #t)) ;; 0.018841 real 0.016001 user 0.0 sys
- 注：この動作もコンカレントには行われません。この例では18.8msほどVMが停止することになります。
> (display-heap-statistics) |PPOsOOOOOSOOOOOOOOOOOOOOOOPPOPOOOOOOOOOOOOOOOOOOOOOOOOP-sOOOOsOs| |OOOOOOOOOssPoooooOOOOOOP-------POOP---P-POP---P--PPPPOOOOOOOOP--| |-----P-------OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO| |OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO| |OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO| |OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOoOOOOOOOOOOOoO| |OOOoso| object:331 static:8 page:51 free:0 watermark:390 limit:8192
- ヒープ全体が小さくなりました＾＾b
表の見方
- "O"(o)：GCで管理されているオブジェクトの入っているブロックです。大文字はFullの状態。小文字は一部が埋まっている状態です。
- "S"(s)：GCで管理されていないデータの入っているブロックです。bytevectorの中身やstringの文字列などが入っています。小文字は一部が埋まっている状態です。
- "P"：ページ単位で確保されているデータのブロックです。大きなデータはここにはいります。"P---"となっているのは複数のページにまたがる大きなデータを意味します。大きなbytevectorの中身や大きなhashtableの表などが入っています。
- "."：キャッシュの部分です。再利用に備えて確保されているブロックです。
- １ブロックはデフォルトで4Kバイトです。
