原文はこちら。
The original article was written by Jinyu Yu (Embedded Systems MSc, KTH Royal Institute of Technology).
https://inside.java/2022/07/01/mitigate-relocation-degradations/

この記事で記載している成果は、Oracle、Uppsala大学、KTHによる共同研究の一環によるものです。ストックホルムのOracle DevelopmentオフィスでのJVM研究について詳細を知りたい方は、inside.javaのブログをフォローしてください。

Oracle, Uppsala University, and KTH in joint JVM research projects
https://inside.java/2020/06/12/joint-research-projects/

---

こんにちは、Jinyu Yuです。KTHの学生で、Embedded Systemsを専攻しています。2021年、Oracleは低レイテンシのガベージコレクターであるZGCについて修士論文を書くという素晴らしい機会を提供してくれました。

Oracle, Uppsala University, and KTH in joint JVM research projects
https://inside.java/2020/06/12/joint-research-projects/

指導教官であるTobias Wrigstad、Per Lidén、Erik Österlundの貴重な指導のもと、私はZGCの再配置性能を向上する実装に成功しました。

キャッシュの局所性はプログラムの性能にとって重要です。キャッシュの局所性を向上させることで、プログラムのスループットを向上させることを目的としたアルゴリズムが多く提案されてきましたが、局所性の向上は必ずしも容易ではなく、時には欠点が利点を上回り、全体的な性能を低下させることもあります。私の論文「Improving relocation performance in ZGC by identifying the size of small objects」では、局所性改善アルゴリズムの一つであるHCSGCの欠点を分析し、それを軽減する再配置の改善策を提案しました。

Improving relocation performance in ZGC by identifying the size of small objects
http://wrigstad.com/oracle/#thesis4
Improving program locality in the GC using hotness
https://dl.acm.org/doi/10.1145/3385412.3385977

The importance of cache locality: why and when

メモリはCPUのキャッシュに比べ、かなり低速であることは既にご存じかもしれません。さらに悪いことに、メモリに保存されたデータは、CPUで処理される前にキャッシュにロードされる必要があります。すべてのメモリフェッチは固定サイズ（キャッシュラインのサイズ、通常は64バイト）であるため、複数の小さなオブジェクトを一度にロードできます。一緒にアクセスされることが多いオブジェクトを同じキャッシュラインに配置すれば、キャッシュの局所性を良好になります。そうすることで、より少ないメモリ操作でオブジェクトをロードすることができ、結果的にパフォーマンスが向上します。

3つの小さなオブジェクト、A、B、Cを考えてみましょう。これらは順番にアクセスされます。3つのオブジェクトがすべて異なるキャッシュラインに入ると、キャッシュ局所性は最悪です。この場合、これらすべてのオブジェクトを取得するために、3回のメモリアクセスが必要です。キャッシュ局所性が良ければ、これらのオブジェクトは同じキャッシュラインに入る可能性があり、一度にロードできます。隣接するキャッシュラインに入る可能性もありますが、それでも、ハードウェアプリフェッチャの存在により、前のケース（同一キャッシュラインに入る場合）に近い良好な性能になるでしょう。ほとんどの場合有効になっているnext-line hardware prefetcherは、メモリアクセスが発生するたびに、次のキャッシュラインを自動的にフェッチします。その結果、小さなオブジェクトの局所性が良くなれば、性能向上につながる可能性が高くなります。

大きなオブジェクトをまとめると、利益が得られないのです。ここで、より大きなオブジェクトBを考えてみます。このBは、今回 128 個の整数を含む配列だとしましょう。この場合、500 バイト以上のメモリを消費するため、1 つのキャッシュ ラインに配置できません。これらの3つのオブジェクトは、A、B[50]、Cと同じようにアクセスされます。下図は、最善の局所性と最悪の局所性をそれぞれ図示したものです。B[50]はBの両方の境界から遠いので、この3つのオブジェクトをどんなに近くに置いても、3回のメモリアクセスが必要です。

Improve the cache locality: method and drawbacks

ここまでで、キャッシュの局所性が小さなオブジェクトに対して重要であることがわかりました。キャッシュの局所性を向上させるポイントは、一緒にアクセスされるオブジェクトを見つけること、言い換えれば、オブジェクトのアクセスパターンを把握することです。

How does ZGC work

キャッシュの局所性を深掘りする前に、ZGCの基本的な考え方を簡単に説明します。ZGCには、3種類のサイズのページ (small/medium/large) があります。オブジェクトはその大きさに応じて異なるページに配置されます。

ページサイズ	オブジェクトサイズ
Small	[0, 256] KB
Medium	(256 KB, 4MB]
Large	>4MB

ZGCのサイクルには3つの同時進行フェーズがあります。Mark/Remapフェーズでは、ZGCは他のGCと同様に、すべてのライブオブジェクトをマークするためにオブジェクトトラバーサルを実行します。その間に、ページごとの生存情報が次のフェーズのために記録されます。次に、evacuation candidates（退避候補、ECと表記）フェーズでは、ライブバイトの比率が75%閾値以下のページがECとしてマークされます。最後のステップである再配置フェーズでは、EC内のすべてのライブオブジェクトが新しいページに再配置されます。古いページとその上のDeadオブジェクトは、その後解放されます。

How does HCSGC work

HCSGCでは、キャッシュの局所性を改善する方法として、ECの拡大と遅延再配置の主要な2方法を提案しました。HCSGC（Hot-Cold Objects Segregation GC）は、その名の通り、オブジェクトがホットな状態かどうかを識別することで局所性を改善しようとするものです。ZGCでは、ページの比較的小さな部分だけをECとして選択し、後で再配置しますが、局所性を操作するためには、より多くの再配置が必要です。HCSGCでは、再配置の回数を増やすため、ホットなオブジェクトを多く含むsmall pageもECとして選択します。前回のGC以降にアクセスされた場合、そのオブジェクトをホットとみなします。再びアクセスされる可能性を考慮すれば、局所性を向上させると、コールドオブジェクトよりもホットオブジェクトでより多くの恩恵を得られるのは明らかです。

HCSGCでは、先ほどの第3フェーズである再配置フェーズは、次のGCサイクルの開始時に移動され、遅延再配置 (Lazy relocation) と呼ばれます。2回のGCサイクルの間、オブジェクトがアクセスされたときにミューテータが再配置を行います。これにより、2つのGCサイクルの間に、ミューテータのアクセスパターンに従ってオブジェクトを配置することが可能になります。

Drawbacks

ECの拡大や遅延再配置により局所性は向上しますが、その代償として再配置性能が低下します。ECを拡大すると、より多くのページが選択されるため、再配置の速度が低下します。そのため、より効果のあるページを選択することが重要です。HCSGCは、ホットオブジェクトとスモールオブジェクトを選択することで、効果的に再配置量を増やそうとしました。ここでいうホットとは、前回のGC以降にアクセスがあったオブジェクト、スモールとは、small pageに配置されたオブジェクトを意味します。しかしながら、small pageは十分に小さいとは言えません。ZGCのsmall pageは256KByteまでのオブジェクトを格納できますが、再配置の恩恵を受けられるのは、数キャッシュライン（せいぜい数百バイト）に配置できるオブジェクトだけだからです。その結果、多くの大きなオブジェクトが移動され、スループットを上げることなく、メモリに大きな負荷がかかることになります。

遅延再配置は、2つの点で後退をもたらします。まず第一に、HCSGCの再配置は、同時実行のGCスレッドではなくミューテータースレッドが処理するため、他のワークロードと競合することになります。第二に、遅延再配置フェーズでは、ガベージが長く保持されるため、メモリがより断片化されることになるため、メモリ使用量が多くなり、GC回数が増加する可能性があります。メモリに制約のある環境では、断片化したメモリはGC回数を大幅に増やし、パフォーマンスの低下につながります。

The relocation improvement

Methodology

さて、私たちはHCSGCがもたらす3つのリグレッションに直面しています。

1. （比較的）大きなオブジェクトの再配置では、メモリに大きな負荷を与える
2. 再配置がミューテーターと競合する
3. メモリが断片化する

局所性を損なわずに再配置量を減らすことが、最初の2つのリグレッションを緩和する鍵になります。簡単な方法は、オブジェクトを再配置する際に、オブジェクトの大きさをチェックするif節を追加することです。しかしながら、これではメモリの断片化に対応できません。というのも、遅延再配置はページ単位で行われるため、ページの一部だけを遅延再配置できないためです。そこで、もう一つのアイデア、大きいオブジェクトと小さいオブジェクトを別々のページに配置する、というものが出てきます。そうすれば、より小さなsmall pageでHCSGCを有効にし、大きなsmall pageでHCSGCを無効にするだけで、3つのリグレッションを同時に緩和できる可能性があります。

そこで、ZGCに4番目のページクラスであるtiny pageを導入します。従来のsmall page (0～256KB) を、新しいsmall page（256B～256KB）と新しいtiny page（0～256B）に分割します。HCSGCは、tiny pageを除くすべてのページクラスで無効となる予定です。その結果、十分に小さなオブジェクトは局所性向上のために最適化される機会を得つつも、そのような向上の恩恵を受けることのない大きなオブジェクトはすべてオリジナルのZGCにおける挙動のままで、高い並行性を維持することになります。

ページサイズ	オブジェクトサイズ
Tiny	[0, 256] Bytes
Small	(256B, 256KB]
Medium	(256 KB, 4MB]
Large	>4MB

Benefits

再配置の改良は、主に移動してもメリットのないオブジェクトを対象としています。1KBytesのオブジェクトを大量に持つプログラムを考えてみましょう。オリジナルのHCSGCの実装では、再配置による性能向上は望めませんが、これらのオブジェクトはすべてsmall pageに配置され、遅延再配置が行われることになります。CPUに制約のある環境では、このようなオブジェクトの移動はシステムに大きな負荷を与え、プログラムの速度を低下させる可能性があります。また、メモリに制約のある環境では、メモリの断片化によりGC回数が増加し、性能が低下するでしょう。これに対して、我々の設計では、これらのオブジェクトをHCSGCが無効な新しいsmall pageに配置します。これらは同時実行のGCスレッドに再配置されるため、ミューテーターと競合することはありません。

Showcase

最も良い結果の一つが、JGraphTベンチマークのmaximal cliqueアルゴリズムによるものです。メモリ制約のある環境をエミュレートするために、メモリサイズを512MBに制限しています。このテストでは、HCSGCはオリジナルのZGCよりも46.31%優れていました。私たちの再配置の改善により、オリジナルのHCSGCよりもさらに3.4%改善されました。

Config	Mean	Standard Deviation	Relative Standard Deviation	Performance
HCSGC	138656.00	930.11	0.67%	0.00%
Tiny pages	133948.00	1284.04	0.96%	3.40%
ZGC	202871.33	11064.45	5.45%	‐46.31%