Граф залежностей 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 протестує кожну з них, перш ніж відхилити
• Широкі посилання на кшталт цілих колонок справді мають багато precedent-ів; індекс прибирає марні перевірки, а не справжні ребра, і побудова цих ребер усе ще пропорційна їхній кількості
• Для посилань через кілька аркушів збережений максимум ігнорує аркуш, тож формули на проміжних аркушах із глибокими виходами дістаються до листового тесту; результати лишаються коректними, слабшає лише обрізання
• Дерево коштує чотири цілі на вузол формули, приблизно 1.6 МБ на 100 000 вузлів, і будь-який AddNode його інвалідує, тож зміни топології платять повне пересортування O(n log n) плюс побудову дерева O(n) на наступній побудові ребер

Той самий квадратичний профіль у клонуванні імен report-band

Версія 2.383.2 виправила сестринську проблему в TXLSXDefinedNames.UniqueCloneName: кожне скопійоване defined name починало пошук суфікса заново з _2, тож повторні копії report-band росли квадратично в пошуках імен. Індекс імен зі scope тепер тримає підказку суфікса на базове ім'я й на scope і перепровіряє останнього повернутого кандидата, бо викликач може його насправді не додати; видалення, перейменування чи зміна scope імені інвалідує індекс, що відновлює іменування «перше вільне». У регресійному наборі 1 024 послідовні клони потребують 5 088 пошуків кандидатів, а чотири черговані базові імена — 5 039, тоді як мінімуми benchmark-у звітів впали з приблизно 240 мс до 18–20 мс. Сам таймінговий гейт report-band досі не стабільний — три з шести пробіжок перевищили його співвідношення 1.05 у першій спробі після виправлення, — і історія продуктивності зберігає ці невдачі в записі, а не підкручує поріг, доки він не пройде

Якщо ваш застосунок на Delphi чи C++Builder генерує або перераховує великі книги Excel, компонент Excel HotXLS для Delphi та C++Builder постачає цей індексований граф залежностей у рушії перерахунку для обох своїх класів книг, Classic і XLSX