HotXLS graf ovisnosti: indeksiranje izlaza array formula

HotXLS 2.383.1, izvorna Excel biblioteka za Delphi i C++Builder, gradi bridove ovisnosti formula kroz indeks izlaznih intervala: čvorovi formula ostaju sortirani po sidrenoj ćeliji, a segment stablo koje drži najveći izlazni redak (OutRow2) svakog podstabla pušta TXLSDepGraph.BuildEdges da preskoči cijele blokove formula koje ne mogu dosegnuti referencirani raspon. Na Win32 radnoj knjigi s otprilike 100.000 formula forsirano preračunavanje palo je sa 18.488 sekundi na 102–109 milisekundi

Nitko ne profilira graf ovisnosti dok batch posao koji je uzimao sekundu ne počne uzimati dvadeset. Graf se gradi iznova kad god se promijeni topologija formula — prvi Recalculate nakon učitavanja ili generiranja radne knjige, ili bilo koji prolaz nakon što je graf poništen — i u pre-fix traceu taj je prvi prolaz sam uzeo 16.074 ms. Evaluacija nikad nije bila problem; odlučivanje tko o kome ovisi jeste

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

Stari graditelj bridova bio je kvadratan u broju formula na listu. Za svaki raspon ovisnosti BuildEdges je binarno pretražio prozor kandidatskih čvorova i zatim svaki testirao s RangeIntersectsOutput, a taj je prozor počinjao na samom vrhu referenciranog lista. Ključevi čvorova dolaze iz XLSDepMakeKey, koji pakira indeks lista od bita 34 naviše, redak u bitove 14–33 i stupac u bitove 0–13, pa je donja granica (Sheet1, 0, 0) značila "svaku formulu od retka 1 do dna referenciranog raspona"

// Prije 2.383.1 - TXLSDepGraph.BuildEdges, za raspon ovisnosti r čvora d
LowerKey := XLSDepMakeKey(FRanges[r].Sheet1, 0, 0);   // vrh lista
UpperKey := XLSDepMakeKey(FRanges[r].Sheet2, FRanges[r].Row2, 16383);
// ...dvije binarne pretrage nad FNodeOrder daju prozor [i, Lo)...
while i < Lo do
begin
  NodeIndex := FNodeOrder[i];
  if RangeIntersectsOutput(FRanges[r], FNodes[NodeIndex]) then
  begin
    // tvrdi brid ili LookupScan brid, dedupliciran kroz EdgeStamp / ScanStamp
  end;
  Inc(i);
end;

Testni primjer koji je ovo izvukao je običan kaskadni model: A2:A50000 svaki dodaje jedan ćeliji iznad, a B1:B50000 svaki udvostručuje susjeda u stupcu A. Referenca na redak r zato je provlačila oko 2r kandidata kroz test pravokutnika, pa je jedna gradnja grafa napravila reda pet milijardi provjera presjeka — procjena "na papiru", ali slaže se s 18,5 sekundi na satu. Svaka je provjera rekla "ne" osim jedne ili dvije

Zašto graditelj bridova ne može početi pretragu na referenciranom retku?

Zato što formula polja sidrena iznad raspona može posjedovati ćelije unutar njega. Svaki TXLSDepNode opisuje izlazni pravokutnik od svog sidra (Row, Col) do (OutRow2, OutCol2), a CSE formula polja dobiva jedan čvor za cijeli svoj pravokutnik, kako to objašnjava članak o inkrementalnom preračunavanju i grafu ovisnosti. Korijen sidren na A1 koji puni A1:A10 mora i dalje primiti brid od formule koja čita samo A5; počnete li binarnu pretragu na retku 5, taj brid tiho nestaje, što znači zastarjelu keširanu vrijednost u isporučenom izvještaju umjesto sporog. Upit je zapravo dvosmjerni — sidro na ili prije Row2, izlaz koji doseže barem Row1 — i jedan sortirni redoslijed ne može odgovoriti na obje polovice. Višećelijski rezultati javljaju se i u modernim radnim knjigama, a članak o dynamic array spill formulama pokriva kako se proliveni rasponi ponašaju u HotXLS-u

Segment stablo maksimalnih izlaznih redaka

HotXLS zadržava sidreni sort za gornju granicu i dodaje augmentirano segment stablo za donju granicu. BuildNodeIndex sortira FNodeOrder po ključu čvora kao i prije, a zatim BuildMaxOutRowTree puni FNodeMaxOutRow2 (alociran na četiri unosa po čvoru) najvećim OutRow2 nađenim pod svakim podstablom. QueryNodeTree silazi samo unutar ključnog prozora i napušta svako podstablo čiji maksimalni izlazni redak leži iznad FRanges[r].Row1, jer nijedna formula u njemu ne može dosegnuti referencirane retke. Listovi koji prežive i dalje prolaze potpuni test RangeIntersectsOutput, pa se rasponi listova i stupci provjeravaju točno kao i prije

// 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
  // izvan ključnog prozora, 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
      // nepromijenjeno: EdgeStamp / ScanStamp suzbijanje, AddDependent / AddScanDependent
    end;
    Exit;
  end;
  Split := (ALeft + ARight) shr 1;
  QueryNodeTree(ATreeIndex * 2, ALeft, Split, ALower, AUpper);           // prvo lijevo podstablo
  QueryNodeTree(ATreeIndex * 2 + 1, Split + 1, ARight, ALower, AUpper);  // čuva stari redoslijed
end;

Rekurzija lijevo-prije-desno nije stilski izbor. Preživjeli listovi posjećuju se točno u redoslijedu kojim ih je posjećivala stara while petlja, pa se polja Dependents i Precedents pune u istom slijedu i topološki redoslijed ostaje determinističan. Isto vrijedi za dvije vrste bridova: tvrdi brid zabilježen prvi i dalje suzbija kasniji LookupScan brid za isti par, dok scan brid zabilježen prije tvrdog zadržava svoje mjesto — razlika koja lookup rasponima sprječava proizvodnju lažnih kružnih referenci. Po referenci trošak pada s veličine prozora na O((k + 1) log n), gdje je k broj formula čiji izlaz stvarno doseže referencirane retke

Što indeks izlaza garantira, i kako se provjerava?

TXLSDepGraph proizvodi iste bridove u istom redoslijedu kao i prije, a novo svojstvo EdgeCandidateChecks broji koliko je izlaznih pravokutnika zadnja gradnja stvarno testirala, pa je tvrdnja mjerljiva a ne retorička. Regresijski test EdgeBuildDeepChainsCheckOneCandidatePerDependency gradi lance točkastih referenci od 1.024 i 100.000 čvorova, ubačenih obrnutim redoslijedom da prisili prostorni sort, i tvrdi točno N − 1 provjeru — 99.999 za dugi lanac — plus očekivani precedent, dependent i topološki redoslijed za svaki čvor. Prateći testovi pokrivaju korijene polja ubačena izvan reda preko raspona listova, duplicirane tvrde i lookup-scan reference (10 provjera, sa suzbijajućim pravilima gore), i ponovnu gradnju nakon AddNode, koja briše sortirnu zastavicu pa sljedeći BuildEdges ili NodeIndexOf gradi stablo iznova i resetira brojač umjesto da ga akumulira

Izmjereno: sa 18,5 sekundi na oko 0,1 sekundu

Pre-fix Win32 trace, zadržan u performansnoj bazi projekta za verziju 2.383.0, zabilježio je dva forsirana preračunavanja od 18.488 ms i 19.578 ms. Nakon indeksiranja, tri serijalna fokusirana pokretanja po arhitekturi mjerila 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-fix Win64 baza nije zabilježena, pa se Win64 ubrzanje ne tvrdi. Isti su pokreti prošli postojeću kapiju koja audit preračunavanja samo za čitanje drži unutar 1,35 puta forsiranog preračunavanja. Apsolutni brojevi ovise o stroju i njegovom opterećenju, pa radno opterećenje reproducirajte na vlastitom hardveru prije citiranja

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 stupcu A
      Sh.Cells[I, 1].Formula := '=A' + IntToStr(I - 1) + '+1';
    for I := 1 to 50000 do                     // 50.000 dependenata u stupcu 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;

Gdje indeks izlaza prestaje pomoći?

Stablo orezuje samo po recima, i to ostavlja nekoliko poštenih granica vrijednih pozornosti prije nego model velikih razmjera dizajnirate oko njega

• Promašaji po stupcu i dalje se plaćaju na listovima: 2.626 formula koje pune A100:Z200 sve dosežu redak 100, pa referenca na AA100:AA200 svaku testira prije odbijanja
• Široke reference poput raspona cijelog stupca stvarno imaju mnogo precedenata; indeks uklanja uzaludne provjere, ne stvarne bridove, i gradnja tih bridova i dalje je proporcionalna njihovom broju
• Za reference koje prelaze preko više listova, pohranjeni maksimum ignorira list, pa formule na međulistovima s dubokim izlazima dosežu test listova; rezultati ostaju točni, samo je orezivanje slabije
• Stablo košta četiri cijela broja po čvoru formule, oko 1,6 MB za 100.000 čvorova, i bilo koji AddNode ga poništava, pa promjene topologije plaćaju potpuno O(n log n) preslagivanje plus O(n) gradnju stabla na sljedećoj gradnji bridova

Isti kvadratni oblik u kloniranju imena report bandova

Verzija 2.383.2 popravila je srodan problem u TXLSXDefinedNames.UniqueCloneName: svako kopirano definirano ime ponovno je pokretalo sufiksnu pretragu od _2, pa su ponovljene kopije report bandova rasle kvadratno u pretragama imena. Indeks scoped imena sada čuva sufiksni trag po baznom imenu i po opsegu te ponovno provjerava zadnji vraćeni kandidat, jer pozivatelj ga možda stvarno ne doda; brisanje, preimenovanje ili promjena opsega imena poništava indeks, što vraća imenovanje prvog slobodnog. U regresijskoj jedinici 1.024 uzastopna klona treba 5.088 kandidatskih pretraga, a četiri izmjenična bazna imena 5.039, dok su minimumi report benchmarka pali s otprilike 240 ms na 18–20 ms. Timing kapija report bandova i dalje nije stabilna — tri od šest pokretanja prešla su njen omjer 1,05 u prvom pokušaju nakon popravka — i performansna povijest te propuste drži zabilježene umjesto da štima prag dok ne prođe

Ako Vaša Delphi ili C++Builder aplikacija generira ili preračunava velike Excel radne knjige, HotXLS Excel komponenta za Delphi i C++Builder isporučuje ovaj indeksirani graf ovisnosti u preračunskom engineu obje svoje klase radnih knjiga, classic i XLSX