Graf de dependențe HotXLS: indexarea ieșirilor de tablou

HotXLS 2.383.1, biblioteca Excel nativă pentru Delphi și C++Builder, construiește muchiile de dependență ale formulelor printr-un index de intervale de ieșire: nodurile de formule rămân sortate după celula de ancorare, iar un segment tree care ține cel mai mare rând de ieșire (OutRow2) al fiecărui subarbore lasă TXLSDepGraph.BuildEdges să sară blocuri întregi de formule care nu pot ajunge la un interval referențiat. Pe un registru de lucru Win32 cu circa 100.000 de formule, recalcularea forțată a căzut de la 18,488 de secunde la 102-109 de milisecunde

Nimeni nu face profiling grafului de dependențe până când un job de batch care dura o secundă nu începe să dureze douăzeci. Graful este reconstruit ori de câte ori se schimbă topologia formulelor — primul Recalculate după încărcarea sau generarea unui registru de lucru, sau orice trecere după ce graful a fost invalidat — și în trasarea de dinainte de reparare doar trecerea aceea întâi a durat 16.074 ms. Evaluarea nu a fost niciodată problema; problema a fost deciderea cine depinde de cine

De ce dura 18 secunde recalcularea a 100.000 de formule?

Bătrânul constructor de muchii era pătratic în numărul de formule de pe o foaie. Pentru fiecare interval de dependență, BuildEdges căuta binar o fereastră de noduri candidate și apoi le testa pe fiecare cu RangeIntersectsOutput, iar fereastra aceea începea chiar din vârful foii referențiate. Cheile nodurilor vin din XLSDepMakeKey, care împachetează indexul foii de la bitul 34 în sus, rândul în biții 14-33 și coloana în biții 0-13, deci limita inferioară (Sheet1, 0, 0) însemna „toate formulele de la rândul 1 până jos, la baza intervalului referențiat"

// Înainte de 2.383.1 - TXLSDepGraph.BuildEdges, pentru intervalul de dependență r al nodului d
LowerKey := XLSDepMakeKey(FRanges[r].Sheet1, 0, 0);   // vârful foii
UpperKey := XLSDepMakeKey(FRanges[r].Sheet2, FRanges[r].Row2, 16383);
// ...două căutări binare peste FNodeOrder produc fereastra [i, Lo)...
while i < Lo do
begin
  NodeIndex := FNodeOrder[i];
  if RangeIntersectsOutput(FRanges[r], FNodes[NodeIndex]) then
  begin
    // muchie tare sau muchie LookupScan, dedublate prin EdgeStamp / ScanStamp
  end;
  Inc(i);
end;

Fixture-ul de performanță care a expus asta este un model de cascadă obișnuit: A2:A50000 adaugă fiecare câte unu celulei de deasupra, iar B1:B50000 dublează fiecare vecinul din coloana A. O referință la rândul r trăgea prin urmare cam 2r candidați prin testul de dreptunghi, deci o singură construire de grafic făcea în ordinea a cinci miliarde de verificări de intersecție — o estimare „pe plic", dar se potrivește cu cele 18,5 secunde de pe ceas. Fiecare verificare spunea „nu", mai puțin una sau două

De ce nu poate constructorul de muchii începe căutarea la rândul referențiat?

Pentru că o formulă de tablou ancorată deasupra unui interval poate deține celule în interiorul lui. Fiecare TXLSDepNode descrie un dreptunghi de ieșire de la ancora lui (Row, Col) până la (OutRow2, OutCol2), iar o formulă CSE de tablou primește un singur nod pentru întregul ei dreptunghi, așa cum explică articolul despre recalcularea incrementală și graful de dependențe. O rădăcină ancorată la A1 care umple A1:A10 trebuie totuși să primească o muchie de la o formulă care citește doar A5; începeți căutarea binară la rândul 5 și muchia aceea dispare în tăcere, ceea ce înseamnă o valoare cachetă învechită într-un raport livrat în loc de unul lent. Interogarea este de fapt bilaterală — ancoră la sau înainte de Row2, ieșire care ajunge cel puțin la Row1 — și o singură ordine de sortare nu poate răspunde ambelor jumătăți. Rezultatele multicelulare apar și în registrele de lucru moderne, iar articolul despre formulele spill de tablou dinamic acoperă cum se comportă intervalele spilled în HotXLS

Un segment tree al rândurilor de ieșire maxime

HotXLS păstrează sortarea după ancoră pentru limita superioară și adaugă un segment tree augmentat pentru limita inferioară. BuildNodeIndex sortează FNodeOrder după cheia nodului ca înainte, apoi BuildMaxOutRowTree umple FNodeMaxOutRow2 (alocat la patru intrări per nod) cu cel mai mare OutRow2 găsit sub fiecare subarbore. QueryNodeTree coboară doar în interiorul ferestrei de chei și abandonează orice subarbore al cărui rând de ieșire maxim stă peste FRanges[r].Row1, pentru că nicio formulă din el nu poate ajunge la rândurile referențiate. Frunzele care supraviețuiesc trec tot prin testul complet RangeIntersectsOutput, deci întinderile de foi și coloanele sunt verificate exact ca înainte

// TXLSDepGraph.BuildNodeIndex / BuildEdges din 2.383.1 (ușor condensat)
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
  // în afara ferestrei de chei, sau nicio ieșire din acest subarbore nu ajunge la 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
      // neschimbat: suprimare EdgeStamp / ScanStamp, AddDependent / AddScanDependent
    end;
    Exit;
  end;
  Split := (ALeft + ARight) shr 1;
  QueryNodeTree(ATreeIndex * 2, ALeft, Split, ALower, AUpper);           // mai întâi subarborele stâng
  QueryNodeTree(ATreeIndex * 2 + 1, Split + 1, ARight, ALower, AUpper);  // păstrează vechea ordine
end;

Recursivitatea stânga-înainte-de-dreapta nu este o alegere de stil. Frunzele care supraviețuiesc sunt vizitate exact în ordinea în care le vizita vechea buclă while, astfel încât tablourile Dependents și Precedents sunt umplute în aceeași secvență, iar ordinea topologică rămâne deterministă. La fel stau lucrurile pentru cele două feluri de muchii: o muchie tare înregistrată prima mai suprimă totuși o muchie LookupScan ulterioară pentru aceeași pereche, în timp ce o muchie de scanare înregistrată înaintea uneia tari își păstrează locul — distincția care împiedică intervalele de lookup să producă referințe circulare false. Per referință, costul scade de la mărimea ferestrei la O((k + 1) log n), unde k este numărul de formule a căror ieșire ajunge efectiv la rândurile referențiate

Ce garantează indexul de ieșire și cum este verificat?

TXLSDepGraph produce aceleași muchii în aceeași ordine ca înainte, iar noua proprietate EdgeCandidateChecks numără câte dreptunghiuri de ieșire a testat efectiv cea mai recentă construire, astfel încât afirmația este măsurabilă, nu retorică. Testul de regresie EdgeBuildDeepChainsCheckOneCandidatePerDependency construiește lanțuri de referințe-punct de 1.024 și 100.000 de noduri, inserate în ordine inversă ca să forțeze sortarea spațială, și afirmă exact N − 1 verificări — 99.999 pentru lanțul lung — plus ordinea așteptată de precedent, dependent și topologică pentru fiecare nod. Testele însoțitoare acoperă rădăcini de tablou inserate dezordonat peste întinderi de foi, referințe duplicate tari și de tip lookup-scan (10 verificări, cu regulile de suprimare de mai sus), și o reconstruire după AddNode, care curăță flag-ul de sortare, astfel încât următorul BuildEdges sau NodeIndexOf reconstruiește arborele și resetează contorul în loc să îl acumuleze

Rezultate măsurate: de la 18,5 secunde la circa 0,1 secunde

Trasarea Win32 de dinainte de reparare, păstrată în baseline-ul de performanță al proiectului pentru versiunea 2.383.0, a înregistrat două recalculări forțate de 18.488 ms și 19.578 ms. După indexare, trei rulări serial focusate per arhitectură au măsurat 102,332-109,429 ms pe Win32 și 116,990-133,995 ms pe Win64, cam de 170 până la 180 de ori mai repede pe Win32; nu a fost înregistrat niciun baseline Win64 de dinainte de reparare, deci nu se revendică niciun câștig pe Win64. Aceleași rulări au trecut poarta existentă care ține un audit de recalculare doar în citire în limita a 1,35 ori o recalculare forțată. Numerele absolute depind de mașină și de încărcarea ei, deci reproduceți sarcina pe propriul hardware înainte să le citați

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                     // lanț de 49.999 de verigi în coloana A
      Sh.Cells[I, 1].Formula := '=A' + IntToStr(I - 1) + '+1';
    for I := 1 to 50000 do                     // 50.000 de dependenți în coloana B
      Sh.Cells[I, 2].Formula := '=A' + IntToStr(I) + '*2';

    Watch := TStopwatch.StartNew;
    Failed := Wb.Recalculate;                  // primul apel construiește graful
    Watch.Stop;
    Writeln(Format('%d formulas not evaluated, %.1f ms',
      [Failed, Watch.Elapsed.TotalMilliseconds]));
  finally
    Wb.Free;
  end;
end;

Unde încetează indexul de ieșire să mai ajute?

Arborele tăie doar pe rânduri, iar asta lasă câteva limite oneste care merită știute înainte să construiți un model foarte mare pe el

• Ratăririle de coloană se plătesc tot la frunze: cele 2.626 de formule care umplu A100:Z200 ajung toate la rândul 100, deci o referință la AA100:AA200 le testează pe fiecare înainte să le respingă
• Referințele late, precum intervalele pe coloană întreagă, au efectiv mulți precedenți; indexul elimină verificări risipite, nu muchii reale, iar construirea muchiilor acelea rămâne proporțională cu numărul lor
• Pentru referințele care se întind pe mai multe foi, maximul stocat ignoră foaia, deci formulele de pe foile intermediare cu ieșiri adânci ajung la testul de frunză; rezultatele rămân corecte, doar tăierea este mai slabă
• Arborele costă patru întregi per nod de formulă, circa 1,6 MB pentru 100.000 de noduri, iar orice AddNode îl invalidează, astfel încât schimbările de topologie plătesc o re-sortare completă O(n log n) plus o construire de arbore O(n) la următoarea construire de muchii

Aceeași formă pătratică în clonarea numelor de benzi de raport

Versiunea 2.383.2 a reparat o problemă soră în TXLSXDefinedNames.UniqueCloneName: fiecare nume definit copiat își repornia căutarea de sufix la _2, deci copiile repetate de benzi de raport creșteau pătratic în căutări de nume. Indexul de nume cu scop păstrează acum o indică de sufix per nume de bază și per scop și reverifică ultimul candidat întors, pentru că apelantul s-ar putea să nu îl adauge efectiv; ștergerea, redenumirea sau rescoparea unui nume invalidează indexul, ceea ce restaurează denumirea prim-disponibil. În suita de regresie, 1.024 de clone secvențiale au nevoie de 5.088 de căutări de candidați, iar patru nume de bază alternate au nevoie de 5.039, în timp ce minimele benchmark-ului de raport au scăzut de la circa 240 ms la 18-20 ms. Poarta de cronometraj a benzilor de raport în sine nu este totuși încă stabilă — trei din șase rulări au depășit raportul ei de 1,05 în prima încercare de după reparare — iar istoricul de performanță ține acele eșecuri înregistrate în loc să calibreze pragul până trece

Dacă aplicația dvs. Delphi sau C++Builder generează sau recalculează registre de lucru Excel mari, componenta Excel HotXLS pentru Delphi și C++Builder livrează acest graf de dependențe indexat în motorul de recalculare pentru ambele clase de registre de lucru, clasic și XLSX