技術記事

DelphiでのHotXLSインクリメンタル数式再計算

上のセルの値を育てていく数式が1万個並んだ列は、スプレッドシートが抱えられる最も安価なモデルの1つです。参照先の数式に出会うたびにその場で計算する評価器では、合計はそれでも正しく出ますが、演算の請求書が違います。最後のセルは9,999個の先祖を評価に引きずり、その1つ上は9,998個であり、1回の全体走査で1万回の掛け算のために約5,000万回の評価に達します。先頭の成長率を1つ変えると、この評価器は請求書全体をもう一度払わされます。どのセルがどのセルを読むかの記録をどこにも残していないからです

セル1つの編集がブック全体の走査に化ける理由

この挙動を生む近道が2つあり、手作りの数式エンジンのほとんどはどちらかを取ります。再帰の近道は、参照先の数式を毎回まっさらから評価し、キャッシュ済みの値を無視します。連鎖が2次の仕事量になり、循環参照はスタックオーバーフローになります。全体走査の近道はより安全で、何も変わらなくなるまで何度でも、ある固定順序ですべての数式を評価します。正しい方式ですが、コストが編集の大きさではなくブックの大きさに連動します

Excelは計算チェーンで両方を避けます。数式セルの順序付けを用意し、編集は小さなセル集合に印を付けて、影響を受ける末尾だけを辿れるようにしています。HotXLSのXLSXエンジンは、TXLSXWorkbook.Recalculateの背後に明示的な依存関係グラフという形で同じ発想を使います。最初の呼び出しが全シートの全数式からグラフを組み立て、すべてを評価します。それ以降の呼び出しは、前回のパス以降に値の変わったセルの下流にある数式だけと、毎回実行が必須の短い数式リストを評価します

Recalculateが編集を1回の順序付きパスに変える仕組み

数式セルはそれぞれ1つのノードになり、数式が読むすべての数式セルから、読む側の数式へ辺が引かれます。SUM(Model!B2:B500)のような参照はその矩形内のすべての数式セルからの辺を生み、シートの連なりを渡る3D参照は連なり内の各シートと突き合わせられます。素の定数はノードになりません。編集の起点としてだけ意味を持ちます

セルへのValueの書き込みは、書いた瞬間にはほぼ何もしません。ブックがセルのアドレスをキューに入れるだけです。Recalculateが始まると、参照がキュー済みアドレスを覆うすべての数式にダーティの印が付き、その印が辺に沿ってその数式の依存先すべてへ、さらにその先へ流れます。Recalculateを1度も呼ばれていないブックはグラフを持たず、書き込みのコストはnilチェック1回なので、値を読み書きするだけのコードはこの機能のために何も払いません

グラフのダーティ部分はその後、Kahnのアルゴリズムでソートされます。パスを安く保つ詳細は、入次数の数え方にあります。ダーティな先行だけを数えるのです。クリーンな先行は既に有効なキャッシュ値を保持しているので、数式がそれを待つことはありません。パスの間、他の数式セルを参照する数式はそのセルのキャッシュ値を読み、再評価はしません。ソートがキャッシュが既に新しいことを保証します。ダーティな数式はそれぞれ正確に1回だけ評価されます

Delphi における HotXLS Workbook.Recalculate 1 パスのフローチャート。ダーティフラグ収集とトポロジカルソートから評価と循環報告まで
毎パスでダーティ集合を集め、トポロジカルにソートし、影響を受ける各セルを 1 回だけ評価します。反復計算がオフなら、参照循環はループせず lxErrorRef として返ってきます

下のコードは冒頭のモデルを組み立て、唯一の入力を編集します。HotXLSのシートインデックスは1始まりなので、Inputsがシート1、Modelがシート2です。Cellsの行と列も同様に1始まりです

uses
  SysUtils, lxCalc, lxHandleX;   // lxOk は lxCalc で宣言されています

var
  Book: TXLSXWorkbook;
  Inputs, Model: TXLSXWorksheet;
  Row: Integer;
  Last: Variant;
begin
  Book := TXLSXWorkbook.Create;
  try
    Inputs := Book.Sheets.Add('Inputs');   // Sheets[1]
    Model  := Book.Sheets.Add('Model');    // Sheets[2]

    Inputs.Cells[2, 2].Value := 0.05;      // Inputs!B2 の成長率の前提
    Model.Cells[2, 2].Formula := 'Inputs!B2*1000';
    for Row := 3 to 10000 do
      Model.Cells[Row, 2].Formula :=
        'B' + IntToStr(Row - 1) + '*(1+Inputs!$B$2)';

    if Book.Recalculate <> lxOk then      // グラフを構築し、9,999 個の数式を評価
      Exit;

    Inputs.Cells[2, 2].Value := 0.07;      // アドレスを 1 つキューに入れる
    if Book.Recalculate = lxOk then        // Inputs!B2 を源とする数式が再実行される(ここでは全部の 9,999)
      Last := Model.Cells[10000, 2].Value; // キャッシュされた結果。通常の値と同じように読む

    // 単発の読み取り。RecalcCell は Recalculate を実行してからセルを返す
    // (シート 2 = Model、行 10000、列 2)
    Book.RecalcCell(2, 10000, 2, Last);
  finally
    Book.Free;
  end;
end;

このモデルではすべての数式がInputs!$B$2を読むため、2回目のパスも9,999個すべてに触れます。本当に全体に影響する編集はグラフでも縮められません。節約が現れるのは入力の多いモデルです。シナリオループが3つか4つのセルを書き、ブックの残りはキャッシュ値を保ちます

HotXLS で編集された 1 つの入力セルが、再評価のため下流の Delphi モデル数式だけをダーティとしてマークする様子を示す依存グラフ例
Inputs!B2 の編集が 1 つのダーティノードを蒔きます。ダーティさは先行から依存へのエッジを流れ下り、そのサブグラフだけが再実行されます

値の書き込みは安価、数式の書き込みはグラフを再構築

インクリメンタルのままなのは値の編集だけです。ノードや辺の集合を変えうるものはすべてグラフ全体を失効させ、次のRecalculateがゼロから再構築して全数式を評価します。対象は、Formulaへの代入、Nullや空値の書き込みによる数式セルのクリア、シートの追加・移動・削除、行や列の挿入・削除、定義名の編集、what-ifデータテーブルの変更です。ユーザー関数の登録や登録解除、OnUserFunctionへの代入は、グラフを保持したまま全ノードをダーティにします

レポートジェネレーターにとっての実用的な帰結はループの形です。数式を1度配置し、Recalculateを呼び、以後は値だけに触れます。顧客ごとに数式テンプレートを書き直してから再計算するループは、反復ごとに完全な再構築を受け取ります。それこそグラフが存在して避けるはずだったコストです。テンプレート変更が本当に要るときは、全数式編集を1回のRecalculateの前にまとめ、再構築を1度で済ませます。シナリオループ自体は以後、値だけを書きます

// モデルは 1 度だけ構築済み。Recalculate 済み
for I := 0 to High(Scenarios) do
begin
  Inputs.Cells[2, 2].Value := Scenarios[I].Growth;    // 値の書き込みだけ
  Inputs.Cells[3, 2].Value := Scenarios[I].Discount;
  if Book.RecalcNeeded then          // セルがキュー済みかダーティのとき True
    if Book.Recalculate <> lxOk then
      Break;
  Results[I] := Model.Cells[10000, 2].Value;
end;

// 未処理が残っているときだけ SaveAs に再計算させる
Book.RecalcBeforeSave := xrmIfDirty;
Book.SaveAs('scenarios.xlsx');

RecalcBeforeSaveのデフォルトはxrmManualで、保存中に再計算することはありません。生成ファイルに使うのはxrmIfDirtyです。グラフが失効しているかダーティな数式があるときだけ再計算するので、ループ内で再計算済みのブックはそのまま書かれ、編集し忘れのブックが古いキャッシュ値のまま保存されることはありません

毎回のパスで強制的に再計算されるExcel関数

NOW、TODAY、RAND、RANDBETWEEN、RANDARRAY、OFFSET、INDIRECT、CELL、INFO、GETPIVOTDATAを呼ぶ数式はHotXLSでは揮発性です。上流に変化があってもなくても、すべてのパスの開始時にダーティの印が付き、その依存先すべても同様です。時計と乱数の関数が揮発性なのは言うまでもありません。OFFSETとINDIRECTが揮発性なのは、読むセルが実行時に引数の値から計算され、数式の静的な走査ではどの辺を引くべきか言えないからです

同じ規則は、グラフビルダーが具体的な矩形へ固定できない参照、他の名前を通じて自分自身を参照する定義名、動的配列のスピル参照、what-ifデータテーブルにも適用されます。定義名一般は問題ではありません。ビルダーは名前をその参照先の範囲へ展開するため、ブックやシートスコープの名前を通る数式には本物の辺が引かれます。それらの名前の解決方法は、定義名とシート間数式の記事が扱います

保守的な方向がここでは正しい選択です。不要な評価は少しの時間で済みますが、欠けた辺は完成品に見えるレポートの中の古い数値を意味します。大規模モデルのホットパスからOFFSETとINDIRECTを外し、計算されたアドレスが本当に必要な少数のセルに閉じ込めてください。連鎖の上流近くの揮発性セルは、事実上、連鎖全体を揮発性にします

OnUserFunctionやRegisterUserFunctionで供給される関数は対の極にいます。揮発性ではないため、ハンドラが再び呼ばれるのは、組み込み関数と同じく、引数に流れ込むセルが変わったときだけです。データベースから為替レートを読むハンドラは、パスをまたいで最後の答えを返し続けることになります。レートを入力セルに書き込み、そのセルを引数として渡してください。グラフが依存を認識し、数式はレートが変わったときに正確に再実行されます。ハンドラ引数の渡され方は、HotXLS数式エンジンのカスタム関数の記事が説明します

循環参照:lxErrorRefか反復計算か

デフォルトのIterate = Falseでは、ソートが循環を見つけるとTXLSXWorkbook.RecalculateはlxErrorRefを返します。循環のメンバーはKahnのアルゴリズムが決して解放できないダーティノードで、その下流のダーティ数式も同じ理由で止まります。それらの数式は前回のキャッシュ値を保持し、ダーティ集合のそれ以外は順番に評価されます。失敗したパスはグラフを失効させるため、次の呼び出しはグラフを再構築し、全数式をもう一度評価します

case Book.Recalculate of
  lxOk:
    Book.SaveAs(OutputFile);
  lxErrorRef:
    // 循環とその下流の数式は古いキャッシュを保持したまま
    // LogWarning は自前のルーチン
    LogWarning('Circular reference in model, report not written');
else
  LogWarning('Recalculation did not complete');
end;

Iterate := Trueは、Excelが提供するのと同じ反復計算を有効にします。エンジンは循環とその止まっている依存先をIterateCount回(デフォルト100)まで繰り返し評価し、どの値もIterateDelta(デフォルト0.001)以上動かなくなったところで止めます。空の循環メンバーは0から始まります。回数上限に達しても最後の結果を保持したままlxOkが返ります。だからこそ生成レポートでは反復をオフに保つべきです。実際のレポートモデルの循環はほぼ必ずミス、たとえば合計行が自分自身のSUM範囲に捕まっているようなもので、そこから欲しいのは明確なエラーコードです。オンにするのは、利子を含む平均残高に利子が掛かるといった、意図したループを軸に組まれたモデルだけにしましょう

循環に見えて循環として報告されないケースが1つあります。VLOOKUP、HLOOKUP、LOOKUP、MATCH、XLOOKUP、XMATCHの検索配列引数は、その範囲のセルが変われば数式をダーティにしますが、循環検出には数えられません。したがって列Bに書かれたVLOOKUP(A1,B:B,1)は普通に評価されます。本物の循環には、数式評価トレーサーが自分自身へ折り返す参照連鎖を1ステップずつ見せてくれます

配列数式とマルチスレッドのパス

旧式のCSE配列数式は、固定された矩形全体で1つのノードです。ルートの数式はパスごとに1回評価され、その行列が各メンバーセルへ書き込まれ(スカラーの結果は矩形全体へ放送され)、矩形のどのセル、左上のアンカーだけでなく、参照する数式はルートからの辺を得ます。動的配列の数式はより慎重に扱われます。毎パス実行され、スピルがサイズを変えると、Recalculateはグラフを再構築し、スピルの形が落ち着くまでパスを繰り返します。32ラウンド以内に落ち着かなければ、呼び出しはlxErrorCalcを返します

RecalcThreadsを1より大きくすると、独立した数式の各トポロジカルレベルがワーカースレッドに渡って評価され、スレッドごとに専用の計算器が動きます。データテーブルは依然として直列に走り、動的配列を含むブックは直列経路に留まります。この値を上げる前に、ユーザー関数ハンドラはすべてスレッドセーフでなければなりません。共有状態に触れるハンドラなら、RecalcThreadsをデフォルトの0に保つほうが安全です

依存関係グラフ、揮発性の扱い、反復計算は、HotXLS Delphi Excel ComponentのXLSXエンジンの一部で、数式計算機、定義名、そしてそれらを取り巻く読み書きパイプラインも同じくカバーします。見積書や連結ブックを開きっぱなしにして一日中新しい入力を流し込むDelphiとC++Builderのアプリケーションでは、編集1回の仕事量が編集が実際に届くセルに従って決まります