HotXLS Dependency Graph: Indexing Array Formula Outputs

HotXLS 2.383.1, the native Excel library for Delphi and C++Builder, builds formula dependency edges through an output-interval index: formula nodes stay sorted by anchor cell, and a segment tree holding the largest output row (OutRow2) of every subtree lets TXLSDepGraph.BuildEdges skip whole blocks of formulas that cannot reach a referenced range. On a Win32 workbook with roughly 100,000 formulas, forced recalculation fell from 18.488 seconds to 102–109 milliseconds

Nobody profiles the dependency graph until a batch job that used to take a second starts taking twenty. The graph is rebuilt whenever formula topology changes — the first Recalculate after loading or generating a workbook, or any pass after the graph has been invalidated — and in the pre-fix trace that first pass alone took 16,074 ms. Evaluation was never the problem; deciding who depends on whom was

Why did recalculating 100,000 formulas take 18 seconds?

The old edge builder was quadratic in the number of formulas on a sheet. For every dependency range, BuildEdges binary-searched a window of candidate nodes and then tested each one with RangeIntersectsOutput, and that window started at the very top of the referenced sheet. Node keys come from XLSDepMakeKey, which packs the sheet index from bit 34 upward, the row into bits 14–33, and the column into bits 0–13, so the lower bound (Sheet1, 0, 0) meant "every formula from row 1 down to the bottom of the referenced range"

// Before 2.383.1 - TXLSDepGraph.BuildEdges, for dependency range r of node d
LowerKey := XLSDepMakeKey(FRanges[r].Sheet1, 0, 0);   // top of the sheet
UpperKey := XLSDepMakeKey(FRanges[r].Sheet2, FRanges[r].Row2, 16383);
// ...two binary searches over FNodeOrder produce the window [i, Lo)...
while i < Lo do
begin
  NodeIndex := FNodeOrder[i];
  if RangeIntersectsOutput(FRanges[r], FNodes[NodeIndex]) then
  begin
    // hard edge or LookupScan edge, deduplicated through EdgeStamp / ScanStamp
  end;
  Inc(i);
end;

The performance fixture that exposed this is an ordinary cascading model: A2:A50000 each add one to the cell above, and B1:B50000 each double the neighbour in column A. A reference to row r therefore dragged about 2r candidates through the rectangle test, so a single graph build performed on the order of five billion intersection checks — a back-of-envelope estimate, but it lines up with the 18.5 seconds on the clock. Every check said "no" except one or two

Why can't the edge builder start the search at the referenced row?

Because an array formula anchored above a range can own cells inside it. Each TXLSDepNode describes an output rectangle from its anchor (Row, Col) to (OutRow2, OutCol2), and a CSE array formula gets one node for its entire rectangle, as the article on incremental recalculation and the dependency graph explains. A root anchored at A1 that fills A1:A10 must still receive an edge from a formula that reads only A5; start the binary search at row 5 and that edge silently disappears, which means a stale cached value in a shipped report instead of a slow one. The query is really two-sided — anchor at or before Row2, output reaching at least Row1 — and a single sort order cannot answer both halves. Multi-cell results show up in modern workbooks too, and the article on dynamic array spill formulas covers how spilled ranges behave in HotXLS

A segment tree of maximum output rows

HotXLS keeps the anchor sort for the upper bound and adds an augmented segment tree for the lower bound. BuildNodeIndex sorts FNodeOrder by node key as before, then BuildMaxOutRowTree fills FNodeMaxOutRow2 (allocated at four entries per node) with the largest OutRow2 found under each subtree. QueryNodeTree descends only inside the key window and abandons any subtree whose maximum output row lies above FRanges[r].Row1, because no formula in it can reach the referenced rows. Leaves that survive still go through the full RangeIntersectsOutput test, so sheet spans and columns are checked exactly as before

// TXLSDepGraph.BuildNodeIndex / BuildEdges since 2.383.1 (lightly condensed)
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
  // outside the key window, or no output in this subtree reaches 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
      // unchanged: EdgeStamp / ScanStamp suppression, AddDependent / AddScanDependent
    end;
    Exit;
  end;
  Split := (ALeft + ARight) shr 1;
  QueryNodeTree(ATreeIndex * 2, ALeft, Split, ALower, AUpper);           // left subtree first
  QueryNodeTree(ATreeIndex * 2 + 1, Split + 1, ARight, ALower, AUpper);  // keeps the old order
end;

The left-before-right recursion is not a style choice. Surviving leaves are visited in exactly the order the old while loop visited them, so the Dependents and Precedents arrays are filled in the same sequence and topological order stays deterministic. The same holds for the two edge kinds: a hard edge recorded first still suppresses a later LookupScan edge for the same pair, while a scan edge recorded before a hard one keeps its place — the distinction that stops lookup ranges from producing false circular references. Per reference, the cost drops from the size of the window to O((k + 1) log n), where k is the number of formulas whose output actually reaches the referenced rows

What does the output index guarantee, and how is it verified?

TXLSDepGraph produces the same edges in the same order as before, and the new EdgeCandidateChecks property counts how many output rectangles the most recent build actually tested, so the claim is measurable rather than rhetorical. The regression test EdgeBuildDeepChainsCheckOneCandidatePerDependency builds point-reference chains of 1,024 and 100,000 nodes, inserted in reverse order to force the spatial sort, and asserts exactly N − 1 checks — 99,999 for the long chain — plus the expected precedent, dependent, and topological order for every node. Companion tests cover array roots inserted out of order across sheet spans, duplicate hard and lookup-scan references (10 checks, with the suppression rules above), and a rebuild after AddNode, which clears the sort flag so the next BuildEdges or NodeIndexOf rebuilds the tree and resets the counter instead of accumulating it

Measured results: from 18.5 seconds to about 0.1 seconds

The pre-fix Win32 trace, retained in the project performance baseline for version 2.383.0, recorded two forced recalculations of 18,488 ms and 19,578 ms. After indexing, three serial focused runs per architecture measured 102.332–109.429 ms on Win32 and 116.990–133.995 ms on Win64, roughly 170 to 180 times faster on Win32; no pre-fix Win64 baseline was recorded, so no Win64 speedup is claimed. The same runs passed the existing gate that keeps a read-only recalculation audit within 1.35 times a forced recalculation. Absolute numbers depend on the machine and its load, so reproduce the workload on your own hardware before quoting them

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                     // 49,999-link chain in column A
      Sh.Cells[I, 1].Formula := '=A' + IntToStr(I - 1) + '+1';
    for I := 1 to 50000 do                     // 50,000 dependents in column B
      Sh.Cells[I, 2].Formula := '=A' + IntToStr(I) + '*2';

    Watch := TStopwatch.StartNew;
    Failed := Wb.Recalculate;                  // first call builds the graph
    Watch.Stop;
    Writeln(Format('%d formulas not evaluated, %.1f ms',
      [Failed, Watch.Elapsed.TotalMilliseconds]));
  finally
    Wb.Free;
  end;
end;

Where does the output index stop helping?

The tree prunes on rows only, and that leaves a few honest limits worth knowing before you design a very large model around it

• Column misses are still paid at the leaves: the 2,626 formulas filling A100:Z200 all reach row 100, so a reference to AA100:AA200 tests each of them before rejecting it
• Wide references such as whole-column ranges genuinely have many precedents; the index removes wasted checks, not real edges, and building those edges is still proportional to their number
• For references that span several sheets, the stored maximum ignores the sheet, so formulas on intermediate sheets with deep outputs reach the leaf test; results stay correct, only the pruning is weaker
• The tree costs four integers per formula node, about 1.6 MB for 100,000 nodes, and any AddNode invalidates it, so topology changes pay a full O(n log n) re-sort plus an O(n) tree build on the next edge build

The same quadratic shape in report-band name cloning

Version 2.383.2 fixed a sibling problem in TXLSXDefinedNames.UniqueCloneName: every copied defined name restarted its suffix search at _2, so repeated report-band copies grew quadratically in name lookups. The scoped name index now keeps a per-base-name, per-scope suffix hint and rechecks the last returned candidate, because the caller may not actually add it; deleting, renaming, or rescoping a name invalidates the index, which restores first-available naming. In the regression suite, 1,024 sequential clones need 5,088 candidate lookups and four alternating base names need 5,039, while the report benchmark minima dropped from roughly 240 ms to 18–20 ms. The report-band timing gate itself is still not stable — three of six runs exceeded its 1.05 ratio in the first post-fix attempt — and the performance history keeps those failures on record rather than tuning the threshold until it passes

If your Delphi or C++Builder application generates or recalculates large Excel workbooks, the HotXLS Excel component for Delphi and C++Builder ships this indexed dependency graph in the recalculation engine for both its classic and XLSX workbook classes