Langphilia! / Seminars / Garbage Collection
{Richard Jones, Rafael Lins}, GARBAGE COLLECTION Algorithms for Automatic Dynamic Memory Management. John Wiley & Sons Ltd, 1996.
（訳注） このページは、上記の本の第1章までをてきとーに訳したものです。 原文の著作権は、原著者にあります。このページの著作権は私にあります。 翻訳許可はもらっていません。
この本はGCの本です。 GCとは、プログラムが利用し終わったヒープ領域を自動的に回収するものです。 昔も今も、メモリは限られた貴重な資源です。 コンピュータの初期、VLSIが現れるまでメモリは高価で、 Unixのような時分割OSでもたった64KBのセグメント1つで動くことが望まれました。 今日、SIMMは比較的安価でインストールも簡単ですが、 プログラムはメモリ資源をますます浪費するようになっています。 MS Windows 95は1ユーザのPC用OSなのに、 快適に利用するには12MB以上のRAMが必要です。 つまり、メモリだけでPCのコストの半分かかるくらいです。 他の大事な資源同様、メモリは注意深く管理し、 不要になったら再利用する必要があります。
多くのプログラムのメモリ要求は単純で予測可能です。 そのようなプログラムのメモリ割り当て・解放は、 プログラマやコンパイラが効率良く行なうことができます。 しかし、非常に大きく複雑になったプログラムもあります。 LispやPrologのような言語では、 複雑に絡み合った大きなデータ構造が良く使われます。 関数型や論理型の言語には複雑な実行パターンがあります。 このため、多くのデータ構造の生存期間は実行時に決定し、 プログラマやコンパイラが決定することはできません。 自動的なメモリの回収が必須です。
GCの重要性の拡大は、 計算機科学コミュニティにおける議論に反映されています。 論文誌や国際会議における論文ばかりか、 1990, 1991, 1993年のObject-Oriented Systems, Languages and Applications (OOPSLA) ではGCに関するワークショップが開催され、 1992年と1995年に国際ワークショップのトピックになりました。 また、Usenetニュースグループでも良く話題になります。
オブジェクト指向は、今日の分析・設計・プログラミングにおいて 強い関心を集めている分野です。 良いソフトウェア工学の鍵は複雑さを制御することです。 オブジェクト指向はこの目標を達成する方法の1つであり、 明確に定義されたインタフェイスを通じて作用し合う オブジェクトに抽象をカプセル化するものです。 プログラマによるメモリ管理は、オブジェクト指向のモジュール性を阻害します。 このため、Smalltalk, Eiffel, Java, Dylanなど ほとんどのモダンなオブジェクト指向言語はGCをサポートしています。 今日では、Modula-3やOberonなどシステムプログラミング用の言語さえ このような健全だが実践的な理由からGCをサポートしています。 CやC++など不親切な言語にもGCライブラリが存在します。
GCに関する文献は多い。 GCについて書かれた論文誌の記事、本の章、国際会議の発表、 技術報告書、博士論文は軽く千を越えます。 それなのにGCには多くの迷信が存在します。 「GCが必要なのはLispと関数型言語だけだ。 インタプリタに必要なだけでコンパイラには要らない。 GCのオーバヘッドは重すぎる。」 −そう、奴らは馬鹿に違いない！ （奴らって誰？） 2つの帰結が出てきます。
本書の目的は、GCに関する経験の蓄積を 単純でとっつきやすい統一的な枠組に組み入れることです。 宣言的・手続き的なプログラミングスタイル、 並行・分散アーキテクチャにおける最先端の技術を説明し比較します。 重要なアルゴリズムは詳細に解説し、 特徴的な機能を図や動作で示します。 アルゴリズムの｛複雑さ、性能、応用性、 関連アルゴリズムとの関係｝も示します。
本書のサーベイは
第1章はメモリ管理の変革とメモリ自動回収の必要性から始めます。 次にヒープ中のオブジェクトの表現を説明し、 GCの異なる戦略を比較する基準について議論します。 最後に本書の疑似コード表記を説明します。
第2章では3つの古典的なGC ｛参照数え (reference counting)、mark-sweep、copying｝方式を紹介します。 これらの方式を既に知っている読者はこの章をとばして下さい。
次の4つの章では、これらの方式とmark-compact方式を詳細に解説します。
各章の終りにポイントをまとめてあります。 これらのまとめは、GC方式を選ぶために 方式、クライアントプログラム、OS、アーキテクチャについて 疑問を解消するのに役立つでしょう。 これらは読者からの疑問を想定しています。 しかし、まとめは各章を読む代わりにはならず、 答が書いてあるわけではありません。 さらに、前の方の章で紹介するGC方式は後の方の章で参照することになります。 単純な実装の特徴や性能は、同じ方式の最先端の実装を計る参考になります。 これらのまとめが単なるお料理本ではなく、 さらなる分析に役立つことを望みます。
本書に欠けているものも明らかにしておくべきでしょう。
最後に、精力的な研究者はオンラインの文献データベースを眺め回し、 他のGCに関する論文を見つけるでしょう。 本書は批判され、無視され、ゴミの山に埋もれ、 焼かれて、海に投げ込まれるかもしれません。 健全なGCの疑問は上がり続けるでしょう。 言語戦争はまた別のものです！ （分かるような分からないような）
GCについて千を越える論文があると既に述べました。 本書の最後の参考文献リストはかなり短くしたものです。 しかし、完全なデータベースが下記からたどれます。
http://www.ukc.ac.uk/computer_science/Html/Jones/gc.htmlこの参考文献リストは概要とオンライン論文へのURLを含みます。 Richard Jonesはこのリストを更新し続け、 文献の追加（BibTeXフォーマットが望ましい）や 存在する論文のURL（と訂正）を歓迎します。
本書で示すコード片の訂正を歓迎します。 Donald Knuthのようにエラー報告に現金を出すまでは行きませんが、 上記ウェブサイトに正誤表があります。 報告は電子メール R.E.Jones@ukc.ac.uk または Richard Jones, Computing Laboratory, University of Kent at Canterbury, Canterbury, Kent, CT2 7NF, UK にお願いします。 （訳の訂正は takagi@ueda.info.waseda.ac.jp へ。）
（省略）
「Lispの最も大きな影響の1つは言語機能ではなかった。 GCと呼ばれる、システムによる自動メモリ管理技術だった。」
Jean E. Sammet
Programming Languages: History and Fundamentals, 1969
ここ十数年でGCの時代がやって来ました。 かつてはLispと関数型言語に限定されていましたが、 今日GCは宣言型だけでなく手続き型のモダンなプログラミング言語の多くでも メモリ管理システムの重要な位置を占めています。 GCは遅くてプログラムの対話性をぶち壊すという意見がありましたが、 モダンな実装技術はGCのオーバヘッドを大幅に減らし、 Cなど古典的な言語でさえヒープのGCが現実的な選択肢となりました。
最もへぼいコンピュータでもメモリサイズが大きくなっているのに、 メモリを使い切れないということはありません。 他の限られた資源同様、メモリも注意深く保持し再利用する必要があります。 今日多くのプログラミング言語でプログラマがメモリを割り当て・解放し、 プログラム文面上のスコープに縛られない 生存期間を持つデータを扱うことができます。 このようなデータは動的に メモリを割り当てると言います。 動的メモリはプログラマが明示的に管理し、 組み込みまたはライブラリの手続きを呼び出すことによって メモリを割り当て、不要になったメモリを解放 することができます。 （この本では、動的メモリとはヒープのことであり、 スタックは動的に割り当てるとは言わない。）
手動回収による動的メモリ管理はあまり嬉しくありません。 もう1つの方法は、動的メモリ管理を実行時システムに任せることです。 プログラマはまだ動的メモリ割り当てを要求しなければなりませんが、 そのメモリがいつ不要になるかを決定する必要はなくなります。 不要になったメモリは自動的に再利用されます。 GC とは正に動的メモリ割り当ての自動管理です。 reference countingなど直接方式 と tracingなど間接方式 を区別したがる人もいます。 しかし、GCという言葉は広く動的メモリ割り当ての自動管理を指して使われるので、 本書でもreference countingとtracingの両方を指します。 本書ではGCとプログラムの「本当の」仕事をする部分を区別します。 Dijkstraの用語に従い、ユーザプログラムをmutator と呼びます。 GCに関する限り、mutatorの仕事はヒープ中に生存するデータ構造の グラフ接続を変更するだけだからです。
本章では3つの疑問に答えます。 GCが解決する問題は何か？ GCのコストはどれくらいか？ 異なるGCアルゴリズムを比較するパラメタは何か？ また、GCの分類を概観し、以降の章で使う表記を説明します。 まず、プログラミング言語とメモリ管理の実装の歴史を 1940年代から現在まで簡単に眺めてみましょう。
プログラミング言語の発展の歴史は、より一層の抽象化を提供し、 それまで手動で明示的に行なっていた動作を自動化するものでした。
コンピュータの初期、プログラマとマシンはビット単位の 単純な入力スイッチを通してコミュニケーションをとっていました。 間もなく単純な入出力装置が現れ、 オペレータとマシンは16進数で簡単にやりとりできるようになりました。 次の段階でプログラマはニモニックコードを使い、 それを機械的に2進表現に落とせるようになりました。 まだ、ユーザはプログラムの実行の隅々まで責任を負っていました。 例えば、特別な注意を払ってプログラムのワード数を数え、 命令の絶対アドレスを知り、プログラムをロードするスペースがあるかとか ジャンプ先を特定する必要がありました。
1940年代後期から1950年代初期までに、この面倒な帳簿つけは マクロコードとアセンブリ言語へと代わりました [Metropolis et al., 1980]。 シンボリックなプログラムは、 アドレスや演算子が数字のコードより意味のある記号コードに変わっており、 機械語プログラムよりも書きやすく理解しやすいものでした。 しかしまだ、プログラマは特定のコンピュータの動作と 機械のどこでどのようにデータを表現するかに密接に関わっていました。 数多くの機械依存の詳細を知らなければ、 アセンブリ言語できちんとプログラミングすることはできませんでした。
これらの問題を解消する高級言語のアイデアは プログラミングを単純にしようとするもので、 1940年代半ばから後期にかけて生まれました。 1952年までに最初の試作コンパイラが現れ、 1957年初めに最初のFortranコンパイラが発表されました。 高級言語のコンパイラは、ターゲットマシンの資源を割り当て、 ユーザプログラムの扱うデータオブジェクトを表現しなければなりません。 メモリ割り当てには3種類の方法があります （静的割り当て→スタック割り当て→ヒープ割り当ての順に 柔軟性とコストが高くなる）。
最も単純な割り当て方針は静的割り当てです。 プログラム中の全ての名前は翻訳時にメモリ中の場所に束縛され、 実行時に束縛が変わることはありません。 このため、手続きの局所変数は手続きが実行される度に同じ場所に束縛されます。 静的割り当てはFortranの最初の実装方針であり、 現在でも例えばFortran 77や並列言語occamに使われています （正誤表より：occamは静的割り当てではない）。 静的割り当てには3つの制限があります。
しかし、静的割り当てには2つの重要な利点があります。
最初のブロック構造言語は、1958年に現れたAlgol-58とAtlas Autocodeでした。 ブロック構造言語は、スタック上のメモリ割り当てによって 静的割り当ての制約をいくつか解消しました。 手続きが呼び出される度に活性レコード (activation record) またはフレーム (frame) がシステムスタックにプッシュされ、 手続きから戻る時にポップされます。 スタック構成は5つの特徴を持ちます。
スタックはLIFO原則なのに対して、 ヒープ中のデータ構造は任意の順序で割り当て・解放できます。 従って、活性レコードと動的データ構造は親手続きの外で生存できます。 ヒープ割り当てには多くの長所があります。
今日ほとんどの高級言語はスタックとヒープの両方にメモリ割り当てができます。
プログラムが直接操作できる値は、プロセサのレジスタ内、 スタック上（局所変数と一時変数を含む）、大域変数内にあります。 これらの場所は、計算の根 (roots) となる ヒープデータへの参照を保持しています。 自動ヒープ管理を行なうには、プログラマが特定の規則に従う必要があります。 ユーザプログラムが動的割り当てデータへアクセスするには、 根を通すか、根からポインタの連鎖をたどらなければなりません。 プログラムは、ヒープの底から勝手なオフセットをとるなどして ヒープ空間にランダムアクセスしてはいけません。 この制限はGC特有のものではありません。 Pascalなど強く型付けされた言語でもこの規則があります。 Cの明示的なmalloc/free割り当て機構を安全に使うにも、ユーザプログラムが メモリの割り当てられていない領域にアクセスしない必要があります。 （GCには制約があるが、安全性のために必要な制約である。）
ヒープ中に割り当てられた個々のデータ片を、 節 (node), cell, object（注1）とか呼びます。 前述の規則の帰結として、ヒープ中のオブジェクトグラフの生存は ポインタ到達可能性 (pointer reachability) によって定義されます。 ヒープ中のオブジェクトが生存しているのは、 オブジェクトのアドレスが根に保持されている場合、 または生存している他のヒープ節が そのオブジェクトを指すポインタを保持している場合です。 もっと形式的に、→を「を指す」関係とします。 任意の節または根Mと任意のヒープ節Nについて、 M→NとはMがNへの参照を保持していることです。 ヒープ中の生存節の集合は、この関係下における根からの 遷移的参照閉包 (transitive referential closure) です。 即ち、次の集合live の極小集合（注2）です。
live = {N ∈ Nodes | (∃r∈Roots . r→N) ∨ (∃M∈live . M→N)}
ただし、この生存ヒープセルの集合は、 実際にプログラムからアクセスされ得るセルの集合の保守的な近似に過ぎません。 ｛最適化コンパイラのプログラムテキスト解析やデータフロー解析 によって死亡と確認されるセル｝が含まれるかも知れません。 典型的な例として、手続きの中で使い終わった局所変数、 スタックフレーム中の初期化されないスロット、 （削除するコストを惜しんで）レジスタに残った無効ポインタが含まれます。 この疑問に対する答えは本章の後の方と、 第9章で保守的なGC技術を考慮する時に後述します。
節の生存は直接間接に決定できます。 直接法は各ヒープ節について、 他のヒープ節や根からの全ての参照を記録する必要があります。 最も有名な直接法は、セルを指すポインタの個数 ＝参照数 (reference count) をセル自身に保持しておきます。 分散システムの直接法なら、各オブジェクトへの参照を保持した 遠隔プロセサのリストで代替することもできます。 いずれにせよ、これらの記録は mutatorがヒープ中のグラフ接続を変えるのに合わせて更新しなければなりません。
間接または追跡 (tracing) 法は、普通 ユーザプログラムのメモリ要求が失敗する度に生存節の集合を計算し直します。 GCは根から始まり、ポインタをたどって全ての到達可能節を訪れます。 訪れた節は生存していると考えられ、 その他の節が占めるメモリは再利用可能とされます。 十分なメモリが回収できれば、ユーザプログラムは要求を満たされて再開します。
伝統的に、ほとんどの手続き型言語はヒープ中のオブジェクトの 割り当て・解放の責任をプログラマに負わせてきました。 Pascalでは、new手続きによってヒープ中のメモリが割り当てられます。 ポインタ変数pがある時、new(p)は ｛pが指すと宣言された型｝のオブジェクトに新しくメモリを割り当て、 このオブジェクトをpが指すようにします。 このオブジェクトはdispose(p)を呼び出すことによって解放 されます。 次ページのアルゴリズム1.1のプログラム片は、リスト[1,2,3]を作ります。
+--+--+ +--+--+ +--+--+
myList--->| 1| -+->| 2| -+->| 3| /|
+--+--+ +--+--+ +--+--+
動的に割り当てられたメモリは到達不可能になることがあります。 生存していないが解放されてもいないオブジェクトは ゴミ (garbage) と呼ばれます。 解放が明示的な言語では、ゴミは再利用できません。 その空間は洩れて (leaked ) しまいます。 次ページのアルゴリズム1.1のプログラムでリストが作られた後に 次の1行を加えると、メモリリークが発生します（図1.2）。
myList^.next := nil;
+--+--+ +--+--+ +--+--+
myList--->| 1| | | 2| -+->| 3| /|
+--+--+ +--+--+ +--+--+
すると、プログラムはリストの第1要素にしかアクセスできなくなります。 アイテム2と3を保持したメモリはプログラムの到達範囲から外れ、 使うことも回収することもできません。 自動メモリ管理ならアクセス不可能なメモリを回収できます。 それが本書の主題です。 （Cなどの明示的なヒープ管理ではメモリリークが大問題で、 専用デバッガも常識。）
program pointer(input, output);
type ptr = ^cell;
cell = record
value : integer;
next : ptr
end;
var myList : ptr;
function Insert (item : ingeger; list : ptr) : ptr;
var temp : ptr;
begin
new(temp);
temp^.value := item;
temp^.next := list;
Insert := temp
end;
begin
myList := Insert(1, Insert(2, Insert(3,nil)))
(* ; myList^.next := nil --- 第2,3要素が到達不可能になる *)
end.
まだ参照されているメモリが解放されてしまうこともあります。 アルゴリズム1.1に次の1行を加えてアイテム2をヒープマネジャに返してしまいます。
dispose(myList^.next);この場合もアイテム3はゴミになりますが、 この小さなプログラムではそれほど害はありません（図1.3）。 しかし、アイテム1のnextフィールドは解放されたメモリを参照しています。 宙ぶら参照 (dangling reference) が発生しました。
+--+--+ -- -- +--+--+
myList--->| 1| -+->| | +- | 3| /|
+--+--+ -- -- +--+--+
プログラムは解放されたメモリに触れる権利を持ちません。 従って、帳簿情報の保持と再利用はヒープマネジャの仕事です。 プログラムが宙ぶら参照をたどると、良くて即座にクラッシュします （情報を破壊しつつ動き続けるよりはマシ）。 ヒープマネジャが解放されたメモリをプログラム中の他のデータ構造に割り当てると、 1つの場所が2つの異なるオブジェクトを表すことになります。 運が良ければ、プログラムはいつかクラッシュするでしょう。 運が悪ければ、プログラムは動き続け、間違った結果を吐き出します。
ゴミと宙ぶら参照は、明示割り当ての裏表です。 ゴミができるのは、オブジェクトが解放される前に参照がなくなる場合です。 宙ぶら参照ができるのは、参照の残っているオブジェクトが解放される場合です。 参照を壊すのと同時に参照先を解放すれば両方の問題を解消できます。 しかし、共有があるのでこれは簡単ではありません （単一参照が保証されていれば簡単）。
2つのリストが尾を共有しているものとします（図1.4）。 行儀の良いリスト解放ルーチンは、リストの先頭を指すポインタが壊れた時 リストの各アイテムを再帰的に解放するものでしょう。 しかし、catかmatのどちらかがこのように破壊されると、 他方はアイテム1つと宙ぶらポインタになってしまいます。 この問題は1950年代後期の自動メモリ回収技術の焦点となりました [McCarthy, 1981]。
+--+--+ +--+--+ +--+--+
cat--->| c| -+--+->| a| -+->| t| /|
+--+--+ | +--+--+ +--+--+
|
+--+--+ |
mat--->| m| -+--+
+--+--+
複雑なプログラムの動的メモリを正しく管理して 明示的に割り当て・解放するのは難しく、 プログラム故障の大きな要因となります。 プログラムは予期せずクラッシュし、 サーバは良く分からない理由でメモリ範囲を越えます。 このようなプログラミングエラーの結果は、 特にマルチスレッド環境では、不確定です。 ヒープマネジャがこのようなオブジェクトを再割り当てしなければ、 宙ぶら参照は無害です。 テストや通常使用では現れないメモリリークも起こるかも知れません。 故障は普通、プログラムがストレス状態にあったり 長期間動き続けていたりする時の表層に過ぎません。 例えば、コンパイラへの入力が機械生成され、 プログラマが正しく書くと期待されているような コードの形式を破っているかも知れません。 開発マシンでコードが実行されても、 メモリリークは気づかれないで残るかも知れません。 しかし、メモリの少ないマシンや長期間動き続けるサーバで実行されると、 そのコードはメモリを使い果たします。 このような状況下でのデバッグは難しく、 故障には再現性がありません。
GCは必須だったり単に要望が強かったりします。 言語の要求かも知れません。 データ構造が親手続きよりも長く生き伸びるには、ヒープ割り当てが必要です。 これらのデータ構造は別の手続きや関数に渡され、 安全に解放できる点をプログラマやコンパイラは決められないことがあります。 共有や｛中断の遅延実行｝があるので、 特に関数型言語では実行順序が予測不可能であるのが普通です。 GCは必須です。
GCが問題の要求であることもあります。 [Boehm and Chase, 1992] には分かりやすい説明があります。 汎用スタックデータ型をCのリストで実装するものとします。 スタックの各ノードはdataとnextという2つのポインタフィールドを持ちます。 Pop操作はスタックの先頭firstを解放し、 スタックの続きを指すポインタを返します。 この時、Popは先頭の要素first->dataを解放すべきでしょうか？ そのデータが静的に割り当てられていた場合、答えはNOです。 動的割り当てでそのデータへの参照が他になければ、答えはYESです。 そのデータが複数のスタックにプッシュされていたら（図1.5）、答えは何でしょう。 これほど単純な場合でも、解放に関する規約が必要です。 応用性を減じてスタックのインタフェイスを複雑化するか （GCの実装と同じ手間）、 不要なコピーを行なって解放を局所的なものにするか （単一参照の保証 vs GC）になります。
ソフトウェア工学は、大規模ソフトウェアシステムの複雑性を管理するのに 最も明解な答を出します。 ソフトウェア技術者の持つ最も強力な2つのツールは、抽象化とモジュール化です。 明示的なメモリ管理はこの原則を妨げるものと私たちは固く信じています。 自動メモリ管理は抽象化を後押しします。 メモリ割り当てモデルが高級になり、 プログラマは帳簿つけの負担を負わずに済みます。 プログラマは高級な設計の詳細や問題の実装に時間を使えるでしょう。 また、実行時システムによるメモリ管理は、 高級言語の静的・スタック割り当てに適合しています。 このような低級な問題の抽象化は、 大域的・スコープ付きのデータに本質的な問題として 高級言語の設計者に広く認識されています。 大域データをどこに置くかとか、 スタック上の手続き活性フレームをどのように用意・始末するかを プログラマが気にする必要はありません。 複雑なプログラムのヒープ割り当てデータにも このような抽象化を適用すべきだと私たちは信じています （静的・スタック割り当ては既に抽象化されているのだから、 ヒープ割り当ても抽象化すべき）。
信頼できるコードは理解できるコードです。 モジュールレベルで言うと、プログラマはモジュールの振舞いを理解するのに そのモジュールだけ、あるいは最悪でも近傍のモジュールを調べれば済むべきです。 プログラム全体を理解しなければモジュール1つ開発できないのでは困ります。 複数の開発チームが参加するような大規模プロジェクトでは、 この条件が本質的なのは明らかです。 対照的に、明示割り当てではあるモジュールのメモリリークによって 他のモジュールが故障する可能性があります。 モジュールの振舞いは使用される文脈に依存してしまいます。
良く引用される目標として、 ソフトウェア部品をハードウェア部品のように組み合わせるには、 インタフェイスが単純できちんと定義されている必要があります。 拡張可能なモジュールは簡単に他のモジュールと組み合わせられるでしょう。 違う言葉で言えば再利用可能なモジュールです。 また、組み合わせられるモジュールが増えるにつれて プログラムの保守が容易になります。 Meyerの提案によると、モジュールはなるべく少数のモジュールを相手に、 なるべく少量の情報をやりとりすべきです [Meyer, 1988]。 Wilsonの正しい観察によると「生存性は大域的な 属性」です [Wilson, 1994]。 帳簿つけの詳細をモジュールのインタフェイスに含めると、 モジュールの抽象性と拡張性が弱くなります。 モジュール機能の変更はメモリ管理コードの変更を伴うかも知れません。 生存性は非局所的な性質なので、 帳簿つけコードの変更は開発されるモジュールの外部に及ぶでしょう。
大域的で明示的な動的メモリ管理は、 段階的詳細化による階層設計から作られたモノリシックなシステムでは 効率的で妥当かも知れませんが、 オブジェクト指向の哲学から外れています。 これは通信最小の原理に反し、インタフェイスを混乱させます。 オブジェクトが異なる文脈で再利用されると、 新しい文脈はこれらを組み合わせる規則を知らなければなりませんが、 これではオブジェクトの組み合わせの自由度が低くなります。 ある著者によると、 複雑なシステムにおけるメモリ管理の問題はGCがなければ、 正しくメモリ管理を行なうよう設計されたプログラムの最大の 目標となる でしょう [Nagle, 1995]。 一方GCは、メモリ管理の問題とクラスのインタフェイスを切り離し、 メモリ管理コードが散らばるのを防ぎます。 このため、GCは多くのオブジェクト指向言語の基本部分となっているのです。
メモリ管理の問題の広がりを示すものとして、 ヒープメモリ利用の正当性を検証するツールの隆盛があります。 最も有名な例はCenterLine [CenterLine, 1992]とPurify [Purify, 1992]です。 この種のツールが出回っているのは、 正しいメモリ管理の重要性と難しさを示しています。 しかし、これらのツールは実践的にデバッグに役立つだけであり、 プログラム実行時に無視できないオーバヘッドがかかります （CenterLineインタプリタでは50倍、 Purifyリンク時ライブラリでは2から4倍 [Ellis, 1993]）。
これらのツールはプログラミングエラーを追跡するのにとても役立ちますが、 問題の本質を指し示してくれる訳ではありません。 デバッグツールは複雑なシステムのインタフェイスを単純化したり、 ソフトウェア部品の再利用性を高めてくれたりはしません。 メモリリークや宙ぶら参照を見つけた後に、 労力をかけて｛実装を、あるいは悪くすると設計から｝直さなければなりません。 デバッグツールは病巣ではなく症状に立ち向かっているのです。 一方GCは効果的なソフトウェア工学ツールであり、 メモリ管理エラーが起こらないことを保証することによって プログラマをエラーの発見作業から解放します。
Rovnerの労作によると、 開発時間の大きな部分がメモリ管理のバグに費やされます [Rovner, 1985]。 その概算によると、 Mesaシステムの開発時間の40%がメモリ管理に費やされました（注3）。 今日、オブジェクト指向言語はますます使われるようになっています。 これらの言語で書かれたプログラムは、伝統的な手続き型言語に比べて 多くのデータをヒープに割り当てます。 オブジェクト指向プログラムの生むデータ構造と問題はしばしば複雑です。 これらの要因がますます明示的なメモリ管理を難しくしています。
設計者とプログラマは、明示的な動的メモリ管理の複雑さを克服するのに 過剰防衛的な傾向があります。 データを静的に割り当て、モジュール間で共有する代わりにコピーし、 モジュール毎にそのコピーを破壊・解放することによって、 大域的な生存性を局所的に変換します。 不要なコピーと静的割り当ては良くても必要メモリの見積りを高くし、 空間を浪費することになります。 悪ければ静的上限の設定が不十分でプログラムが故障します。
良く採られる選択肢は、領域特有のGCを作ることです。 しかし、領域特有のGCが進んだGC技術に勝ることは多くありません。 応用性が限られているので、 幅広い応用によって開発コストを償却することができません。 このため、テストも十分に行なわれません。 Wilsonによると、これら不十分なGCが多いことは GCの重要性を明らかにしています [Wilson, 1994]。 GCは「ネジ止め」ではなくシステムの一部であるべきです。
GCはあらゆる言語のあらゆる問題を解決する訳ではありません。 動的割り当てが単純なプログラムは、 明示割り当ての方が実行時のコストが低いかも知れません（注4）。 しかし、複雑なプログラム中に再利用される 単純な問題を解決することに傾注しましょう。 短期的な利益は長期的にはコストをもたらすかもしれません。 問題の性質はGCでは解決できないものかも知れません。 厳しいリアルタイムシステムでは、 メモリ要求や消費時間の上限を保証する必要があります。 厳しいリアルタイムプログラミングにおけるGCの問題は、 まだ特殊なハードウェアを使わなければなりません。
また、GCはあらゆるメモリ管理の問題を解決する訳でもありません。 GCには時間と空間とのコストがかかり、次の2つの節でそれを紹介します。 さらに、GCは明示的なメモリ割り当ての2つの古典的なバグ ＝宙ぶらポインタとメモリリークを排除できますが、 他のエラーには弱く、またGC特有のデバッグ問題も現れます。
GCは、際限なく増殖するデータ構造の問題を解決しません。 DetlefsとKalsowの報告によると、 このようなデータ構造は「驚くほど多く」、 例えば再計算を避けてキャッシュされる中間結果などがあります [Detlefs and Kalsow, 1995]。 このような増殖はテスト段階や短期間の使用では無害で、 プログラムはメモリを使い切る前に正常終了します。 しかし、長期間動くサーバにこのコードが使われると、 問題は大きくなりプログラムはクラッシュします。
前述したように、GCの最大の利点は抽象化をサポートし、 ソフトウェア部品のインタフェイスを単純化することです。 不幸なことに、オブジェクトの具体表現がヒープデータを参照しているのに 抽象表現がそうでない場合、この抽象化は別のエラーの源を隠してしまいます。 最もありそうな例は、ヒープ割り当てデータへの参照のスタックが 配列として実装される場合です。 Popは何をすべきでしょうか？ スタックの抽象表現に従えば、 スタックトップが指すヒープオブジェクトへの参照を返し、 スタックポインタをデクリメントするでしょう。 しかし、これだとヒープデータは、スタックの具体表現である 配列からアクセス可能なまま残ってしまいます（図1.6）。 安全な解によるPopは、ヒープデータへの参照を返す前に スタックトップにあるポインタをnullにすべきです。
tracing GCは、プログラムスタックを含む計算の根から ポインタをたどって生存データを識別します。 不幸なことに、スタックは無効なポインタで汚染されていることがあります。 無効なポインタを追跡すると、メモリリークが起きます （スタックに無効なポインタが残っていると、 ゴミが生存データと見なされ、GCされない）。 スタックフレームの汚染を防ぐ1つの手段は、 局所変数を使い終わったらnullにしておくことです。 しかし、フレームの死亡後に無効なデータが 別のフレームに残るかもしれません。 手続きAが手続きB, Cをこの順に呼び、 Bはスタックフレーム中にヒープデータを指すポインタxを持つものとします。 フレームの始末は高価なので、Bがフレームを始末せずに終了し、 そしてCがスタックフレームにxと重なる作業空間を予約し、 この作業空間が初期化されないと、ヒープオブジェクトは再び到達可能になります。 復活！ この問題は保守的なGC実装者に広く知られていますが（第9章）、 DetlefsとKalsowの指摘によると、xは全く正しいポインタであり もっと根の深い問題です [Detlefs and Kalsow, 1995]。 通常、xを保持する作業空間は次の収集までに使われるので、 この種のエラーはそれほど深刻ではありません。 しかし、DetlefsとKalsowによると、マルチスレッド環境は特に スタックフレーム汚染によるメモリリークに弱く、 前述の例で言うとCを実行中のスレッドがブロックされ、 xが上書きされるまでに収集が行なわれる可能性があります。 （xの参照先が到達可能とされた後、 xが上書きされてメモリリークが発生。 だが、その次のGCで回収されるのでは？）
DetlefsとKalsowの作ったツールは、 Modula-3プログラムにおけるこの問題を検査するものです。 Modula-3は強く型付けされた言語であり、 各ヒープオブジェクトに型がタグ付けされます。 そのツールはヒープ割り当ての型を見たり、ヒープ利用状況の型と 呼び出しサイト（ubiquitousな型があるので）を見たりできます。 また、プログラマは選択した1つの根から到達可能なオブジェクトを識別したり、 あるオブジェクトが到達不可能であることを言明したりできます。 言明が偽の場合、ツールは根からそのオブジェクトへのパスを表示します。
GCはプログラム実行に大きなオーバヘッドをかけるという意見があります。 過去、この意見が正しいアプリケーションもありましたが、 そのコストはシステムに強く依存していました。 例えば1970年代から1980年代初期にかけての研究によると、 大きなLispプログラムは実行時間の40%までGCが占めていました [Steele, 1975; Foderaro and Fateman, 1981; Gabriel, 1985]。 比較できる場合、GC付きの言語で書かれたプログラムは 伝統的な言語で書かれた同等プログラムよりも遅いのが普通でした。 GCは明らかな槍玉にあげられました。 しかし、これらの言語の実装が遅いのはGC以外の理由も多く、 引数渡しの仕組みが非効率であったり、 高階関数や式の遅延評価をサポートしているせいであったりしました。
モダンな技術はGCのオーバヘッドを大幅に減らし、 Modula-2+やModula-3などシステムプログラミング用の言語さえ GCをサポートするようになりました。 自動メモリ管理のコストはアプリケーションや言語に強く依存しており、 そのオーバヘッドを単純に計算することはできません。
これらの条件を考えて、GCの実行時間は数%から20%程度になります。 平均して、きちんと実装されたシステムで10%と言えるでしょう [Wilson, 1994]。 しかし、GCのオーバヘッドに関する単純な数字は 用心して受け取る必要があります。
異なるGCアルゴリズムの比較は、原理的にも実践的にも難しいことです。 アルゴリズムの複雑さの公式は決定できますが、 定数や実装の詳細が実際の性能に大きな影響を与えるからです。 本書では異なるGC技術を幅広くサーベイします。
困ったことに、これらは独立なパラメタではありません。 さらに、異なる文献の結果は異なるマシン、 異なるCPU、異なるOSで採られたものです。 アルゴリズムの実装法は、 全体の性能にデリケートな予期しない影響を及ぼします。 回収サイクルの実行時間は、ヒープ中の生存データの トポロジーや量に依存する部分があります。 単純にヒープの大きさやオブジェクトのレイアウトを少し変更するだけで、 回収の間隔が変わり、従って生存グラフも変わってしまいます。 データへのアクセスパターンが変われば、 ディスク・メインメモリ・キャッシュへのアクセスも変わります。 グラフの渡り歩き・コピーの順序は、仮想メモリの振舞いに影響を与えます。 設計における1つの選択の影響を議論するには、 「他の全ての要因は等しい」ことが望ましいのですが、 現実的にはそんなことはほとんどありません。
しかし、GCアルゴリズムを選択する時に考慮すべき原則は考えられます。 ★GCは安全 (safe) でなければなりません。 生存データが誤って回収されるようなことがあってはいけません。 しかし、ある種のGCはポインタ到達可能性の不変条件を無視する 過激な最適化コンパイラと競合する危険があります。 このことは第9章の保守的なGCのところで議論します。
★GCは包括的 (comprehensive) であるべきです。 ゴミは回収されずヒープ中に残るべきではありません。 しかし、GC方式によって包括的な回収のアプローチはさまざまです。
プログラマはプログラム実行中のGCのオーバヘッドを知りたいでしょう。
漸次 (incremental) GCは、GC中もmutatorを中断させません。
GC全体の時間と中断時間以外にも考慮すべき時間要素があります。 対話的なリアルタイムの反応には、中断時間の上限だけでは不十分です。 mutatorの満足な進捗のためには、どんな間隔でも GCに費やす時間の割合が一定であることも重要です。 （バッチ処理vs時分割処理。 任意の時間をとると、GCにかかる時間が全体に比例していること。）
ヒープ中に新しいデータを割り当てるコストも、 ゴミを回収する時間と同じくらい重要です。 一般に、分断されたヒープの割り当てはまとまったヒープより高価で、 新しいオブジェクトが収まる大きさのフリーメモリを探し回る必要があります。 全てのデータが同じ固定サイズの場合、 不定サイズのオブジェクトを割り当てるよりも簡単です。 分断されたヒープ中に可変サイズのデータを割り当てる問題はGC特有ではなく、 明示的・自動的な全てのヒープ管理システムに共通のものです。
自動メモリ管理は、ポインタ書き込みなどmutatorの操作に 直接オーバヘッドを課すことがあります。
GCの役割は普通、mutatorがヒープを使い果たした時に メモリを回収することです。 しかし、GCは独自の目的で追加メモリを要求し、 空間オーバヘッドが必要だと考えるかも知れません。 GCはヒープ中のセルに参照数やマークビットを付け、セルの生存や （移動GCなら）そのセルの新しいアドレスを記録するかも知れません。 また、GCは｛そのセルに格納された全てのポインタの場所｝が 分かる情報を必要とするかも知れません （もっとも、この情報はmutatorも必要とすることが多く、 その場合はGCのオーバヘッドではありません）。 （そのセルに格納された＊ことのある＊全てのポインタ？ それともコンスの2つのポインタ？） （ポインタ値のハッシュみたいなものか？ 参照先がどの世代かとか。）
また、GCはヒープデータ構造の渡り歩きスタックなど 固有の追加データ構造を使うかも知れません。 copying GCは移動なしのGCに比べて余分なアドレス空間を要し、 現在ヒープの占めるメモリ領域から全ての生存データを拾い集めて 新しい領域にコンパクトにコピーします。 ヒープのレイアウトと回収戦略のため、 copying GCは移動しないGCの2倍までのアドレス空間を必要とします。
プログラムのヒープ占有率 (residency ) は普通、定数ではありません。 回収アルゴリズムは占有率に影響するかも知れないし、 しないかも知れません。 参照数GCでは占有率は問題になりませんが、 追跡GCではヒープ占有率が高いほど回収頻度が高くなるでしょう （mutatorのメモリ要求例外が多くなるので）。 占有率が上がるにつれてメモリ管理システムの性能が下がらないことが重要です。
最後に、GCアルゴリズムは一般的な目的であるかも知れません。 その応用性はある種のプログラミング言語、例えば純関数型言語や 論理型言語に束縛されているかも知れません。 あるいは、ある種のプログラミングイディオムに縛られ、例えば ループを成すデータ構造の作成やアクセスが制限されるかも知れません。
これらの要素の多くは互いに関係しています。 時間と空間のトレードオフは計算機科学に共通のものであり、 異なるアプリケーションは異なる要素の優先度を望むでしょう。例えば、
異なるアーキテクチャ・コンパイラ・アプリケーションプログラム に対するGCの移植性も、考慮すべき重要な点です。 他の設計と同様に、保守の容易さも重視すべきです。 コンパイラに密接に結び付いたreference countingなどのメモリ管理は、 もっと単純なインタフェイスを持つ追跡GCなどに比べて保守が大変です。
本書では、このような制約のトレードオフを考慮して 提案された方式を比較します。 どのGC戦略を使うかという疑問に本書が「答え」を出すのではなく、 正しい疑問を見分け、提案されたアプローチを検証するのに 本書が役立つことを望みます。 GCのスローガンは、「自分のシステムの要求を知り、 生成されるデータの性質＝量・型・トポロジー・生存期間を理解しよう」 というものです。 これはGC独自の提案ではありません。 明示割り当てでも言えることです。 明らかに、明示的なメモリ管理を行なうプログラムの性能は、 割り当てられるプログラムの振舞いと利用する割り当て器 の両方を良く理解することによって改善できることが多いのです [Zorn, 1993; Wilson et al., 1995]。
まとめると、GCは ソフトウェア技術者に有用なツールであることを述べました。 GCはある種の問題やプログラミングスタイルに必須であり、 少なくとも他の選択肢に比べて現実的であると私たちは信じています。 GC付きのシステムを経験すれば、 GCが開発時間を削減してくれると分かるでしょう。 少なくとも明示的なメモリ管理と並ぶ選択肢として考慮する価値はあります。 メモリ管理のバグを追う開発時間を、 もっと有益な性能や機能を向上する他の部分に集中できるのですから。
本章の最後として、本書の残りで前提とするヒープの仕組みと ヒープ中のオブジェクトのレイアウトについて説明します。 GCアルゴリズムの説明に使う疑似コードの表記も説明します。
ヒープは連続したワードの配列かも知れないし、 不連続なブロックの集合からなるかも知れません。 ヒープ中のユーザデータはセル、節、 オブジェクト とか呼ばれます。 明らかに、最後の言葉はオブジェクト指向的な意味です （2度も言ってる）。 1つのセルは連続したバイトかワードの配列で、 fields に分かれています （コンスに限らない）。 1つのフィールドはポインタ値か非ポインタ値を持ちます。 非ポインタ値を持つフィールドはatomic です。 これを敷衍して、ポインタフィールドを持たないオブジェクト はアトムと呼ばれます。 プログラムのそれぞれの根から到達可能なヒープデータは、 ｛データセルを節に、ヒープオブジェクトへの参照を枝に｝ 持つ有向グラフを成します。 参照は、ヒープセルのポインタフィールドに格納されます。 これらのグラフは重複しても良いし、互いに素かも知れません。
本書ではヒープを連続したスロットの配列として扱うことが多く、 Heapと書きます。 オブジェクトの大きさが固定のアルゴリズムでは、 1スロットの大きさは普通オブジェクト1個分です。 オブジェクトの大きさが可変の場合、 1スロットの大きさは1ワードです。 ヒープの底はHeap_bottom、ヒープトップはHeap_topと書きます。
一般に、セルは最初のワードのメモリアドレスで参照します （バイトアドレスだとビッグ・リトルエンディアンによって違う）。 セルNに対して、Nのポインタフィールド（の指すアドレス）のリストを Children(N)と書きます。 ｛場合によって、セルの任意のポインタ・非ポインタ フィールドを参照することがあります。 この場合、セルを配列として扱います。 即ち、セルNのi番目のフィールドはN[i]と書きます。 フィールドは0から数えます。｝
セルの直接の子孫を参照するには、 ポインタフィールドを手繰る必要があります。 Cから借りた表記を使います。 即ち、セルNに対して、pがリストChildren(N)のメンバである時、 Nの子供は*pと書きます。 （子供はセル内のフィールド、子孫は参照先のセル。）
（表記の使用例） 図1.7の根のセルはアドレスがnであり、 影つきの2つのフィールドが子供です。 このセルにはヘッダと非ポインタデータフィールドがあります。 4つのフィールドはそれぞれ1ワード長です。 nの子供は2つのセルを指しており、 これら（子孫）のアドレスは*(n+2)と*(n+3)です。
本書ではあらゆるGCアルゴリズムに共通の枠組を用います。 私たちは4つの理由から、実際のプログラミング言語よりも 疑似コードを使うことを選びました。
mutatorの命令セットは、NewとUpdateという2つの操作を行ないます。 Newはヒープマネジャから新しいオブジェクトを貰い、 新しく貰ったオブジェクトの先頭を指すポインタを返します。 Newの引数として割り当てるメモリの大きさを渡すことができます。 固定サイズのオブジェクトしか扱わないアルゴリズムや アルゴリズムが理解しやすくならない場合、 この引数は省略します。
Updateはセルのフィールド値を変更します。 Updateは代入操作の一般化であり、｛変更するフィールドと 新しい値＝普通はポインタかそうでない値nil｝の2引数を取ります （非ポインタ＝アトミックな値はGCには無関係）。
手続き本体の範囲や制御文のスコープは、インデントで表します。 代入操作 = は、複数代入に良く使います。
a, b = b, aは、aとbの値を取り替えます。 Cに従って等号演算子は==ですが、 その他の関係演算子は≦、≧、≠など数学の記号を使います。
セルのフィールドを読んだり変更したりするため、 左辺値を返す手続きを適当に使います。 例えば、セルNの参照数はRC(N)であり、次の文で初期化します。
RC(N) = 1
計算機とプログラミング言語についての初期の歴史は、 [Metropolis et al., 1980]の Donald KnuthとLuis Trabb Pardoを参照すると良いでしょう。 Lispの初期の版では明示的な解放関数eralisが使われましたが、 すぐにGCが取って代わりました [McCarthy, 1981]。
分断されたヒープのメモリ割り当て技術について一般的な説明は、 [Knuth, 1973; Standish, 1980; Bozman et al., 1984; Aho et al., 1986] にあります。 Paul Wilson, Mark Johnstone, Michael Neely, David Bolesは、 明示割り当て技術、特に割り当て器の振舞いに関する分析の失敗 をサーベイしています [Wilson et al., 1995]。