Concurrent Marking in G1

原文はこちら。
The original article was written by Thomas Schatzl (OpenJDK developer, Oracle).
https://tschatzl.github.io/2022/08/04/concurrent-marking.html

最近の JDK-8210708 の変更により、G1 がマーク・ビットマップを使用してliveness情報を保存する方法が根本的に変更されました。これまでは、G1が交互に使用するヒープにまたがる 2 つのビットマップを使ってこの情報を記録していましたが、現在はビットマップは 1 つだけを使用します。

JDK-8210708 Use single mark bitmap in G1
https://bugs.openjdk.org/browse/JDK-8210708

これは、GCの多くの場所における、G1によるビットマップの使用方法を変更するだけでなく、G1GCのネイティブメモリ消費を大量に削減することができるのです（正確にはJavaヒープサイズの1.5%）。この機会に、現在のコンカレント・マーキング・サイクルの仕組みと、G1のビットマップ利用方法を詳しく説明します。

副次的な効果として、この変更により、オリジナルのG1の論文にあったもうひとつの重要な部分が廃止されました。

Garbage-first garbage collection
https://dl.acm.org/doi/10.1145/1029873.1029879

この記事はかなり技術的なものです。影響についての議論は最後にあります。

Introduction and Background

old世代でガベージコレクションの必要性があると判断した後、G1はまずオブジェクトグラフを同時にトレースすることでold世代の生存オブジェクトを判断し、その後のGCポーズ時にインクリメンタルにガベージを取り戻してJavaヒープをコンパクトにします。G1は、Javaヒープの外部にあるビットマップにliveness情報を格納します。

先ほど紹介したG1の論文の2.5節では、この変更前のデータ構造とマーキングがどのように動作しているかを説明しています。ここでは、まずこの2つの実装の共通点を再確認し、次のセクションで現在の処理の全容を詳述します。なお、旧実装については論文をご参照ください。

G1のコンカレント・マーキングでは、snapshot-at-the-beginning (SATB) アルゴリズム、つまり、マーキング開始時に生存しているオブジェクトを生かしたままにしておくというアルゴリズムが使われています。

Real-time garbage collection on general-purpose machines
https://dl.acm.org/doi/10.1016/0164-1212%2890%2990084-Y

G1は、その時点でold世代のヒープ内容の仮想スナップショットを取得します。そのマーク時点で生存しているヒープコンテンツのみがマークされ、それ以降に割り当てられたものは暗黙のうちに生きているとみなされ、トレースされません。これは、liveness分析のために検査されるオブジェクトの量が固定されるという利点があると同時に、そのスナップショットの後に生存しなくなった可能性のあるオブジェクトは回収されません。この新しいガベージを回収するためには、別のコンカレント・マーキング・サイクルが必要です。

作業するデータが固定されていることで、シンプルな保証された終了特性が得られます。G1の設計では、マーキングサイクル中にガベージとなったオブジェクトを早期に回収することよりも、この点を重要視しています。さらに、G1ではyoung世代のコレクションと同時にold世代のコレクションをインターリーブできるため、最近割り当てられたオブジェクトにはこの制限が適用されず、今でも迅速に回収できます。

コンカレント・マーキング中にSATBを不変に保つために、G1は以下のようにpre-writeバリア（例えば、割り当てx.a = yが与えられる）を使用して、新しい値の割り当ての前に古い値を保存するようにします。

  if (marking-active) {
    if (x.a != null) {
      enqueue x.a into per-thread buffer
    }
  }

  x.a = y                  // Actual assignment

このpre-writeバリアは、x.aの以前の値 (nullでない場合、null参照に対しては何もできないので、初期化書き込みのように多くの書き込みがnull値を上書きする) を参照のスレッド単位のバッファに追加して処理対象とします。これらのスレッドごとのバッファの値は、マーキングのためのルートとして扱われます。

G1論文の2.5.3節では、バリア設計についてより詳しい説明があります。

Data structures in use

コンカレント・マーキングの結果は、生存しているすべてのオブジェクトについて、オブジェクトの開始点に対応する単一のビットが設定（すなわちマーク）される単一のビットマップです。オブジェクトは最小オブジェクトアライメントに合わせた任意の位置で開始でき、デフォルトの最小オブジェクトアライメントは8バイト（-XX:ObjectAlignmentInBytes）で、ビットマップの1バイトで8ビットを含んでいます。つまり、ビットマップはJavaヒープの約1/64(= ~1.5%)を使用することになります。

G1 は、 (”A generational mostly-concurrent garbage collector”で説明されているものと同様の) fingerと明示的なmark stackを使用して、3 色マーキング抽象化におけるグレーセットを実装しています。

A generational mostly-concurrent garbage collector
https://dl.acm.org/doi/10.1145/362422.362480
Tri-color marking (三色マーキング)
https://en.wikipedia.org/wiki/Tracing_garbage_collection#Tri-color_marking

G1では複数のマークスレッドを使用するため、グローバルなfingerに加え、スレッドごとのローカルなfingerが存在します。同様に、グローバルなmark stackに加え、スレッドごとのローカルなmark stackがあります。

G1における3色マーキング抽象化の実装は以下のようになっています。マーキング終了時にはmark stackは空で、global fingerはJavaヒープの最高位アドレスにあるので、ビットマップ上のマークされたものはすべてblack objectになります。

white object	白	ビットマップ上にマークがないオブジェクト
black object	黒	ビットマップ上でglobal fingerの「左」（つまり、より低位のアドレスにある）にマークされ、どのmark stackにもないオブジェクト
gray object	灰	次のいずれかを満たすオブジェクト。ビットマップ上で、 (1) global fingerの左側にあり、いずれかのmark stack上にあるまたは (2) global finderの右側 (より高位のアドレスにある) ある

マーキング目的でglobal fingerを使用するのは最適化です。新しく発見された生存オブジェクトは、global fingerの左側にある場合のみ、マークスタックにプッシュされる必要があります。これにより、mark stackに使用されるスペースがおよそ50％削減されます。

マーク開始時にJavaヒープの仮想スナップショットを取るために、G1はすべてのリージョンについて、そのリージョンへの最後の割り当てが終了した場所を示すtopの現在値をtop-at-mark-start (tams) ポインタとして記録します。リージョンのbottomとそのtamsの間の領域は、トレースの対象ですが、tamsより上の領域は必要ありませんし、トレース対象ではありません。

Concurrent Marking in G1

コンカレント・マーク・サイクルは、G1内でいくつかのステップで構成されていますが、そのうちのいくつかはマーキング、すなわちライブ・オブジェクト・グラフのトレースに直接関係し、他のものは、その後のGCの準備のためにマーキング情報を使用するVMおよびGCデータ構造の管理に関係しています。

チューニングガイドの図7.2は、コンカレント・マーキングがポーズとどう関連しているかを示しています。

Garbage-First (G1) Garbage Collector
https://docs.oracle.com/en/java/javase/18/gctuning/garbage-first-g1-garbage-collector1.html#GUID-F1BE86FA-3EDC-4D4F-BDB4-4B044AD83180（英語）
https://docs.oracle.com/javase/jp/18/gctuning/garbage-first-g1-garbage-collector1.html#GUID-F1BE86FA-3EDC-4D4F-BDB4-4B044AD83180（日本語）

以下の小さなステートダイアグラムは、コンカレント・サイクルのフェーズをブレイクダウンしたものです。これらは (Pause) でマークされていることがわかります。

Concurrent Start	マークデータ構造にルートからの情報を入力し、プロセスを開始する
Concurrent Clear Claimed Marks	クラスとクラス・ローダーのガベージ・コレクションを初期化する。このフェーズはコンカレント・スタート・ポーズからコンカレント・フェーズに押し出されたものであり、長時間実行される可能性がある。この記事では、このフェーズの詳細には触れない。
Concurrent Scan Root Regions	young世代のオブジェクトのルートをJavaヒープスナップショットのルートにスキャンするフェーズ
Concurrent Mark	実際にトレース作業を行うフェーズ。以下のステップで構成されている。 1. Concurrent Mark From Rootsフェーズ：すべてのルートがマークされた状態で生存オブジェクトをトレースする 2. Concurrent Precleanフェーズ：Concurrent Mark中に発見した`j.l.ref.References`オブジェクトの前処理を行う。ここでG1は、いくつかの`j.l.ref.Reference`インスタンスについて、後続のRemarkポーズでさらなる処理が実際に必要かどうかをこの時点で決定できる。すなわち、直前のConcurrent Markフェーズで`j.l.ref.Reference`の参照先が`null`もしくは生存していることがわかっている場合、そのような参照はこのdiscovered referenceのリストから削除でき、Remark ポーズでのさらなる処理は不要。これが、この記事でこのフェーズについて説明するすべてである。 3. Remarkポーズ：マーキングが完了し、クラスのアンロード、参照処理、記憶セット再構築の初期化など、様々な後始末が行われる。Remarkポーズは、稀に様々な理由でConcurrent Markの最初からマーキングを再開することがある（図中の破線で示した部分）。
Concurrent Rebuild Remembered Sets and Scrub Regions	実際のマーキングが完了後、そのマーキング情報を使用して記憶セット情報を作成し、クラスアンロード後に利用できない、以前にアンロードしたクラスインスタンスのヒープのクリーニングを準備する。
Cleanup	記憶セットの管理作業を完了し、old世代のGCを準備するためのポーズ
Concurrent Cleanup for Next Mark	次回のコンカレント・マーク・サイクルで利用されるビットマップをクリアする

Concurrent Start pause

Concurrent Startポーズは、ルート、すなわちトレースされたJavaヒープの外側からJavaヒープへのロケーションを投入することによって、オブジェクトグラフを通してマークを開始します。これらはVM内部データ構造（スレッドスタックやクラスなど）からのルートであり、一方ではyoung世代からの参照もあります。

このポーズは通常のyoung世代のGCポーズであり、G1では以下の追加作業をこのタイミングで実行します。

G1で仮想スナップショットを取得
ヒープ中のすべてのold世代リージョンはtamsを現在のtopに設定する。young世代リージョンと、Closed Archiveリージョンのような一部の特殊なリージョンでは、tamsをbottomに設定する。これはつまり今後トレースされないという意味である。
通常のルート処理では、VM内部データ構造からのルートは直接マークビットマップ上にオブジェクトをマークする。
young世代のGCがsurvivor領域やold世代にオブジェクトをコピーした領域は、Root Region（メモリ範囲に相当する領域）として記録される。Root Regionでは、後でスナップショットされた領域へのルートが同時に検索される。これにより、ポーズ中の高価な反復処理とこれらのオブジェクトのマーキングが回避される。
スレッドごとのマーキング構造がリセットされる（local fingerがnullに設定され、local mark stackが初期化される）。
global fingerはヒープの開始点に設定される。

下図は、Concurrent Startポーズ前、オブジェクト配置済みリージョンがどうなっているかを示したものです。

             Region 0                     Region 1                             Region N            
 +-----------------------------+-----------------------------+ ... +-----------------------------+
 |AAABBBCCCCDDEEEFFFFFFFGGGGHH |                             |     |KKKKKK                       |
 +-----------------------------+-----------------------------+ ... +-----------------------------+
 ^                            ^^                                   ^      ^
 |                            |bottom == top                       |      |
 bottom                     top                                    bottom top

ポーズはその後tamsを更新し、Root Regionを追加します。おそらく以下のような状態になるでしょう。

             Region 0                     Region 1                             Region N            
 global finger
 |                                                                        / root-region \
 v            *                                                           v             v 
 +-----------------------------+-----------------------------+ ... +-----------------------------+
 |AAABBBCCCCDDEEEFFFFFFFGGGGHH |                             |     |KKKKKKRRRRRSSSTUUVVV         |
 +-----------------------------+-----------------------------+ ... +-----------------------------+
 ^                            ^^                                   ^      ^             ^
 |                            |bottom == top == tams               |      |             |
 bottom             top == tams                                    bottom tams          top

この図では、箱の中の大文字がJavaオブジェクトを示しています。リージョン1はその前後で空だったため、そのtamsはbottomに設定されていました。また、Concurrent Startポーズにより、オブジェクトRからVがoldリージョンNに昇格し、ルートリージョンとしてマークされています。

Eオブジェクトの開始点の上にある*は、そのオブジェクトが内部のVMルートからの参照を持っていたことを示しています。

Concurrent Scan Root Regions

Concurrent Startポーズでは、young世代（survivorおよび昇格したオブジェクト）からの参照を追跡しませんでした。そのため、Concurrent Scan Root Regionsフェーズでは、同時実行で以前記録されたルートリージョン内の全オブジェクトを走査し、すべての参照をスナップショットが取得された領域（tams以下）にマークします。

この例では、リージョンNのオブジェクトRからVまでがスキャンされようとしています。

Concurrent Root Region Scanの後、より多くのオブジェクトがビットマップにマークされます。このケースでは、図に示す通りHがマークされています。

             Region 0                     Region 1                             Region N            
 global finger
 |                                                                        / root-region \
 v            *             *                                             v             v 
 +-----------------------------+-----------------------------+ ... +-----------------------------+
 |AAABBBCCCCDDEEEFFFFFFFGGGGHH |                             |     |KKKKKKRRRRRSSSTUUVVV         |
 +-----------------------------+-----------------------------+ ... +-----------------------------+
 ^                            ^^                                   ^      ^             ^
 |                            |bottom == top == tams               |      |             |
 bottom             top == tams                                    bottom tams          top

G1は、このコンカレント・フェーズが次のGCの前に完了したことを確認します。最悪の場合、完了するまで次のGC開始を遅らせます。もしG1がそうしなければ、SATBに関して、次のGCでオブジェクトが生き残れないという問題が発生します。

このフェーズでは、複数の同時実行スレッドを使用します。

Concurrent Mark

Concurrent Mark Cycleの前のフェーズでマークを設定しますが、実際のマークはConcurrent Mark From Rootsのサブフェーズで開始されます。ここでは、tams以下のすべての生存オブジェクトをマークします。それと同時に、このフェーズはすべてのリージョンについて、tams以下にある生存データの量を計算します。

ワーカースレッドはリージョンを要求し、マークのためにそのリージョンのbottomとtamsマーカーの間のビットマップをスキャンします。スレッドはまず、1リージョン右にアトミックにglobal fingerを移動し、そのリージョンを要求します。リージョンごとに要求し、global fingerをリージョン単位で進めることで、global fingerでの競合を回避することはできますが、その代償としてある程度の精度が犠牲になります。しかし、このコストは低く、せいぜいいくつかのオブジェクトが複数回スキャンされる程度です。

リージョンのビットマップをスキャンすると、マークスレッドはそのlocal fingerをマークからマークへと進めていきます。スレッドがマークに遭遇した場合、対応するオブジェクトの参照を調べます。

参照がnullの場合はスキップ（null参照は無視可）。
参照がリージョンのスナップショットされた領域の外側（リージョンのtamsの上）を指している場合も無視可
それ以外の場合は、その参照されたオブジェクトをアトミックにマークしようとする
- その参照がマーク済みの場合は、何もしない。
  マーク済みオブジェクトは、黒（処理済み）か灰色になり、global fingerの左側にあった場合はマークスタックに記録する。灰色のオブジェクトは、global fingerを進めたり、マークスタックを見たりするときに自動的にチェックする。
- その参照がマークされておらず、その参照がglobal fingerに対して左側にある場合、それをローカルマークスタックにプッシュする。
  global fingerの右側にある参照オブジェクトは自動的に処理されるため、これは必要ない。

スレッドは定期的にそのローカルマークスタックと、pre-writeバリアがもたらすグローバルSATBバッファセットを減らそうとします。ローカルマークスタックに空間が残っていない場合、その一部をグローバルマークスタックにプッシュする。ローカルマークスタックが空の場合、グローバルマークスタックから仕事を得るか、他のタスクのローカルマークスタックから盗もうとします。

アルゴリズムは、ローカルおよびグローバルマークスタックの両方が空で、local finger/global fingerがそれぞれのスキャン対象の領域の終わり（すなわち、要求された領域とヒープの終わり）に到達した場合に終了します。（境界付き）グローバルマークスタックがオーバーフローした場合、すべてのマーキングスレッドを同期させ、global fingerをヒープの最初にリセットして、すでに訪れたすべてのオブジェクトを暗黙的に灰色にして、効果的にマークを再スタートさせます。

保留中のセーフポイントとの同期を容易にするために、G1マーキングスレッドは、メトリックをスキャンされたオブジェクトとwordの動的な数に基づいて、定期的にポーリングを行います。

オプションのConcurrent Precleanフェーズの後、G1はRemarkポーズをスケジュールします。

このポーズでは、G1は残りのすべてのSATBバッファを排出し、再度参照のためにJavaスレッドスタックを走査し、マーキングアルゴリズムが終了するまで新たに灰色になったオブジェクトを追うことによってマーキングを最終化します。

このマーキング最終化フェーズでは、グローバルマークスタックがオーバーフローする可能性があります。その場合、G1はglobal fingerとスレッドごとのマーキング状態をリセットし、別のConcurrent Markを開始します。

マーキングの最終化後、Remarkポーズはj.l.ref.Referenceインスタンスを処理し、クラスをアンロードし、完全に空のリージョンを回収して、その中のガベージの量に基づいて後で退避可能なold世代のリージョンを選択します。選択されたリージョンは、mixed collectionsで退避できるように、続くコンカレントフェーズでその記憶集合を再構築します。

以下はRemarkポーズの開始時における領域の内容及び関連するマーキングデータ構造の状態の例です。

                                                                                          global finger
            Region 0                     Region 1                            Region N            |
                                                                                                 |
  *         * *  *          *                                                                    v
 +-----------------------------+-----------------------------+ ... +-----------------------------+
 |AAA.......DDEEEFFFFFFF....HH |ZZZZZZZZ                     |     |......RRRRRSSSTUUVVVWWWWW    |
 +-----------------------------+-----------------------------+ ... +-----------------------------+
 ^                            ^^        ^top                       ^      ^                  ^
 |                            |bottom == tams                      |      |                  |
 bottom             top == tams                                    bottom tams               top

global fingerがヒープの最後に移動すると、リージョン0とリージョンNのtams以下のいくつかのオブジェクトは、図中の.で示されるように生存していない、つまりガベージであることがわかりました。リージョン1やリージョンNのような領域は、マーク中に割り当てられたものです。マークはないけれども、G1がtamsの上に割り当てたことで、暗黙のうちに生存しているとみなされていました。このフェーズでクラスをアンロードした後、.で示されるガベージには、クラスがアンロードされた、つまり解析不可能なオブジェクトが含まれる可能性があります。これは、絞り込みの際にこれらのリージョンを反復したり、記憶集合を使ってオブジェクトを退避させようとする際に問題となります。そのため、G1がこれらのリージョンで生存オブジェクトを探す必要がある場合、単にオブジェクトごとにJavaヒープを反復するのではなく、生存オブジェクトを走査するために、G1がビットマップを使用します。

これらの「穴」から、後で同時並行で解析不能なオブジェクトが除去されます。つまり、特別なfillerオブジェクトがその場所に置かれ、その領域が再び解析可能になるようにします。

次のConcurrent Rebuild Remembered Setsフェーズでの記憶集合再構築のためのリージョン選択は、liveness情報に基づいてリージョンを選択します。生存データの量がリージョンの所定の割合（-XX:G1MixedGCLiveThresholdPercentで決定、デフォルト85）より小さい場合、その領域はコレクションセットの候補に選択されます。例えばリージョン0についてこの条件を満たし、クラスのアンロードが発生した場合、続くConcurrent Rebuild Remembered Sets and Scrub Regionsフェーズが必要です。

この目的のために、G1はこの時点までに割り当てられたすべてのold世代リージョンの生存データをスキャンし、リージョン0へのクロスリージョンポインタを検索する必要があります。
まず、Remarkポーズは、top-at-rebuild-start (TARS) と呼ばれる、すべてのリージョンの現在のtopポインタのスナップショットを取得します。

下図はこれらの値の関係を示しています。

            Region 0                     Region 1                            Region N
 +-----------------------------+-----------------------------+ ... +-----------------------------+
 |AAA.......DDEEEFFFFFFF....HH |ZZZZZZZZ                     |     |......RRRRRSSSTUUVVVWWWWW    |
 +-----------------------------+-----------------------------+ ... +-----------------------------+
 ^                            ^^        ^top == tars               ^      ^                  ^
 |                            |bottom == tams == pb                |      |                  |
 bottom             top == tams                                    bottom tams == pb         top == tars
                     == tars == pb

tamsとtarsの違いに注意してください。tamsはマーク開始時のtop値を示し、tarsは再構築開始時のtop値を示すもので、その間にオブジェクトがリージョンに割り当てられる場合があります。tamsはconcurrent mark cycleの最後のconcurrentフェーズにて必要になるので、tamsはそのままキープされます。

（topまでの間で）リージョンが解析可能な現在の位置を追跡するために、G1はすべてのリージョンについて、この時点でtamsと同等である解析可能なbottom (PB) ポインタを保持します（他の時点では単にbottomと同等です）。

別のポインタを使う理由は、tamsとpbには異なる目的、意味があるためです。前者はビットマップのどのアドレスまでマークがある可能性があるかを示すため、後者はリージョンのどのアドレスから解析可能かを示すためです。Remarkポーズでは同じですが、素早く値が乖離します。

Concurrent Rebuild Remembered Sets and Scrub Regions

このconcurrentフェーズでは、以前に選択された候補リージョンの記憶集合を再構築します。各old世代リージョンについて、G1はそれぞれのbottomとtarsの間の生存オブジェクトをスキャンしてクロスリージョン参照を行い、それぞれの記憶集合に追加する必要があります。このフェーズの完了後にのみ、G1はすべての収集セット候補リージョンのためのすべての記憶集合を収集したことを確認することができ、それらを退避させることができるのです。

このスキャンの間のbottomとtarsの間の領域内の参照の変更は、通常通りpost-writeバリアが捕捉します。GC中のtars後の割り当てにより、絞り込みのためのクロスリージョン参照の適切な待ち行列も発生します。

このフェーズは複数のスレッドが実行し、各々がold世代リージョンの一つを要求します。リージョン内の場所により、ある生存オブジェクトから次の生存オブジェクトへの歩みは異なります。

bottomとpbの間には、クラスアンロード済みのガベージオブジェクトが存在する可能性があります。G1はビットマップを使って生存オブジェクトを辿っていきます。
pbとtarsの間は、これらのオブジェクトすべてならびにそのクラスが生存している必要があるため、G1がオブジェクトを辿ることができます。

ヒープの前者の領域を辿る間、bottomとpbの間のガベージを含む領域は再び解析可能にされます。つまり、G1 はfillerオブジェクト（基本的には整数配列）をそこに置き、これらのオブジェクトのためにブロックオフセットテーブルを修正します。スレッドがpbに到達すると、その値は直ちにbottomにリセットされます（mutatorはまだ動作中です!）。これは、すべてのリージョンのスクラビングが完了する前であっても、リージョン全体が再び完全に解析可能になることを意味します。

スクラビングを行う理由の一つは、以下のようなものです。

G1が生存オブジェクトを記録するためにヒープ全体に対して一つのビットマップしか持っていない
しかし、ビットマップは次のマーキングが完全にクリアされるために再び必要とされる
ビットマップをクリアすると、生存していない（解析できない可能性のある）オブジェクトの情報が失われる
そのため、ビットマップをクリアする前に、Javaヒープを再び完全に解析可能にする必要がある。

下図は、このコンカレントフェーズ中にスクラビングが実行された後のリージョン0を示しています。

            Region 0
 +-----------------------------+
 |AAAaaaaaaaDDEEEFFFFFFFbbbbHH |
 +-----------------------------+
 ^                            ^
 |                            |
 bottom     top == tams == tars
  == pb

ガベージ領域はfillerオブジェクト (小文字のaとbで表示しているもの) に置き換えられ、pbはリージョンの最下位アドレスにリセットされました。これらのfillerオブジェクトは到達不可能であることに注意してください（実際、生存オブジェクトからのそれらへの参照はバグのしるしです）。そのため、生存オブジェクトの退避時には自動的にfillerオブジェクトをスキップします。

複数のスレッドがリージョンを要求します。セーフポイントまでの時間を小さく保つために、定期的にセーフポイントとの同期を行います。

このフェーズに含まれるScrub RegionsはJDK-8210708で新たにG1に追加されたものです。

JDK-8210708 Use single mark bitmap in G1
https://bugs.openjdk.org/browse/JDK-8210708

Cleanup pause

Cleanupポーズで、コレクションセットの候補リストを絞り込みます。G1は候補リージョンの占有率と連結性に基づいて効率スコア (efficiency score) を計算し、効率性の懸念からGCの可能性が低い、あるいは難しすぎるものを削除します。以下のエントリで、このメカニズムについてより詳しく説明しています。

Welcome 20% less memory usage for G1 remembered sets – Prune collection set candidates early
https://tschatzl.github.io/2021/02/26/early-prune.html
https://logico-jp.io/2021/02/28/welcome-20-less-memory-usage-for-g1-remembered-sets-prune-collection-set-candidates-early/

選定で落とされたこうしたリージョンは、いずれにせよ多くの場合あまり領域の取り戻しができません。時には、昇格によって使われるよりもずっと少なかったり、収集に多くの時間がかかり、さらに悪いことに、次のマーキングまでの時間を長くするだけだったりするでしょう。

この時点でG1は領域回収フェーズを開始するためのold世代領域の収集準備が整いました。しかし、最小ミューテーター使用率（MMU）要件を維持するために、G1は混合コレクションを開始する前に、別の最後のyoung世代のPrepare Mixed GCまで待つことを余儀なくされます。

A parallel, real-time garbage collector
https://dl.acm.org/doi/10.1145/381694.378823

Cleanupポーズが中断した（MMUの観察もしています）ミューテーターフェーズは、非混合コレクションのポーズのための予測を使用してMMUを維持するようにサイズ設定されています。ガベージコレクションの種類を変更すると、その計算中に行われた仮定が無効になります。

Concurrent Cleanup

Concurrent Cleanupフェーズでは、G1は、bottomとtams間の領域でマーク・ビットマップをクリアし、tamsをリセットしてG1の次のコンカレント・マーキング・サイクルに備えます。このフェーズでコンカレント・マーキング・サイクルは完了します。

Traceability in the VM

Concurrent Mark Cycleは簡単にログを使って追跡できます。 -Xlog:gc,gc+marking で、現在のconcurrent mark cycleフェーズを出力し、これらのフェーズの終了時にフェーズで要した時間を出力します。以下はその出力例です。

[441.432s][info][gc        ] GC(119) Pause Young (Concurrent Start) (G1 Evacuation Pause) 16928M->16520M(20480M) 199.167ms
[441.432s][info][gc        ] GC(120) Concurrent Mark Cycle
[441.432s][info][gc,marking] GC(120) Concurrent Clear Claimed Marks
[441.432s][info][gc,marking] GC(120) Concurrent Clear Claimed Marks 0.016ms
[441.432s][info][gc,marking] GC(120) Concurrent Scan Root Regions
[441.502s][info][gc,marking] GC(120) Concurrent Scan Root Regions 70.532ms
[441.502s][info][gc,marking] GC(120) Concurrent Mark
[441.502s][info][gc,marking] GC(120) Concurrent Mark From Roots
[443.770s][info][gc,marking] GC(120) Concurrent Mark From Roots 2267.531ms
[443.770s][info][gc,marking] GC(120) Concurrent Preclean
[443.770s][info][gc,marking] GC(120) Concurrent Preclean 0.032ms
[443.771s][info][gc,marking] GC(120) Concurrent Mark 2268.438ms
[443.771s][info][gc        ] GC(120) Pause Remark 16880M->16880M(20480M) 0.718ms
[443.771s][info][gc,marking] GC(120) Concurrent Rebuild Remembered Sets and Scrub Regions
[445.328s][info][gc,marking] GC(120) Concurrent Rebuild Remembered Sets and Scrub Regions 1556.808ms
[445.328s][info][gc        ] GC(120) Pause Cleanup 17184M->17184M(20480M) 0.383ms
[445.328s][info][gc,marking] GC(120) Concurrent Cleanup for Next Mark
[445.343s][info][gc,marking] GC(120) Concurrent Cleanup for Next Mark 15.138ms
[445.343s][info][gc        ] GC(120) Concurrent Mark Cycle 3911.573ms

このログのスニペットは、この投稿で説明した順序で実行されたフェーズを表しています。また、対応するJFRイベントもあります。

Differences to original G1

上記の文章は、JDK20のJDK-8210708による変更後のコンカレント・マーキング・サイクルとその間の単一ビットマップの使用方法について説明したものです。以前は、コンカレント・サイクルはこのG1の論文で説明されているものに近かいものでした。

JDK-8210708 Use single mark bitmap in G1
https://bugs.openjdk.org/browse/JDK-8210708
Garbage-first garbage collection
https://dl.acm.org/doi/10.1145/1029873.1029879

主な違いは、オリジナルのG1が2つのマーキングビットマップを維持し、それに対応する2つのtamsをリージョンごとに持っていた点です。ビットマップとtamsの1セットは、「次」のマーキングビットマップが完全に構築されるまで、オブジェクトの生存を決定するために使用されるマーキングの「前」の結果を含んでいます。Remarkポーズはこれらを入れ替え、「次」のビットマップを「前」のビットマップにし、次のコンカレント・マーキング・サイクルで使用するために以前の「前」のビットマップをクリアするものでした。

そのため、G1は常に、領域内のどのオブジェクトが生存しているか、「前」のマーキングを使って知っていました。リージョンの内容やpbポインタをスクラブする必要はありませんでした。

オリジナルの G1 の主な欠点は、ビットマップのネイティブメモリ使用量が現在のメカニズムの2倍であることです。Java ヒープの1.5%ではなく、この情報のために3%を維持する必要がありました。大きなヒープでは、このサイズは相対的にも絶対的にもかなりのスペースになる可能性があります。とりわけ実際の記憶集合は現在でははるかに少ないスペースで済んでいます。

G1 GC – JDK 18 G1/Parallel/Serial GC changes
https://tschatzl.github.io/2022/03/14/jdk18-g1-parallel-gc-changes.html#g1gc
https://logico-jp.io/2022/04/05/jdk-18-g1-parallel-serial-gc-changes/#g1-gc

Impact Discussion

次の図は、以前の投稿と同じオプションを使用したBigRAMTesterベンチマークでのG1ネイティブメモリ使用量を示しています。参考のため、JDK 17のメモリ使用量（紺色）を追加しています。JDK 18では、記憶集合のデータ構造の改善により大幅に減少し（ピンク）、JDK 20ではJDK-8210708で導入された変更によりさらに大幅に減少しています（シアン）。

[JDK-8210708] Use single mark bitmap in G1
https://bugs.openjdk.org/browse/JDK-8210708

JDK 19はJDK 18と全く同じメモリ使用量なので、ここでは省略しました。

JDK 18とJDK 20のグラフはどちらも、メモリ使用量の下限を破線で示しています（対応する使用量の合計の線に比べてわずかに暗い色を使用）。この改善は、マークビットマップの削除に対応し、G1ネイティブメモリの総消費量を最大6.5%から推奨値1.5%に低下させました。これは記憶集合のストレステストであり、ネイティブメモリ使用量の大部分は実際の記憶集合（総メモリ使用量と下限との差）であるため、このアプリケーションでは改善はそれほど大きくありません。

通常、アプリケーションの記憶集合のネイティブメモリ使用量はもっと少ないので、相対的なネイティブメモリ使用量の減少はもっと大きいはずです。

このベンチマークでは、この変更の前後で、GCポーズやコンカレント・マーク・サイクルの時間に大きな違いはありません。

(観察力のある読者は、JDK 18とJDK 20の間でグラフの形が変わり、それぞれのグラフの下限とピークの間のメモリ使用量が回帰していることに気づいたかもしれません。これはJDK-8292654で修正されています）。

[JDK-8292654] G1 remembered set memory footprint regression after JDK-8286115
https://bugs.openjdk.org/browse/JDK-8292654

Summary

これが役立つことを願っています。コメント、提案は筆者に直接か、hotspot-gc-use@openjdk.java.net または hotspot-gc-dev@openjdk.java.net までお願いします。

Logico Inside

Concurrent Marking in G1

Introduction and Background

Data structures in use

Concurrent Marking in G1

Concurrent Start pause

Concurrent Scan Root Regions

Concurrent Mark

Concurrent Rebuild Remembered Sets and Scrub Regions

Cleanup pause

Concurrent Cleanup

Traceability in the VM

Differences to original G1

Impact Discussion

Summary

コメントを残すコメントをキャンセル

2022年9月
日	月	火	水	木	金	土
				1	2	3
4	5	6	7	8	9	10
11	12	13	14	15	16	17
18	19	20	21	22	23	24
25	26	27	28	29	30

Introduction and Background

Data structures in use

Concurrent Marking in G1

Concurrent Start pause

Concurrent Scan Root Regions

Concurrent Mark

Concurrent Rebuild Remembered Sets and Scrub Regions

Cleanup pause

Concurrent Cleanup

Traceability in the VM

Differences to original G1

Impact Discussion

Summary

共有:

いいね:

コメントを残す コメントをキャンセル

コメントを残すコメントをキャンセル