メインコンテンツまでスキップ

V8の並行マーク

· 約17分
Ulan Degenbaev、Michael Lippautz、Hannes Payer — メインスレッドの解放者

この投稿では、並行マーク と呼ばれるガベージコレクション技術について説明します。この最適化により、ガベージコレクターがヒープをスキャンして生存オブジェクトを発見・マークしている間もJavaScriptアプリケーションの実行が続けられます。我々のベンチマークでは、並行マークによりメインスレッドのマーキング時間が60%～70%短縮されることが示されています。並行マークは、Orinocoプロジェクト という、古いガベージコレクターを新しい主に並行かつ並列のガベージコレクターに徐々に置き換えるプロジェクトの最後の欠片です。Chrome 64およびNode.js v10では並行マークがデフォルトで有効になっています。

背景​

マーキングはV8の Mark-Compact ガベージコレクターのフェーズの一つです。このフェーズでは、コレクターはすべての生存オブジェクトを発見し、マークします。マーキングは、グローバルオブジェクトや現在アクティブな関数など、既知の生存オブジェクト（いわゆるルート）から開始されます。コレクターはルートを生存オブジェクトとしてマークし、それらに含まれるポインタを辿ってさらに生存オブジェクトを発見します。コレクターは新たに発見されたオブジェクトをマークし続け、ポインタを辿り続け、マークするべきオブジェクトがなくなるまでこのプロセスを繰り返します。マーキングの終了時には、ヒープ上でマークされていないすべてのオブジェクトがアプリケーションから到達不能となり、安全に再利用することができます。

マーキングを グラフ走査 として考えることができます。ヒープ上のオブジェクトはグラフのノードであり、オブジェクト間のポインタはグラフのエッジです。グラフ内のノードを指定すると、そのノードのすべての出力エッジを ヒドゥンクラス を使用して見つけることができます。

Figure 1. オブジェクトグラフ

V8はオブジェクトごとに2つのマークビットとマーキングワークリストを使用してマーキングを実装しています。2つのマークビットは3つの色を表します: 白 (00)、灰 (10)、黒 (11)。最初はすべてのオブジェクトが白であり、まだコレクターに発見されていないことを意味します。白いオブジェクトはコレクターに発見され、マーキングワークリストに追加されると灰になります。灰色のオブジェクトはマーキングワークリストから取り出され、すべてのフィールドを訪問すると黒になります。この仕組みは三色マーキングと呼ばれます。マーキングは灰色のオブジェクトがなくなると終了します。残りの白いオブジェクトは到達不能となり、安全に再利用できます。

Figure 2. ルートからマーキング開始

Figure 3. コレクターが灰色オブジェクトのポインタを処理して黒に変える様子

Figure 4. マーキング終了後の最終状態

上記のマーキングアルゴリズムは、アプリケーションがマーキング実行中に一時停止している場合にのみ機能します。マーキング中にアプリケーションの実行を許可すると、アプリケーションがグラフを変更し、最終的にコレクターに生存オブジェクトを誤って解放させてしまう可能性があります。

マーキングの一時停止時間の短縮​

マーキングを一度に実行すると、大規模なヒープでは数百ミリ秒かかることがあります。

このような長い一時停止は、アプリケーションの応答性を低下させ、ユーザー体験を損ねる可能性があります。2011年にV8は世界全体を停止するマーキングからインクリメンタルマーキングに切り替えました。インクリメンタルマーキングでは、ガベージコレクターがマーキング作業を小さなチャンクに分割し、チャンクの間にアプリケーションの実行を許可します。

ガベージコレクターはアプリケーションによる割り当て率に合わせて各チャンクで行うインクリメンタルマーキングの作業量を選定します。一般的なケースではこれによりアプリケーションの応答性が大幅に改善されます。ただし、メモリプレッシャーのある大規模なヒープでは、割り当てに追いつこうとするコレクターの動作により依然として長い一時停止が発生することがあります。

インクリメンタルマーキングにはコストがかかります。アプリケーションはオブジェクトグラフを変更するすべての操作についてガベージコレクターに通知する必要があります。V8ではダイクストラ方式のライトバリアを使用して通知を実装しています。JavaScriptでobject.field = value形式の書き込み操作が行われると、V8はライトバリアコードを挿入します:

// `object.field = value` の後に呼び出されます。
write_barrier(object, field_offset, value) {
  if (color(object) == black && color(value) == white) {
    set_color(value, grey);
    marking_worklist.push(value);
  }
}

書き込みバリアは、黒いオブジェクトが白いオブジェクトを指さないという不変条件を強制します。これは強い三色不変条件とも呼ばれ、アプリケーションがガベージコレクタから生存しているオブジェクトを隠すことができないことを保証します。そのため、マークの終了時に白いオブジェクトはすべてアプリケーションから完全に到達不能であり、安全に解放することができます。

インクリメンタルマークは、以前のブログ記事で説明したアイドル時間のガベージコレクションスケジューリングとうまく統合されます。ChromeのBlinkタスクスケジューラは、アイドル時間中にメインスレッド上で小さなインクリメンタルマークのステップをスケジュールすることができ、スタッタリングを発生させません。この最適化は、アイドル時間が利用可能な場合に非常に効果的です。

書き込みバリアのコストのため、インクリメンタルマークはアプリケーションのスループットを低下させる可能性があります。追加のワーカースレッドを利用することで、スループットと一時停止時間の両方を改善することが可能です。ワーカースレッドでマークを行う方法は2つあります: 並列マークと並行マークです。

主に並列マークはメインスレッドとワーカースレッド上で行われます。このフェーズ中、アプリケーションは完全に停止されます。これは、マルチスレッド版の停止型マーク（stop-the-world marking）です。

並行マークは、主にワーカースレッド上で行われます。この間もアプリケーションは動作を続けることができます。

以下の2つのセクションでは、V8に並列マークと並行マークのサポートを追加した方法について説明します。

並列マーク​

並列マーク中、アプリケーションが並行して実行されていないと仮定できます。これにより、オブジェクトグラフが静的で変化しないと仮定できるため、実装が大幅に簡素化されます。オブジェクトグラフを並列にマークするために、ガベージコレクションのデータ構造をスレッドセーフにし、スレッド間で効率的にマーク作業を共有する方法を見つける必要があります。以下の図は、並列マークに関与するデータ構造を示しています。矢印はデータの流れの方向を示しています。簡単のため、ヒープの断片化解消に必要なデータ構造は図に含めていません。

図5. 並列マークのデータ構造

スレッドはオブジェクトグラフからデータを読み取るだけで、変更することはありません。オブジェクトのマークビットとマーク作業リストは、読み取りと書き込みアクセスをサポートする必要があります。

マーク作業リストと作業のスティーリング​

マーク作業リストの実装はパフォーマンスの鍵であり、高速なスレッドローカルのパフォーマンスと、作業がなくなった場合に他のスレッドにどれだけ作業を分散できるかのバランスを取ります。

このトレードオフでの極端な両端は、(a) すべてのオブジェクトが共有可能であるため、最良の共有のために完全に並行なデータ構造を使用することと、(b) スレッドローカルスループットを最適化するため、完全にスレッドローカルなデータ構造を使用することです。図6は、スレッドローカルの挿入と削除に基づくセグメントを使用することで、V8がこれらのニーズをどのようにバランスしているかを示しています。セグメントが満杯になると、それを共有グローバルプールに公開してスティーリング可能にします。この方法で、V8は可能な限り同期なしでローカルに動作し続け、別のスレッドがローカルセグメントを完全に消耗して新しいオブジェクトサブグラフに到達するケースにも対応できます。

図6. マーク作業リスト

並行マーク​

並行マークでは、メインスレッドでJavaScriptが実行されている間に、ワーカースレッドがヒープ上のオブジェクトを訪れることができます。これにより、多くの潜在的なデータ競合が発生する可能性があります。例えば、JavaScriptがオブジェクトフィールドに書き込みを行っているのと同時に、ワーカースレッドが同じフィールドを読み取っている場合があります。データ競合により、ガベージコレクタが生存オブジェクトを解放したり、プリミティブ値とポインタを混同したりする可能性があります。

オブジェクトグラフを変更するメインスレッド上の各操作は、データ競合の潜在的な原因となります。V8は多くのオブジェクトレイアウト最適化を備えた高性能エンジンであるため、データ競合の潜在的な原因のリストはかなり長くなります。以下は高レベルの内訳です:

  • オブジェクトの割り当て。
  • オブジェクトフィールドへの書き込み。
  • オブジェクトレイアウトの変更。
  • スナップショットからのデシリアライズ。
  • 関数の逆最適化中のマテリアライズ。
  • 若い世代のガベージコレクション中の移動。
  • コードのパッチング。

メインスレッドはこれらの操作中、ワーカースレッドとの同期を取る必要があります。同期のコストと複雑さは操作によって異なります。ほとんどの操作はアトミックメモリアクセスによる軽量な同期を可能としますが、一部の操作はオブジェクトへの排他アクセスを必要とします。以下の小節では、興味深いケースをいくつか取り上げます。

書き込みバリア​

オブジェクトフィールドへの書き込みによるデータ競合は、書き込み操作をリラックスしたアトミック書き込みに変えることで解決され、書き込みバリアを調整します。

// atomic_relaxed_write(&object.field, value); の後に呼び出される
write_barrier(object, field_offset, value) {
  if (color(value) == white && atomic_color_transition(value, white, grey)) {
    marking_worklist.push(value);
  }
}

以前使用されていた書き込みバリアと比較:

// `object.field = value` の後に呼び出されます。
write_barrier(object, field_offset, value) {
  if (color(object) == black && color(value) == white) {
    set_color(value, grey);
    marking_worklist.push(value);
  }
}

変更点は2つ:

  1. ソースオブジェクトの色チェック (color(object) == black) がなくなった。
  2. value の白から灰への色の遷移が原子的に行われるようになった。

ソースオブジェクトの色チェックを削除することで、書き込みバリアはより保守的になります。すなわち、それらのオブジェクトが実際には到達可能でなくても、オブジェクトをライブとしてマークする可能性があります。このチェックを削除したのは、書き込み操作と書き込みバリアの間に必要な高コストなメモリフェンスを回避するためです:

atomic_relaxed_write(&object.field, value);
memory_fence();
write_barrier(object, field_offset, value);

メモリフェンスがない場合、オブジェクトの色の読み取り操作が書き込み操作の前に再順序付けされる可能性があります。この再順序付けを防がないと、書き込みバリアが灰色のオブジェクト色を観測してスルーする可能性があり、その間に作業スレッドがオブジェクトを新しい値を確認せずにマークする可能性があります。Dijkstraらによって提案された元の書き込みバリアもオブジェクトの色をチェックしませんでした。彼らは単純さのためにそうしましたが、私たちは正確性のために必要なのです。

バイルアウトワークリスト​

例えばコードパッチングなどの一部の操作では、オブジェクトへの排他的なアクセスが必要です。初期段階で、オブジェクトごとのロックを回避することを決定しました。これは、メインスレッドがオブジェクトロックを保持している間にスケジュール解除された作業スレッドを待機しなければならない優先度反転問題を引き起こす可能性があるからです。オブジェクトをロックする代わりに、作業スレッドがオブジェクトの訪問を中断することを許可しました。作業スレッドは、オブジェクトをバイルアウトワークリストにプッシュすることでこれを行い、このリストはメインスレッドだけが処理します:

図7. バイルアウトワークリスト

作業スレッドは、最適化コードオブジェクト、隠しクラス、および弱いコレクションでバイルアウトします。これを訪問するにはロックまたは高コストの同期プロトコルが必要です。

振り返ってみると、バイルアウトワークリストは増分開発にとって非常に良いものでした。作業スレッドがすべてのオブジェクトタイプでバイルアウトすることで実装を開始し、並行性を一つずつ追加しました。

オブジェクトレイアウトの変更​

オブジェクトのフィールドは3種類の値を格納できます: タグ付きポインタ、タグ付き小型整数（Smiとも呼ばれる）、またはタグなしの値（アンボクシングされた浮動小数点数など）。ポインタタグ付けは、アンボクシングされた整数を効率的に表現するための良く知られた技術です。V8では、タグ付き値の最下位ビットがポインタか整数かを示します。これは、ポインタがワードアラインされているという事実を利用しています。そのフィールドがタグ付きかタグなしを示す情報は、オブジェクトの隠しクラスに保存されています。

V8の一部の操作では、オブジェクトを別の隠しクラスに遷移させることによって、タグ付きからタグなしか（またはその逆）にフィールドを変更します。このようなオブジェクトレイアウトの変更は、並行マーキングに対して安全ではありません。この変更が、作業スレッドが古い隠しクラスを使用してオブジェクトを並行して訪問している間に発生すると、2種類のバグが発生する可能性があります。まず、作業スレッドがタグなしの値をポインタと間違えて見逃す可能性があります。この種のバグには、書き込みバリアが保護を提供します。次に、作業スレッドがタグなしの値をポインタと誤認して参照解除し、それが無効なメモリアクセスにつながり、通常プログラムクラッシュを招きます。このケースを処理するために、私たちはオブジェクトのマークビットで同期するスナップショットプロトコルを使用しています。このプロトコルには、タグ付きからタグなしのフィールドを変更するメインスレッドと、オブジェクトを訪問する作業スレッドの2当事者が関与します。フィールドを変更する前に、メインスレッドはオブジェクトが黒としてマークされていることを確認し、後で訪問するためにバイルアウトワークリストにプッシュします:

atomic_color_transition(object, white, grey);
if (atomic_color_transition(object, grey, black)) {
  // バイルアウトワークリストを排出する間に、メインスレッドがオブジェクトを再訪問します。
  bailout_worklist.push(object);
}
unsafe_object_layout_change(object);

以下のコードスニペットに示されているように、作業スレッドはまずオブジェクトの隠しクラスを読み込み、原子的リラックス読み込み操作を使用して、隠しクラスによって指定されたオブジェクトのすべてのポインタフィールドをスナップショットします。そして、原子的な比較とスワップ操作を使用してオブジェクトを黒としてマークしようとします。マークが成功した場合、メインスレッドがレイアウトを変更する前にオブジェクトを黒としてマークしているため、スナップショットは隠しクラスと一致しているはずです。

snapshot = [];
hidden_class = atomic_relaxed_load(&object.hidden_class);
for (field_offset in pointer_field_offsets(hidden_class)) {
  pointer = atomic_relaxed_load(object + field_offset);
  snapshot.add(field_offset, pointer);
}
if (atomic_color_transition(object, grey, black)) {
  visit_pointers(snapshot);
}

白のオブジェクトが安全でないレイアウト変更を受ける場合、メインスレッドでマーキングする必要があります。安全でないレイアウト変更は比較的まれであるため、実世界のアプリケーションのパフォーマンスには大きな影響を与えません。

すべてをまとめる​

既存のインクリメンタルマーキングインフラストラクチャに並行マーキングを統合しました。メインスレッドはルートをスキャンし、マーキングワークリストを埋めることでマーキングを開始します。その後、メインスレッドはワーカースレッド上で並行マーキングタスクを投稿します。ワーカースレッドはマーキングワークリストを共同で排出することで、メインスレッドが迅速にマーキングを進めるのを支援します。時々、メインスレッドもベイルアウトワークリストとマーキングワークリストを処理することでマーキングに参加します。マーキングワークリストが空になると、メインスレッドがガベージコレクションを最終化します。最終化中、メインスレッドはルートを再スキャンし、さらに多くの白のオブジェクトを発見する場合があります。それらのオブジェクトはワーカースレッドの助けを借りて並行してマーキングされます。

結果​

私たちの実世界ベンチマークフレームワークでは、モバイルとデスクトップでそれぞれ約65%および70%のガベージコレクションサイクルごとのメインスレッドマーキング時間の削減が確認されました。

メインスレッドでのマーキングに費やした時間（低いほど良い）

並行マーキングはNode.jsでのガベージコレクションのジャンク（遅延）も削減します。これは特に重要です。というのも、Node.jsはアイドルタイムガベージコレクションスケジューリングを実装しておらず、ジャンクがクリティカルでないフェーズでマーキング時間を隠すことができなかったからです。並行マーキングはNode.js v10で提供されました。