JA 06_mathematical_model

06. インクリメンタル・ジェネレーターの計算量モデル

🇺🇸 English | 🇯🇵 日本語 | Introduction

Roslyn Incremental Source Generator のパフォーマンスを維持するためには、どの操作がどれだけの計算量（アロケーションコストと処理時間）を発生させるかを厳密に理解しなければならない。

本文書では、本プロジェクトのジェネレーターアーキテクチャに基づく最悪計算量（Worst-Case Complexity）と、それを抑止するために適用されている設計ポリシーを規定する。

Ⅰ. 計算量の基本モデル

ジェネレーターの処理は、アーキテクチャ上大きく2つのフェーズに分割される。

1. PrepareData (データ抽出フェーズ): 属性やクラス構造から構造的データを抽出する。
2. SourceWriter (ソース生成フェーズ): 抽出されたデータを利用し、C# ソースコード文字列を合成する。

コンパイル対象のソースファイル数を $S$、各ファイルに含まれる対象プロパティ（属性）の平均数を $P$、対象属性に指定されている NamedArguments の最大数を $N$ と定義する。

1. PrepareData の計算量

属性の解析中、ジェネレーターは指定された NamedArguments を個別に走査して値を抽出しなければならない。 例えば、PrepareData.cs 内の GetNamedArgumentExpressionSyntax メソッドでは、LINQ のアロケーションを排除するため、意図的な foreach ループと AST ノードの直接照合が強制されている。

// [WHY] 構文ツリーの解析中にデリゲートアロケーションを排除するため、LINQを避けASTノードを直接判定
foreach (var argument in attributeSyntax.ArgumentList.Arguments)
{
    if (argument.NameEquals?.Name.Identifier.ValueText == name)
    {
        return argument.Expression;
    }
}

引数の数 $N$ に対して、設定項目（$M$ 個）ごとにこのループ処理が発生するため、時間計算量は $O(M \times N)$ となり、構造的には $O(N)$ に単純化される。

Note

抽出結果は、厳密に readonly record struct と EquatableArray<T> で構成される純粋な値型 DTO にパッケージ化される。このアーキテクチャ上の制約により、抽出フェーズでのメモリ割り当てコストは最小化される。

2. SourceWriter の計算量

生成されるソースコードの文字数を $K$ と定義する。 文字列の連結処理において、システムはメモリの再割り当てを積極的に抑制しながら線形に書き出すため、SourceWriter（スレッド静的 StringBuilder プールをカプセル化している）の使用を強制する。時間計算量は正確に $O(K)$ となる。

Tip

using var _ = writer.ClassScope(@class); などのゼロアロケーションスコープを厳格に利用することで、ガベージコレクション (GC) への運用負荷は強制的に $O(1)$（ヒープアロケーション 0 バイト）に維持される。

---

Ⅱ. Incremental Cache による最適化と「最悪ケース」

Incremental Generator は過去のコンパイル出力を積極的にキャッシュし、差分のみを排他的に再計算する。 GeneratorHelper.cs 内において、パイプラインは以下の実行チェーンを実行する。

context.ExtractData(framework, version, attributeName, prepareData, id, selectMany) // O(N)
    .SelectAndReportExceptions(getSourceCode, context, id) // O(K)
    .AddSource(context);

インクリメンタルキャッシュのヒット率を $H$ ($0 \le H \le 1$) と仮定すると、このパイプラインを流れる実際の全体計算量 $T$ は以下のようにモデル化される。

$$ T \approx (1 - H) \times O(S \times P \times (N + K)) $$

シナリオ	キャッシュ状態	全体計算量 $T$ の近似	パイプラインへの影響
通常編集時 (メソッド内編集など)	ヒット ($H \to 1$)	$O(1) \approx 0$	モデルの等価性比較（Equals()）のみで早期終了するため、負荷は実質ゼロに縮退する。
構造変更時 (基底クラスの変更など)	ミス ($H \to 0$)	$O(S \times P \times (N + K))$	全ファイルの再解析・ソース生成が走り、理論上の最悪値に達する。

Note

実効パフォーマンスの概算値（日常的な編集・タイピング時: $T \approx 0$）

• 実行レイテンシ: ほぼ 0 ms（実測値 $\le 0.1 \sim 0.5 \text{ ms}$）
• GC ヒープ割り当て: 完全 0 Bytes
• 開発者体験への影響: メソッド内のロジック編集や日常的なキーストロークにおいて、Roslyn パイプラインはモデルの等価性比較（Equals()）により早期に打ち切られる。そのため、ジェネレーターによる CPU・メモリ負荷は実質ゼロとなり、大規模プロジェクトでも IDE の応答遅延が完全に排除される。

最悪ケース (Worst-Case Scenario)

最も深刻な計算負荷は、広範囲なアーキテクチャの変更によりキャッシュヒット率が $H = 0$ に強制された場合に発生する。

シナリオ: 広く消費されている共通の Base クラス内で定義された [DependencyProperty] の名前、型、または属性パラメータ（例: DefaultValue）を変更する。

このアクションは以下のコンパイライベントをトリガーする。

1. Roslyn は、Base クラスに依存するすべてのファイルが構造的に影響を受けたと識別する。
2. インクリメンタルキャッシュは、すべてのターゲットファイル $S$ 全体で完全に無効化（$H = 0$）される。
3. すべてのプロパティ $S \times P$ に対して、$O(N)$ の構文解析と $O(K)$ のソース生成が同期して実行される。

最悪計算量: $O(S \times P \times (N + K))$

Warning

エンタープライズ規模のソリューション（$S$ が数千単位）において、この最悪ケースのシナリオをトリガーすると、IDE が数秒間フリーズすることになる。

---

Ⅲ. パフォーマンス低下を防ぐためのアーキテクチャ上の工夫

この最悪計算量がキーストロークのたびにトリガーされるのを完全に防ぐため、ジェネレーターは厳格なアーキテクチャルールを施行する。

DTO 内での ISymbol 保持禁止、EquatableArray<T> による等価性の厳格な実装、および SourceWriter によるアロケーションフリーな生成に関する詳細は、05. コード生成とパフォーマンス最適化 (Ⅳ. パフォーマンス最適化ルール) を参照のこと。

---

🇺🇸 English | 🇯🇵 日本語 | Introduction