ガーベッジ・コレクションの利点は明らかで、信頼性の増加、クラスのインタフェース設計とメモリ管理の切り離し、開発者がメモリ管理エラーを追跡するために費やす時間の減少などです。ダングリング・ポインターやメモリリークというよく知られている問題は、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は、ガーベッジ・コレクションより前のヒープです。影付きブロックはユーザー・プログラムから到達可能でないので、影付きブロックはガーベッジです。

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

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

コピー・コレクター

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

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

ヒープ圧縮

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

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

参考文献

• Brian Goetz氏による Javaの理論と実践 のすべての記事をお読みください。
  
  
• Garbage Collection:Algorithms for Automatic Dynamic Memory Management (John Wiley & Sons、1997年)は、広範囲な文献をもとにしたガーベッジ・コレクション・アルゴリズムに関する包括的な概論です。著者のRichard Jones氏は、Garbage Collection Pageでガーベッジ・コレクションに関する約2000の最新の文献を整備しています。
  
  
• IBM Developer Kits for the Java platform1.4はa mark-sweep-compactを使用しており、ポーズ時間の削減のためにincremental圧縮をサポートしています。
  
  
• 3回シリーズの「Sensible sanitation -- Understanding the IBM Java Garbage Collector」(developerWorks 、2002年8月-9月)は、IBM Developer Kits for the Java platform 1.2と1.3で採用されているガーベッジ・コレクション・ストラテジーについて説明しています。
  
  
• 「Fine-tuning Java garbage collection performance」(developerWorks 、2003年1月)では、ガーベッジ・コレクションの問題を検知してトラブルシューティングする方法について解説しています。
  
  
• IBM Systems Journal の記事では、mark-sweepガーベッジ・コレクションおよびmark-sweep-compactガーベッジ・コレクションの詳細を含めIBM Developer Kits for the Java platform1.1.xの構築に際しての教訓のいくつかについて書かれています。
  
  
• Garbage Collection mailing listではガーベッジ・コレクションに関するFAQを保持しています。
  
  
• ガーベッジ・コレクションの良い点・悪い点に関して記した２部シリーズも参照してください。
  
  
• C++クラスのとても便利なライブラリであるBoostライブラリには、C++にガーベッジ・コレクションの基本形を提供するために参照カウントを使用しているshared_ptrのスマートなポインタ・クラスを含んでいます。
  
  
• developerWorks Java technologyゾーンで他の多数のJava技術関連記事をご覧ください。
  
  

著者について

この記事を評価する

コメント

上に戻る

目次

• オプション-選択肢
• ガーベッジ・コレクションはどのように機能するのか
• 基本アルゴリズム
• では、どのアプローチを?
• 参考文献
• 著者について
• コメント