原文はこちら。
The original article was written by Thomas Schatzl (OpenJDK developer, Oracle).
https://tschatzl.github.io/2022/02/15/card-table-card-size.html

JDK 18 で設定可能なカードテーブル (card table) のカードサイズ (card size) が導入されました（JDK-8272773）。この記事では、カードテーブルとは何か、そしてこの新しいオプションを試したくなった理由をご紹介します。

[JDK-8272773] Configurable card table card size – Java Bug System
https://bugs.openjdk.java.net/browse/JDK-8272773

Introduction and Background

ガベージコレクタは、一時停止中のオブジェクトを移動させる際にそのオブジェクトへの参照をすべて調整して新しい場所を指すようにする必要があります。

素朴で非常に遅いアプローチでは、Javaヒープの非退避領域のすべてを反復して探し出すことになります。

カードテーブルを使うと、これらの参照を見つけるのが速くなります。これはside data structureで、各要素がJavaヒープの小さな部分に対応します。これらの要素をカード (card) と呼びます。さて、Javaアプリケーション（mutator）が参照を変更すると、VMはその参照を含むカードを特別な値に設定するコードを実行します。GCポーズ時に、ガベージコレクタがカードテーブル（Javaヒープよりはるかに小さいためトラバースが高速）を検索して、これらの特別な値を探します。この特別な値が見つかると、ガベージコレクタは退避領域への参照のために対応するJavaヒープ領域を検索します。このようなデータ構造は、一般に記憶集合 (remembered set) とも呼ばれます。

以下の論文では、この手法をより詳しく説明しています。

Remembered Sets Can Also Play Cards (1993)
https://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.51.7061

すべてのHotSpotの stop-the-world ガベージコレクター（Serial、Parallel、G1 GC）は、何らかの形でカードテーブルを使っています。Serial GCとParallel GCの場合、上記論文にあるように、ほぼ確実に使用しています。

この記事ではG1を使用してこの変更の影響を説明するため、G1GCがどのようにカードテーブルを使用するかについてもう少し背景を説明する必要があるでしょう。G1では、カードテーブルのデータ構造は存在するものの、（Serial GCやParallel GCとは）使用方法が全く異なります。

G1で利用方法が異なる理由は、G1が任意のヒープ領域でも独立した退避が可能であるため、すべての領域で独自の記憶セットが必要になるからです。これは、領域ごとに追加されたカードの集合で、すべてのカードはその領域への参照があるかもしれない場所を示しています。

Heap Layout
https://docs.oracle.com/en/java/javase/17/gctuning/garbage-first-g1-garbage-collector1.html#GUID-15921907-B297-43A4-8C48-DC88035BC7CF
ヒープレイアウト
https://docs.oracle.com/javase/jp/17/gctuning/garbage-first-g1-garbage-collector1.html#GUID-15921907-B297-43A4-8C48-DC88035BC7CF

• mutatorが動作する間、G1ではカードテーブルは潜在的な参照の場所を一時的に保存するだけです。対応するカードをマークすることに加えて、mutatorスレッドは、そのカードが以前にマークされていなければその変更をスレッドローカルのログバッファに保存し、同時調整のためのバックグラウンド・スレッドがそれを定期的に処理します。この同時調整により、カードテーブル上のマークがクリアされ（その間、同じカードの追加調整リクエストのためのフィルタとして機能します）、カードに対応する領域が参照用にスキャンされ、適切な記憶集合に設定されます。
• GCポーズ中、カードテーブルのデータ構造は再利用されます。まずコレクションセット全体のために結合された記憶集合を決定するために再利用され（gc+phases=debug のログレベルでのMerge Heap Rootsフェーズ）、続いて（Scan Heap Rootsフェーズで）他のガベージコレクタと同様にそのコレクションセットへの参照をスキャンします。
  GCが終了すると、G1は（Clear Logged Cards および Redirty Logged Cards フェーズで）mutatorフェーズで使用するためにカードテーブルを準備する必要があります。

Garbage Collection Pauses and Collection Set
https://docs.oracle.com/en/java/javase/17/gctuning/garbage-first-g1-garbage-collector1.html#GUID-3A99AE6C-F80A-4565-A27C-B4AEDF5CDF71
ガベージ・コレクションによる一時停止とコレクション・セット
https://docs.oracle.com/javase/jp/17/gctuning/garbage-first-g1-garbage-collector1.html#GUID-3A99AE6C-F80A-4565-A27C-B4AEDF5CDF71

The Change

これまで、カードがカバーする領域の大きさは512バイトに固定されていました。このサイズは、カードテーブルのサイズ（カード1枚につき1バイト、結果としてJavaヒープサイズの約0.2%のメモリ使用量）と、ガベージコレクション時にその領域内の参照を見つけるのにかかる時間とのトレードオフになっていました。

JDK 18では、-XX:GCCardSizeInBytesを使用して、128、256、512（デフォルト）、1024（1024は64ビットのみ、単位はいずれもバイト）のいずれかから値を選択できます。

Impact Discussion

元々の貢献者であるV. Chandが、この値を1024バイトに増やした場合、G1で SPECjbb2015 critical-jOPS (latency) スコアが向上することを確認しました。この場合、ハードウェアと使用するベンチマークの組み合わせにより、Clear Logged Cardsフェーズ（当時はClear Card Tableフェーズと呼ばれていました）が大幅に短縮されたことが改善の原因です。

SPECjbb2015はOld世代とYoung世代間の実際の参照数が非常に少なく、典型的なチューニングを施した設定ではYoung世代のGCのみが実行され、Young世代は膨大（ヒープの90％ほど）になっています。SPECjbb2015は、旧世代と若世代の間の実際の参照数が非常に少なく、典型的な調整済みの設定では、若世代のGCのみが実行され、若世代は膨大（ヒープの90%程度）になっています。そのため、次のmutatorフェーズのためにカードテーブルを準備し、young世代のサイズに比例して時間を要するClear Logged Cardsフェーズは、かなり長い時間がかかります。カードテーブルのカードサイズを2倍にすることでその作業を半分にし、ポーズ時間とベンチマークスコアへの影響を観察しました。この効果は、CRに添付したスプレッドシートで確認できます。

[JDK-8272773] Configurable card table card size – Java Bug System
https://bugs.openjdk.java.net/browse/JDK-8272773

より興味深く、より一般的なケースは、カードテーブルのサイズを小さくすることです。
アプリケーションのScan Heap Roots時間がガベージコレクション時間の大部分を占め、参照がかなりまとまって存在している場合、より小さなカードを使用することで大きな性能向上が期待できるかもしれません。もちろん、このメリットは、カードテーブルが大きくなるにつれてスキャンする（より小さい）カードや、の追加メモリ使用量によって相殺されるかもしれませんが、全体としてはメリットが上回る可能性があります。

この種のアプリケーションとしては、BigRAMTester（JDK-8152438のLRU管理型オブジェクトキャッシュ）があり、まさにこの挙動を示しています。

[JDK-8152438] Threads may do significant work out of the non-shared overflow buffer – Java Bug System
https://bugs.openjdk.java.net/browse/JDK-8152438

GCポーズ時間の約60-70%は、参照用のカードを探すのに費やされています。下図のScan Heap Rootsフェーズ（ログのFound Rootsメトリックによる）でスキャンされたキロバイトあたりの参照数（roots: Scan Cardsメトリックによる）からわかるように、参照数は多くありません。

つまり、完全に空のカードであろうとなかろうと、すべてのカードを含めて平均すると、カードテーブルには1枚あたり1～2個のルートしか存在しないのです。カードサイズを128バイトから1024バイトまで変えてグラフにプロットすると、カードサイズを変えることでこの比率をかなり改善できることがわかります。

このアプリケーションでは、カードサイズを小さくすると、比例してメモリ単位でスキャンするrootの量が増える、つまり作業量が少なくなります。これは、より正確な位置を持つことで、Scan Heap Rootsフェーズがかなり減少する可能性があることを示しています。ここでの仮説は、rootsの間隔がかなり広い（roots/カードの比率がかなり近しい）ため、カードサイズを1024バイトに増やしても、スキャン対象のkBあたりのrootsの量はあまり変化しないというものです。

下図は、このアプリケーションにおいて、カードサイズが一時停止時間に与える影響を示しています。

カードサイズが1024バイトの場合（水色）、GCポーズ時間が増加します。これは、他のケースよりも探索対象のメモリ量が多いためで、他のすべての利点を帳消しにしてしまっています。カードサイズが128バイト（青）と256バイト（紫）の場合のGCPポーズ時間は基本的に同じです。カードサイズが小さいほどScan Heap Rootsフェーズは短くなりますが、ガベージコレクションの他のフェーズ（主にMerge Heap Rootsフェーズですが、Clear Logged Cardsフェーズも）は比例して長くなる傾向があり、互いに相殺し合っています。

このアプリケーションでは、他のオプションのチューニングをしなくても、256バイトのカードサイズが最適と思われます。GCポーズ時間は、半分のメモリ使用量である128バイトのカードサイズの場合と同じくらいで、デフォルトの512バイト（黄色）の場合よりも約20％優れています。

カードテーブルサイズを256バイトにした場合にJavaヒープメモリ使用量が0.2%増える点を許容できるなら、このアプリケーションでは価値のあるトレードオフと思われます。

Summary

Serial GC、Parallel GC、G1 GCで使われるトラッキング用の記憶集合の粒度を変更する新しいオプション -XX:GCCardSizeInBytes がJDK 18で追加されました。これを使うと、様々なGCフェーズに必要な作業量を変更できます。この投稿では、アプリケーションによっては、カードサイズ変更によってGCポーズ時間が大幅に変わる、つまり時には良く、時には悪くすることがあることを示しています。

カードサイズを使ったチューニングの経験を聞かせていただければ幸いです。コメントは筆者、hotspot-gc-use@openjdk.java.net または hotspot-gc-dev@openjdk.java.net までお願いします。