GC本を読む ~第1章~

プログラミング Garbage Collection

ふとGarbage Collectionについて気になって調べていた所，ガベージコレクションのアルゴリズムと実装という本がとても参考になるという情報を得たので買ってみました． 買った後に550ページにも及ぶ超大作であることに気がついたのですが，まぁ買ってしまったし，全体をザーッと眺めた感じとても丁寧に説明している印象を受けたので，じっくり読んでいこうと思います．

ただ，こういう分厚い本はなんだかんだ最後まで読まずに積んでしまうのが世の常です．なので，最後まで読むぞという強い気持ちと，もし途中で諦めたとしても，また日が経ったときに続きから読み始めやすいように，こうして1章ごとにブログにまとめていこうと思い筆を取りました．

自分用のメモなので，途中自分が考えたログを残していたり，明らかに知っている内容のメモは飛ばしていたりします．

第1章 GCを学ぶ前に

GCの話を進めていく上で重要になってくる用語や基礎的な理論について説明している章．

オブジェクトやヒープ，ミューテータについて

用語 説明
オブジェクト アプリケーションによって利用されるデータの塊
ヘッダ オブジェクト内に埋め込まれた，オブジェクト自体の情報を保持する部分
フィールド オブジェクトの利用者がアクセス可能な部分
ミューテータ オブジェクトを生成したりポインタを更新したりする機能
HEAP_SIZE ヒープ領域のサイズ
$heap_start ヒープ領域の先頭アドレスを参照するポインタ
$heap_end ヒープ領域の終端の次のアドレスを参照するポインタ

データの塊であるオブジェクトは，そのメタ情報1を保持するヘッダとデータ自体を保持するフィールドによって構成される． オブジェクトの種類って何ぞやと思ったが，後の章で説明されそうな雰囲気．

フィールドはポインタと非ポインタの2種類に分類される．C言語とかのアレ． (でもポインタだって結局メモリの番地を格納するデータ型じゃんって思ったが，3秒考えて，GCだから参照先のデータの生存を考えなきゃいけないし，別種類で扱ったほうがスマートか，そりゃそうだと気づいた．)

この本のアルゴリズム編では1フィールドのサイズを1ワードとしている．オブジェクトの中にフィールドは複数存在可能．

さて，このフィールドがポインタか非ポインタかを判別するというのは少し工夫が必要らしい．これは第6章の保守的GCで詳しく述べられるようだ． とりあえず扱っている言語処理系はポインタかどうかを判別可能であるという前提で話が進む．

このヒープ領域内に配置されたオブジェクトの管理を行う仕組みのことをGCという． (てっきり使用済みのメモリの廃棄だけかと思っていたが，確保なども含めてGCというのか)

ミューテータから参照できるオブジェクトを生きていると表現し，逆に参照できないオブジェクトを死んでいると表現する． GCはこの死んでいるオブジェクト(ゴミ)を廃棄して次のオブジェクトの割り当てに活用する． (ミューテータは生成したオブジェクトのアドレスを辿る連結リスト的なのを持っているっぽい．どうやってそれを更新していくかはまだ謎．)

アロケーションやチャンク，ルートについて

アロケーション時，ミューテータは作りたいオブジェクトのサイズをアロケータに要求する．アロケータはヒープ領域の空き領域から要求を満たすものを見つけてミューテータに返す． 空き領域が足りない場合はGCが行われ，不要なオブジェクトが開放される．それでも足りない場合はエラーを返すかヒープ領域を拡張する． (拡張方法についてこの章では詳しく書いていない)

この空き領域のことをチャンクと呼ぶ．初期状態ではヒープ領域は1つの大きなチャンクで湿られている．アロケーションとGCを繰り返していくと，このチャンクが飛び飛びに存在していくことになる．(これをどう対処していくかがGCアルゴリズムの腕の見せどころ？)

ミューテータはヒープ領域のオブジェクトを連結リスト的に辿っていくことができるため，その先頭アドレスを指すルートが存在する．コールスタックやレジスタ，グローバル変数領域がミューテータにとってのルートにあたるらしい． (関数内で静的に作ってあるポインタ変数に動的にメモリを確保しても，どこかのグローバル変数領域がその参照を持っているということ...??)

評価項目

GCのアルゴリズムの性能は次の4つの項目によって評価される．

項目 詳細
スループット 単位時間あたりの処理能力
最大停止時間 GCによってミューテータの実行が停止する時間の最大値
ヒープ領域の使用効率 -
参照の局所性 参照関係のあるオブジェクト同士をヒープ領域上でどれだけ近く配置しているか

スループットは画一的に評価できない．(大体こういうのは何かしらとトレードオフあるイメージ)． 各GCアルゴリズムによってこのスループットがどういう意味を持つのかは後の章で語られそう．

参照局所性を高めるとキャッシュメモリに読み込まれる確率が上がるので，レイテンシが下がるというやつ．(プログラムの最適化とかでこの話はよく聞く)

今回は以上．

所感

大学の授業で似たような話は既に習ったので特に詰まることはなかった．気になった部分もこの先の章で詳しく語られそう．

読みながら，言語のRuntimeがやるべき部分とハードウェアがやるべき部分の境目がイマイチ分からないなと感じたが，監修者まえがきで．

GC をサポートするハードウェアはほとんどないのが現実です。ハードウェアサポートすれば確実に性能が上がるのに残念です。

という言葉を見たので，ほとんど言語処理系が頑張っているんだろうなと思う．

次回

taxio.hatenablog.com

  1. オブジェクトのサイズや種類↩