Граф зависимостей HotXLS: индексация выходов формул массива

HotXLS 2.383.1, нативная Excel-библиотека для Delphi и C++Builder, строит рёбра зависимостей формул через индекс выходных интервалов: узлы формул остаются отсортированными по якорной ячейке, а дерево отрезков, хранящее максимальную выходную строку (OutRow2) каждого поддерева, позволяет TXLSDepGraph.BuildEdges пропускать целые блоки формул, которые не могут дотянуться до сосланного диапазона. На книге Win32 примерно со 100 000 формул принудительный пересчёт упал с 18.488 секунды до 102–109 миллисекунд

Никто не профилирует граф зависимостей, пока батч, отъедавший секунду, не начинает отъедать двадцать. Граф перестраивается при каждом изменении топологии формул — первый Recalculate после загрузки или генерации книги, или любой проход после инвалидации графа, — и в трейсе до фикса один только первый проход занимал 16 074 мс. Само вычисление никогда не было проблемой; проблемой было решить, кто от кого зависит

Почему пересчёт 100 000 формул занимал 18 секунд?

Старый строитель рёбер был квадратичен по числу формул на листе. Для каждого диапазона зависимостей BuildEdges бинарным поиском находил окно кандидатов, затем проверял каждого через RangeIntersectsOutput, и окно это начиналось с самого верха сосланного листа. Ключи узлов идут из XLSDepMakeKey, пакующего индекс листа с бита 34 и выше, строку в биты 14–33 и столбец в биты 0–13, так что нижняя граница (Sheet1, 0, 0) означала «каждую формулу от строки 1 до низа сосланного диапазона»

// До 2.383.1 — TXLSDepGraph.BuildEdges, для диапазона зависимостей r узла d
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, — и один порядок сортировки не может ответить на обе половины сразу. Многоячеечные результаты встречаются и в современных книгах, и статья про формулы разлива динамических массивов рассказывает, как ведут себя разлитые диапазоны в HotXLS

Дерево отрезков из максимальных выходных строк

HotXLS оставляет сортировку по якорю для верхней границы и добавляет расширенное дерево отрезков для нижней. BuildNodeIndex сортирует FNodeOrder по ключу узла, как раньше, затем BuildMaxOutRowTree заполняет FNodeMaxOutRow2 (выделено по четыре записи на узел) наибольшим OutRow2, найденным под каждым поддеревом. QueryNodeTree спускается только внутри ключевого окна и бросает любое поддерево, чья максимальная выходная строка лежит выше FRanges[r].Row1, потому что ни одна формула в нём не дотянется до сосланных строк. Пережившие листья всё равно проходят полный тест RangeIntersectsOutput, так что диапазоны листов и столбцы проверяются ровно как раньше

// TXLSDepGraph.BuildNodeIndex / BuildEdges с 2.383.1 (слегка ужато)
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-ребро для той же пары, а скановое ребро, записанное раньше жёсткого, сохраняет своё место — это то различие, что не даёт lookup-диапазонам плодить ложные циклические ссылки. На ссылку цена падает с размера окна до O((k + 1) log n), где k — число формул, чей выход реально достаёт до сосланных строк

Что гарантирует индекс выходов и как это проверено?

TXLSDepGraph выдаёт те же рёбра в том же порядке, что и раньше, а новое свойство EdgeCandidateChecks считает, сколько выходных прямоугольников реально проверила последняя сборка, так что заявление измеримо, а не риторично. Регрессионный тест EdgeBuildDeepChainsCheckOneCandidatePerDependency строит цепочки точечных ссылок из 1 024 и 100 000 узлов, вставленных в обратном порядке, чтобы форсировать пространственную сортировку, и утверждает ровно N − 1 проверок — 99 999 для длинной цепочки — плюс ожидаемые precedent, dependent и топологический порядок для каждого узла. Сопутствующие тесты покрывают корни массивов, вставленные вне порядка через диапазоны листов, дублирующиеся жёсткие и lookup-scan ссылки (10 проверок, с правилами подавления выше) и пересборку после AddNode, которая сбрасывает флаг сортировки, так что следующий BuildEdges или NodeIndexOf перестраивает дерево и сбрасывает счётчик, а не накапливает его

Замеры: с 18.5 секунды до примерно 0.1 секунды

Трейс Win32 до фикса, сохранённый в перфоманс-базлайне проекта для версии 2.383.0, записал два принудительных пересчёта — 18 488 мс и 19 578 мс. После индексации три серийных точечных прогона на архитектуру намерили 102.332–109.429 мс на Win32 и 116.990–133.995 мс на Win64, примерно в 170–180 раз быстрее на Win32; базлайна 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                     // цепочка из 49 999 звеньев в столбце A
      Sh.Cells[I, 1].Formula := '=A' + IntToStr(I - 1) + '+1';
    for I := 1 to 50000 do                     // 50 000 зависимых в столбце B
      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;

Где индекс выходов перестаёт помогать?

Дерево отсекает только по строкам, и это оставляет несколько честных пределов, о которых стоит знать, прежде чем строить вокруг него очень большую модель

• Промахи по столбцам всё ещё оплачиваются на листьях: 2 626 формул, заполняющих A100:Z200, все достают до строки 100, так что ссылка на AA100:AA200 проверит каждую из них, прежде чем отвергнуть
• Широкие ссылки вроде диапазонов в целый столбец действительно имеют много влияющих; индекс убирает холостые проверки, а не настоящие рёбра, и построение этих рёбер по-прежнему пропорционально их количеству
• Для ссылок через несколько листов хранимый максимум игнорирует лист, поэтому формулы на промежуточных листах с глубокими выходами доходят до листового теста; результаты остаются корректными, слабее лишь отсечение
• Дерево стоит четыре целых числа на узел формулы, около 1.6 МБ на 100 000 узлов, и любой AddNode его инвалидирует, так что изменения топологии платят полную пересортировку O(n log n) плюс построение дерева O(n) при следующей сборке рёбер

Тот же квадратичный профиль в клонировании имён репорт-бэндов

Версия 2.383.2 починила родственную проблему в TXLSXDefinedNames.UniqueCloneName: каждое скопированное определённое имя начинало поиск суффикса заново с _2, так что повторные копии репорт-бэндов росли квадратично по поиску имён. Индекс имён с областями видимости теперь держит подсказку суффикса на пару «базовое имя, область» и перепроверяет последнего возвращённого кандидата, потому что вызывающий может его и не добавить; удаление, переименование или смена области имени инвалидирует индекс, возвращая схему «первое доступное». В регрессионном наборе 1 024 последовательных клона требуют 5 088 поисков кандидатов, а четыре чередующихся базовых имени — 5 039, при этом минимумы репорт-бенчмарка упали примерно с 240 мс до 18–20 мс. Сами тайминговые ворота репорт-бэндов всё ещё нестабильны — три прогона из шести превысили их отношение 1.05 в первой попытке после фикса, — и история производительности хранит эти отказы в записи, а не подкручивает порог, пока он не пройдёт

Если ваше приложение на Delphi или C++Builder генерирует или пересчитывает большие книги Excel, Excel-компонент HotXLS для Delphi и C++Builder поставляет этот индексированный граф зависимостей в движке пересчёта для обоих своих классов книг, классического и XLSX