HotXLS 依赖图：为数组公式输出建索引

HotXLS 2.383.1，这个面向 Delphi 和 C++Builder 的原生 Excel 库，通过一个输出区间索引来构建公式依赖边：公式节点仍按锚点单元格排序，一棵保存每个子树最大输出行（OutRow2）的 segment tree 让 TXLSDepGraph.BuildEdges 能整块跳过够不到被引用区域的公式。在一个约 10 万条公式的 Win32 工作簿上，强制重算从 18.488 秒降到 102–109 毫秒

没人会去 profile 依赖图，直到一个过去一秒跑完的批处理作业开始要二十秒。公式拓扑一变，图就会重建——加载或生成工作簿后的第一次 Recalculate，或者图失效之后的任何一趟——而在修复前的 trace 里，光是第一趟就花了 16,074 ms。求值从来不是问题；判断谁依赖谁才是

为什么重算 10 万条公式要 18 秒？

旧的边构建器对一张表上的公式数量是平方级的。对每个依赖区域，BuildEdges 先二分出一个候选节点窗口，再用 RangeIntersectsOutput 逐个测试，而这个窗口的起点是被引用表的表头。节点键来自 XLSDepMakeKey，它把 sheet 索引装进第 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 做两次二分得到窗口 [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 每个单元格给上面的单元格加一，B1:B50000 每个把 A 列邻居翻倍。于是对第 r 行的一个引用会把约 2r 个候选拖过矩形测试，一次建图要做大约五十亿次相交检查——这是拍脑袋的量级估计，但和表上的 18.5 秒对得上。每次检查几乎都说「不」，只有一两个例外

为什么边构建器不能从被引用行开始搜索？

因为锚在区域上方的数组公式可能拥有区域内部的单元格。每个 TXLSDepNode 描述一个从锚点（Row、Col）到（OutRow2、OutCol2）的输出矩形，一条 CSE 数组公式为自己的整个矩形拿一个节点，增量重算与依赖图那篇文章讲过。锚在 A1、填满 A1:A10 的根公式，仍然必须从一个只读 A5 的公式那里收到一条边；从第 5 行开始二分，这条边就无声消失，意味着发布出去的报告里是一个过期缓存值，而不是慢一点。这个查询其实是两边的——锚点不晚于 Row2、输出至少够到 Row1——单一的排序顺序回答不了两半。多单元格结果在现代工作簿里同样出现，动态数组 spill 公式那篇讲了 spill 区域在 HotXLS 里的行为

一棵最大输出行的 segment tree

HotXLS 为上界保留锚点排序，为下界加一棵增强 segment tree。BuildNodeIndex 照旧按节点键给 FNodeOrder 排序，然后 BuildMaxOutRowTree 把每个子树下的最大 OutRow2 填进 FNodeMaxOutRow2（按每节点四个条目分配）。QueryNodeTree 只在键窗口内下降，任何最大输出行落在 FRanges[r].Row1 之上的子树直接放弃，因为里面的公式没有一个够得到被引用的行。存活下来的叶子仍然过完整的 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 数组按同样序列填充，拓扑顺序保持确定性。两种边也一样：先记录的硬边仍然抑制同一对后来的 LookupScan 边，先于硬边记录的 scan 边保住自己的位置——正是这个区分挡住了查找区域产生假循环引用。每个引用的开销从窗口大小降到 O((k + 1) log n)，k 是输出真正够到被引用行的公式数量

输出索引保证什么，又如何验证？

TXLSDepGraph 产出与从前相同的边、相同的顺序，而新的 EdgeCandidateChecks 属性统计最近一次构建实际测试了多少个输出矩形，所以这个说法是可测量的，不是修辞。回归测试 EdgeBuildDeepChainsCheckOneCandidatePerDependency 构建 1,024 和 100,000 节点的点引用链，按逆序插入以迫使空间排序，并断言恰好 N − 1 次检查——长链是 99,999 次——外加每个节点期望的前置、依赖和拓扑顺序。配套测试覆盖乱序插入、跨表区域的数组根，重复的硬边与 lookup-scan 引用（10 次检查，含上述抑制规则），以及 AddNode 之后的重建——它会清掉排序标志，下一次 BuildEdges 或 NodeIndexOf 重建这棵树并把计数器清零而不是累加

实测结果：从 18.5 秒到约 0.1 秒

修复前的 Win32 trace 保存在 2.383.0 的项目性能基线里，记录了两次强制重算：18,488 ms 和 19,578 ms。索引之后，每个架构串行跑三遍 focused 运行，Win32 测得 102.332–109.429 ms，Win64 测得 116.990–133.995 ms，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 的引用要把它们逐个测试一遍才拒绝
• 整列区域这类宽引用确实有很多前置；索引去掉的是浪费的检查，不是真实的边，而构建这些边的开销仍与它们的数量成正比
• 对跨多张表的引用，存储的最大值不看 sheet，所以中间表上输出很深的公式会到达叶子测试；结果仍然正确，只是剪枝变弱
• 这棵树每个公式节点花四个整数，10 万节点约 1.6 MB，任何 AddNode 都会让它失效，所以拓扑变化要在下一次建边时付一次完整的 O(n log n) 重排序加一次 O(n) 建树

report-band 名称克隆里同样的平方级形态

2.383.2 修了 TXLSXDefinedNames.UniqueCloneName 里的一个同族问题：每个复制的 defined name 都把后缀搜索从头 _2 开始，反复复制 report-band 会让名称查找平方级增长。作用域名称索引现在按 base name、按 scope 保存一个后缀提示，并复查上次返回的候选——因为调用方未必真的加它；删除、改名或改 scope 会让索引失效，恢复「取第一个可用名」的行为。回归套件里，1,024 个顺序克隆需要 5,088 次候选查找，四个交替 base name 需要 5,039 次，而报告基准的最小值从约 240 ms 降到 18–20 ms。report-band 计时门槛本身仍然不稳——修复后第一次尝试六次运行有三次超出它的 1.05 比值——性能历史把这些失败记在案，而不是把阈值调到能过为止

如果你的 Delphi 或 C++Builder 应用要生成或重算大型 Excel 工作簿，面向 Delphi 和 C++Builder 的 HotXLS Excel 组件的重算引擎为 Classic 与 XLSX 两个工作簿类都带上了这棵建好索引的依赖图