Orinoco: 若い世代のガベージコレクション
V8でのJavaScriptオブジェクトは、V8のガベージコレクタによって管理されているヒープ上に割り当てられます。以前のブログ記事では、ガベージコレクションの停止時間を短縮する方法（複数回）やメモリ消費量を削減する方法について既に説明しました。本記事では、Orinocoの最新機能の1つである並列スカベンジャーを紹介し、V8のガベージコレクタの設計決定や、進行途中で実装した代替アプローチについて議論します。
V8は、そのヒープを世代に分割し、オブジェクトは最初に若い世代の「ナーサリー」に割り当てられます。ガベージコレクションを生き残ると、オブジェクトは若い世代の一部である中間世代にコピーされ、さらに別のガベージコレクションを生き残ると、これらのオブジェクトは古い世代に移されます（図1参照）。V8は、若い世代を頻繁に収集するガベージコレクタと、若い世代と古い世代の両方を含む全ヒープを収集するガベージコレクタの2つを実装しています。古い世代から若い世代への参照は、若い世代のガベージコレクションにおけるルートとして機能します。これらの参照は記録され、オブジェクトが移動されたときに効率的なルート識別と参照更新を提供します。
若い世代は比較的小さいため（V8では最大16MiB）、オブジェクトで素早く埋まり、頻繁な収集が必要となります。M62まで、V8はCheneyのセミスペースコピー方式のガベージコレクタ（以下参照）を使用していました。この方式では若い世代が2つの半分に分割されます。JavaScriptの実行中は、若い世代の片方の半分だけがオブジェクトを割り当てるのに使用可能で、もう片方は空のままに保たれます。若い世代のガベージコレクション中に、生存しているオブジェクトは片方からもう片方へコピーされ、メモリはオンザフライでコンパクト化されます。一度コピーされたオブジェクトは中間世代の一部とみなされ、古い世代に昇格されます。
v6.2以降、V8は若い世代を収集するデフォルトのアルゴリズムとして並列スカベンジャーに切り替えました。これはHalsteadのセミスペースコピー収集器に類似していますが、静的ではなく動的なワークスティールを複数スレッドで使用する点が異なります。以下では、a) シングルスレッドのCheneyセミスペースコピー収集器、b) 並列Mark-Evacuate方式、c) 並列スカベンジャーの3つのアルゴリズムを説明します。
シングルスレッドCheneyのセミスペースコピー
v6.2まで、V8はCheneyのセミスペースコピーアルゴリズムを使用していました。このアルゴリズムはシングルコアの実行や世代スキームに適しています。若い世代の収集の前には、メモリのセミスペースの両方がコミットされ、適切なラベルが割り当てられます：現在のオブジェクトセットを含むページは「from-space」と呼ばれ、オブジェクトがコピーされるページは「to-space」と呼ばれます。
スカベンジャーは、コールスタック内の参照および古い世代から若い世代への参照をルートとして考慮します。図2はアルゴリズムを示しており、最初にスカベンジャーがこれらのルートをスキャンし、まだ「to-space」にコピーされていない「from-space」内で到達可能なオブジェクトをコピーします。すでにガベージコレクションを生き延びたオブジェクトは昇格（移動）して古い世代に移されます。ルートをスキャンし、最初のコピーラウンドの後、to-spaceに新しく割り当てられたオブジェクトが参照についてスキャンされます。同様に、昇格した全オブジェクトも「from-space」への新しい参照についてスキャンされます。これらの3つのフェーズはメインスレッドで交互に行われます。このアルゴリズムは、「to-space」または古い世代のいずれからも新しいオブジェクトが到達可能でなくなるまで続きます。この時点で、「from-space」には到達不可能なオブジェクト、すなわちゴミだけが残ります。
並列Mark-Evacuate
V8の完全なMark-Sweep-Compactコレクタに基づいた並列Mark-Evacuateアルゴリズムを試験しました。主な利点は、既存の完全なMark-Sweep-Compactコレクタからのガーベッジコレクションインフラストラクチャを利用できることです。このアルゴリズムは、図3に示すように、マーキング、コピー、ポインタの更新の3フェーズで構成されています。若い世代のページをスイープしてフリーリストを維持することを避けるため、若い世代はセミスペースを使用して管理され、ガーベッジコレクション中に生存オブジェクトを_to-space_にコピーすることで常にコンパクトに保たれます。若い世代は最初に並列でマークされます。その後、生存オブジェクトは対応するスペースに並列でコピーされます。作業は論理ページに基づいて分配されます。コピーに参加するスレッドは、自身のローカルアロケーションバッファ（LAB）を保持し、コピーの終了時にマージされます。コピー後、オブジェクト間のポインタを更新するために同じ並列化スキームが適用されます。これらの3つのフェーズはロックステップで実行されます。つまり、フェーズ自体は並列で実行されますが、次のフェーズに進む前にスレッドは同期する必要があります。
並列スカベンジ
並列Mark-Evacuateコレクタは、生存状態の計算、生存オブジェクトのコピー、ポインタの更新のフェーズを分離します。一目瞭然の最適化は、これらのフェーズを統合することであり、マーキング、コピー、ポインタの更新を同時に行うアルゴリズムになります。これらのフェーズを統合することで、実際にV8で使用される並列Scavengerが得られます。このScavengerは、Halstead’sセミスペースコレクタと似ており、V8が動的な作業盗難と単純な負荷分散メカニズムを使用してルートをスキャンする点で異なります（図4参照）。シングルスレッドのCheneyアルゴリズムと同様に、フェーズはルートのスキャン、若い世代内のコピー、古い世代への昇格、ポインタの更新です。我々は、通常、ルートセットの大部分が古い世代から若い世代への参照であることを発見しました。我々の実装では、ルートセットをガーベッジコレクションスレッド間に自然に分割するため、記憶セットがページごとに維持されます。オブジェクトは並列で処理され、新たに見つかったオブジェクトはガーベッジコレクションスレッドが盗むことができるグローバルな作業リストに追加されます。この作業リストは、タスクのローカルストレージと、作業を共有するためのグローバルストレージを高速で提供します。バリアは、現在処理中のサブグラフが作業盗難に適さない場合（例えばオブジェクトの線形チェーン）に、タスクが早期終了しないようにします。すべてのフェーズは並列で実行され、各タスクでインターリーブされ、作業タスクの利用を最大化します。
結果と成果
Scavengerアルゴリズムは当初、シングルコア性能を最適化することを念頭に設計されていました。それ以来、状況は変化しました。低価格のモバイルデバイスでもCPUコアは豊富であることが一般的です。さらに重要なのは、しばしばこれらのコアが実際に稼働状態にあるということです。これらのコアを完全に活用するために、V8のガーベッジコレクタの最後のシーケンシャルコンポーネントの1つであるScavengerを最新化する必要がありました。
並列Mark-Evacuateコレクタの大きな利点は、正確な生存情報が得られることです。この情報は、ほとんどが生存オブジェクトを含むページを移動および再リンクすることで、コピーを完全に回避するなどに活用できます。これは完全なMark-Sweep-Compactコレクタでも実行されます。しかし実際には、これが観察されるのは主にシンセティックベンチマークであり、実際のウェブサイトではほとんど見られませんでした。並列Mark-Evacuateコレクタの欠点は、3つの独立したロックステップフェーズを実行する際のオーバーヘッドです。このオーバーヘッドは、主に死んだオブジェクトで構成されるヒープでガーベッジコレクタが呼び出される場合（多くの実際のウェブページで見られるケース）に特に顕著です。なお、主に死んだオブジェクトで構成されるヒープでのガーベッジコレクションの呼び出しは実際には理想的なシナリオであり、ガーベッジコレクションは通常、生存オブジェクトのサイズで制約を受けるためです。
並列Scavengerは、この性能ギャップを埋め、小規模またはほぼ空のヒープでは最適化されたCheneyアルゴリズムに近い性能を提供しながら、ヒープが大規模化して生存オブジェクトが大量に存在する場合でも高いスループットを維持します。
V8は他の多くのプラットフォームと同様に、Arm big.LITTLEをサポートしています。小さいコアでの作業のオフロードはバッテリー寿命を向上させますが、小さいコア向けの作業パッケージが大きすぎる場合、メインスレッドでスタールを引き起こす可能性があります。我々は、ページレベルの並列性が若い世代のガーベッジコレクションにおいてbig.LITTLEで作業を必ずしも均等に分散しないことを観察しました。Scavengerは、明示的な作業リストと作業盗難を使用した中粒度の同期を提供することで、この問題を自然に解決します。
