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

13.2K Views

July 15, 22

スライド概要

Game Creators Conference 2017の講演で使用したスライドです。

『ラピッドイテレーションを実現するRE ENGINEの設計』 - 石田 智史

profile-image

株式会社カプコンが誇るゲームエンジン「RE ENGINE」を開発している技術研究統括によるカプコン公式アカウントです。 これまでの技術カンファレンスなどで行った講演資料を公開しています。 【CAPCOM オープンカンファレンス RE:2022】  https://www.capcom.co.jp/RE2022/ 【CAPCOM オープンカンファレンス RE:2019】  http://www.capcom.co.jp/RE2019/

シェア

埋め込む »CMSなどでJSが使えない場合

各ページのテキスト
1.

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

2.

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

3.

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

4.

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

5.

RE ENGINEのイテレーション

6.

リモートでの実機編集

7.

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

8.

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

9.

パッケージ作成

10.

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

11.

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

12.

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

13.

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

14.

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

15.

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

16.

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

17.

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

18.

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

19.

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

20.

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

21.

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

22.

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

23.

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

24.

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

25.

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

26.

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

27.

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

28.

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

29.

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

30.

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

31.

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

32.

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

33.

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

34.

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

35.

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

36.

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

37.

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

38.

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

39.

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

40.

アセット間の依存情報 • 依存関係は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

41.

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

42.

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

43.

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

44.

アセット間の依存関係

45.

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

46.

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

47.

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

48.

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

49.

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

50.

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

51.

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

52.

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

53.

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

54.

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

55.

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

56.

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

57.

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

58.

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

59.

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

60.

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

61.

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

62.

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

63.

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

64.

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

65.

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)

66.

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

67.

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

68.

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

69.

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)

70.

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

71.

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

72.

FrameGCの動作

73.

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

74.

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

75.

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

76.

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

77.

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

78.

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

79.

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

80.

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)

81.

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)

82.

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

83.

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

84.

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

85.

インクリメンタルサイクル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

86.

インクリメンタルサイクル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

87.

インクリメンタルサイクル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

88.

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

89.

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

90.

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

91.

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

92.

参照カウンタ操作 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)

93.

ローカル/グローバル変換 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)

94.

サイクルルート登録 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

95.

参照型フィールドストア 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)

96.

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

97.

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

98.

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

99.

ローカル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)

100.

サイクルコレクション 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()

101.

トレースサイクル 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++

102.

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

103.

コレクトサイクル 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)