« 3月22日のトレーニング | トップページ | 3月24日のトレーニング »

2010年3月24日 (水)

ガベージコレクションのアルゴリズムと実装を読む(2日目)

ガベージコレクションのアルゴリズムと実装を読み始めて2日目になりました。

今日は、2章の「マークスイープGC」を読みました。

マークスイープGCは「マークフェイズ」と「スイープフェイズ」がある。

生きているオブジェクトに対してマークビットを立てる。
マークビットが立っていないオブジェクトをスイープフェイズで回収する。

分かりやすいアルゴリズムでした。疑似コードもマークして、スイープといった
ロジックになっていました。

メリット
実装が簡単(疑似コードから大体わかりました)
保守的GCと相性がいい
(オブジェクトの移動がないため。。だそうです。以降の保守的GCを読めば分かるはず)

デメリット
フラグメンテーションが発生しやすい
アロケーション速度の問題(FreeListをたどって行く必要がある。最悪、毎回最後まで)
コピーオンライトと相性が悪い(マークビットを立てるとコピーが頻発する)

で、デメリットを解消するために考えられた方法が
複数フリーリストを用意する
BiBOP法
ビットマップマーキング

ビットマップマーキングの例(リスト9)で私が詰まってしまったので、
筆者にTwitterで質問してみました。
詰まった内容:
2行目の
obj_num = (obj - $heap_start) / WORD_LENGTH

3行目の
index = obj_num / WORD_LENGTH
に具体的な数値を当てはめると、以降の配列のアクセスがおかしくならないか?

具体例)
obj_num = (3 * 32 - 1 * 32) / WORD_LENGTH(=32) = 2
index = 2 / WORD_LENGTH(=32) = 1/16

(実際、リストの次の段にobj_num = 8の例がありますが)

これは私のミスでした。C言語の整数の扱いのように小数を切り捨てるということを
しなければいけませんでした。
ということで、実際には

obj_num = (3 * 32 - 1 * 32) / WORD_LENGTH(=32) = 2
index = 2 / WORD_LENGTH(=32) = 0(切り捨てる)

となります。

これで、すっきりしました。(作者と簡単に連絡が取れるのは良いなぁ。)

|

« 3月22日のトレーニング | トップページ | 3月24日のトレーニング »

C言語」カテゴリの記事

コメント

コメントを書く



(ウェブ上には掲載しません)




トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/50625/47896678

この記事へのトラックバック一覧です: ガベージコレクションのアルゴリズムと実装を読む(2日目):

« 3月22日のトレーニング | トップページ | 3月24日のトレーニング »