キーポイント
- The generational hypothesis is key to efficient modern garbage collection
- HotSpot counts the number of collections an object has survived to implement generational GC
- The Parallel collector is still the most widely used Java GC
- Algorithmic complexity of GC is difficult to reason about concisely
- Compacting collectors (like ParallelOld) behave completely differently to in-place collectors
Java 8では、古い世代のHotSpot VM用のデフォルトのガベージコレクタは、ParallelOldと呼ばれています。このデフォルトは、Java 11ではG1コレクタに変更されました。
注記: 技術的なコレクタの変更はJava 9で行われましたが、Java 10と11でG1に大幅な機能強化が行われたことと、事実としてLTSリリース以外のJavaを運用する企業が極めて少ないことから、このように記述しています。
この記事では、ガベージコレクションの基本理論と、それがHotSpotのコレクタにどのように実装されているかを論じていきます。デフォルトが変更された理由や、ガベージコレクションに対するJavaのアプローチに関する最近の変化について論じる上で、よい導入部になるでしょう。
基本概念
ガベージコレクションはシステムの"ハウスキーピング"処理であって、アプリケーションの主処理とは別のものです。使用されなくなったメモリの探索と判定を行い、自動的に回収して再利用します。
Dijkstra博士の定義によるならば、参照カウントは自動メモリ管理の一形式ですが、ガベージコレクションの一形式ではない、ということは明らかです。
参照カウントは、オブジェクト毎のメタデータをプログラム実行に沿って(例えば、参照タイプのフィールドに新たな値を設定する時に)更新することで動作します。メタデータ更新に必要な処理はアプリケーションスレッドで行われるので、独立したアクティビティとして明確に分離することはできません。
実践的なGCアルゴリズムはGC roots — 有効(live)であることが分かっているオブジェクトのセット — から始まり、ポインタを追って有効なオブジェクトをすべて決定することで進行します。
このようなトレーシングコレクタ(tracing collector)では、グラフ理論アルゴリズムを実装することによって、ヒープメモリを有効なものと再利用可能(reclaimable)なものとに分割します。
現代的なGCの文脈においては、コンカレント(concurrent)とパラレル(parallel)が、いずれもコレクションアルゴリズムの説明に用いられています。これらは同意語のようにも思えますが、実際には意味がまったく違います。
- コンカレント — アプリケーションスレッド動作中もGCスレッドの動作が可能であること
- パラレル — ガベージコレクションアルゴリズムの実行に複数のスレッドを使用すること
この２つの用語は等価ではないどころか、まったく違う用語であるとさえ言えます — コンカレントがストップ・ザ・ワールド(stop-the-world)の対義語であるのに対して、パラレルはシングルスレッド(single-threaded)の対義語なのです。
実際に運用されているコレクタでは、GC負荷サイクル内に複数のフェーズが存在します。それぞれのフェーズは、入り混じった特性を示す場合もあります。
例えば、シングルスレッドでコンカレントなフェーズもあれば、パラレルでストップ・ザ・ワールドなフェーズも十分にあり得るのです。
注記: コンカレント型のコレクタは、ストップ・ザ・ワールド型のコレクタよりもはるかに複雑です。それだけではありません。計算量の消費という面でも高価であると同時に、その動作に関して他にも注意すべき事があります。
その他の、GCについて知っておくべき用語を紹介しましょう。
- Exact — Exactコレクタは、十分な型情報を持ち、トラバースの必要な整数とポインタの違いなども常に把握しています。
- Evacuating — すべての有効なオブジェクトを別のメモリ領域へ移動(evacuate — 退避)させます。コレクションサイクル終了時には、元のメモリ領域は完全に空になっていて、再利用が可能です。
- Compacting — コレクションサイクルが終わると、生き残ったオブジェクトはひとつの連続ブロックとしてメモリリージョンの先頭にアレンジされていて、残りの領域は再利用可能です。
Exact GCスキームの対局にあるのがConservativeスキームです。このスキームには、Exactスキームの持つ型情報が欠けているため、結果として、一般的にメモリ浪費が多くなっています。
CompactingとEvacuatingの２つを含むものとして、Movingコレクタについて言及しているソースもありますが、この２つのタイプは差異が極めて大きいため、ひとつのグループにまとめるのは不都合な場合が少なくありません。
これとは逆に、オブジェクトの移動を伴わないコレクタはIn-placeコレクタと呼ばれています。In-placeアルゴリズムでは、メモリフラグメンテーションに対処してフリーブロックをひとつにまとめるために、使用可能なメモリブロックのフリーリストが必要になります。
HotSpotの実用的検討事項
最初は定義から始めて、それにまつわる基本的な部分を検討しましょう。
- Movingコレクタが割り当てたオブジェクトは、ライフタイム全体を通じた静的アドレスというものを持ちません。
- Compactingコレクタは、メモリフラグメンテーションを防止します。
- Evacuatingコレクタは、フラグメントの防止に加えて、生存オブジェクトを部分的に圧縮することが可能ですが、
- ヒープが単一のメモリプールで構成されている場合には、このアルゴリズムでガベージコレクションを行うことはできません。
世代別仮説(Generational Hypothesis)は、オブジェクト指向システムにおいて観察された実行時の振る舞いのひとつで、オブジェクトを大きく2つのクラス — 短命な一時的オブジェクトと、プログラムのワーキングセットを構成する長寿命な(long-lived)オブジェクトに分類するものです。
注記: 世代別コレクタが非世代別コレクタより常に効率的であるという保証はありませんが、現実的には、ほぼすべてのアプリケーションが世代別GCによる恩恵を受けます。
GCにおけるMark-Sweep-Compact命名法(Blackburn、McKinleyなどによる)とは、次のようなものです。
- Marking: オブジェクトグラフをトレースして、オブジェクトの有効性(liveness)を判別します。
- Sweeping: 有効なオブジェクトは動かさずに、未使用スペースを求めます。
- Evacuating: 生き残ったオブジェクトを別のプールへ移動することで、スペースを解放します。
- Compacting: 生き残ったオブジェクトを同一プール内で移動して、スペースを解放します。
世代別GCでは、若いコレクタと古いコレクタがまったく別のアルゴリズムであることが少なくありません。
この結果のひとつとして、フェーズによって異なるアルゴリズムを採用している場合に、そのコレクタを正確に分類することが難しくなっています。例えばCMSでは、若い世代にはEvacuatingコレクタを、古い世代にはIn-Place Mark-Sweepコレクタを使用し、コンカレントコレクションが(フラグメントなどの原因で)失敗した場合にはMark-Compactにフォールバックします。
HotSpotにおける若い世代のコレクション
HotSpotでは、従来のコレクタはメモリをEden、Survivor 0、Survivor 1、Tenuredという４つのプールに分割します。前者3つが全体としてYoungスペースにグループされるもので、TenuredがOldスペースに相当します。
YoungスペースはYoungコレクション中にガベージコレクションされます。ここではパラレル、ストップ・ザ・ワールド、Evacuatingが使用され、生き残ったオブジェクトがどちらかのSurvivorスペースに移動されます。
このコレクションアルゴリズムでは、現在アクティブなメモリプール内で有効なデータをマークし、それをアクティブでないプールに退避します。コレクションが完了すると、2つのSurvivorスペースの役目が逆転します — アクティブなプールが非アクティブ(つまり空)になり、アクティブでなかったプールがアクティブになるのです。この方法はhemispheric(半球型)コレクションと呼ばれることもあります。
このアプローチには大量のメモリが必要です。シングルパスのアルゴリズムでは、コレクション対象となったメモリの中に、有効なものがどれだけあるのかを事前に知ることはできません。このため、toスペース(オブジェクトを退避する領域)はクリーンする領域と同じ大きさでなければならず、実際に生き残るサイズの2倍の領域が必要になります。
これは同時に、スペースの半分は常に空である、ということでもあります。これらの特性は、ワーキングセットの極めて大きい最近のワークロードにおいては、古い世代のコレクションには不向きです — 実際、運用されているHotSpotコレクタの中で、古い世代に対してhemisphericコレクションを使用しているものはありません。
一方で、若い世代にはhemisphericコレクションが使用されます。世代別仮説が適用可能なワークロード — 例えば大部分がガベージである領域には、このアプローチが適しているからです。生き残ったオブジェクトが若い世代から古い世代に昇格するという事実が、この場合にはメリットとして働きます。
Evacuatingコレクタのもうひとつのメリットは、フリースペースの処理方法です。最も単純なアプローチは、領域の先頭ポインタを使ってフリーリストを構成するものです。有効なデータが退避されると、"自然な"方法で圧縮 — 実際には解放、が行われます。
OpenJDKの若い世代のコレクタで使用されているEvacuatingアプローチでは、一般的にパストレースを使用しています。ただし、このコレクションは1回のパスのみで行われます — Mark、Sweep、Compactといったフェーズはありません。
世代別仮説の影響
オブジェクトの寿命は通常は分かりませんし、現実のアプリケーションでは動的に変化します。従って、オブジェクトの実際の生存時間を実時間で追跡するというのは不可能であり、意味もありません。
代わりにHotSpotでは、オブジェクトが生き延びたコレクションの回数を記録しています。この情報には、オブジェクトヘッダ内のメタデータの数ビットを使用します。オブジェクトが有効なコレクションを生き延びると、物理的に古い世代に移動(プロモート)されて、別のコレクタ下で管理されるようになります。
このメカニズムは、アプリケーションのアロケーション率と興味深い関係があります。アロケーション率が上昇すると、若い世代は短時間で埋められるようになりますが、"短命なオブジェクト"に想定されるライフタイム(ミリ秒で計測される)は一定のままです。
このため、より多くのオブジェクトがGCサイクルを生き残るようになり、結果として若い世代のSurvivorスペースが、古い世代に昇格する条件を満たさないオブジェクトで溢れるようになります。この状況でJVMには、一部のオブジェクトを早期にプロモートする以外の選択肢がなくなります。これがPremature Promotion(早期プロモーション)と呼ばれる効果です。
これらのオブジェクトの大半は、実際には短命であるため、古い世代に移動後間もなく、寿命を終えることになります。残念ながらJVMにはこれらを回収するメカニズムがないため、古い世代で次のGCが行われるのを待たなければなりません。
ガベージコレクションアルゴリズムの複雑性分析("ビッグ・オー記法(big-O notation)"と呼ばれることもあります)を行いたいというのは、開発者の持つ当然の希望でしょう。しかし実際には、このアプローチではあまり満足のいく結果は得られません。
単純に考えると、MarkフェーズとCompactフェーズの時間的な複雑性はライブセットのサイズに、Sweepフェーズはヒープ全体のサイズに、それぞれ比例するように思われるかも知れません。
しかしながら、現実の実装ではフェーズの分離が必ずしも明確ではない(HotSpotの若い世代用のコレクタで既に論じたように)という問題を別にしても、さらに深い問題が存在するのです。
それはすなわち、ガベージコレクションは、その性質そのものから、使用されている最も汎用的なアルゴリズムのひとつである、という単純な事実です。つまり、ビッグ・オー分析に固有の仮定 — データサイズの増加という制限的動作に着目する — は、ガベージコレクションでは成立しないのです。
実運用システムにおけるGCアルゴリズムには、想定されるあらゆる範囲の入力やワークロードに対して、許容範囲内の動作を行うことが求められます。その全体的なパフォーマンスを表現する手段として、ビッグ・オー分析の漸近的な方法はまったく適していないのです。
別の言い方をするならば、ライブセットとヒープサイズは(オブジェクトグラフのトポロジの違いから)、根本的に独立した変化をする可能性があります。つまり、乗法スケーリング係数(multiplicative scaling factor)が、ワークロード毎にまったく違う効果を起こすかも知れない、ということです。
例えば、Compactionではバイトコピーが必要なので、Compactionフェーズがライブセットのサイズに対して線形であったとしても、移動の必要なオブジェクトのサイズもファクタのひとつであるかも知れません。多くの要素を持つ配列が多数あれば、停止時間に関するその他の考慮事項はすぐに意味がなくなってしまいます。
GCアルゴリズムのさまざまな形式には、2次効果としてよく知られているものもあります。例えば、生き残っているオブジェクトの極めて少ないメモリ領域("スパース(sparse)ヒープ")にCompactionを実行する場合、有効なデータはもっと密度の高い領域に統合されます。オブジェクトが長く行き続ければ、この領域は以降のGCサイクルでさらに密になる(スパースでなくなる)でしょう。
これをCMSのようなIn-placeコレクタと比較すると、寿命の長いオブジェクトがプログラムのライフタイム全体を通じてスパースのまま残されることが分かるはずです。実際に時間が経つにつれて、フリースペースはますますフラグメント化されて、フリーメモリブロックのリスト(free lsit)管理はますます高価なものになるでしょう。
全体として、GCに対する各アプローチの時間的および空間的コストモデルは大きく異なっているので、単純なアルゴリズム的複雑さでは測ることはできません。HotSpotの場合、In-spaceコレクタの究極的なフォールバックモードは、十分な連続領域が見つからなかった場合の、Compactingコレクタへのフォールバックになります。これには重大な動作上の影響であって、単純なアプローチでカバーできるものではありません。
要約
Java仮想マシンに実装されているガベージコレクションについて、いくつか基本的な面から論じてきました。ガベージコレクションは、コンピュータ科学では完成された分野です。HotSpotに存在するコレクタはいずれも堅牢で十分にテストされていて、極めて大規模なクラスのワークロードでも良好に動作します。ほとんどのJavaアプリケーションは、GCの動作をそれほど気にかける必要はありません。
GCの動作にセンシティブな極めて稀なケースでは、ガベージコレクションの原理(とJVMでの実装方法)に関する深い知識を習得しておくことは、技術者自身のツールキットとして非常に有効です。
Javaの最近のリリースでは、ガベージコレクションサブシステムが再び積極的な改善対象領域になっています。ただし、これらの変更を十分に理解するためには、基本をしっかり把握しておかなくてはなりません。今後の記事ではこれらの変更について詳細に議論し、なぜデフォルトのガベージコレクタが変更されたのか、Java 11にアップグレードする上でこれはどのような意味を持つのか、といったことを論じていきたいと思っています。
著者について
Ben Evans氏は、JVMのパフォーマンス最適化を手掛けるjClarityの創業者のひとりです。氏はLJC(ロンドンのJUG)のオーガナイザであり、JCP Executive Committieのメンバとして、Javaエコシステムのための標準定義を支援しています。氏はJava Championであり、JavaOne Rockstarで3回講演しています。また、"The Well-Grounded Java Developer"、"Java in a Nutshell"の最新版、"Optimizing Java"の著者でもあります。Javaのプラットフォームやパフォーマンス、アーキテクチャ、並列性、および関連するテーマについて、いつも講演を行っています。氏は講演や指導、コンサルタント業務にも携わっています。詳細は直接連絡してください。