ゴミ話: オリノコガーベッジコレクター
ここ数年で、V8のガーベッジコレクター（GC）は大きく変化しました。オリノコプロジェクトは、逐次処理型の完全停止ガーベッジコレクターを、主に並列および同時並行のコレクターとして段階的フォールバックを持つ形に変革しました。
注: 記事を読むよりもプレゼンテーションを見る方が良い人は、下のビデオをお楽しみください！そうでない場合は、ビデオをスキップして読み進めてください。
すべてのガーベッジコレクターには、定期的に行うべきいくつかの重要なタスクがあります:
- 生存/死亡オブジェクトの識別
- 死亡オブジェクトに占有されていたメモリの再利用
- メモリの圧縮/断片化整理（任意）
これらのタスクは逐次的に実行することもでき、または任意にインターリーブすることもできます。単純な方法としては、JavaScriptの実行を一時停止し、これらのタスクをメインスレッドで順番に実行します。この方法は、以前の ブログ記事で述べた通り、メインスレッドのジャンクやレイテンシーの問題、さらにはプログラムのスループットの低下を引き起こす可能性があります。
主なGC（完全マーク圧縮）
主なGCは、ヒープ全体からゴミを収集します。
マーキング
どのオブジェクトを収集できるかを判断することは、ガーベッジコレクションの重要な部分です。ガーベッジコレクターは、到達可能性を「生存」の代替指標として使用します。これは、ランタイム内で現在到達可能なすべてのオブジェクトを保持し、到達不能なオブジェクトを収集できるという意味です。
マーキングは、到達可能なオブジェクトを見つけるプロセスです。GCは、「ルートセット」と呼ばれる既知のオブジェクトポインタのセットから開始します。これには、実行スタックとグローバルオブジェクトが含まれます。その後、JavaScriptオブジェクトへの各ポインタを追いかけ、そのオブジェクトを到達可能としてマークします。GCはそのオブジェクト内のすべてのポインタを追いかけ、このプロセスを再帰的に続け、ランタイム内で到達可能なすべてのオブジェクトを見つけてマークするまで実行します。
スイープ
スイープは、死亡したオブジェクトが残したメモリの隙間を「フリーリスト」と呼ばれるデータ構造に追加するプロセスです。マーキングが完了したら、GCは到達不能オブジェクトが残した連続的な隙間を見つけ、それを適切なフリーリストに追加します。フリーリストは、メモリチャンクのサイズによって分けられており、迅速な検索が可能です。今後メモリを割り当てる際には、フリーリストを参照して適切なサイズのチャンクを見つけるだけです。
圧縮
主なGCは、断片化のヒューリスティックに基づいていくつかのページを退避/圧縮することを選択します。これは昔のPCのハードディスク断片化整理のようなものと考えることができます。我々は生存オブジェクトを現在圧縮されていない他のページにコピーします（そのページのフリーリストを利用します）。この方法で、死亡したオブジェクトが残したメモリ内の小さなバラバラな隙間も有効活用することができます。
生存オブジェクトをコピーするガーベッジコレクターの潜在的な弱点として、多くの長寿命オブジェクトを割り当てる場合には、それらをコピーするコストが高くなる点が挙げられます。このため、非常に断片化されたページのみを圧縮し、生存オブジェクトをコピーしないスイープを他のページに対して行うことを選択しています。
世代別レイアウト
V8のヒープは世代と呼ばれる異なる領域に分割されています。若い世代（さらに「ナーサリー」と「中間」世代に分割）と古い世代があります。オブジェクトは最初にナーサリーに割り当てられます。次のGCを生き残ると、若い世代にとどまりますが「中間」とみなされます。さらに次のGCを生き残ると、古い世代に移動されます。
ガーベッジコレクションには重要な用語があります: 「世代仮説」。これは、ほとんどのオブジェクトは若い時に死ぬということを基本的に示しています。言い換えると、ほとんどのオブジェクトは割り当てられた後、GCの観点からすぐに到達不能になります。これはV8やJavaScriptだけでなく、ほとんどの動的言語にも当てはまります。
V8の世代的ヒープレイアウトは、オブジェクトの寿命に関するこの特性を活用するように設計されています。GCは圧縮移動型GCであり、ガベージコレクションを生き延びたオブジェクトをコピーします。一見すると直感に反するようですが、コピーすること自体はGCの際にコストがかかります。しかし、世代仮説によれば、実際にガベージコレクションを生き延びるオブジェクトはごくわずかです。生き残るオブジェクトだけを移動することで、他のすべての割り当てが『暗黙の』ガベージとなります。つまり、コピーにかかるコストは割り当ての数ではなく、生き残ったオブジェクトの数に比例するということです。
マイナーGC（スカベンジャー）
V8には2つのガベージコレクターがあります。すべてのヒープからガベージを収集するメジャーGC（マークコンパクト）と、若い世代のガベージを収集する**マイナーGC（スカベンジャー）**です。世代仮説に基づき、新しく割り当てられたオブジェクトはガベージコレクションが必要になる可能性が高いことから、マイナーGCが若い世代でガベージを収集する効率的な方法になります。
スカベンジャーでは、生き残ったオブジェクトは常に新しいページに移動されます。V8は若い世代のためのセミスペース方式を採用しています。これにより、常に総スペースの半分が空いており、この移動ステップを可能にします。スカベンジ中、この初期的に空いている領域は『To-Space』と呼ばれ、コピー元の領域は『From-Space』と呼ばれます。最悪の場合、すべてのオブジェクトがスカベンジを生き延び、すべてをコピーする必要が出てくる可能性があります。
スカベンジには追加のルートセットである新しいオブジェクトへの参照を含む古い参照があります。これはオールドスペース内で若い世代のオブジェクトを指し示すポインタです。すべてのスカベンジでヒープ全体を追跡する代わりに、書き込みバリアを使用して、古いから新しいへの参照リストを維持します。スタックやグローバルと組み合わせることで、若い世代への参照をすべて把握することができ、オールド世代全体を追跡する必要がなくなります。
移動ステップでは、生き残ったオブジェクトを連続したメモリチャンク（ページ内）に移動します。これにより、死んだオブジェクトが残したギャップ（断片化）が完全に除去されるというメリットがあります。その後、To-SpaceとFrom-Spaceを切り替えます。GCが完了すると、新しい割り当てがFrom-Spaceの次の空きアドレスで行われます。
この戦略だけでは若い世代のスペースがすぐに足りなくなります。2回目のGCを生き延びたオブジェクトはTo-Spaceではなくオールド世代に移動されます。
スカベンジの最後のステップでは、移動された元のオブジェクトを参照しているポインタを更新します。すべてのコピーされたオブジェクトは元のポインタを更新するための転送アドレスを残します。
スカベンジでは、実際にこれらの3つのステップ（マーク、移動、ポインタ更新）を、個別のフェーズではなくインターリーブ形式で行います。
オリノコ
これらのアルゴリズムや最適化のほとんどは、ガベージコレクションの文献でよく見られるもので、多くのガベージコレクション対応言語で使用されています。ただし、最新かつ最先端のガベージコレクション技術は大きく進化しています。ガベージコレクションに費やされる時間を測る際の重要な指標の1つは、メインスレッドがGC中に停止している時間です。従来の「世界停止型」ガベージコレクターでは、この時間が積み重なることがあり、GCに費やされた時間はユーザー体験に直接影響を与え、ページのもたつき、描画性能の低下、遅延といった問題を引き起こします。
オリノコは、最新かつ最高の並列的、インクリメンタル、同時的なガベージコレクション技術を使用してメインスレッドを解放するためのGCプロジェクトのコードネームです。ここでの用語には、GCの文脈で特定の意味を持つものがあり、それらを詳細に定義する価値があります。
並列処理
並列とは、メインスレッドとヘルパースレッドがほぼ同等の作業を同時に行うことです。これは依然として「世界停止型」アプローチですが、総停止時間は参加するスレッド数で分割されます（同期のオーバーヘッドを除く）。これは3つの技術の中で最も簡単です。JavaScriptヒープは停止しており、JavaScriptが実行されていない状態なので、各ヘルパースレッドは、他のヘルパーがアクセスする可能性のあるオブジェクトへのアクセスを同期させる必要があるだけです。
インクリメンタル
インクリメンタルは、メインスレッドが断続的に少量の処理を実行する方法です。インクリメンタルポーズでは、全体的なGC処理を行うのではなく、GCに必要な作業の一部だけを実行します。これはより困難です。なぜなら、各インクリメンタル作業セグメントの間にJavaScriptコードが実行されるため、ヒープの状態が変化し、以前にインクリメンタルで行った作業が無効になる可能性があるからです。図からわかるように、メインスレッドでの処理時間が削減されるわけではありません（実際には少し増えることが多いです）が、それが時間にわたって分散されます。これは元の問題の一つ、メインスレッドの遅延を解決するための優れた手法です。JavaScriptを断続的に実行しながらガベージコレクションタスクを継続できるため、アプリケーションは引き続きユーザー入力に応答したりアニメーションを進行したりできます。
コンカレント
コンカレントでは、メインスレッドがJavaScriptを継続して実行し、ヘルパースレッドが完全にバックグラウンドでGC作業を行います。これは3つの手法の中で最も困難です。JavaScriptヒープ上の何でもいつでも変化する可能性があり、以前に行った作業が無効になるリスクがあります。それに加えて、ヘルパースレッドとメインスレッドが同時に同じオブジェクトを読み書きするため、レースコンディションにも注意が必要です。ここでの利点は、メインスレッドがJavaScriptを完全に自由に実行できることです—ただし、ヘルパースレッドとの同期に伴うわずかなオーバーヘッドがあります。
V8でのGCの状況
スカベンジング
現在、V8は若い世代のGC中に作業をヘルパースレッド間で分散するために並列スカベンジングを使用しています。各スレッドには複数のポインタが割り当てられ、それを追跡して、To-Spaceにあるライブオブジェクトを即座に退避させます。スカベンジングタスクはオブジェクトを退避させようとする際、原子的な読み取り/書き込み/比較と交換操作を通じて同期を取らなければなりません。別のスカベンジングタスクが異なる経路で同じオブジェクトを発見し、それを移動させようとする可能性があるためです。どちらのヘルパースレッドもオブジェクトを成功裏に移動させた後、ポインタを更新します。他のタスクがそのオブジェクトに到達して他のポインタを見つけ次第更新できるよう、転送ポインタを残します。サバイバーオブジェクトを素早く同期なしで割り当てるため、スカベンジングタスクはスレッドローカルの割り当てバッファを使用しています。
メジャーGC
V8でのメジャーGCは、コンカレントマーキングから開始します。ヒープが動的に計算された限界に近づくと、コンカレントマーキングタスクが開始されます。ヘルパースレッドにはそれぞれ複数のポインタが割り当てられ、見つかったすべてのオブジェクトについてその参照をたどりながら、それらをマークします。コンカレントマーキングは完全にバックグラウンドで行われ、JavaScriptがメインスレッドで実行されている間も進行します。JavaScriptがコンカレントに新しい参照を作成する場合に備えて、それを追跡するためにライトバリアが使用されています。
コンカレントマーキングが終了するか動的割り当て制限に達すると、メインスレッドで迅速なマーキング完了ステップが実行されます。この段階でメインスレッドのポーズが開始されます。これはメジャーGCの総ポーズ時間を示します。メインスレッドはルートを再びスキャンし、すべてのライブオブジェクトがマークされていることを確認してから、複数のヘルパースレッドと共に並列コンパクションとポインタ更新を開始します。オールドスペース内のすべてのページがコンパクションの対象となるわけではありません—対象外のものは、前述したフリーリストを使用してスウィープされます。メインスレッドはポーズ中にコンカレントスウィーピングタスクを開始します。これらは並列コンパクションタスクやメインスレッド自体とも同時に実行され、JavaScriptがメインスレッドで動作している間でも継続できます。
アイドルタイムGC
JavaScriptのユーザーはガーベージコレクタに直接アクセスすることはできません。それは完全に実装に依存しています。しかしV8は、JavaScriptプログラム自体ができなくても、埋め込む側がガーベージコレクションをトリガーできる仕組みを提供しています。GCは『アイドルタスク』をポストすることができ、これは最終的にいずれトリガーされるオプションの作業です。Chromeのような埋め込み側は、自由またはアイドル状態の時間の概念を持つことができます。例えばChromeでは、60fpsでアニメーションをレンダリングする場合、ブラウザは各フレームに約16.6msを使います。アニメーションの作業が早めに完了した場合、Chromeは次のフレームまでの空き時間にGCが生成したこれらのアイドルタスクを実行することを選択できます。
詳細については、アイドルタイムGCに関する詳細な公開資料をご参照ください。
まとめ
V8のガベージコレクタは、その導入以来大きな進化を遂げてきました。既存のGCに並列、インクリメンタル、および並行技術を追加することは数年にわたる努力でしたが、その結果、多くの作業をバックグラウンドタスクに移行することができました。これにより、停止時間、遅延、およびページロードが劇的に改善され、アニメーション、スクロール、およびユーザーインタラクションがより滑らかになりました。並列スカベンジャーは、ワークロードによって異なりますが、メインスレッドの若い世代のガベージコレクションの合計時間を約20%〜50%削減しました。アイドル時間GCは、アイドル状態のGmailのJavaScriptヒープメモリを45%削減できます。並行マーキングとスイーピングは、重いWebGLゲームでの停止時間を最大50%削減しました。
しかし、ここでの作業はまだ終わっていません。ガベージコレクションの停止時間を短縮することは、ウェブで最高のユーザー体験を提供するために依然として重要であり、さらに高度な技術を模索しています。さらに、ChromeのレンダラーであるBlinkにもガベージコレクタ（Oilpanと呼ばれる）があり、2つのコレクタ間の協力を改善し、OrinocoからOilpanへの新しい技術の移植を進めています。
ほとんどの開発者は、JavaScriptプログラムの開発中にGCについて考える必要はありませんが、内部の一部を理解することで、メモリ使用量と有用なプログラミングパターンについて考える助けになります。例えば、V8ヒープの世代別構造では、短命のオブジェクトはガベージコレクタの観点から実際には非常に安価であり、コレクションを生き残るオブジェクトに対してのみ費用がかかるからです。このようなパターンはJavaScriptだけでなく、多くのガベージコレクション対応言語に効果的です。