「ガベージコレクションのアルゴリズムと実装」の感想

2010-03-18

#gc

なんかうかつに読んでると、「これじゃうまく動かないんじゃ！？」と思ってあわてるんだけど、よくよく追ってみるとちゃんと動きそうだとわかる。まるで気が抜けない…。

想定している知識が、C、ポインタ、union、メモリ構造、テンプレート、他にいろんな言語とか超スパルタン、ガチ過ぎる。

ガベージコレクションのアルゴリズムと実装

ガベージコレクションのアルゴリズムと実装

posted at 10.03.18

中村成洋相川光
秀和システム
売り上げランキング: 448

Amazon.co.jp で詳細を見る

1ビット参照カウント

大抵のオブジェクトは１つからしか参照されないのでカウンタは１ビットでもいいんじゃない？ってことで結構いいかも、と思ってたんだけど、よく考えたら例えばコンテナに突っ込んだり、関数に渡したり、ヘタしたら関数内で生成したオブジェクトを返そうとしただけでカウンタが２になって振り切れちゃうので、ほとんどうまくいかないんじゃないかという気がしてきた。

部分マークスイープ法

リスト16:dec_ref_cnt() の3～4行目でカウンタが０になったときにdelete(obj)してるけど、オブジェクトの色がハッチだったときはキューに登録されてるのでそれを取り除かないとまずいのではないか？
リスト17:new_obj() の9行目は値を戻すので return new_obj(size)

途中まで読んで

1.8 ルート（19ページ）のfor文でrootsに$がついてない
「3.6.1 ビット参照カウント」で tag() や set_multiple_tag() や delete_ptr() が、渡したポインタじゃなくてそれが参照するオブジェクトを対象とするのがすごくわかりにくい気がする
- tag() や set_multiple_tag() が示されてないのもあるんだけど
- tag() はオブジェクトのタグを調べる関数にして、delete_ptr() じゃなくて dec_ref_cnt_1bit() に変更して、あとコピー前にMULTIPLEタグをつけるようにしたらわかりやすいのではないか？

copy_ptr(dest_ptr, src_ptr){
  set_multiple_tag(src_ptr)
  dec_ref_cnt_1bit(*dest_ptr)
  *dest_ptr = *src_ptr
}

dec_ref_cnt_1bit(obj){
  if(tag(obj) == UNIQUE)
    reclaim(obj)
}

tag(obj){
  return obj & MULTIPLE
}

set_multiple_tag(ptr){
  *ptr |= MULTIPLE
}

オブジェクトの色分けだけど犯人かどうかと同じに、完全にゴミなら黒、完全に生きてるなら白、ゴミかもしれないならグレーがいいなぁと思った。なんかの論文で本のような色分けだったらあれですけど。
11章のコラム「なぜRubiniusのGC解説を？」に「RHG」がある

新着記事