Graf závislostí HotXLS: indexovanie výstupov array formúl

HotXLS 2.383.1, natívna Excel knižnica pre Delphi a C++Builder, stavia hrany závislostí formul cez output-interval index: nody formul zostávajú zoradené podľa anchor bunky a segment tree držiaci najväčší výstupný riadok (OutRow2) každého podstromu nechá TXLSDepGraph.BuildEdges preskočiť celé bloky formul, ktoré nedosiahnu na referencovaný range. Na Win32 workbooku so zhruba 100 000 formulami klesol vynútený prepočet z 18,488 sekundy na 102–109 milisekúnd

Nikto neprofiluje graf závislostí, kým batch job, ktorý trval sekundu, nezačne trvať dvadsať. Graf sa prestavia vždy, keď sa zmení formula topológia — prvé Recalculate po načítaní alebo vygenerovaní workbooku, alebo akýkoľvek prieskum po invalidácii grafu — a v trace pred opravou zabral ten prvý prieskum sám o sebe 16 074 ms. Vyhodnocovanie nikdy problém nebolo; problém bolo rozhodnúť, kto na kom závisí

Prečo prepočet 100 000 formul trval 18 sekúnd?

Starý edge builder bol kvadratický v počte formul na hárku. Pre každý dependency range binary-searchoval BuildEdges okno kandidátskych nodov a potom testoval každý cez RangeIntersectsOutput a to okno začínalo na samom vrchu referencovaného hárku. Kľúče nodov pochádzajú z XLSDepMakeKey, ktorý balí sheet index od bitu 34 nahor, riadok do bitov 14–33 a stĺpec do bitov 0–13, takže spodná medza (Sheet1, 0, 0) znamenala „každú formulu od riadku 1 až po dno referencovaného rangeu“

// Pred 2.383.1 — TXLSDepGraph.BuildEdges, pre dependency range r nodu d
LowerKey := XLSDepMakeKey(FRanges[r].Sheet1, 0, 0);   // vrch hárku
UpperKey := XLSDepMakeKey(FRanges[r].Sheet2, FRanges[r].Row2, 16383);
// ...dve binary searches cez FNodeOrder dajú okno [i, Lo)...
while i < Lo do
begin
  NodeIndex := FNodeOrder[i];
  if RangeIntersectsOutput(FRanges[r], FNodes[NodeIndex]) then
  begin
    // hard edge alebo LookupScan edge, deduplikované cez EdgeStamp / ScanStamp
  end;
  Inc(i);
end;

Performance fixture, ktorý to odhalil, je obyčajný kaskádový model: A2:A50000 pripočítajú jedničku bunke nad sebou a B1:B50000 zdvojnásobia suseda v stĺpci A. Referencia na riadok r tým pádom ťahala zhruba 2r kandidátov cez rectangle test, takže jedno stavanie grafu vykonalo rádovo päť miliárd intersection checkov — odhad na obálke, ale sedí to s 18,5 sekundy na hodinách. Každý check povedal „nie“ okrem jedného či dvoch

Prečo nemôže edge builder začať hľadanie na referencovanom riadku?

Pretože array formula ukotvená nad rangeom môže vlastniť bunky vnútri neho. Každý TXLSDepNode popisuje výstupný obdĺžnik od svojej kotvy (Row, Col) po (OutRow2, OutCol2) a CSE array formula dostáva jeden node pre celý svoj obdĺžnik, ako vysvetľuje článok o inkrementálnom prepočte a grafe závislostí. Root ukotvený na A1, ktorý napĺňa A1:A10, musí stále dostať hranu od formuly, ktorá číta len A5; začnite binary search na riadku 5 a tá hrana poticho zmizne, čo znamená zastaralú cached hodnotu v odoslanom reporte namiesto pomalej. Dopyt je v skutočnosti obojstranný — kotva na Row2 alebo skôr, výstup siahajúci aspoň po Row1 — a jedno poradie triedenia nedokáže odpovedať obe polovice. Viacbunčné výsledky sa ukazujú aj v moderných workbookoch a článok o dynamic array spill formulách pokrýva, ako sa spilled rangey správajú v HotXLS

Segment tree maximálnych výstupných riadkov

HotXLS ponecháva anchor triedenie pre hornú medzu a pridáva augmentovaný segment tree pre spodnú medzu. BuildNodeIndex triedi FNodeOrder podľa kľúča nodu ako predtým, potom BuildMaxOutRowTree napĺňa FNodeMaxOutRow2 (alokované na štyri položky na node) najväčším OutRow2 nájdeným pod každým podstromom. QueryNodeTree zostupuje len vnútri kľúčového okna a opúšťa každý podstrom, ktorého maximálny výstupný riadok leží nad FRanges[r].Row1, pretože žiadna formula v ňom nedosiahne na referencované riadky. Listy, ktoré prežijú, stále prechádzajú plným testom RangeIntersectsOutput, takže sheet span a stĺpce sa kontrolujú presne ako predtým

// TXLSDepGraph.BuildNodeIndex / BuildEdges od 2.383.1 (mierne skondenzované)
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
  // mimo kľúčového okna, alebo žiadny výstup v tomto podstrome nedosahuje 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
      // nezmenené: potlačenie EdgeStamp / ScanStamp, AddDependent / AddScanDependent
    end;
    Exit;
  end;
  Split := (ALeft + ARight) shr 1;
  QueryNodeTree(ATreeIndex * 2, ALeft, Split, ALower, AUpper);           // najprv ľavý podstrom
  QueryNodeTree(ATreeIndex * 2 + 1, Split + 1, ARight, ALower, AUpper);  // drží staré poradie
end;

Rekurzia ľavý-pred-pravým nie je štýlová voľba. Preživšie listy sa navštívia presne v poradí, v akom ich navštevovala stará slučka while, takže polia Dependents a Precedents sa napĺňajú v tej istej postupnosti a topologické poradie zostáva deterministické. To isté platí pre dva druhy hrán: hard edge zaznamenaná prvá aj naďalej potláča neskoršiu LookupScan hranu pre tú istú dvojicu, kým scan edge zaznamenaná pred hard si drží svoje miesto — rozdiel, ktorý bráni lookup rangeom produkovať falošné kruhové referencie. Na referenciu náklady klesajú z veľkosti okna na O((k + 1) log n), kde k je počet formul, ktorých výstup reálne dosahuje na referencované riadky

Čo garantuje output index a ako sa to overuje?

TXLSDepGraph produkuje tie isté hrany v tom istom poradí ako predtým a nová vlastnosť EdgeCandidateChecks počíta, koľko výstupných obdĺžnikov posledné stavanie reálne testovalo, takže tvrdenie je merateľné, nie rétorické. Regression test EdgeBuildDeepChainsCheckOneCandidatePerDependency stavia point-reference reťazce 1 024 a 100 000 nodov, vložených v opačnom poradí, aby vynútil priestorové triedenie, a assertuje presne N − 1 checkov — 99 999 pre dlhý reťazec — plus očakávané precedent, dependent a topologické poradie pre každý node. Súrodé testy pokrývajú array rooty vložené mimo poradia cez sheet span, duplicitné hard a lookup-scan referencie (10 checkov, s pravidlami potlačenia vyššie) a prestavbu po AddNode, ktorá zruší sort flag, takže ďalšie BuildEdges alebo NodeIndexOf prestavia tree a resetujú počítadlo namiesto toho, aby ho akumulovali

Namerané výsledky: z 18,5 sekundy na zhruba 0,1 sekundy

Win32 trace pred opravou, uložený v performance baseline projektu pre verziu 2.383.0, zaznamenal dva vynútené prepočty 18 488 ms a 19 578 ms. Po indexovaní namerali tri sériové focused runy na architektúru 102,332–109,429 ms na Win32 a 116,990–133,995 ms na Win64, zhruba 170 až 180-krát rýchlejšie na Win32; žiadna Win64 baseline pred opravou sa nezaznamenala, takže sa nehlási žiadne Win64 zrýchlenie. Tie isté runy prešli existujúcou bránou, ktorá drží read-only audit prepočtu do 1,35-násobku vynúteného prepočtu. Absolútne čísla závisia od stroja a jeho záťaže, takže workload si pred citovaním reprodukujte na vlastnom hardvéri

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                     // reťazec 49 999 článkov v stĺpci A
      Sh.Cells[I, 1].Formula := '=A' + IntToStr(I - 1) + '+1';
    for I := 1 to 50000 do                     // 50 000 dependentov v stĺpci B
      Sh.Cells[I, 2].Formula := '=A' + IntToStr(I) + '*2';

    Watch := TStopwatch.StartNew;
    Failed := Wb.Recalculate;                  // prvé volanie stavia graf
    Watch.Stop;
    Writeln(Format('%d formulas not evaluated, %.1f ms',
      [Failed, Watch.Elapsed.TotalMilliseconds]));
  finally
    Wb.Free;
  end;
end;

Kde output index prestáva pomáhať?

Tree prunuje len po riadkoch a to zanecháva niekoľko úprimných limitov, ktoré stoja za poznanie skôr, než okolo neho navrhnete veľmi veľký model

• Zásahy vedľa v stĺpcoch sa stále platia na listoch: 2 626 formul napĺňajúcich A100:Z200 všetkých dosahuje riadok 100, takže referencia na AA100:AA200 každú z nich otestuje, než ju odmietne
• Široké referencie ako whole-column rangey reálne majú mnoho precedents; index odstraňuje plytvané checky, nie reálne hrany, a stavanie týchto hrán zostáva proporcionálne ich počtu
• Pri referenciach cez viac hárkov uložené maximum ignoruje hárok, takže formuly na medziľahlých hárkoch s hlbokými výstupmi dosiahnu na leaf test; výsledky zostávajú správne, len pruning je slabší
• Tree stojí štyri integer na formula node, zhruba 1,6 MB pre 100 000 nodov, a každé AddNode ho invaliduje, takže zmeny topológie platia plné O(n log n) pretriedenie plus O(n) stavanie stromu pri ďalšom stavani hrán

Ten istý kvadratický tvar pri klone report-band mien

Verzia 2.383.2 opravila súrodenecký problém v TXLSXDefinedNames.UniqueCloneName: každý skopírovaný defined name reštartoval svoje hľadanie suffixu na _2, takže opakované kópie report-bandov rástli kvadraticky v name lookupoch. Scoped name index si teraz drží suffix hint na base meno a scope a znova skontroluje posledného vráteného kandidáta, pretože ho volajúci nemusí reálne pridať; zmazanie, premenovanie alebo rescope mena invaliduje index, čo obnoví pomenovanie prvej voľnej. V regression suite potrebuje 1 024 sekvenčných klonov 5 088 candidate lookupov a štyri sa striedajúce base mená 5 039, kým minima report benchmarku klesli zo zhruba 240 ms na 18–20 ms. Timing brána report-bandov sama o sebe nie je stále stabilná — tri z šiestich runov prekročili jej pomer 1,05 v prvom pokuse po oprave — a performance history necháva tie zlyhania v zázname namiesto ladenia prahu, kým neprejde

Ak vaša aplikácia v Delphi alebo C++Builder generuje alebo prepočítava veľké Excel workbooke, HotXLS Excel component pre Delphi a C++Builder dodáva tento indexovaný graf závislostí v prepočtovom engine pre obe svoje triedy workbookov, classic aj XLSX