HotXLS依存グラフ：配列数式出力のインデックス化

DelphiとC++Builder向けのネイティブExcelライブラリであるHotXLS 2.383.1は、出力区間インデックスを通して数式の依存エッジを構築します。数式ノードはアンカーセル順のソートを保ったまま、各部分木の最大出力行（OutRow2）を保持するセグメントツリーにより、TXLSDepGraph.BuildEdgesが参照範囲に届き得ない数式ブロックを丸ごとスキップできます。約10万数式のWin32ワークブックで、強制再計算は18.488秒から102～109ミリ秒まで落ちました

1秒で終わっていたバッチジョブが20秒かかり始めるまで、依存グラフをプロファイリングする人はいません。グラフは数式のトポロジが変わるたびに再構築されます。ワークブックのロードや生成後の最初のRecalculate、あるいはグラフが無効化された後のどのパスでもです。修正前のトレースでは、その最初のパスだけで16,074ミリ秒を食っていました。評価は最初から問題ではなく、誰が誰に依存しているかの判定が問題だったのです

10万数式の再計算に18秒もかかった理由

旧エッジビルダーは、シート上の数式数に対して2次的に振る舞いました。依存範囲ごとにBuildEdgesは候補ノードのウィンドウを二分探索し、その1つ1つをRangeIntersectsOutputでテストします。そしてそのウィンドウの始点は参照シートの最上部でした。ノードキーはXLSDepMakeKeyから来ます。シートインデックスをビット34以降へ、行をビット14～33へ、列をビット0～13へ詰め込むもので、下限(Sheet1, 0, 0)は「参照範囲の底までの行1以下の全数式」を意味しました

// 2.383.1より前：TXLSDepGraph.BuildEdges、ノードdの依存範囲rに対して
LowerKey := XLSDepMakeKey(FRanges[r].Sheet1, 0, 0);   // シートの最上部
UpperKey := XLSDepMakeKey(FRanges[r].Sheet2, FRanges[r].Row2, 16383);
// ...FNodeOrderへの2回の二分探索がウィンドウ[i, Lo)を作る...
while i < Lo do
begin
  NodeIndex := FNodeOrder[i];
  if RangeIntersectsOutput(FRanges[r], FNodes[NodeIndex]) then
  begin
    // ハードエッジまたはLookupScanエッジ、EdgeStamp / ScanStampで重複排除
  end;
  Inc(i);
end;

これを暴いた性能フィクスチャは、ありふれたカスケードモデルです。A2:A50000がそれぞれ上のセルに1を加え、B1:B50000がそれぞれ列Aの隣接セルを2倍にします。行rへの参照はしたがって約2r個の候補を矩形テストに引きずり込むため、グラフ1回の構築が50億回オーダーの交差チェックを実行した計算になります。概算ですが、ストップウォッチの18.5秒と綺麗に合います。チェックは1つか2つを除いてすべて「ノー」でした

エッジビルダーは参照行から探索を始められないのか

範囲より上にアンカーされた配列数式が、その内部のセルを所有できるからです。各TXLSDepNodeはアンカー（Row、Col）から（OutRow2、OutCol2）までの出力矩形を表し、CSE配列数式はその矩形全体に対して1つのノードを得ます。増分再計算と依存グラフの記事が説明する通りです。A1にアンカーされA1:A10を満たすルートは、A5だけを読む数式からエッジを受け取らなければなりません。二分探索を行5から始めれば、そのエッジは音もなく消えます。遅いレポートの代わりに、出荷されたレポートに古いキャッシュ値が残るということです。問い合わせは実は両側あります。アンカーはRow2以下、出力はRow1以上に届くこと。単一のソート順では両方に答えられません。複数セルの結果は現代のワークブックにも現れます。動的配列スピル数式の記事が、スピル範囲がHotXLSでどう振る舞うかを扱っています

最大出力行のセグメントツリー

HotXLSは上限のためにアンカーソートを保ち、下限のために拡張セグメントツリーを追加します。BuildNodeIndexは従来どおりノードキーでFNodeOrderをソートし、続いてBuildMaxOutRowTreeが各部分木の下にある最大のOutRow2をFNodeMaxOutRow2（ノードあたり4エントリで確保）に詰めます。QueryNodeTreeはキーウィンドウの内部だけを降り、最大出力行がFRanges[r].Row1より上にある部分木は放棄します。その中には参照行に届く数式が1つもないからです。生き残った葉はそれでも完全なRangeIntersectsOutputテストを通るため、シート範囲と列のチェックは以前とまったく同じです

// 2.383.1以降のTXLSDepGraph.BuildNodeIndex / BuildEdges（やや簡略化）
procedure BuildMaxOutRowTree(ATreeIndex, ALeft, ARight: Integer);
var
  Mid: Integer;
begin
  if ALeft = ARight then
  begin
    FNodeMaxOutRow2[ATreeIndex] := FNodes[FNodeOrder[ALeft]].OutRow2;
    Exit;
  end;
  Mid := (ALeft + ARight) shr 1;
  BuildMaxOutRowTree(ATreeIndex * 2, ALeft, Mid);
  BuildMaxOutRowTree(ATreeIndex * 2 + 1, Mid + 1, ARight);
  FNodeMaxOutRow2[ATreeIndex] := Max(FNodeMaxOutRow2[ATreeIndex * 2],
    FNodeMaxOutRow2[ATreeIndex * 2 + 1]);
end;

procedure QueryNodeTree(ATreeIndex, ALeft, ARight, ALower, AUpper: Integer);
var
  Split: Integer;
begin
  // キーウィンドウの外、またはこの部分木の出力はRow1に届かない
  if (ARight < ALower) or (ALeft >= AUpper) or
     (FNodeMaxOutRow2[ATreeIndex] < FRanges[r].Row1) then
    Exit;
  if ALeft = ARight then
  begin
    Inc(FEdgeCandidateChecks);
    if RangeIntersectsOutput(FRanges[r], FNodes[FNodeOrder[ALeft]]) then
    begin
      // 変更なし：EdgeStamp / ScanStampによる抑制、AddDependent / AddScanDependent
    end;
    Exit;
  end;
  Split := (ALeft + ARight) shr 1;
  QueryNodeTree(ATreeIndex * 2, ALeft, Split, ALower, AUpper);           // 先に左の部分木
  QueryNodeTree(ATreeIndex * 2 + 1, Split + 1, ARight, ALower, AUpper);  // 旧順序を維持
end;

左を先にする再帰は見た目の好みではありません。生き残った葉は旧whileループが訪れたのとまったく同じ順序で訪問されるため、DependentsとPrecedents配列は同じシーケンスで満たされ、トポロジカル順序は決定論的であり続けます。2つのエッジ種別についても同様です。先に記録されたハードエッジは、同じペアに対して後から来るLookupScanエッジを依然として抑制しますし、ハードの前に記録されたスキャンエッジはその座標を保ちます。ルックアップ範囲が偽の循環参照を生まないための区別です。参照1つあたりのコストはウィンドウサイズからO((k + 1) log n)へ落ちます。kは出力が実際に参照行へ届く数式の数です

出力インデックスが保証するものと、その検証方法

TXLSDepGraphは以前と同じエッジを同じ順序で生成し、新しいEdgeCandidateChecksプロパティは直近の構築が実際にテストした出力矩形の数を数えます。主張が修辞ではなく測定可能だということです。リグレッションテストEdgeBuildDeepChainsCheckOneCandidatePerDependencyは1,024ノードと10万ノードの点参照チェーンを構築し、空間ソートを強制するために逆順に挿入した上で、チェック数がちょうどN − 1であること（長いチェーンで99,999）と、全ノードについて期待される先行・後続・トポロジカル順序をアサートします。追加のテストは、シート範囲をまたいで順不同に挿入された配列ルート、重複するハード参照とルックアップスキャン参照（上記の抑制ルール付きで10チェック）、そしてAddNode後の再構築をカバーします。これはソートフラグをクリアするため、次のBuildEdgesやNodeIndexOfがツリーを再構築し、カウンタは累積ではなくリセットされます

測定結果：18.5秒から約0.1秒へ

修正前のWin32トレースは、バージョン2.383.0のプロジェクト性能ベースラインに残っており、強制再計算2回を18,488ミリ秒と19,578ミリ秒と記録していました。インデックス化後は、アーキテクチャごとに3回の逐次focused実行で、Win32では102.332～109.429ミリ秒、Win64では116.990～133.995ミリ秒を測定しました。Win32では約170～180倍の高速化です。修正前のWin64ベースラインは記録されていないため、Win64の高速化は主張しません。同じ実行は、読み取り専用の再計算監査を強制再計算の1.35倍以内に保つ既存のゲートも通過しています。絶対値はマシンと負荷に依存するので、数字を引用する前に自分のハードウェアでワークロードを再現してください

uses
  System.SysUtils, System.Diagnostics, lxHandle;

procedure TimeChainRecalc;
var
  Wb: TXLSWorkbook;
  Sh: TXLSWorksheet;
  I, Failed: Integer;
  Watch: TStopwatch;
begin
  Wb := TXLSWorkbook.Create;
  try
    Sh := Wb.Sheets.Add;
    Sh.Cells[1, 1].Value := 1;
    for I := 2 to 50000 do                     // 列Aに49,999リンクのチェーン
      Sh.Cells[I, 1].Formula := '=A' + IntToStr(I - 1) + '+1';
    for I := 1 to 50000 do                     // 列Bに50,000の依存先
      Sh.Cells[I, 2].Formula := '=A' + IntToStr(I) + '*2';

    Watch := TStopwatch.StartNew;
    Failed := Wb.Recalculate;                  // 最初の呼び出しがグラフを構築する
    Watch.Stop;
    Writeln(Format('%d formulas not evaluated, %.1f ms',
      [Failed, Watch.Elapsed.TotalMilliseconds]));
  finally
    Wb.Free;
  end;
end;

出力インデックスが効かなくなる場所

ツリーは行だけで枝刈りをするため、巨大なモデルをこれを前提に設計する前に知っておくべき正直な限界がいくつか残ります

• 列のミスマッチは依然として葉で支払う：A100:Z200を満たす2,626個の数式はすべて行100に届くため、AA100:AA200への参照は各数式を拒否する前にテストする
• 列全体の範囲のような広い参照は実際に多くの先行を持つ。インデックスが取り除くのは無駄なチェックであって本物のエッジではなく、それらのエッジ構築は依然として数に比例する
• 複数シートにまたがる参照では、保存された最大値はシートを無視するため、深い出力を持つ中間シート上の数式は葉のテストまで到達する。結果は正しいまま、枝刈りが弱くなるだけだ
• ツリーは数式ノードあたり整数4つのコスト（10万ノードで約1.6MB）がかかり、どのAddNodeでも無効化される。トポロジ変更は、次のエッジ構築で完全なO(n log n)の再ソートとO(n)のツリー構築を支払うことになる

レポートバンド名複製にもあった同じ2次の形

バージョン2.383.2は、TXLSXDefinedNames.UniqueCloneNameの兄弟問題を修正しました。複製された定義名は毎回サフィックス探索を_2からやり直すため、レポートバンドの繰り返しコピーで名前検索が2次的に増えていたのです。スコープ付き名前インデックスは、ベース名ごと・スコープごとのサフィックスヒントを保持し、最後に返した候補を再チェックします。呼び出し側が実際には追加しないかもしれないためです。名前の削除、改名、スコープ変更はインデックスを無効化し、最初に見つかった空き名の方式へ戻します。リグレッションスイートでは、1,024個の逐次複製が5,088回、4つの交互ベース名が5,039回の候補検索で済み、レポートベンチマークの最小値は約240ミリ秒から18～20ミリ秒へ落ちました。レポートバンドのタイミングゲート自体はまだ安定していません。修正後最初の試行で6実行のうち3回が1.05比率を超えたのです。性能履歴はその失敗を記録に残し、ゲートが通るまで閾値を調整するようなことはしていません

DelphiやC++Builderのアプリケーションが大きなExcelワークブックを生成または再計算するなら、DelphiとC++Builder向けのHotXLS Excelコンポーネントは、このインデックス化された依存グラフを再計算エンジンに搭載しています。クラシックとXLSXの両ワークブッククラスが対象です