HotXLS graf zavisnosti: indeksiranje izlaza array formula

HotXLS 2.383.1, nativna Excel biblioteka za Delphi i C++Builder, gradi grane zavisnosti formula kroz indeks izlaznih intervala: čvorovi formula ostaju sortirani po ćeliji sidra, a segmentno stablo koje drži najveći izlazni red (OutRow2) svakog podstabla dozvoljava TXLSDepGraph.BuildEdges-u da preskoči cele blokove formula koje ne mogu da dosegnu referencirani opseg. Na Win32 workbook-u sa oko 100.000 formula, forsirano preračunavanje palo je sa 18,488 sekundi na 102–109 milisekundi

Niko ne profilše graf zavisnosti dok batch posao koji je oduvek trajao sekundu ne počne da traje dvadeset. Graf se gradi iznova kad god se promeni topologija formula — prvi Recalculate posle učitavanja ili generisanja workbook-a, ili bilo koji prolaz posle što je graf poništen — i u traci pre popravke taj je prvi prolaz sam zauzeo 16.074 ms. Evaluacija nikada nije bila problem; odlučiti ko od koga zavisi jeste

Zašto je preračunavanje 100.000 formula trajalo 18 sekundi?

Stari graditelj grana bio je kvadratan po broju formula na listu. Za svaki opseg zavisnosti, BuildEdges je binarno pretražio prozor kandidata pa testirao svaki sa RangeIntersectsOutput, i taj je prozor počinjao sasvim na vrhu referenciranog lista. Ključevi čvorova dolaze iz XLSDepMakeKey, koji pakuje indeks lista od bita 34 naviše, red u bitove 14–33 i kolonu u bitove 0–13, pa je donja granica (Sheet1, 0, 0) značila „svaku formulu od reda 1 do dna referenciranog opsega“

// Pre 2.383.1 - TXLSDepGraph.BuildEdges, za opseg zavisnosti r čvora d
LowerKey := XLSDepMakeKey(FRanges[r].Sheet1, 0, 0);   // vrh lista
UpperKey := XLSDepMakeKey(FRanges[r].Sheet2, FRanges[r].Row2, 16383);
// ...dve binarne pretrage nad FNodeOrder daju prozor [i, Lo)...
while i < Lo do
begin
  NodeIndex := FNodeOrder[i];
  if RangeIntersectsOutput(FRanges[r], FNodes[NodeIndex]) then
  begin
    // hard grana ili LookupScan grana, deduplicirano kroz EdgeStamp / ScanStamp
  end;
  Inc(i);
end;

Performans fičer koji je ovo razotkrio je običan kaskadni model: A2:A50000 svaki dodaje jedan ćeliji iznad, a B1:B50000 svaki udvostručava suseda u koloni A. Referenca na red r je zato vukla oko 2r kandidata kroz pravougaoni test, pa je jedan build grafa obavljao reda pet milijardi provera preseka — gruba procena na papiru, ali se poklapa sa 18,5 sekundi na satu. Svaka je provera rekla „ne“ osim jedne-dve

Zašto graditelj grana ne može da počne pretragu od referenciranog reda?

Jer array formula zakačena iznad opsega može da poseduje ćelije unutar njega. Svaki TXLSDepNode opisuje izlazni pravougaonik od svog sidra (Row, Col) do (OutRow2, OutCol2), a CSE array formula dobija jedan čvor za ceo svoj pravougaonik, kako objašnjava članak o inkrementalnom preračunavanju i grafu zavisnosti. Koren zakačen na A1 koji puni A1:A10 mora i dalje da primi granu od formule koja čita samo A5; počnite binarnu pretragu od reda 5 pa ta grana tiho nestane, što znači zastarelu keširanu vrednost u isporučenom izveštaju umesto sporog. Upit je zapravo dvosmeran — sidro na ili pre Row2, izlaz koji dostiže bar Row1 — i jedan redosled sortiranja ne može da odgovori na obe polovine. Višećelijski rezultati javljaju se i u modernim workbook-ovima, a članak o dynamic array spill formulama pokriva kako se prosuti opsezi ponašaju u HotXLS-u

Segmentno stablo maksimalnih izlaznih redova

HotXLS zadržava sidreno sortiranje za gornju granicu i dodaje prošireno segmentno stablo za donju. BuildNodeIndex sortira FNodeOrder po ključu čvora kao i pre, pa BuildMaxOutRowTree puni FNodeMaxOutRow2 (alokacija od četiri unosa po čvoru) najvećim OutRow2 nađenim pod svakim podstablom. QueryNodeTree silazi samo unutar prozora ključa i odustaje od svakog podstabla čiji maksimalni izlazni red leži iznad FRanges[r].Row1, jer nijedna formula u njemu ne može da dosegne referencirane redove. Listovi koji prežive i dalje prolaze puni RangeIntersectsOutput test, pa se rasponi listova i kolone proveravaju baš kao i pre

// TXLSDepGraph.BuildNodeIndex / BuildEdges od 2.383.1 (blago sažeto)
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
  // van prozora ključa, ili nijedan izlaz u ovom podstablu ne doseže 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
      // nepromenjeno: EdgeStamp / ScanStamp potiskivanje, AddDependent / AddScanDependent
    end;
    Exit;
  end;
  Split := (ALeft + ARight) shr 1;
  QueryNodeTree(ATreeIndex * 2, ALeft, Split, ALower, AUpper);           // prvo levo podstablo
  QueryNodeTree(ATreeIndex * 2 + 1, Split + 1, ARight, ALower, AUpper);  // čuva stari redosled
end;

Rekurzija levo-pre-desno nije stilska odluka. Preživeli listovi posećuju se tačno redom kojim ih je posećivala stara while petlja, pa se nizovi Dependents i Precedents pune istim redosledom i topološki redosled ostaje determinističan. Isto važi za dve vrste grana: hard grana zabeležena prva i dalje potiskuje kasniju LookupScan granu za isti par, dok scan grana zabeležena pre hard zadržava svoje mesto — razlika koja sprečava lookup opsege da proizvode lažne kružne reference. Po referenci, cena pada sa veličine prozora na O((k + 1) log n), gde je k broj formula čiji izlaz stvarno doseže referencirane redove

Šta indeks izlaza garantuje i kako se to proverava?

TXLSDepGraph proizvodi iste grane istim redosledom kao i pre, a novo svojstvo EdgeCandidateChecks broji koliko je izlaznih pravougaonika poslednji build stvarno testirao, pa je tvrdnja merljiva a ne retorička. Regresioni test EdgeBuildDeepChainsCheckOneCandidatePerDependency gradi lance referenci na tačku od 1.024 i 100.000 čvorova, ubačenih obrnutim redosledom da nametne prostorno sortiranje, i tvrdi tačno N − 1 proveru — 99.999 za dugi lanac — plus očekivani precedent, dependent i topološki redosled za svaki čvor. Prateći testovi pokrivaju korene nizova ubačene van reda preko raspona listova, duplikate hard i lookup-scan referenci (10 provera, sa pravilima potiskivanja odozgo), i rebuild posle AddNode, koji briše zastavicu sortiranja pa sledeći BuildEdges ili NodeIndexOf gradi stablo iznova i resetuje brojač umesto da ga gomila

Izmereni rezultati: sa 18,5 sekundi na oko 0,1 sekunde

Win32 traka pre popravke, sačuvana u performansnom baseline-u projekta za verziju 2.383.0, zabeležila je dva forsirana preračunavanja od 18.488 ms i 19.578 ms. Posle indeksiranja, tri serijska fokusirana pokretanja po arhitekturi izmerila su 102.332–109.429 ms na Win32 i 116.990–133.995 ms na Win64, otprilike 170 do 180 puta brže na Win32; pre-popravni Win64 baseline nije zabeležen, pa se Win64 ubrzanje ne tvrdi. Ista su pokretanja prošla postojeću kapiju koja drži audit preračunavanja samo za čitanje unutar 1,35 puta forsiranog preračunavanja. Apsolutni brojevi zavise od mašine i njenog opterećenja, pa reprodukujite radno opterećenje na sopstvenom hardveru pre nego što ih citirate

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                     // lanac od 49.999 karika u koloni A
      Sh.Cells[I, 1].Formula := '=A' + IntToStr(I - 1) + '+1';
    for I := 1 to 50000 do                     // 50.000 zavisnih u koloni B
      Sh.Cells[I, 2].Formula := '=A' + IntToStr(I) + '*2';

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

Gde indeks izlaza prestaje da pomaže?

Stablo rezidbu vrši samo po redovima, i to ostavlja par iskrenih ograničenja vrednih poznavanja pre nego što oko njega dizajnirate vrlo velik model

• Promašaji po koloni i dalje se plaćaju na listovima: 2.626 formula koje pune A100:Z200 sve dosežu red 100, pa referenca na AA100:AA200 testira svaku od njih pre odbacivanja
• Široke reference poput opsega cele kolone zaista imaju mnogo precedenata; indeks uklanja izgubljene provere, ne prave grane, i gradnja tih grana i dalje je proporcionalna njihovom broju
• Za reference koje prelaze više listova, sačuvani maksimum ignoriše list, pa formule na posrednim listovima sa dubokim izlazima dolaze do testa lista; rezultati ostaju ispravni, samo je rezidba slabija
• Stablo košta četiri cela broja po čvoru formule, oko 1,6 MB za 100.000 čvorova, i bilo koji AddNode ga poništava, pa promene topologije plaćaju puno O(n log n) ponovno sortiranje plus O(n) gradnju stabla pri sledećoj gradnji grana

Isti kvadratni oblik u kloniranju imena report-band

Verzija 2.383.2 popravila je srodan problem u TXLSXDefinedNames.UniqueCloneName: svako kopirano definisano ime ponovo je počinjalo pretragu sufiksa od _2, pa su ponovljene kopije report-band-a rasle kvadratno u pretragama imena. Indeks opseženih imena sada čuva hint sufiksa po baznom imenu i po opsegu i ponovo proverava poslednjeg vraćenog kandidata, jer pozivalac možda stvarno ne dodaje ime; brisanje, preimenovanje ili promena opsega imena poništava indeks, što vraća imenovanje prvim slobodnim. U regresionom suite-u, 1.024 uzastopna klona traži 5.088 pretraga kandidata, a četiri naizmenična bazna imena 5.039, dok su minimumi benchmark-a izveštaja pali sa otprilike 240 ms na 18–20 ms. Report-band vremenska kapija sama po sebi još nije stabilna — tri od šest pokretanja prešla su njen odnos 1,05 u prvom pokušaju posle popravke — i performansna istorija drži te neuspehe na zapisu umesto da šteluje prag dok ne prođe

Ako Vaša Delphi ili C++Builder aplikacija generiše ili preračunava velike Excel workbook-ove, HotXLS Excel komponenta za Delphi i C++Builder isporučuje ovaj indeksirani graf zavisnosti u motoru preračunavanja za obe svoje klase workbook-a, klasičnu i XLSX