Javaの理論と実践: ガーベッジ・コレクション小史

ガーベッジ・コレクションはどのように機能するのか

Java言語はガーベッジ・コレクションを利用しているプログラミング言語の中では最も広く用いられていますが、最初にガーベッジ・コレクションを利用した言語ではありません。ガーベッジ・コレクションは、Lisp、Smalltalk、Eiffel、 Haskell、 ML、 Scheme、Modula-3など多くのプログラミング言語に不可欠なもので、1960年代初めからずっと使用されてきました。 Javaの理論と実践 の今回の記事で、Brian Goetzはガーベッジ・コレクションの最も一般的なテクニックについて解説します。

Brian Goetz (brian@quiotix.com), Principal Consultant, Quiotix

Brian Goetz は18 年間以上に渡って、専門的ソフトウェア開発者として働いています。彼はカリフォルニア州ロスアルトスにあるソフトウェア開発コンサルティング会社、Quiotixの主席コンサルタントであり、またいくつかのJCP Expert Groupの一員でもあります。2005年の末にはAddison-Wesleyから、Brianによる著、Java Concurrency In Practiceが出版される予定です。Brian著による有力業界紙に掲載済みおよび掲載予定の記事のリストを参照してください。



2003年 10月 28日

ガーベッジ・コレクションの利点は明らかで、信頼性の増加、クラスのインタフェース設計とメモリ管理の切り離し、開発者がメモリ管理エラーを追跡するために費やす時間の減少などです。ダングリング・ポインターやメモリリークというよく知られている問題は、Javaプログラムでは簡単に生じません。(Javaプログラムは、メモリリーク、正確には意図しないオブジェクトを保持することがありまが、これは別の問題です)。しかし、ガーベッジ・コレクションにも、パフォーマンスへの影響、ポーズ、設定の複雑さ、厳密な終了処理といった負担がかからないわけではありません。

ガーベッジ・コレクションのポーズがなく、CPU時間がガーベッジ・コレクションに失われず、ガーベッジ・コレクターが仮想記憶やキャッシュに悪影響を与えず、ヒープがアプリケーションの占有率 (ヒープ占有)より大きい必要がない、といった理想的なガーベッジ・コレクションの実装なんて、目にしたことがないでしょう。もちろん、完璧なガーベッジ・コレクターなんて存在はしませんが、ガーベッジ・コレクターはここ10年で著しく改善されてきました。

オプション-選択肢

JDK1.3には3つの異なるガーベッジ・コレクション・ストラテジーがあり、JDK1.4.1 には6つの異なるガーベッジ・コレクション・ストラテジーと、ガーベッジ・コレクションの設定やチューニングに関する12以上のコマンドライン・オプションがあります。これらはどう違って、なぜこんなに必要なのでしょう。

各ガーベッジ・コレクションの実装は到達可能でないオブジェクトの識別や再生に異なるストラテジーを使用しており、ユーザー・プログラムおよびスケジューラにそれぞれ影響しています。異なる種類のアプリケーションは、ガーベッジ・コレクションに異なる要求をします。たとえば、リアルタイム・アプリケーションは短い限られた期間のコレクション・ポーズを要求するのに対して、エンタープライズ・アプリケーションは高いスループットのために長く予測できないほどのポーズを容認するかもしれません。


ガーベッジ・コレクションはどのように機能するのか

ガーベッジ・コレクションには、参照カウント、mark-sweep、mark-compact、コピーといった基本的なストラテジーがいくつかあります。また、ジョブを徐々に 実行することができるアルゴリズム(ヒープ全体を同時に集める必要はなく、その結果短いコレクション・ポーズとなる)や、ユーザー・プログラムが起動している間に実行することができるアルゴリズム(コンカレント コレクター)などもありますが、ユーザー・プログラムが停止している間に、コレクション全体を実行しなければならないアルゴリズムもあります(いわゆるstop-the-world コレクター)。さらに、JDK1.2以降で使用されている世代別コレクターのようなハイブリッドコレクターも存在しており、異なるヒープの領域で異なるコレクション・アルゴリズムを使用しています。

ガーベッジ・コレクションのアルゴリズムを判断する時は、以下の基準のいずれかあるいはすべてを考慮するようにします。

  • ポーズ時間: コレクターはコレクションを行なうために処理を停止するのか。どれくらい長く。ポーズは制限されるのか。
  • ポーズ予測: ガーベッジ・コレクションのポーズは、ガーベッジ・コレクターよりもユーザー・プログラムに便利にスケジュールされることができるのか。
  • CPUの使用: 利用できるCPU時間のうち何パーセントがガーベッジ・コレクションに費やされるのか。
  • メモリ・フットプリント: 多くのガーベッジ・コレクション・アルゴリズムではヒープを別々のメモリ領域に分割する必要があり、いくつかのメモリ領域はある時間帯ユーザー・プログラムがアクセスできなくなるかもしれません。つまり、実際のヒープサイズはユーザー・プログラムの最大のヒープ占有率よりも数倍大きい可能性があるということです。
  • 仮想記憶の相互作用: 物理メモリに制限のあるをシステムでは、完全なガーベッジ・コレクションは、コレクション処理の間にメモリ内の非常駐ページを調べて、避難することができます。ページフォルトの損失は大きいので、ガーベッジ・コレクターが参照地点を適切に管理することは望ましいことです。
  • キャッシュの相互作用: メイン・メモリにヒープ全体が収まるシステムにおいても(実際はすべてのJavaアプリケーションに該当しますが)、ガーベッジ・コレクションにはユーザー・プログラムに使用されるデータをキャッシュからフラッシュし、ユーザー・プログラムにパフォーマンス・コストをもたらす効果があります。
  • プログラム地点への影響: ガーベッジ・コレクターの仕事は参照できないメモリを再利用するだけであると思っている人もいますが、ガーベッジ・コレクターはユーザー・プログラムの参照地点を改善するべきだと考える人もいます。コレクターの圧縮およびコピーはコレクション中にオブジェクトを再配置して、位置を改善する可能性をもっています。
  • コンパイラおよびランタイムへの影響: ガーベッジ・コレクションのアルゴリズムには、参照カウンタの更新のようにポインタ割り当てが行なわれる場合は常に、コンパイラやランタイム環境との連携が必要となるものがあります。これは、コード生成というコンパイラの仕事、および追加命令を実行するランタイム環境のオーバヘッドを生み出します。これらの要件のパフォーマンスへの影響はどうでしょう。コンパイル時間の最適化を妨げるのでしょうか。

選択したアルゴリズムにかかわらず、ハードウェアとソフトウェアのトレンドがガーベッジ・コレクションをはるかに実用的にしてきました。1970年代および1980年代の実証研究では、ガーベッジ・コレクションは大規模なLispプログラムではランタイムの25%から40%を消耗するという結果でした。ガーベッジ・コレクションはまだ完全ではないものの、大いに進歩してきたのです。


基本アルゴリズム

すべてのガーベッジ・コレクションのアルゴリズムが直面している問題は同じで、アロケータに分配されても、ユーザー・プログラムに到達可能でないメモリのブロックの識別です。到達可能でないとはどういう意味でしょう。メモリ・ブロックには2つの方法のうちのいずれかで到達することができます。ユーザー・プログラムがルート でブロックへの参照を保持する方法か、別の到達可能なブロックにブロックへの参照が保持されている方法かです。Javaプログラムでは、ルートとはアクティブなスタック・フレーム上の静的変数またはローカル変数に保持されたオブジェクトへの参照です。到達可能なオブジェクトとはルートセットからの推移的閉包(transitive closure)です。

参照カウンタ

最も簡単なガーベッジ・コレクション・ストラテジーは参照カウンタです。参照カウンタは単純ですが、コンパイラの助けが必要で、mutator (ガーベッジ・コレクターの観点からのユーザー・プログラムの用語)のオーバーヘッドをもたらします。それぞれのオブジェクトは関連する参照カウンタ、つまりそのオブジェクトへのアクティブな参照の数を保持しています。オブジェクトへの参照カウンタが0である場合は、オブジェクトはガーベッジであり(ユーザー・プログラムから到達可能でない)再利用することができます。割り当てステートメントなどをとおしてポインタ参照が変更されるたびに、あるいは、参照がスコープから外れる時に、コンパイラは参照オブジェクトの参照カウンタを更新するためにコードを生成しなければなりません。オブジェクトの参照カウンタが0になった場合、ランタイムは直ちにブロックを再利用するか(再利用されたブロックが参照するブロックの参照カウンタをディクリメントします)、あるいは据え置きコレクションのキューに配置することができます。

stringのように多くのANSI C++ライブラリ・クラスが、ガーベッジ・コレクションの状況を提供するために参照カウンタを使用しています。割り当て演算子をオーバーロードし、C++スコープに提供されている厳密な終了処理を利用することによって、C++プログラムはあたかもガーベッジ・コレクションのように、stringクラスを使用することができます。参照カウンタは単純で、incrementalコレクションに役立ち、コレクション・プロセスは参照地点をきちんと把握しています。しかし、参照カウンタは到達可能でない循環構造(循環的にリンクされているリストや親ノードへのback-pointerを含むツリーのような、直接または間接に互いを参照するオブジェクト)を再利用することができないといった多くの理由から製品のガーベッジ・コレクターではほとんど使われていません。

トレース・コレクター

JDKの標準ガーベッジ・コレクターでは参照カウンタは使用しておらず、代わりにトレース・コレクター を使用しています。トレース・コレクターは(コレクションの全期間である必要はないが)処理を停止して、すべての到達可能なオブジェクトを調べるまで、ルートセットおよび次の参照からオブジェクトをトレースし始めます。ルートは、プログラム・レジスタ、スレッドのスタック内のローカルの(スタック・ベースの)変数、静的変数にあります。

Mark-sweepコレクター

1960年にLisp発明者John McCarthy氏によって最初に提案されたトレース・コレクターの最も基本的なものはmark-sweep コレクターで、処理は停止され、ルートからそれぞれの生きているノードを参照し、参照したノードをマークする、というものです。次に続く参照がなければ、コレクションは完全で、ヒープはsweepされます(つまり、ヒープ内のすべてのオブジェクトが検討されます)。そして、マークされていないオブジェクトは、ガーベッジとして再利用され、フリー・リストに戻されます。図1は、ガーベッジ・コレクションより前のヒープです。影付きブロックはユーザー・プログラムから到達可能でないので、影付きブロックはガーベッジです。

図1. 到達可能オブジェクトと到達可能でないオブジェクト
到達可能オブジェクトと到達可能でないオブジェクト

Mark-sweepの実装は簡単で、循環構造を簡単に再利用することができ、参照カウンタのようには、コンパイラまたはmutatorに負担をかけません。しかし、Mark-sweepにも足りない点があります。コレクション・ポーズが長くなることがあり、ヒープ全体がsweep過程で参照されます。これは、ヒープが展開される仮想記憶システムにマイナスのパフォーマンス結果をもたらすことになりえます。

mark-sweepの重要な問題は,すべてのアクティブな(割り当てられた)オブジェクトは、到達可能であろうとなかろうと、sweepフェーズの間に参照されるということです。これは、オブジェクトのほとんどがガーベッジであるかもしれないため、コレクターはガーベッジの検査や取り扱いにかなりの労力を費やすことになります。さらに、Mark-sweepコレクターは、ヒープを寸断しておく傾向があります。つまり十分に空きのメモリが利用できるような時でも、局所的な問題を引き起こしたり、割当ての失敗を引き起こすこ可能性があるということです。

コピー・コレクター

コピー・コレクター (トレース・コレクターの別の形式)では、ヒープは2つに等しく分割されて、1つはアクティブなデータを含み、もう1つは使用されません。アクティブなスペースがいっぱいになった時、処理は停止され、生きているオブジェクトはアクティブなスペースからアクティブでないスペースにコピーされます。スペースの役割は、古いアクティブでないスペースを新たなアクティブなスペースへと変更させることです。

コピー・コレクションには、生きているオブジェクトだけを参照するという利点があります。つまり、ガーベッジ・オブジェクトは調べず、メモリへ展開されたり、キャッシュにもたらされる必要がないということです。コピー・コレクターのコレクション・サイクルの期間は、生きているオブジェクトの数によります。しかし、コピー・コレクターには、新しいコピーをポイントするために参照をすべて調節して、あるスペースから別のスペースにデータをコピーするというコストがかかります。長く生きているオブジェクトは、すべてのコレクションの前後にコピーされます。

ヒープ圧縮

コピー・コレクターには他にも利点があり、生きているオブジェクトはヒープのbottomへ圧縮されます。これにより、ユーザー・プログラムの参照地点を改善してヒープの分割を防ぐだけでなく、オブジェクト割当ての手間も削減することになります。よって、オブジェクトの割当てとはヒープの先頭ポインタにポインタを追加することになります。フリーリストや索引リストを維持したり、best-fitアルゴリズムあるいはfirst-fitアルゴリズムを遂行する必要はありません。リスト1のように、Nバイトを割当てることは、ヒープの先頭ポインタにNを加えたり、前の値を返すことと同じくらい単純なことです。

リスト1. コピー・コレクターでの簡単なメモリ割当て
void *malloc(int n) { 
    if (heapTop - heapStart < n)
        doGarbageCollection();

    void *wasStart = heapStart;
    heapStart += n;
    return wasStart;
}

ガーベッジ・コレクターのない言語で精巧なメモリ管理スキーマを実装している開発者には、コピー・コレクターでの割当て(簡単なポインタ追加)がいかに簡単であるかに驚くかもしれません。これは、オブジェクト割当ては困難であるという考えが普及していることが理由であるかもしれません。初期のJVM実装ではコピー・コレクターは使用していなかったので、開発者は割当ての手間はCのような他の言語と同じくらいであると暗黙的に考えるのですが、実際は、Javaランタイムでの割当ての方がかなり簡単なのです。割当ての手間が小さいだけでなく、次のコレクション・サイクルの前にガーベッジになるオブジェクトについても、ガーベッジ・オブジェクトは参照されず、コピーされないので、deallocationの手間は0になります。

Mark-compactコレクター

コピー・アルゴリズムのパフォーマンスは素晴らしいのですが、mark-sweepコレクターの2倍のメモリが必要であるという欠点があります。mark-compact アルゴリズムはコレクションをいくらか複雑にしながらもこの問題を回避するように、mark-sweepアルゴリズムとコピー・アルゴリズムを組み合わせています。mark-sweepのようにmark-compactは2フェーズのプロセスがあり、生きているそれぞれのオブジェクトはmarkingのフェーズで参照されマークされます。それから、マークされたオブジェクトは生きているオブジェクトがすべてヒープのbottomに圧縮されるように、コピーされます。すべてのコレクションで完全な圧縮が行なわれる場合、生じるヒープはコピー・コレクターの結果と似ています。つまり、ヒープのアクティブな部分と自由なエリアの間には明確な境界があって、割当ての手間はコピー・コレクターの手間と同じようなものです。長く生きているオブジェクトは、ヒープのbottomに蓄積する傾向があります。したがって、それらのオブジェクトはコピー・コレクターのようには繰り返しコピーされません。


では、どのアプローチを?

そうすると、JDKはガーベッジ・コレクション用に、これらのアプローチのどれを取り入れているのでしょう。ある意味、すべてを取り入れています。初期のJDKはシングル・スレッドのmark-sweepあるいはmark-sweep-compactを使用していました。JDK 1.2以降はgenerationalコレクション という混合のアプローチを採用しています。これは、ヒープがオブジェクトのageに基づいていくつかのセクションに分割され、異なるgenerationは異なるコレクション・アルゴリズムを使用して集められています。

generationalガーベッジ・コレクションはランタイムでのコード生成がいくらか必要なものの、非常に有効であることが分かっています。

参考文献

コメント

developerWorks: サイン・イン

必須フィールドは(*)で示されます。


IBM ID が必要ですか?
IBM IDをお忘れですか?


パスワードをお忘れですか?
パスワードの変更

「送信する」をクリックすることにより、お客様は developerWorks のご使用条件に同意したことになります。 ご使用条件を読む

 


お客様が developerWorks に初めてサインインすると、お客様のプロフィールが作成されます。会社名を非表示とする選択を行わない限り、プロフィール内の情報(名前、国/地域や会社名)は公開され、投稿するコンテンツと一緒に表示されますが、いつでもこれらの情報を更新できます。

送信されたすべての情報は安全です。

ディスプレイ・ネームを選択してください



developerWorks に初めてサインインするとプロフィールが作成されますので、その際にディスプレイ・ネームを選択する必要があります。ディスプレイ・ネームは、お客様が developerWorks に投稿するコンテンツと一緒に表示されます。

ディスプレイ・ネームは、3文字から31文字の範囲で指定し、かつ developerWorks コミュニティーでユニークである必要があります。また、プライバシー上の理由でお客様の電子メール・アドレスは使用しないでください。

必須フィールドは(*)で示されます。

3文字から31文字の範囲で指定し

「送信する」をクリックすることにより、お客様は developerWorks のご使用条件に同意したことになります。 ご使用条件を読む

 


送信されたすべての情報は安全です。


static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=60
Zone=Java technology
ArticleID=218787
ArticleTitle=Javaの理論と実践: ガーベッジ・コレクション小史
publish-date=10282003