ラピッドイテレーションを実現するRE ENGINEの設計

ラピッドイテレーションを実現 するRE ENGINEの設計 株式会社カプコン 石田智史

RE ENGINE • カプコン内製の次世代ゲームエンジン • MT Frameworkからアーキテクチャを一新 • マルチプラットフォーム対応 • PS4,XboxOne,PC(Steam/UWP)… • バイオハザード7で採用 • 今後、様々なタイトルで活用

RE ENGINEの特徴 •高いパフォーマンス •高解像度で高フレームレートを実現 •高い開発効率 •高速なイテレーションを実現 このセッションで扱う内容

ゲーム開発のイテレーション 遅い コーディ 動作確認 プレイ ング 調整 多い 遅い 長い 手間 ビルド 起動 実機確 DCC編 認 集 長い コンバート バグ修正 QA 手間 パッケージ 生成

RE ENGINEのイテレーション

リモートでの実機編集

全リソースのリロード対応

リアルタイムコーディング

パッケージ作成

ラピッドイテレーションを実現 • 待ち時間が減る • トライ＆エラーの回数が増える • 実機で動かす頻度が増える • QAでのバグが減る ➢余力をゲームの品質向上に費やせる

バイオハザード7の開発結果 • 最終プロジェクト規模 • C#ゲームコード約28万行、アセット総数約15万 • 高速なイテレーションを維持 • フルビルド~10秒、開発終盤まで何度もレベル調整が繰り返えされた • 実機での安定したパフォーマンスを実現 • VRで60fpsを切る=発売できない • 平穏なQA • 大規模タイトルでは弊社史上初？ 炎上なし！

アジェンダ • ツールアーキテクチャ • リソースアーキテクチャ • スクリプトアーキテクチャ

RE ENGINE ツールアーキテクチャ

旧ツールアーキテクチャ • ランタイム上でツールが動作 • 独自のUIシステム • 実機上でのリアルタイム編集と調整 • 問題点 • 実機上では解像度や性能に制約がある • UIを自作する必要がある • 実機動作までに手間がかかる • ランタイムクラッシュで編集データが消失

新ツールアーキテクチャ • ツールプロセスを完全に分離 • ランタイム、ツール間はTCP/IPで同期 • ツールはPC上で動作しWPF/C#で実装 • 利点 • 高速、高解像度なPC上で動作 • 豊富なWPFのUI機能 • 異なる実機上で即座に編集 • ランタイムのクラッシュに影響を受けない TCP/IP

新ツールアーキテクチャの課題 • 言語間の互換性がない • ランタイムはC++言語、ツールはC#言語を使用 • ランタイム操作を非同期で行う必要がある • コードが煩雑で冗長になり易い • 通信コストが問題になり易い • データ転送速度が限られる

RE ENGINEのソリューション • 通信プロトコルの統一 • リモートオブジェクトシステム

通信プロトコルの統一 • ランタイム、ツール間の通信方法を統一 • 全ての通信を共通のプロトコルで行う • 効率的なプロトコルの実装 • C#とC++言語間の定義の共通化 • バイナリ形式の通信 • 非同期コードの簡潔な記述

通信プロトコル (1/2) • リモートエンティティ • C++/C#言語間で相互にバイナリシリアライズ、デシリアライズ可能なクラ ス • C#言語で定義し、対応するC++ヘッダを自動生成 自動生成 runtime/remote.h

通信プロトコル (2/2) • Query/Responseプロトコル • Query/Responseはリモートエンティティ継承 • QueryはExecuteメソッドを持ち、戻り値にResponseを返す • Responseが返ると、対応するハンドラが実行される Runtime Tool Serialize Deserialize Query Execute TCP/IP Handler Query Response Response Deserialize Serialize

Query/Responseプロトコル(1/3) • プロトコル実例 • ツールのマウスカーソル位置に対応するワールド座標をランタイムから取得 する • Query/Responseをツール側で定義(C#)

Query/Responseプロトコル(2/3) • C++ヘッダファイルを自動生成 • Queryの実行コードをランタイム側に実装(C++) • ワールド座標を計算し、Responseとして返す runtime/remote.cpp 自動生成 runtime/remote.h

Query/Responseプロトコル(3/3) • ツールからランタイムにQueryを送信 • Responseが返るとコールバックが実行 • Responseを元に任意の処理を記述 ➢ ランタイムからツールへのQueryも同様の流れ

リモートオブジェクトシステム • ツール上でランタイムのオブジェクトを透過的に扱う仕組み • プロセスや言語の違いを吸収できる • リモートオブジェクト • ツール上の仮想的なランタイムインスタンス • 任意にランタイム上に実体化 • ツール/ランタイム間で状態を同期

リモートオブジェクト(1/3) • ランタイムから全ての型情報を取得 • 型名とプロパティ情報で構成 RuntimeType SampleClass TCP/IP Runtime(C++) 0 Int Param 1 Bool Flag 2 String Name Tool(C#)

リモートオブジェクト(2/3) • リモートオブジェクトの作成 • ランタイムタイプから仮想的なインスタンスを構築 • 各プロパティに対応する値を持つ RuntimeType RemoteObject SampleClass SampleClass 0 Int Param 0 10 1 Bool Flag 1 True 2 String Name 2 “Test” Create

リモートオブジェクト(3/3) • リモートオブジェクトのラップ • RuntimeObjectを継承し、アクセッサを実装 • 使用頻度の高い基本型など • ランタイム型を直接扱うように記述できる ラッパークラスなし ラッパークラスあり RuntimeWrapper

リモートオブジェクトの同期(1/2) • 初回同期時にインスタンスIDを割り当て • ツールから同期したインスタンスは正のID • ランタイムから同期したインスタンスは負のID • インスタンスをテーブルでマッピング • ツール、ランタイム双方が2つのテーブルを持つ 1 RemoteObjectA Sync 1 Tool ２ ３ ４ 1 ID:1 ２ ３ ４ New TCP/IP RemoteObjectB New 1 ２ ３ ４ ObjectA ２ ３ ４ ID:-1 ObjectB Sync Runtime

リモートオブジェクトの同期(2/2) • 基本的な状態の同期 • 適時Syncを手動で呼び出す • 自動的な状態の同期 • モニターリストに登録 • 毎フレーム、ランタイムインスタンスの状態 を監視 • 変化があったプロパティのみをツール側に自動送 信 • 負荷が高い • インスペクタ表示時など限定的に利用 RemoteObject Object Sync(OneWay) RemoteObject Object Sync(TwoWay) RemoteObject Object Sync(OneWayToSource)

ウィジェットシステム • ランタイム上で動作するツール機能 • ツール側からリモートオブジェクトを介して操作 • 通信コストやレスポンスを改善 Runtime Tool RemoteObject FrameProfileWidget RemoteObject LightViewWidget RemoteObject ManipulatorWidget

リモートオブジェクトの動作

まとめ • ツールプロセスの分離は非常に効果的 • ランタイムを自由に切り替えできる • 実機でしか調整できないことも多い • VRやモバイル端末など • ランタイムはクラッシュしやすい • 通信プロトコルや同期の仕組みを整備 • プロセス分離の煩雑さが軽減できる

RE ENGINE リソースアーキテクチャ

旧リソースアーキテクチャ • ファイルベースのリソース管理 • リソースロードはゲームコードで行う • 問題点 • 同期ロードによるスパイク • 再起動が必要なリソース更新 • コンバートによる長い待ち時間 • 手動でのパッケージ作成 • 不要リソースの混入、必要リソースの不足

新リソースアーキテクチャ • アセットベースのリソース管理 • リソースロードはエンジン側で自動的に行う • 利点 • リソースロードの完全なコントロール • 全リソースの非同期ロード対応 • 全リソースの動的リロード対応 • キャッシュによるコンバート時間の短縮 • 自動的なパッケージ作成 • 必要なリソースのみを最適な順序で自動パック

新リソースアーキテクチャの課題 • シーン再生時 • 使用リソースを事前にロードする必要がある • パッケージ作成時 • 使用リソースやロード順序を把握する必要がある • エンジン側で非同期ロード、リロード対応が必要 • 全てのリソースで徹底するのは難しい

RE ENGINEのソリューション • 静的なアセット間依存情報の構築 • リソースアクセスの制約

静的なアセット間依存情報の構築 • アセットの概念を導入 • ファイルにメタデータを追加したもの • メタデータに他のアセットへの依存情報を含める • ゲームコードによるリソースロードを廃止 • ゲームコードからは使用リソースがわからない • ゲームは一つの巨大なシーンアセットで構築 ➢マスターシーンアセット

アセットの概念を導入 • アセット • 中間データとメタデータのファイルで構成 • メタデータに依存関係を保存 • アセットをコンバートしたものがリソースになる • ツール起動時に全アセットのメタデータをロード • 全アセット間の依存関係を静的に構築できる Sample.mesh Sample.fbx Asset Resource Sample.fbx.meta Convert Sample.mesh

アセット間の依存情報 • 依存関係はReferenceとIncludeの2種類 • リソースが他のリソースを参照する=Reference • リソースが他のアセットの内容に依存する=Include Scene MotionList Motion Mesh Motion Sequence Material Texture Texture Effect Sequence Shader UVSequence HLSL HLSL HLSL Texture HLSL HLSL Reference Include

Reference情報の活用 • リソースロード/パッケージ作成時 • Referenceのリソースのみを抽出 Scene MotionList Motion Mesh Motion Sequence Material Texture Texture Effect Sequence Shader UVSequence HLSL HLSL HLSL Texture HLSL HLSL Reference Include

Include情報の活用 • アセット更新時のコンバート処理 • 全てのInclude元のアセットをコンバート • コンバート済みリソースの共有 • 全IncludeアセットのハッシュからリソースIDを計算 • リソースIDを元にサーバーにアップロード/ダウンロード Convert Scene MotionList Convert Motion Motion Convert Sequence Sequence MotionList ResourceID Update

マスターシーンアセット • ゲームを構成する全てのシーンアセットが含まれる • アセット間の依存関係のルートになる • 進行に応じてシーンをアクティブ化 • シームレスロードも容易に実現 MasterScene SystemScene TitleScene Chapter1Scene Chapter2Scene Chapter3Scene Mesh Stage1Scene Stage2Scene Stage3Scene Material Texture Texture Texture

アセット間の依存関係

リソースアクセスの制約 • 同期ロードは実装しない • スパイクの大きな要因になる • リソースのロードが完了するまでコードをブロック • 直感的で使い易いので多用されがち • 非同期ロードのみをサポート • リロード対応は強制 • 古いリソースアクセスは警告 ➢ゲームコードへの影響はない • リソースに直接アクセスする手段は存在しない

非同期ロード時のリソースアクセス • リソース作成直後はアクセスできない • ロード完了前にアクセスするとASSERTに失敗 ASSERT • リソースのロード完了を待ってからアクセス ハンドルが有効かを判定 有効な場合のみアクセス可能

全リソースが非同期ロード対応 • ロードによるスパイクが原理的に発生しない • ロード順序の並び替えが可能になる • コンバート時間が隠蔽される 同期ロード 非同期ロード A A Convert B C D Convert B B E B C D E

リロード時のリソースアクセス • 更新リソースを先行してロード • 旧リソースと新リソースの両方がメモリに存在 • 旧リソースに新リソースへの参照を追加 • リソースハンドルに更新を問い合わせ • 更新がある場合、新旧リソースを入れ替え • 全リソースハンドルの更新完了時に旧リソースが解放 • リロードは開発時のみ有効化 ResourceHandle NewTexture Texture NewTexture

全リソースがリロード対応 • リソースアクセス前に更新がないかを判定 • 更新がある場合はリソースの更新処理を行う 更新があるか判定(リリース時は常にfalse) 新旧リソースを交換 • 更新対応せずに旧リソースにアクセスした場合 • 大量の警告ログ(クラッシュはしない)

非同期ロード＆コンバートの動作

まとめ • ゲームコードによるリソースロードを廃止 • リソース間の依存関係が静的に決定できる • 依存関係を元に様々な効率化、自動化が可能 • エンジン側でリソースロードを完全に制御できる • 全リソースの非同期ロード、リロード対応。シークタイムの最適化 • エンジン側のリソースアクセスは制約を設ける • 同期ロードは最初から用意しない • リロードは先に行って対応を強制

RE ENGINE スクリプトアーキテクチャ

旧スクリプトアーキテクチャ • 全ゲームロジックをC++言語でコーディング • プログラマはスクリプト言語を使用しない • 問題点 • 長大なビルド時間 ~15分 • 分散ビルドを利用しても！ • 多発するクラッシュ • メモリリーク、メモリ破壊 • 広大で混沌としたC++言語仕様

新スクリプトアーキテクチャ • 全ゲームロジックをC#言語でコーディング • アプリケーション固有のC++コードは存在しない • 利点 • ビルドが圧倒的に早い ~10秒 • クラッシュしない • 自動メモリ管理 • メモリリーク、メモリ破壊が起こらない • 洗練されたC#言語仕様 バイオハザード7のコードメトリクス

新スクリプトアーキテクチャの課題 • 実行速度がC++より遅い • ネイティブコードとのマーシャルコスト • 例外等の厳密なハンドリング • ガベージコレクションによる停止時間 • 全スレッドが不定期に長時間停止(StopTheWorld) • コンソールゲーム機との互換性が低い • JITコンパイル禁止、ロンチハードへの対応リスク

RE ENGINEのソリューション • 独自の仮想マシン(REVM)を開発 • 独自のガベージコレクションを実装

独自の仮想マシンREVMを開発 • AOTコンパイル前提の設計 • JITコンパイルはサポートしない • C++言語との高い親和性 • マーシャルコストの大幅な削減 • コンパクトな標準ライブラリ • Core FXから、必要最小限の機能をインポート • MITライセンス

AOTコンパイル前提の設計 • C#コードをILに変換しAOTコンパイル • ジェネリクスなどを事前に展開し静的にリンク • 開発時 • 型情報とマイクロコードを出力 • リリース時 • 型情報とC++コードを出力 Develop application.dll CSC runtime.dll mscorlib.dll MicroCode AOTコンパイラ Release C++

開発時 • イテレーション速度を優先 • ILを独自のマイクロコードに変換 • ILはインタプリタ実行に適さないため • マイクロコードをインタプリタで実行 • ホットパッチに対応 • 再起動なしにリアルタイムにコード変更を反映 IL MicroCode

リリース時 • 実行パフォーマンスを優先 • ILをC++コードに変換(IL2CPP) • C++のランタイムコードと静的リンク • マーシャルコードは全てインライン展開 • ランタイムのビルドが必要 • 分散ビルドして~15分程度 IL C++

C++言語との高い親和性(1/4) • マネージドオブジェクト • C++/C#でインスタンスモデルを統合 • C#のオブジェクトは全てマネージドオブジェクト • C++で定義されたクラスをC#で継承可能 • 参照カウンタ(RC)でインスタンスの寿命を管理 ➢マーシャルコストなしで双方向にやり取りできる VTable RC Flags C++ Fields C# Fields ManagedObject

C++言語との高い親和性(2/4) • 自動的なC++クラスのC#への公開 • ClangでC++のソースコードを解析 • マネージドオブジェクト継承クラスをC#に公開 • シングルトンクラスをStaticクラスとしてC#に公開

C++言語との高い親和性(3/4) • C++からC#メソッド呼び出し • C++のTemplateを活用し静的に解決 ➢関数ポインタ呼び出しと同等のコスト • 変換コードは全てインライン展開される

C++言語との高い親和性(4/4) • C#からC++メソッド呼び出し • IL2CPP用とインタプリタ用の２段マーシャルコード ➢C++メソッドを直接呼び出すのと同等コスト • IL2CPP時のマーシャルコードはインライン展開される IL2CPP Interpreter

REVMのパフォーマンス(1/2) • C++コードとC#コードの速度比較 N-Body String Concatenation Object Instantiation Method Calls List Operations Fibonacci Numbers ArrayAccess Ackermann's Function 0 200 400 C#(REVM+NoException) 600 800 C#(REVM) 1000 1200 1400 C++ (ms) The Great Win32 Computer Language Shootout (PS4)

REVMのパフォーマンス(2/2) • 開発時(インタプリタ)とリリース時(IL2CPP)の比較 Develop(PS4) 22.11ms 4.77 BehaviorLateUpdate 1.69 3.85 BehaviorUpdate Release(PS4) 16.36ms 1.53 0 Develop 2 Release 4 6

独自のガベージコレクションを実装 • 既存のガベージコレクタはゲームに適さない • 世代別GC方式 • メジャーGCによる不定期な長時間の停止 • コンカレントGC方式 • GC実行中の速度低下、メモリに十分な空きが必要 • 自動参照カウント方式 • 循環参照リーク、カウンタ操作の高いオーバーヘッド • ゲーム用途に適したリアルタイムGCを実装 • FrameGC方式

FrameGC方式 • ゲーム用途に限定したアルゴリズム • メインループによる定期的な同期ポイントが必要 • C#コードはスクリプトとしての利用が前提 • 特徴 • 予測と制御可能な停止時間 • 即時解放性 • メモリを限界近くまで利用可能 • マルチコアでの高いパフォーマンス • C++言語との高い親和性 • アルゴリズムの詳細 • 付録の解説と疑似コードを参照

FrameGCの流れ Thread1 Stack LocalTable LocalFrameGC C++Method RC(-1) Thread2 Stack LocalTable C#Method RC(-2) LocalFrameGC C++Method RC(-1) C#Method RC(-2) GlobalFrameGC GlobalTable RC(-3) RC(1) RC(1) RC(-3) C#Method RC(-4) RC(0) RC(1) C#Method C#Method RC(-5) RC(0) RC(1) LocalGC RC(-6) RC(1) RC(0)

FrameGCの要点 • 参照カウンタの利点を活かす • 負荷がオブジェクト数に依存しない • 不要なオブジェクトは即座に解放できる • C++言語との高い親和性 • 参照カウンタの欠点を解消する • 参照カウンタで管理するオブジェクト数を減らす • オブジェクトを所属スレッドからのみ参照可能なローカルと、全スレッドから参照 可能なグローバルに分け、グローバルオブジェクトのみを参照カウンタ管理 • 参照カウンタ操作を減らす • グローバルオブジェクトへの書き込み時のみカウンタを操作 • 循環参照ゴミを効率的に回収する • 循環参照する可能性のある型とフィールドのみを対象にインクリメンタルに処理

FrameGCの最適化 • ローカルフレームGCの高速化が重要 • C++からC#メソッド呼び出し毎に最も高頻度で発生する • ローカルヒープの導入 • スレッド毎に4KBのヒープ領域を保持 • 小さなローカルオブジェクトはローカルヒープから割り当て • 確保時はポインタをインクリメント • 解放時はポインタをリセット • スタック割り当てに近い速度 LocalHeap Local A Local BB Global Local Local C A Local D 4KB

FrameGCの動作

FrameGCのパフォーマンス • 探索/戦闘シーンの1フレームのプロファイル 探索シーン C++>C#メソッドコール ローカルオブジェクト生成 グローバルオブジェクト生成 ローカル>グローバル変換 グローバルテーブル登録 サイクルテーブル登録 ローカルフレームGC ローカルGC グローバルフレームGC ローカルフィールドストア グローバルフィールドストア ローカルフレームGC時間(ms) ※ グローバルフレームGC時間(ms) サイクルGC時間(ms) ※ローカルフレームGC時間はマルチコアで並列に実行されるので実際は数倍高速 戦闘シーン 2063 2457 5 55 49 4 1018 0 4 5039 1059 0.116 0.042 0.013 2093 5085 14 330 300 18 1143 0 8 6714 2385 0.174 0.166 0.037 PS4

まとめ • C#は素晴らしい! • プログラマの生産性を大きく向上させる • アプリケーションによるストップバグが発生しない • パフォーマンスの問題はない • REVMは下手なC++コードよりも高速に動作する • FrameGCはゲームにGCは向かないという常識を変える

ご清聴ありがとうございました • ご質問は？

付録 • FrameGCアルゴリズム解説 • FrameGCアルゴリズム疑似コード

FrameGCアルゴリズム(1/7) • ローカルオブジェクト • 生成されたスレッドからのみ参照可能なオブジェクト • スレッド毎にローカルテーブルに登録される • 参照カウンタ(RC)は負でローカルテーブルのインデックスを指す • C#から生成したオブジェクトは全てローカルオブジェクトになる LocalTable RC(-1) RC(-2) RC(-3) RC(-4) RC(-5)

FrameGCアルゴリズム(2/7) • グローバルオブジェクト • 全てのスレッドから参照可能なオブジェクト • 参照カウンタ(RC)は正でオブジェクトの参照数を表す • C++から生成したオブジェクトは全てグローバルオブジェクトになる RC(1) RC(1) RC(1) RC(2) RC(2)

FrameGCアルゴリズム(3/7) • ローカル>グローバル変換 • 全スレッドから参照可能になる時に変換 • 静的フィールドにストア時 • グローバルオブジェクトのフィールドにストア時 • ローカルテーブルから消去されRCは1になる • 参照先も全てグローバルに変換する RC(1) LocalTable RC(-1) RC(-2) RC(-3) RC(-4) RC(-5)

FrameGCアルゴリズム(4/7) • ローカルフレームGC • 対象スレッドのC#スタックが無くなったとき • 全てのローカルテーブルのオブジェクトを解放 • 非常に高速かつ最も高頻度に起こるGC Thread Stack LocalTable LocalFrameGC C++Method RC(-1) C#Method RC(-2) RC(-3) C#Method RC(-4) C#Method RC(-5)

FrameGCアルゴリズム(5/7) • ローカルGC • ローカルテーブルが一杯になったとき • スタックから参照されないローカルオブジェクトを解放 • 対象スレッドのスタックからローカルオブジェクトを保守的に検索 • アドレスがローカルテーブルに存在するかで判定 • 参照される全てのローカルオブジェクトを再帰的にスワップ • 参照されないローカルオブジェクトを解放 Thread Stack LocalTable C++Method RC(-1) C#Method RC(-2) RC(-3) C#Method RC(-4) RC(-5) RC(-5)

FrameGCアルゴリズム(6/7) • グローバルオブジェクト解放 • 参照カウンタが0になった時 • いずれかのスレッドにC#スタックが存在する • 参照カウンタをインクリメントし、グローバルテーブルに登録 • 全スレッドにC#スタックが存在しない • 即座に解放 • 全スレッドのC#スタックが無くなったとき ➢グローバルフレームGC • 全てのグローバルテーブルのオブジェクトを解放

FrameGCアルゴリズム(7/7) • 循環参照する型のグローバルオブジェクト • 自身のフィールド内から自身へ到達可能性がある場合 • 参照カウンタデクリメント時 • 参照カウンタが1以上の時 • サイクルルートに登録 • 参照カウンタが0の時 • サイクルルートから消去 • 通常のグローバルオブジェクト解放処理 • 毎フレーム ➢インクリメンタルサイクルGC • サイクルルートを一定数スキャンし循環参照を検出 ClassA ClassA FieldA 循環する ClassB String FieldA String FieldB 循環しない

インクリメンタルサイクルGC(1/5) • グローバルオブジェクトは参照カウンタ • 循環参照を解放できない • 参照カウンタデクリメント時にサイクルルートに登録 • 循環する可能性のある型のみ • 毎フレーム、サイクルルートをスキャンして循環参照を検出 CycleGarbage RC(1) RC(1) RC(1) RC(1) RC(1) RC(1) String RC(1) CycleRoot 循環参照しない RC(1) RC(2)

インクリメンタルサイクルGC(2/5) • トレースサイクル • サイクルルートからオブジェクトを取り出す • 循環する可能性のある参照を再帰的にトレース • トレース済みのオブジェクトのRCは負で、トレーステーブ ルのインデックスを示す • MCに直前のRCの値を入れる • TCをトレース毎にインクリメント RC(-1) RC(1) RC(-4) RC(1) RC(1) RC(1) CycleRoot RC(1) RC(-2) RC(1) RC(-3) String RC(1) RC(-6) RC(1) RC(2) RC(-5) MC TC RC(-1) 1 10 RC(-2) 1 1 RC(-3) 1 1 RC(-4) RC(-5) 1 1 2 2 1 RC(-6) 1 0 TraceTable

インクリメンタルサイクルGC(3/5) • スキャンサバイバー • MCとTCが一致しないオブジェクトを見つける • 見つけたオブジェクトをルートとしてRCを再帰的 に元に戻す(MCで上書き) RC(-1) RC(1) RC(-4) RC(1) RC(1) RC(-2) String RC(1) RC(2) RC(-5) MC TC RC(-1) 1 10 RC(-2) 1 1 RC(-3) 1 1 RC(-4) RC(-5) 1 1 2 2 RC(-6) 1 0 RC(1) RC(-3) RC(-6) RC(1) TraceTable

インクリメンタルサイクルGC(4/5) • コレクトサイクル • トレーステーブル内のオブジェクトの参照先を解放 • トレーステーブル内のオブジェクトを解放 RC(-1) RC(-4) RC(-2) String RC(1) MC TC RC(-1) 1 10 RC(-2) 1 1 RC(-3) 1 1 RC(-4) 1 1 RC(2) RC(1) RC(-3) RC(1) TraceTable

インクリメンタルサイクルGC(5/5) • トレースサイクルのインクリメンタル化 • トレース数が閾値を超えた場合、トレースを中断 • 中断時のオブジェクトを、サイクルルートに再登録 • 閾値で1フレームの最大負荷を調整 注)閾値を超える深さの循環参照は解放できない • フルサイクルコレクション RC(-1) • サイクルルートが溢れた場合には、閾値なしの完全なト レースを行う RC(1) RC(2) RC(1) CycleRoot Threshold RC(-2) RC(-3) RC(-4) TraceTable

FrameGCのオーバーヘッド • ライトバリア • 参照型のフィールドストア時にストア先がローカル(RCが負)かを判定 • グローバルならAtomicな参照カウンタ操作を伴う • ローカル>グローバル変換 • 参照するローカルオブジェクトもグローバル化 Write Barrier Local to Global

FrameGCアルゴリズム疑似コード • スレッドローカル変数 • LocalTable • LocalCount • LocalFrame • グローバル変数 • GlobalTable • GlobalCount • GlobalFrame • CycleRootTable • CycleRootCount ※グローバル変数へのlockは省略

インスタンス作成 Create(S) LocalCount >= MaxLocalCount LocalGC() RC(S) = -LocalCount LocalTable[LocalCount++] = S

参照カウンタ操作 AddRef(S) RC(S) < 0 ToGlobal(S) else InterlockedIncrement(RC(S)) Release(S) RC(S) >= 0 IsCycleType(S) ToCycleRoot(S) else InterlockedDecrement(RC(S)) == 0 ToLocal(S)

ローカル/グローバル変換 ToGlobal(S) L = LocalTable[--LocalCount] RC(L) = RC(S) LocalTable[-RC(S)] = L RC(S) = 1 for T in children(S) AddRef(T) ToLocal(S) GlobalFrame > 0 AddRef(S) GlobalTable[GlobalCount++] = S else for T in children(S) Release(T) Free(S)

サイクルルート登録 ToCycleRoot(S) InterlockedDecrement(RC(S)) == 0 CycleRootIndex(S) > 0 RemoeCycleRoot(S) ToLocal(S) else CycleRootIndex(S) == 0 CycleRootIndex(S) = CycleRootCount CycleRootTable[CycleRootCount++] = S RemoveCycleRoot(S) L = CycleRootTable[--CycleRootCount] CycleRootIndex(L) = CycleRootIndex(S) CycleRootIndex(S) = 0 CycleRootTable[CycleRootIndex(L)] = L

参照型フィールドストア StoreField(T,F,S) RC(T) < 0 T.F = S else AddRef(S) P = T.F while InterlockedCAS(T.F,S,P) != P P = T.F Release(P) StoreStaticField(F,S) AddRef(S) P=F while InterlockedCAS(F,S,P) != P P=F Release(P)

C++>C#メソッド呼び出し Invoke(M) ++LocalFrame == 1 ++GlobalFrame M() --LocalFrame == 0 LocalFrameGC() --GlobalFrame == 0 GlobalFrameGC()

ローカルフレームGC LocalFrameGC() while LocalCount > 1 Free(LocalTable[--LocalCount])

グローバルフレームGC GlobalFrameGC() while GlobalCount > 0 Release(GlobalTable[--GlobalCount])

ローカルGC LocalGC() ScanPoint = 1 for Address in Stack IsValidAddress(Address) T = Address RC(T) < 0 && -RC(T) < LocalCount && LocalTable[-RC(T)] == T ScanLocal(T) while LocalCount > ScanPoint Free(LocalTable[--LocalCount]) ScanLocal(S) -RC(S) >= ScanPoint L = LocalTable[ScanPoint] L != S RC(L) = RC(S) RC(S) = -ScanPoint LocalTable[-RC(S)] = S LocalTable[-RC(L)] = L ScanPoint++ for T in children(S) ScanLocal(T)

サイクルコレクション CycleGC() TraceCount = 1 while CycleRootCount > 1 L = CycleRootTable[--CycleRootCount] CycleRootIndex(L) = 0 TraceCycle(L) for TB in TraceTable TB.MC != TB.TC ScanSurvivor(TB.Ref) CollectCycle()

トレースサイクル TraceCycle(S) RC(S) >= 0 CycleRootIndex(S) > 0 RemoveCycleRoot(S) TraceTable[TraceCount].Ref = S TraceTable[TraceCount].MC = RC(S) TraceTable[TraceCount].TC = 0 RC(S) = -TraceCount TraceCount++ for T in children(S) IsCycleType(T) TraceCycle(T) RC(T) < 0 TraceTable[-RC(T)].TC++

スキャンサバイバー ScanSurvivor(S) RC(S) < 0 RC(S) = TraceTable[-RC(S)].MC for T in children(S) ScanSurvivor(T)

コレクトサイクル CollectCycle() for TB in TraceTable RC(TB.Ref) < 0 for T in children(TB.Ref) Release(T) for TB in TraceTable RC(TB.Ref) < 0 Free(TB.Ref)