原文はこちら。
The original article was written by Jonas Norlinder (Senior Member of Technical Staff, Oracle), Erik Österlund (Consulting Member of Technical Staff, Oracle), Tobias Wrigstad (Docent at Uppsala University), and David Black-Schaffer (Uppsala University, Uppsala, Sweden).
https://inside.java/2024/11/22/mark-scavenge-gc/
このエントリは、Mark-Scavengeと呼ばれる新しいGCアルゴリズムについてまとめたものです。このエントリでは、オブジェクトを移動させるGC (moving GC) において、到達可能性 (reachability) を有効性 (liveness) の代用とすると、不必要なデータ移動につながること、そしてその課題に対しての対処法を説明しています。 この研究は、OracleとUppsala大学の共同研究の最新論文です。 論文の全文はACMのウェブサイトでご覧いただけます。
Mark–Scavenge: Waiting for Trash to Take Itself Out
https://dl.acm.org/doi/10.1145/3689791
モダンなGCでは、弱い世代別仮説が成り立ち、ほとんどのオブジェクトは早期に破棄されると仮定しています[4]。そのため、ヒープを年齢ごとに領域に分割します。弱い世代仮説が成り立つ場合、Young領域にあるオブジェクトのほとんどは、ほとんどいつでもガベージになることでしょう。したがって、Young世代内では、有効オブジェクトを操作するGCアルゴリズムは、ガベージオブジェクトを操作するアルゴリズムよりも効率的です。 GCがメモリを取り戻す必要がある以下の例を考えてみましょう。
領域Aと領域Cには4個の有効オブジェクトがあり、領域Bには有効オブジェクトが2個しかないため、退避目的であれば密度の低い領域 Bを選択するのが最も効率的です。この例では、オブジェクトeとfを領域Dに退避（移動）させ、参照ポインタを更新後、領域Bをすべて解放します。ここまでは良いのですが、GC が何かを有効であるとみなす場合、それは何を意味するのでしょうか？The Garbage Collection Handbook[1]には以下のような記述があります。
An object is said to be live if it will be accessed at some time in the future execution of the mutator.
（ミューテータの将来の実行時にアクセスされる場合、オブジェクトは有効である、と言う）
– The Garbage Collection Handbook
残念ながら、オブジェクトの「真の有効性」に関するこのような情報は、未来を予測できる人々のみが入手可能であり、正確性を期すためには、オブジェクトが無効であると誤って予測してはいけません。このような完璧な予測の代わりに、GCは通常、ポインタの到達可能性[1]を使って有効性を推定します。しかし、その到達可能性を使用すると、オブジェクトを移動させてメモリを再利用するという「無駄な作業」が発生する可能性があります。この無駄な作業は、システムがそのオブジェクトに到達可能ではないのに、GCがそのオブジェクトを移動させることに起因します。
研究対象のOpenJDKでは、すべてのGCが有効性を到達可能性で推定しています。例えば、SerialやG1は、scavenge（掃き集め）の過程で実施しています。scavengingとは、ルートからヒープを巡回し、到達可能なオブジェクトを発見次第、再配置することを意味します。ZGCは、オブジェクトを発見しコピーするために、Mark (マーク) とEvacuate (退避) のフェーズを別個に利用しています。オブジェクトは発見時に有効であるとマークされ、マーキング時に有効と検出された場合は後でコピーされます。
到達可能性を有効性として使用することで、事実上garbageオブジェクトのコピーがどの程度発生するのかを調査することにしました。我々の知る限り、この種の研究を発表したのは我々が初めてです。当初の仮説は、MarkとEvacuateのフェーズを別個に実行するGCは、有効性情報が処理されるよりもずっと前に有効性を計算するため、パフォーマンスが低下するだろうというものでした。回収時には見られないこの遅延が原因で、有効性情報が古くなる可能性がありました。 一方、マーキング後の計算済み有効性マップでは、密度の低い領域だけ退避を許可します。つまり、退避は、投資対効果の高いページ（例えば、ページ全体を解放するために、一部のオブジェクトをコピーする）に集中し、選択的に行うことができます。 最終的には、実験を実行することで無駄な作業の量を把握することができました。
ZGCでGCによる無駄な作業を計測し始めたのは、ZGCがロードバリア（load barrier）という、必要とする最も適切なインフラを持っていたからです。ロードバリアがなければ、オブジェクトへのアクセス、つまりプログラムが最終的にオブジェクトを使用したかどうかを簡単に検出することはできませんでした。ZGCにインスツルメンテーションを施し、Markフェーズ中に到達可能であったものの、次のGCサイクルで到達不能になる前に、その後一度もアクセスされなかったYoungオブジェクトを特定しました。これにより、無駄な作業であるGC再配置を特定します。 次に、これらのオブジェクトのうち、GCによって移動された数を測定しました。これを「無駄な作業」と呼びます。つまり実際に不要になったオブジェクトの移動です。
今回、手を入れたZGCを使用してDaCapoベンチマーク・スイート[2]および SPECjbb2015 [3]を実行し、退避したオブジェクトの真の有効性（使用可能性）に関する情報を収集しました。 以下のプロットの第4グループ（ZGC (barrier) ）のそれぞれの棒グラフで特定のベンチマークを表しており、二度と触れられず、次のGCで到達できなくなったために退避した不要なオブジェクトの割合を測定したものです。このデータから、ポインタの到達可能性が有効性を過剰に近似し、マーキングと退避の間に遅延があるため、不必要に退避されるオブジェクトの割合が非常に高いことがわかります。
より精度の低い測定でG1とシリアルGCの実験を繰り返しましたが、その理由はこれらのGCには負荷バリアがないためです。 結果は似ており、正確なロードバリアベースの測定（ZGC barrier）と大きく異なるものではありませんでした。 回収フェーズではオブジェクトを発見するとすぐに退避させられますが、到達可能な物体はすべて退避させられるため、かなりの無駄な作業が発生します。研究のデータからは、発見してマークしてからコピーまでの時間がマークによる退避（Mark–Evacuate）よりも短いにもかかわらず、必ずしも無駄な作業が減るわけではないことがわかっています。この研究では、オブジェクトを移動させるGCにおいて、素朴に到達可能性を有効性の代わりとして使用することは、かなりの無駄な作業をもたらすとの結論を得ました。
GCがより並行処理すればするほど、GCが作業を行う際のスケジューリングの自由度は高くなります。 しかし、コンカレントGCは、GC中にプログラムを停止しないため、プログラムの割り当て率を予測し、一致させる必要がありますが、誤った予測に耐えるためには、GCがメモリ解放作業する間、割り当ての急増に対応できる「ヘッドルーム」（バッファまたは利用可能なメモリ）も必要です。 ヘッドルームは通常使用されませんが、必要な安全対策です。
我々は、次のGCサイクルまで退避を遅延させ、オブジェクトが到達不能になる可能性を高めることで、無駄な作業を削減する新しいGCアルゴリズムを提案します。このアルゴリズムをMark-Scavengeと呼ぶことにします。Mark-Scavengeは、Mark-Evacuateと同様に到達可能性の発見を行い、密度の低い領域のみを退避のために選択しますが、Mark-Evacuateとは異なり、マーキング後すぐに退避することはありません。これはつまり、マーキング後に利用可能になる新しいメモリは、完全に空であることが判明した領域だけである、ということです。我々のインサイトは、ヘッドルームはマーク後の割り当てに対応できるということです。密度の低い領域から有効性情報を取得しているので、標準的な退避を使うことで、密度の低い領域から新たなヘッドルームをオンデマンドで作成できます。もしこのようなことが起こらなければ、これらの領域のオブジェクトは到達不能になるためのGCサイクルを余分に持っていたことになりますし、もし起こったとすれば、それらのオブジェクトは無効なのでGCは退避させる必要はありません。オブジェクトが次のGCサイクルでまだ到達可能であれば、scavenge（回収）方式で退避させ、発見次第再配置します。このように、Mark-ScavengeはScavengingとMark-Evacuateの優れた要素を兼ね備えています。つまり、選択的に避難させることができ、発見と避難の間に遅延がないのです（これはMark-Scavengeにはなかったことです）。
世代ZGCのYoungコレクションに対して、Mark-Evacuateの代わりにMark-Scavengeを実装しました。 以下のグラフでは、Mark-Scavengeがいかに多くの無駄な作業をなくすことに成功しているかを示しています。
最も顕著な結果は、無効オブジェクトの再配置が（最大で）91%削減されたことです。割り当ての停止を回避するために必要なだけのメモリでGCを実行すれば、無駄な作業のコストはほとんど隠蔽されますが、負荷の高いマシン（例えば、割り当て率が一時的に急上昇する）で実行した場合、性能向上は2～4％と大きくなります。本研究での最良の結果は SPECjbb2015 によるもので、critical-jOPS（レイテンシ）が 2～4%、max-jOPS（スループット）が 2～8% 改善しました。マシンにストレスを与える構成の場合、Cassandraのレイテンシは99、99.9、99.99パーセンタイルで20%削減されます。
この研究結果から、有効性と到達可能性を同一視すると、moving GCでガベージ・データが大幅にコピーされることがわかります。ZGCのMark-Scavenge実装で実証されたように、負荷の高いマシンではパフォーマンスに悪影響を及ぼします。この研究のインサイトから、GCのエンジニアや研究者が、最先端の技術をさらに改善できる可能性があります。
Logico Inside 