C++のための高性能ガベージコレクション

C++向け高性能ガベージコレクション

過去には、JavaScript、DOM（Document Object Model）、そしてそれらがV8でどのように実装・最適化されているかについて、すでに 何度か 記事を書いてきました。しかし、Chromiumの全てがJavaScriptでできているわけではありません。ブラウザの大部分や、V8が組み込まれているBlinkレンダリングエンジンはC++で書かれています。JavaScriptは、レンダリングパイプラインで処理されるDOMと対話するために使用されます。

DOMを取り巻くC++オブジェクトグラフはJavaScriptオブジェクトと密接に絡み合っているため、Chromiumチームは数年前に、この種のメモリ管理を行うためのガベージコレクタ「Oilpan」に切り替えました。OilpanはC++で書かれたガベージコレクタで、C++メモリを管理し、クロスコンポーネントトレーシングを使用してV8と連携することができます。これにより、絡み合ったC++/JavaScriptオブジェクトグラフ全体を単一のヒープとして扱います。

この記事は、Oilpanのコア原則とC++ APIの概要を提供する、Oilpanに関する一連のブログ記事の最初のものです。今回は、サポートされている機能の一部を取り上げ、それらがガベージコレクタのさまざまなサブシステムとどのように連携するかを説明し、スイーパーによるオブジェクトのコンカレントな再利用について深く掘り下げます。

最もエキサイティングなのは、Oilpanは現在Blinkに実装されていますが、ガベージコレクションライブラリの形でV8に移行していることです。その目標は、C++のガベージコレクションを、V8のすべての埋め込みユーザーや、より一般的に多くのC++開発者が容易に利用できるようにすることです。

背景 #

Oilpanはマーク・スイープガベージコレクタを実装しており、ガベージコレクションは2つのフェーズに分かれています。マーキング（マーク処理）では、管理対象のヒープから生存しているオブジェクトをスキャンし、スイーピング（スイープ処理）では、管理対象ヒープ上の不要なオブジェクトを再利用します。

V8でコンカレントマーキングを導入した際に、マーキングの基本についてはすでに説明しました。おさらいすると、すべてのオブジェクトをスキャンして生存しているオブジェクトを見つけることは、オブジェクトをノード、オブジェクト間のポインタをエッジとするグラフ探索と見なすことができます。探索は、レジスタ、ネイティブ実行スタック（以降、スタックと呼びます）、およびその他のグローバル変数であるルートから開始されます。これはこちらで説明されています。

C++もこの点ではJavaScriptと変わりません。ただし、JavaScriptとは異なり、C++オブジェクトは静的に型付けされているため、実行時にその表現を変更することはできません。Oilpanで管理されるC++オブジェクトは、この事実を活用し、ビジターパターンを通じて他のオブジェクトへのポインタ（グラフのエッジ）の説明を提供します。Oilpanオブジェクトを記述するための基本的なパターンは次のとおりです。

class LinkedNode final : public GarbageCollected<LinkedNode> {
 public:
  LinkedNode(LinkedNode* next, int value) : next_(next), value_(value) {}
  void Trace(Visitor* visitor) const {
    visitor->Trace(next_);
  }

 private:
  Member<LinkedNode> next_;
  int value_;
};

LinkedNode* CreateNodes() {
  LinkedNode* first_node = MakeGarbageCollected<LinkedNode>(nullptr, 1);
  LinkedNode* second_node = MakeGarbageCollected<LinkedNode>(first_node, 2);
  return second_node;
}

上記の例では、LinkedNodeはGarbageCollected<LinkedNode>を継承していることからわかるように、Oilpanによって管理されています。ガベージコレクタがオブジェクトを処理する際、オブジェクトのTraceメソッドを呼び出すことで、そこから伸びるポインタを発見します。Member型は、Oilpanが提供するスマートポインタで、マーキング中のグラフ探索中に一貫した状態を維持するために使用され、例えばstd::shared_ptrに構文的に似ています。これにより、Oilpanは管理対象オブジェクト内のポインタがどこにあるかを正確に把握できます。

熱心な読者はおそらく、例でfirst_nodeとsecond_nodeがスタック上の生のC++ポインタとして保持されていることに気づいたでしょう（そして怖気づいたかもしれません）。Oilpanはスタックでの作業のために抽象化を追加せず、ルートを処理する際に管理対象ヒープへのポインタを見つけるために、保守的なスタックスキャンにのみ依存します。これは、スタックを単語ごとに反復処理し、それらの単語を管理対象ヒープへのポインタとして解釈することで機能します。つまり、Oilpanはスタック割り当てオブジェクトへのアクセスにパフォーマンスペナルティを課しません。代わりに、保守的にスタックをスキャンするガベージコレクションの時間にコストを移動させます。レンダラーに統合されたOilpanは、興味深いスタックが存在しないことが保証される状態に達するまでガベージコレクションを遅延させようとします。Webはイベント駆動型であり、実行はイベントループ内のタスク処理によって駆動されるため、そのような機会は豊富にあります。

OilpanはBlinkで使用されており、これは大規模なC++コードベースで多くの成熟したコードが含まれています。そのため、以下の機能もサポートしています。

• ミックスインとそれらのミックスインへの参照（内部ポインタ）を通じた多重継承。
• コンストラクタ実行中にガベージコレクションをトリガーすること。
• Persistentスマートポインタ（ルートとして扱われる）を通じて、非管理メモリからオブジェクトを生存させ続けること。
• シーケンシャル（例: vector）および連想（例: set、map）コンテナをカバーするコレクションと、コレクションのバックエンドのコンパクション。
• 弱参照、弱コールバック、およびエフェメロン。
• 個々のオブジェクトを再利用する前に実行されるファイナライザコールバック。

C++のためのスイーピング #

Oilpanでのマーキングがどのように機能するかについての詳細なブログ記事は、続報をお待ちください。この記事では、マーキングが完了し、OilpanがTraceメソッドの助けを借りてすべての到達可能なオブジェクトを発見したと仮定します。マーキング後、到達可能なすべてのオブジェクトにはマークビットが設定されています。

スイーピングは、不要なオブジェクト（マーキング中に到達不可能だったオブジェクト）を再利用し、それらの基盤となるメモリをオペレーティングシステムに返却するか、後続の割り当てに利用可能にするフェーズです。以下では、Oilpanのスイーパーが、使用法と制約の観点から、そして高い再利用スループットをどのように達成するかを示します。

スイーパーは、ヒープメモリを反復処理し、マークビットをチェックすることで不要なオブジェクトを見つけます。C++のセマンティクスを維持するために、スイーパーはメモリを解放する前に、各不要オブジェクトのデストラクタを呼び出す必要があります。非自明なデストラクタはファイナライザとして実装されます。

プログラマの観点からは、スイーパーが使用する反復処理は構築順序を考慮しないため、デストラクタが実行される順序は定義されていません。これは、ファイナライザが他のオンヒープオブジェクトに触れることが許可されないという制約を課します。これは、管理対象言語がファイナライゼーションセマンティクス（例: Java）で順序をサポートしていないことが多いため、ファイナライゼーション順序を必要とするユーザーコードの記述における一般的な課題です。Oilpanは、Clangプラグインを使用して、他の多くのことの中でも、オブジェクトの破壊中にヒープオブジェクトにアクセスされないことを静的に検証します。

class GCed : public GarbageCollected<GCed> {
 public:
  void DoSomething();

  void Trace(Visitor* visitor) {
    visitor->Trace(other_);
  }

  ~GCed() {
    other_->DoSomething(); // error: Finalizer '~GCed' accesses
                           // potentially finalized field 'other_'.
  }

 private:
  Member<GCed> other_;
};

好奇心旺盛な方のために: Oilpanは、オブジェクトが破棄される前にヒープにアクセスする必要がある複雑なユースケースのために、事前ファイナライゼーションコールバックを提供します。ただし、そのようなコールバックは、各ガベージコレクションサイクルでデストラクタよりも多くのオーバーヘッドを課すため、Blinkでは控えめに使用されています。

インクリメンタルおよびコンカレントスイーピング #

マネージドC++環境におけるデストラクタの制約について説明したので、Oilpanがスイープフェーズをどのように実装し、詳細に最適化するかを見ていきましょう。

詳細に入る前に、一般的にWeb上でプログラムがどのように実行されるかを思い出すことが重要です。JavaScriptプログラムやガベージコレクションを含むすべての実行は、イベントループでタスクをディスパッチすることによってメインスレッドから駆動されます。レンダラーは、他のアプリケーション環境と同様に、メインスレッドの作業を支援するために、メインスレッドと並行して実行されるバックグラウンドタスクをサポートしています。

単純に始めると、Oilpanは当初、ストップ・ザ・ワールド・スイーピングを実装していました。これは、アプリケーションのメインスレッドでの実行を中断するガベージコレクションの最終停止の一部として実行されていました。

［画像: Stop-the-world sweeping］

ソフトリアルタイム制約を持つアプリケーションにとって、ガベージコレクションを扱う際の決定要因はレイテンシです。ストップ・ザ・ワールド・スイーピングは、ユーザーに見えるアプリケーションのレイテンシを引き起こす可能性のある、かなりの停止時間を引き起こす可能性があります。レイテンシを削減するための次のステップとして、スイーピングはインクリメンタルになりました。

［画像: Incremental sweeping］

インクリメンタルアプローチでは、スイーピングは分割され、追加のメインスレッドタスクに委任されます。最良の場合、そのようなタスクはアイドル時間で完全に実行され、通常のアプリケーション実行への干渉を回避します。内部的には、スイーパーはページという概念に基づいて作業を小さな単位に分割します。ページは2つの興味深い状態を持つことができます。スイーパーがまだ処理する必要があるスイープ対象ページと、スイーパーがすでに処理したスイープ済みページです。割り当ては、すでにスイープされたページのみを考慮し、利用可能なメモリチャンクのリストを維持するフリーリストからローカル割り当てバッファ（LAB）を再充填します。フリーリストからメモリを取得するために、アプリケーションはまず、すでにスイープされたページでメモリを探し、次にスイープアルゴリズムを割り当てにインライン化してスイープ対象ページを処理するのを支援しようとし、メモリがない場合にのみOSから新しいメモリを要求します。

Oilpanは長年インクリメンタルスイーピングを使用してきましたが、アプリケーションとその結果のオブジェクトグラフがますます大きくなるにつれて、スイーピングがアプリケーションのパフォーマンスに影響を与え始めました。インクリメンタルスイーピングを改善するために、コンカレントなメモリ再利用のためにバックグラウンドタスクを活用し始めました。バックグラウンドタスクがスイーパーを実行する際とアプリケーションが新しいオブジェクトを割り当てる際のデータ競合を排除するために使用される、2つの基本的な不変条件があります。

• スイーパーは、定義上、アプリケーションから到達できない不要なメモリのみを処理します。
• アプリケーションは、定義上、スイーパーによって処理されていない、すでにスイープされたページにのみ割り当てを行います。

どちらの不変条件も、オブジェクトとそのメモリに対する競合がないことを保証するはずです。残念ながら、C++はデストラクタに大きく依存しており、これはファイナライザとして実装されています。Oilpanは、開発者を支援し、アプリケーションコード自体のデータ競合を排除するために、ファイナライザをメインスレッドで実行することを強制します。この問題を解決するために、Oilpanはオブジェクトのファイナライゼーションをメインスレッドに延期します。より具体的には、コンカレントスイーパーがファイナライザ（デストラクタ）を持つオブジェクトに遭遇すると、それをファイナライゼーションキューにプッシュします。このキューは、アプリケーションも実行しているメインスレッドで常に実行される別のファイナライゼーションフェーズで処理されます。コンカレントスイーピングの全体的なワークフローは次のようになります。

［画像: Concurrent sweeping using background tasks］

ファイナライザはオブジェクトのペイロード全体にアクセスする必要がある場合があるため、対応するメモリをフリーリストに追加するのは、ファイナライザを実行した後まで遅延されます。ファイナライザが実行されない場合、バックグラウンドスレッドで実行されているスイーパーは、再利用されたメモリをすぐにフリーリストに追加します。

結果 #

バックグラウンドスイーピングはChrome M78でリリースされました。私たちのリアルワールドベンチマークフレームワークは、メインスレッドのスイープ時間を25%〜50%（平均42%）削減することを示しています。以下に選択された項目の一部を示します。

［画像: Main thread sweeping time in milliseconds］

メインスレッドで費やされる残りの時間は、ファイナライザの実行用です。Blinkで頻繁にインスタンス化されるオブジェクトタイプのファイナライザを削減するための継続的な作業が行われています。ここでエキサイティングなのは、これらの最適化はすべてアプリケーションコードで行われているということです。なぜなら、ファイナライザが存在しない場合、スイーピングは自動的に調整されるからです。

V8のすべてのユーザーが利用できるリリースに近づくにつれて、C++ガベージコレクション全般とOilpanライブラリのアップデートに関するさらなる記事にご期待ください。