GC本を読んで学ぶ2

• 全てのガベージコレクションは以下のいずれかに基づいている(ガベージコレクタ毎にさまざまな方法で領域ごとにこれらのアプローチを組み合わせているらしい)
  • マークスイープGC
  • コピーGC
  • マークコンパクトGC
  • 参照カウントGC

大体wikiに載ってる

• ストップザ・ワールド的なアプローチ例
  • コレクタスレッド1
    • ガベージコレクションを実行するスレッド
  • ミューテータスレッドN
    • アプリケーションコードを実行するスレッド(コレクタスレッド実行時は停止)

これの利点はヒープのスナップショットがとれる + ヒープ中のオブジェクトのトポロジが変化しないこと

• 自動メモリ管理を行うのに必要な機能
  • 新しいオブジェクトの領域の割当
  • 生きているオブジェクトの特定
  • 死んだオブジェクトの使用している領域の回収

完全に判別するのは厳しいので参照を追って参照が存在しないオブジェクトは死んでいる判定にすることによって安全に回収する

• マークスイープGC
  • まずルート集合(レジスタ、スレッドのスタック、グローバル変数)からオブジェクトのグラフを走査して到達可能なオブジェクトにマークをつける(所謂tracing)
  • スイープフェーズでヒープ中の全てのオブジェクトにマークがついているか調べてなければゴミとして回収する(わかりやすい)
  • 間接的GCアルゴリズム
  • ゴミを探すというよりは生きているものを探して他は全てゴミとして扱う

Mark-and-Sweep: Garbage Collection Algorithm)

わかりやすい
コレクタがシングルスレッドなら探索リストをDFSで実装できる(これによってハードウェアキャッシュがあたることを期待できる)

三色抽象化を利用してオブジェクトの状態を表現できるらしい
黒(処理済み)、白(未処理(永遠に未処理の可能性もある))、灰(処理途中もしくは再処理が必要)
並行GCのアルゴリズムで特に有用らしい

• 時間的局所性

  python total = 0 for i in range(1, 11): total += i

  とした場合にtotalに対して複数回のアクセスが発生するので、その値をキャッシュするのが有効(アドレスをイメージしたほうがわかりやすそう)

• 空間的局所性

  python l = [1,2,3,4,5] for i in l: print(i)

  この場合lに対して複数回のアクセスが発生するので、その値付近をキャッシュするのが有効(これもメモリが連続して確保されている際にアクセスすることを考えたほうがわかりやすいか、CPUのプリフェッチとかもこれ系)

マークビットの領域は通常オブジェクトのヘッダワードの中に用意する
いまいちオブジェクトのヘッダワードのイメージがよくわからんとなったので適当に調べた感じ
Javaだとこんな感じらしい

セットアソシアティブ方式とダイレクトマッピング方式はこれがめちゃくちゃわかりやすかった
(アドレス空間/キャッシュ容量/ブロックサイズ/タグ/オフセット/インデックスとか用語から説明されてて助かる(基本と応用とったくせに完全に記憶から消失した))

オブジェクトヘッダにマークビットを用意することによってrace conditionを解消できる(外部に持つと更新状態が競合する可能性が存在する) ビットマップではなくバイトマップを使うとマーク処理のrace conditionが解消できるらしい(よくわかってない)

• 安全性に関しての結論
  • コレクタはどこに格納された値であってもミューテータが保持する値を書き換えてはいけない(オブジェクトを移動させるどんなアルゴリズムも使えない, 移動するとポインタの修正が発生する)
    • オブジェクトのようなもの(のようなものって具体的になんなんだろう)のマークビットを変更することによってユーザのデータを破壊する恐れがある
  • ミューテータがコレクタのデータと干渉する機会を最小限にすることが有益
    • ヘッダワードに持つよりはオブジェクトと分離したデータ構造(これがバイトマップかな)に保存したほうがリスクが小さい
    • コレクタによるページング回数を減らすのも有益

マークスイープGCのメモリアロケータはフラグメンテーションを避ける為に一定サイズのブロックを連続して配置するらしい
(メモリアクセスのパターンが均一になってハードウェアのプリフェッチの機構と相性が良い)
マークフェーズのオブジェクトヘッダの読み取りによって発生するキャッシュミスの回数を減らす方法の一つにBiBoPというものがあるらしい
(同じページには単一の型のみを割り当てることによってオブジェクト毎の型情報をページ単位に圧縮が出来る)