GC

メモリ管理の神話

• GC は malloc/free より(常に)遅い
  場合によるが大抵は互格以上．malloc/free にはメモリリーク，ダングリングポインタという問題がある．
• 参照カウントは GC ではない(から遅くない)
  参照カウントは GC の一種である．しかも欠点が多い．
  • 参照カウントはごみになったことがすぐわかるので，即座に回収できる．という点がメモリ管理を自分で仕切りたいプログラマに受けている?
  • ref/unref を追加すればいいので，既存のプログラムからの移行が容易に感じられる．実際はメモリ管理がプログラム全体に散らばるのでデバッグや最適化が大変になるし，マルチスレッド環境では排他制御のオーバヘッドがばかにならなくなってしまう．
• GC を使うと後始末(finalize)できない
  後始末とメモリ回収は話が別．C++ ではデストラクタで同時に行なうことが強制されるが．

結論としては C/C++ のような言語でメモリ管理の必要なプログラムを書く場合は，BoehmGC のような保守的GC ライブラリを使おうということだった．

アルゴリズム

基本アルゴリズムとその派生

• 参照カウント(reference counting)方式
  • 遅延参照カウンタ法
  • sticky 参照カウント
  • 部分マーク・スイープ法
• マーク・スイープ(mark & sweep)方式
  • BiBOP(Big Bag of Pages)
  • 反転(reverse)ポインタ法
  • マーク・圧縮(compaction) GC
• コピー(copying)方式
  • 部分的圧縮法
  • 近似的深さ優先(approximately depth-first)コピー法
  • 世代別(generational) GC

実装上の問題

• 保守的(conservative) GC
  ポインタらしきものはポインタとみなす(ごみでないかもしれないオブジェクトは回収しない)．
• exact GC
  ごみは確実に回収する．

言語仕様との関連

• オブジェクトの途中を指せるか?
• 循環構造が生じるか?

GC 用ビットの確保

• オブジェクトに含めるか，ビットテーブルを別に用意するか?

マーク・スイープ方式

• 実行時間はマークは生きているオブジェクト数に比例し，スイープはヒープサイズに比例する．
• マークフェーズにおいて，オブジェクトを(深さ優先で)たどるためスタックを利用する．このスタックを保持するためにメモリを食ってしまう．
  • オブジェクトに反転ポインタの格納場所を示すフラグを追加し，オブジェクトをスタックとしても利用するように改良したのが反転ポインタ法．
• 回収したヒープはフリーリストで管理する．フラグメンテーションの可能性がある．
  • ヒープをページ単位で管理し，同一ページに同一サイズのオブジェクトだけを割り付けるように改良したのが BiBOP．オブジェクトサイズごとにフリーリストが存在するので，スイープフェーズを短縮でき，フラグメンテーションも回避できる．
  • また，コンパクションするように改良したものに，マーク・圧縮GCがある．

コピー方式

• 実行時間は生きているオブジェクト数に比例し，ヒープサイズとは無関係．
• コンパクションするのでフラグメンテーションを回避できる．データの局所性が上がるので，仮想メモリ，キャッシュとの相性がいいかも?
• マーク・スイープ方式ではスタックが必要になるが，to space をスタック(実際は FIFO だが)として利用できる．ヒープの半分しかオブジェクトを割り付けられないという欠点も少しは相殺されるかも．
  • ただし，(FIFO なので)幅優先探索になる．仮想メモリ，キャッシュの効率を上げるには深さ優先の方が有利．
  • ヒープを二つではなく N 個の部分空間に分割し，一つを to space とし，部分空間内ではマーク・スイープ方式を利用することでヒープの有効領域を拡大したのが部分的圧縮法(多数空間法)．
  • 親子関係のあるオブジェクトを同じページに割り付けることで，幅優先ではなく近似的に深さ優先に走査できるように改良したのが，近似的深さ優先コピー法．Symbolics の Lispマシンで最初に実装された．
  • 多くのオブジェクトは生成後，短時間でごみになる．ある程度の時間を生き抜いたオブジェクトはなかなかごみにならない．したがってオブジェクトを GC のたびにコピーするのは非効率である．そこでオブジェクトに「年齢」の概念を導入し，通常は新世代だけを回収し(minor GC)，たまに旧世代を回収する(major GC)ように改良したのが，世代別GC．

世代別 GC

• HotSpot JVM?
  • minor GC はパラレル GC を適用．マルチプロセッサシステムで有効．
  • major GC はシリアル GC．GC によるアプリケーションの停止時間を短縮するために Mostly-concurrent GC (CMS: Concurrent Mark and Sweep) を適用．

• Tiki:GC
  書いているうちに内容がかぶってきましたね．Tiki間のディレクトリサービス みたいなものがあれば便利なのかな．
  • Tiki:メモリリーク
• GC-FAQ
• Richard Jones's Garbage Collection Page
  • Garbage Collection: algorithms for automatic dynamic memory management
    Richard Jones 氏による有名な教科書．
• Paul R. Wilson, Uniprocessor Garbage Collection Techniques (ps)

• 一般教養としてのGarbageCollection
  東大の「コンパイラ演習」の資料より．

• lazy sweeping
  mark-and-sweep方式でGCによるユーザプログラムの停止時間を短くするテクニック． markフェーズが終了した時点でユーザプログラムの実行を再開し，ユーザプログラムが allocate要求をした時点でsweepを行う．

• VisualWorksのGC戦略
  渡邊克宏@元SRA 氏の OHP がある．

• .NETアプリを軽快にするためのガベージ・コレクション講座 (@IT 2007-02-13)

実装

• BoehmGC

• Cでいう所のポインタ(笑)、つまり、(GC_)mallocで確保した まさにドンピシャ「ではない」アドレスも、GCでMarkの対象と なるんでしょうかね？たとえば確保したアドレスを++したアドレス値とか。
• アドレスがマークの対象という意味がよくわかりませんが． 普通，メモリはブロック(セル，チャンク)として扱われるので， 問題ないと思います．(意図をはずしてます?)
• ブロックの先頭ではなく中間を指すポインタ(かも知れないword値)です。 たとえばGC_malloc(4)の返し値が0x11111110だった場合、 確保された領域は0x11111110から0x11111113までであるわけですが、 この時0x11111112や0x11111113というwordがプロセスメモリの(笑)どこかに 存在すると、それがこの4byte領域の回収を阻止するのか否か？です。
• なるほど．派生ポインタの問題ですね．オブジェクトの先頭への ポインタを基底ポインタ．基底ポインタに対してオフセットを加減算したりして 得られたポインタを派生ポインタと呼ぶことにします．
• 基底ポインタしかない場合に，任意のワードwを調べたい場合は， 次のような条件を調べればいいと思います．
  • wがヒープ領域内に存在するか(OSによってはヒープが連続じゃ ない場合があるなぁ．面倒だけど調べることは可能)
  • wをメモリブロックサイズでアライメントしたアドレスaは， 下で示したmemory markingの式で成立するか
  • wがオブジェクトの先頭を指すポインタか
  • 一方，派生ポインタは最後の条件をwが「a->オブジェクト本体のアドレス」と 「a->オブジェクト本体のアドレス + a->サイズ」の間にあればいいわけです． これで派生ポインタがあっても，メモリブロックが回収可能か判定できると 思いますが，どこかに穴がありますかね?
  • アライメントしただけでmemory markingの式がなりたつという保証は ありません。バウンダリ>オフセットの場合。ですので単にwがメモリ管理ライブラリ が割り当てたメモリブロックの中に収まっているかどうかを判定し、memory markingの式が成り立たない場合は、メモリブロック内をたどってオブジェクトの先頭を見つけ出した後そのオブジェクトをmarkする と思われます。
• あっそうか。まぁ確かにコンサバ(笑)の必要条件を満たしてはいるんですね。
  俺が考えたのは、もう一歩突っ込んで、たとえば「奇数アドレスは 派生ポインタとすら見なさない」というルールをつけたらどうなるか？です。 RubyのIntのようなものがポインタだと勘違いされなくなります。 でもこれは「無駄なアガキだ」が答えのようですね(^^;。 本物の奇数アドレスを指したbyte*を取りこぼす恐れがあるんで コンサバの必要条件を満たさない。つーわけで成仏しました(笑)

• 今気になっているのが、Rubyみたいに「整数を奇数アドレスポインタ として実装する(ことでinstance生成をケチる)」という実装をした場合、 Boehmのような生CレベルのGCは攪乱されてしまわないか?という事です。 まぁboehmのソース読めっていう話ではあるんですが(^^; -戯
• 「整数を〜」という話は始めて聞きましたが，これは基本型のような よく利用されるもののインスタンス生成を抑えると同時に，(オブジェクト への)ポインタとの区別を容易にする工夫といえます．オブジェクトは 4バイト(偶数)アドレスにアライメントされているはずなので．
• Rubyにしろ，BoehmにしろCを使うもの(conservative GC)の宿命として， malloc/free系との 混在も考慮しなければいけないなど，ポインタと非ポインタの判定を どう行なうかという問題があります．ここが「攪乱」と書かれた由縁でしょうか?
• 例えば，オブジェクトへのポインタは配列objectsに格納し，オブジェクト の先頭はサイズ，識別子(後述)，マークフラグなどの管理情報が格納されていると します．そこで，新しいオブジェクトOが生成された場合，処理系はobjectsから 未使用のindexを選び，objects[index]にOのアドレスを格納します． さらに，Oの識別子部にindexを格納します．こうすることで，任意のアドレスAが オブジェクトへのポインタなのかどうかを次の式で評価することができます．

    objects[A->識別子] == index
  

• このようなテクニックをmemory markingと呼ぶらしいです．Boehm GCでも これと同じようなことをやってます．他のアルゴリズムも併用しますが． Rubyにおける「整数〜」もこれと同じで「攪乱」の原因ではなく，解決の 手段と言えるのではないでしょうか?

• Rubyの中では恐らく辻褄が取れているのだと思うのですが、 俺が自分で詳細を知らない(ソース読めという話はさておき(^^;)GCライブラリを 使う場合に、同じことが自動的に実現されるかどうかは、ちょっと別の話かと。
• 1Objectは必ず1回のallocで確保するというルールが護られているならば、 その構造(ユーザープログラミングから見えるかどうかは別)を仮定することで 色々な作戦を立てられると思いますが、Objectの先頭以外を指すポインタ (らしきもの)が存在し得るCという言語を対象としたboehmのような奴では、 そういう仮定は出来ないわけで(説明読み不足だったらすみません)。
• 上に書いたように(ん〜，上から読んでも時系列順じゃないので文章を追うのが 大変かな．せめてTikiにページ内へのポインタ，まさしく派生ポインタが使えれば...)， 派生ポインタが存在してもBoehm GCではちゃんと回収してくれるはずです．
  派生ポインタに関してはユーザが手動で解放しなければいけないとなるとmalloc/freeと 同等かそれ以上にメモリ管理が面倒になる気が(^^;)

• conservative GCは，GCのない言語からGCのある言語を作成する 場合に有効である．(C -> Lisp，C -> Ruby)．

• プログラミング言語とGC

• Concurrent Cycle Collection in Reference Counted Systems

• 熱力学とガベージコレクション