Dependency графата в HotXLS: индекс на array изходите

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

Никой не profile-ва dependency графата, докато batch job, който преди е отнемал секунда, не започне да отнема двадесет. Графата се преизгражда при всяка промяна на формулната топология — първият Recalculate след зареждане или генериране на работна книга, или всеки проход след инвалидация — и в pre-fix trace-а самият този първи проход отне 16074 ms. Оценката никога не е била проблемът; решаването кой от кого зависи беше

Защо преизчисляването на 100 000 формули отнемаше 18 секунди?

Старият edge builder беше квадратичен спрямо броя формули на лист. За всеки dependency диапазон BuildEdges binary-search-ваше прозорец от кандидат възли и после тестваше всеки с RangeIntersectsOutput, а прозорецът тръгваше от самия връх на референцирания лист. Node ключовете идват от XLSDepMakeKey, който пакетирава sheet индекса от бит 34 нагоре, реда в битове 14–33 и колоната в битове 0–13, така че долна граница (Sheet1, 0, 0) значеше „всяка формула от ред 1 надолу до дъното на референцирания диапазон“

// Преди 2.383.1 - TXLSDepGraph.BuildEdges, за dependency диапазон r на възел d
LowerKey := XLSDepMakeKey(FRanges[r].Sheet1, 0, 0);   // връх на листа
UpperKey := XLSDepMakeKey(FRanges[r].Sheet2, FRanges[r].Row2, 16383);
// ...две binary searches върху FNodeOrder дават прозореца [i, Lo)...
while i < Lo do
begin
  NodeIndex := FNodeOrder[i];
  if RangeIntersectsOutput(FRanges[r], FNodes[NodeIndex]) then
  begin
    // hard ръб или LookupScan ръб, дедупликирани през EdgeStamp / ScanStamp
  end;
  Inc(i);
end;

Performance fixture-ът, който изплува това, е обикновен каскаден модел: A2:A50000 всяка добавя едно към клетката над себе си, а B1:B50000 всяка удвоява съседа си в колона A. Референция към ред r затова дърпаше около 2r кандидата през правоъгълния тест, така че едно построяване на графата извършваше пет милиарда проверки за пресичане — приблизителна оценка на гърба на плика, но съвпада с 18.5 секунди на часовника. Всяка проверка отговаряше „не“, освен една-две

Защо edge builder-ът не може да започне търсенето от референцирания ред?

Защото array формула, закачена над диапазон, може да притежава клетки вътре в него. Всеки TXLSDepNode описва изходен правоъгълник от своята anchor (Row, Col) до (OutRow2, OutCol2), а CSE array формула получава един възел за целия си правоъгълник, както обяснява статията за инкременталното преизчисляване и dependency графата. Корен, закачен на A1 и запълващ A1:A10, все пак трябва да получи ръб от формула, която чете само A5; започнете binary search от ред 5 и този ръб тихо изчезва, което значи остаряла кеширана стойност в изпратен отчет вместо бавен. Заявката всъщност е двустранна — anchor на или преди Row2, изход, достигащ поне Row1 — и една-единствена сортировка не може да отговори и на двете половини. Multi-cell резултати се появяват и в съвременни работни книги, а статията за dynamic array spill формулите покрива как spill-нати диапазони се държат в HotXLS

Segment tree на максималните изходни редове

HotXLS пази anchor сортировката за горната граница и добавя augment-иран segment tree за долната. BuildNodeIndex сортира FNodeOrder по node ключ както преди, после BuildMaxOutRowTree запълва FNodeMaxOutRow2 (алокирани по четири записа на възел) с най-големия OutRow2, открит под всяко поддърво. QueryNodeTree слиза само вътре в key прозореца и изоставя всяко поддърво, чийто максимален изходен ред лежи над FRanges[r].Row1, защото никоя формула в него не може да достигне референцираните редове. Оцелелите листа продължават да минават през пълния RangeIntersectsOutput тест, така че sheet обхватите и колоните се проверяват точно както преди

// 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
  // извън key прозореца, или никой изход в това поддърво не достига 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 се запълват в същата последователност и топологичният ред остава детерминистичен. Същото важи и за двата вида ръбове: hard ръб, записан пръв, продължава да потиска по-късен LookupScan ръб за същата двойка, а scan ръб, записан преди hard, пази мястото си — разграничението, което спира lookup диапазоните да раждат фалшиви circular reference-и. На референция цената пада от размера на прозореца на O((k + 1) log n), където k е броят формули, чийто изход реално достига референцираните редове

Какво гарантира output индексът и как се проверява?

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

Измерени резултати: от 18.5 секунди на около 0.1 секунди

Pre-fix Win32 trace-ът, запазен в performance baseline-а на проекта за версия 2.383.0, записа две принудителни преизчислявания от 18488 ms и 19578 ms. След индексирането три последователни focused прогона на архитектура измериха 102.332–109.429 ms на Win32 и 116.990–133.995 ms на Win64, около 170 до 180 пъти по-бързо на Win32; нямаше записан pre-fix Win64 baseline, така че не се претендира Win64 ускорение. Същите прогона минаха съществуващия gate, който държи read-only одит на преизчисляването в рамките на 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 dependent-и в колона 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;

Къде output индексът спира да помага?

Дървото подрязва само по редове, което оставя няколко честни ограничения, полезни да знаете, преди да изградите около него много голям модел

• Пропуски по колона все още се плащат на листата: 2626-те формули, запълващи A100:Z200, всички достигат ред 100, така че референция към AA100:AA200 тества всяка от тях, преди да я отхвърли
• Широки референции като цели-колонни диапазони наистина имат много precedents; индексът маха излишни проверки, не истински ръбове, а построяването им остава пропорционално на броя им
• За референции, обхващащи няколко листа, съхраненият максимум игнорира листа, така че формули на междинни листи с дълбоки изходи достигат leaf теста; резултатите остават коректни, само подрязването е по-слабо
• Дървото струва четири integer-а на формулен възел, около 1.6 MB за 100 000 възла, и всяко AddNode го инвалидира, така че промените в топологията плащат пълно O(n log n) пре-сортиране плюс O(n) построяване на дървото при следващия edge build

Същата квадратична форма в клонирането на report-band имена

Версия 2.383.2 поправи родствено проблем в TXLSXDefinedNames.UniqueCloneName: всяко копирано defined name рестартираше suffix търсенето си от _2, така че повтарящи се report-band копия растяха квадратично в name lookup-и. Scoped name индексът вече пази suffix hint за базово име и за scope и преизпитва последния върнат кандидат, защото извикващият може реално да не го добави; изтриване, преименуване или rescope на име инвалидира индекса, което възстановява first-available именуването. В регресионния suite 1024 последователни клона искат 5088 candidate lookup-и, а четири редуващи се базови имена искат 5039, докато минимумите на report benchmark-а паднаха от около 240 ms на 18–20 ms. Самият report-band timing gate още не е стабилен — три от шест прогона надминаха коефициента му 1.05 при първия опит след поправката — а performance историята пази тези провали в запис, вместо да настройва прага, докато мине

Ако вашето Delphi или C++Builder приложение генерира или преизчислява големи Excel работни книги, HotXLS Excel компонентът за Delphi и C++Builder доставя тази индексирана dependency графа в engine-а за преизчисляване и за двата му класа работни книги, classic и XLSX