オリノコ：若年期世代回収（GC）

Japanese Translation:

サマリー:

V8 は、若き世代データを処理するために従来の Cheney 半空間アルゴリズムを新たな並列 Scavenger に置き換え、メモリの管理を大幅に強化しました。バージョン 6.2 からこの移行により、エンジンが複数の CPU コアを実効的に活用でき、動作が劇的に高速化され、待機時間が削減される一方、小規模なヒープ上でも速度は損なわれなくなっています。重要な技術的要素として、タスクをスレッド間で分散させて効率を最大化する動的ワークスティーリングを使用しています。従来の静的メソッドとは異なり、このアプローチでは複数のタスク上で走査フェーズとコピーフェーズを組み合わせて実行し、高速なローカルストレージを保証すると同時に、より良いバランスのためにグローバルワークリストを共有します。以前のバージョンは静的なワークスティーリングに依存しており、現代のマルチコアハードウェアで課題がありました。新しいシステムは Halstead の設計に触発されていますが、高スループットに適応させており、ベンチマークにおいて若き世代のガーベージコレクション時間を 20〜50% 削減しています。これは、Web アプリケーション全体としての GC 時間の約 55% 削減に相当します。その結果、開発者はより高速なアプリ起動と滑らかなユーザー体験を享受でき、V8 は、強力なサーバーから低エンドのモバイルハードウェアまで幅広いデバイスにおいて、性能とメモリの効率性を両立させることで、引き続き極めて競争力の高い状態を維持しています。

V8 エンジンにおける JavaScript オブジェクトは、V8 のガブリーコレクション (GC) によって管理されるヒープ上に割り当てられます。これまでのブログ記事で、GC のポーズ時間削減やメモリ使用量の低減について繰り返しご説明しておりましたが、今回は、V8 のほぼ並行・並列型のガブリーコレクションエンジンである「オリーノコ (Orinoco)」の最新機能であるパラレルスクーベンジャー (Scavenger) を紹介するとともに、開発過程で検討した設計決定や代替案についても議論します。

V8 は管理ヒープを世代に分割しており、オブジェクトは当初「若い世代」の「ナースリー」として割り当てられます。ガブリーコレクションを生き延びたオブジェクトはコピーされ、「中間世代」へ移動しますが、これは依然として若い世代の一部となります。さらに別の GC を生き延びた後では、これらのオブジェクトは古くしい世代（Old Generation）へ移動します（図 1 を参照）。

V8 は以下の 2 つのガブリーコレクションを実装しています：
- 若い世代を頻繁に収集するもの。
- 若年世代も老年世代も含む全体ヒープを収集するもの。
老年世代から若い世代への参照は、若い世代の GC における「ルート」として機能します。
これらの参照は記録されおり、オブジェクトが移動した際に効率的なルートの特定や参照更新を実現するためのものです。

図 1：世代型ガブリーコレクション

若い世代は比較的小さく（V8 では最大 16MiB に制限）、オブジェクトで急速に満ちてしまい、頻繁な収集が求められます。v6.2 より以前、V8 は若年世代の収集アルゴリズムとしてチェーニー (Cheney) の半空間コピー式 GC を採用していましたが（以下参照）、これは若年世代を 2 つの領域に分割します。JavaScript の実行時には、若い世代のうち一方の領域だけがオブジェクトの割り当てに使用され、もう一方は空のまま保たれます。若き世代の GC が発生すると、生きているオブジェクトが一方から他方へコピーされ、メモリアリーナ内で即座に緊密化 (compacting) されます。一度もコピーされたことがない生きているオブジェクトのみが「中間世代」に含まれ、さらに GC を生き延びると古くしい世代へと昇格します。

v6.2 から、V8 は若年世代の収集アルゴリズムのデフォルトを、ハルステッド (Halstead) の半空間コピー式コレクションに類似したパラレルスクーベンジャーに変更しました（違いとしては、V8 が複数スレッド間で動的なワークスティーリングを採用している点にあります）。以下では 3 つのアルゴリズムについて説明します： a) シングルスレッド型のチェーニー半空間コピー収集器。 b) 並行マーク・エバシュート方式。 c) パラレルスクーベンジャー。

チェーニーの単スレッド半空間コピー

v6.2 より以前、V8 は単一コアの実行にも世代型スキームにも適合しうるチェーニーの半空間コピーアルゴリズムを採用していました。若年世代の収集直前、メモリの両方の半空間領域はコミットされ、適切なラベルが付けられます：現在のオブジェクトセットを含むページを「呼出しスペース (from-space)」、「オブジェクトのコピー先」を「呼び出スペース (to-space)」と呼びます。

スクーベンジャーでは、コールスタック内の参照および老年世代から若年世代への参照をルートとみなします。図 2 は初期段階でこれらルートを走査し、from-space で到達可能なが to-space にまだコピーされていないオブジェクトのみをコピーするアルゴリズムを示しています。すでに GC を生き延びているオブジェクトは古くしい世代へ昇格（移動）されます。ルート走査および最初の複製ラウンドの後に、新しく割り当てられた to-space 内のオブジェクトに対する参照も同様に走査されます。さらに、昇格された全てのオブジェクトについても from-space への新たな参照が走査されます。この 3 つのフェーズはメインスレッド上で交互に実行されます。このアルゴリズムは、to-space も老年世代からも新たに到達可能なオブジェクトが存在し続けるまで継続します。この時点で from-space は未到達のオブジェクト（つまり、ゴミ）のみを含み残ります。

図 2：V8 の若年世代 GC で使用されるチェーニーの半空間コピーアルゴリズム

並行マーク・エバシュート方式

V8 のフル Mark-Sweep-Compact コレクタをベースに、並行マーク・エバシュートアルゴリズムを実装し検証しました。主な利点は、フルマークスイープコレクションインフラストラクチャを活用できることです。このアルゴリズムは図 3 に示すように、マーク（生きているオブジェクトの特定）、コピー、ポインタ更新という 3 つのフェーズから構成されます。若年世代のページをスーミングせずにフリーリストを維持するため、GC 中に生きていまするオブジェクトを to-space へコピーして常に緊密化されたまま保つ半空間方式が依然として採用されています。

まず若年世代に対して並列でマーク処理が行われ、その後に生きているオブジェクトが並列に対応する領域へコピーされます。作業は論理的なページの単位で分担され、コピーに参加するスレッドはそれぞれローカル割付バッファ (LAB) を維持しており、コピー完了時にマージします。コピー終了後、同様の並列化方式を用いてオブジェクト間のポインタ更新も実行されます。この 3 つのフェーズはロックステップ（互いに同期して）で実行され、各スレッドは次のフェーズに進む前に同期をとる必要があります。

図 3：V8 の若年世代向け並行マーク・エバシュート GC

パラレルスクーベンジャー

並行マーク・エバシュート収集器は、生きているかどうかの判定、生きているオブジェクトのコピー、ポインタ更新というフェーズを分離しています。明らかな最適化として、これらのフェーズを統合し、マーク・コピー・ポインタ更新を同時に実行するアルゴリズムを得ることができます。このフェーズ統合により得られたものが V8 で採用されているパラレルスクーベンジャーであり、ハルステッドの半空間収集器に類似していますが、V8 ではルートの走査のために動的なワークスティーリングと単純な負荷分散機構を採用しています（図 4 を参照）。

単スレッド型チェーニーアルゴリズムと同様に、以下のフェーズが存在します：

ルートの走査。
若年世代内でのコピー。
古くしい世代への昇格。
ポインタの更新。

我々は、ルートの大部分は通常、老年世代から若年世代への参照であることを発見しました。実装ではページ単位でレメンバーセット (remembered set) を維持しており、これにより自然にルートの集合が GC スレッド間で分散されます。オブジェクトはその後並列処理されます。新たに発見されたオブジェクトはグローバルワークリストに追加され、GC スレッドからここへワークを盗むことができます。このワークリストはタスクローカルな高速ストレージおよび、作業共有のためのグローバルストレージを提供します。バーリアーにより、現在処理中のサブグラフがワークスティーリングに適さない場合（例：線形チェイン状のオブジェクト）にタスクが早すぎるタイミングで終了しないことを保証します。全てのフェーズは並列実行され、各タスク上で交互に実行されることで、ワーカータスクの利用効率を最大化します。

図 4：V8 の若年世代向けパラレルスクーベンジャー

結果と結論

スクーベンジャーアルゴリズム当初の設計では、シングルコアでの最適なパフォーマンスを念頭に置いていました。その後、状況は大きく変わりました。現在では、低性能なモバイルデバイスでも多数の CPU コアが存在することが一般的であり、さらに多くの場合、これらのコアは実際に動作しています。これらコアを完全に活用するためには、V8 の GC における最後のシーケンシャル成分であったスクーベンジャーの近代化が不可欠でした。

並行マーク・エバシュート収集器の最大の利点は、正確な生きているかどうかの情報（ライブネス情報）を利用できる点にあります。例えば、これを用いてほとんどが生きているオブジェクトを含むページを全くコピーせずに移動・再リンクし、パフォーマンス向上を図ることが可能ですが、これはフル Mark-Sweep-Compact コレクタも同様に実行します。実際には、この手法は合成ベンチマークでは効果が観測されたものの、実ウェブサイトのケースではあまり顕著ではありませんでした。一方で、並行マーク・エバシュート収集器の欠点としては、3 つの別々のロックステップフェーズを実行することによるオーバーヘッドが存在します。特にヒープがほとんど死んでいるオブジェクトで構成されている場合（多くの現実の Web サイトに見られる状況）、GC を呼び出す際のこのオーバーヘッドが目立ちます。なお、死んでいるオブジェクトが大半のヒープ上で GC を実行することは理想的なシナリオであり、GC の時間は通常、生きているオブジェクトのサイズに限定されるためです。

パラレルスクーベンジャーはこのパフォーマンスギャップを埋め、小さいかあるいはほぼ空のヒープ上では最適化されたチェーニーアルゴリズムに匹敵するパフォーマンスを提供しつつ、大量の生きているオブジェクトを含む大きなヒープでも高いスループットを実現します。

V8 は ARM big.LITTLE などのプラットフォームもサポートしています。小コアでタスクオフロードを行うことによりバッテリー寿命を延ばすことができますが、小コアへの作業パッケージが大きすぎるとメインスレッドでの停止（ストール）を引き起こす可能性があります。我々は観察し、ページレベルの並列化では若年世代 GC において big.LITTLE アーキテクチャに適切に負荷が分散しないことを確認しました（ページ数が限られているため）。スクーベンジャーは、明示的なワークリストとワークスティーリングによる中粒度の同期を提供することで、この問題を自然に解決します。

図 5：様々なウェブサイトにおける若年世代 GC の総時間（ms）

現在、V8 はパラレルスクーベンジャーを標準搭載しており、多数のベンチマークにおいてメインスレッド上の若年世代 GC 全体の時間を約 20%〜50% 削減しています（詳細はパフォーマンスウォーターフォール参照）。図 5 は実ウェブサイトの比較を示しており、最大値と平均値ともにポーズ時間が改善され、最低値も維持されています（改善率は約 55% に達し、これは約 2 倍の向上です）。並行マーク・エバシュート方式でもさらなる最適化の可能性がありますが、次はどのような展開になるかお楽しみにください。