Graf závislostí HotXLS: indexování výstupů maticových vzorců

HotXLS 2.383.1, nativní Excel knihovna pro Delphi a C++Builder, staví závislostní hrany vzorců přes index výstupních intervalů: uzly vzorců zůstávají setříděné podle ukotvené buňky a segmentový strom držící největší výstupní řádek (OutRow2) každého podstromu nechá TXLSDepGraph.BuildEdges přeskočit celé bloky vzorců, které na odkazovaný range nemohou dosáhnout. Na sešitu Win32 se zhruba 100 000 vzorci klesl vynucený přepočet z 18,488 sekundy na 102–109 milisekund

Nikdo neprofiluje graf závislostí, dokud batch job, co dával za sekundu, nezačne brát dvacet. Graf se staví znovu pokaždé, když se změní topologie vzorců — první Recalculate po načtení nebo vygenerování sešitu, nebo jakýkoli průchod poté, co byl graf zneplatněn — a v trace před opravou bral už tenhle první průchod sám 16 074 ms. Vyhodnocování nikdy problém nebylo; problémem bylo rozhodnout, kdo na kom závisí

Proč trval přepočet 100 000 vzorců 18 sekund?

Starý tvůrce hran byl kvadratický v počtu vzorců na listu. Pro každý závislostní range BuildEdges binary searchem našel window kandidátních uzlů a pak každý otestoval přes RangeIntersectsOutput, a tenhle window začínal na samotném vršku odkazovaného listu. Klíče uzlů pocházejí z XLSDepMakeKey, který zabalí index listu od bitu 34 výš, řádek do bitů 14–33 a sloupec do bitů 0–13, takže dolní mez (Sheet1, 0, 0) znamenala „každý vzorec od řádku 1 dolů až na spodek odkazovaného range“

// Před 2.383.1 - TXLSDepGraph.BuildEdges, pro závislostní range r uzlu d
LowerKey := XLSDepMakeKey(FRanges[r].Sheet1, 0, 0);   // vršek listu
UpperKey := XLSDepMakeKey(FRanges[r].Sheet2, FRanges[r].Row2, 16383);
// ...dvě binary searches nad FNodeOrder dají window [i, Lo)...
while i < Lo do
begin
  NodeIndex := FNodeOrder[i];
  if RangeIntersectsOutput(FRanges[r], FNodes[NodeIndex]) then
  begin
    // hard edge nebo LookupScan edge, deduplikované přes EdgeStamp / ScanStamp
  end;
  Inc(i);
end;

Performance fixture, která to odhalila, je obyčejný kaskádový model: A2:A50000 přičítá jedničku buňce nad sebou a B1:B50000 zdvojnásobuje souseda ve sloupci A. Odkaz na řádek r tak zatáhl obdélníkovým testem zhruba 2r kandidátů, takže jediná stavba grafu provedla řádově pět miliard testů průniku — odhad na papíře, ale se 18,5 sekundy na hodinkách to sedí. Každý test řekl „ne“ kromě jednoho dvou

Proč nemůže tvůrce hran začít hledat až na odkazovaném řádku?

Protože maticový vzorec ukotvený nad range může vlastnit buňky uvnitř něj. Každý TXLSDepNode popisuje výstupní obdélník od své kotvy (Row, Col) po (OutRow2, OutCol2) a CSE maticový vzorec dostává jeden uzel pro celý svůj obdélník, jak vysvětluje článek o inkrementálním přepočtu a grafu závislostí. Kořen ukotvený na A1, který plní A1:A10, musí i tak dostat hranu od vzorce, který čte jen A5; začněte binary search na řádku 5 a tahle hrana potichu zmizí, což znamená zastaralou cachovanou hodnotu v odeslaném reportu místo pomalého. Dotaz je doopravdy oboustranný — kotva na Row2 nebo před ním, výstup sahající aspoň na Row1 — a jediné řazení nedokáže odpovědět na obě poloviny. Vícebuňkové výsledky se objevují i v moderních sešitech a článek o spill vzorcích dynamických polí rozebírá, jak se v HotXLS chovají spill range

Segmentový strom maximálních výstupních řádků

HotXLS nechává řazení podle kotvy pro horní mez a přidává augmentovaný segmentový strom pro dolní mez. BuildNodeIndex setřídí FNodeOrder podle klíče uzlu jako dřív a pak BuildMaxOutRowTree naplní FNodeMaxOutRow2 (alokované na čtyři položky na uzel) největším OutRow2 nalezeným pod každým podstromem. QueryNodeTree sestupuje jen uvnitř key window a opustí každý podstrom, jehož maximální výstupní řádek leží nad FRanges[r].Row1, protože žádný vzorec v něm nemůže na odkazované řádky dosáhnout. Listy, které přežijou, dál prochází plným testem RangeIntersectsOutput, takže rozsahy listů a sloupce se kontrolují přesně jako dřív

// TXLSDepGraph.BuildNodeIndex / BuildEdges od 2.383.1 (lehce zhuštěné)
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 key window, nebo žádný výstup v tomto podstromu nedosáhne 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
      // beze změny: potlačení přes EdgeStamp / ScanStamp, AddDependent / AddScanDependent
    end;
    Exit;
  end;
  Split := (ALeft + ARight) shr 1;
  QueryNodeTree(ATreeIndex * 2, ALeft, Split, ALower, AUpper);           // nejdřív levý podstrom
  QueryNodeTree(ATreeIndex * 2 + 1, Split + 1, ARight, ALower, AUpper);  // drží původní pořadí
end;

Rekurse nejdřív levý, pak pravý není stylistická volba. Přeživší listy se navštíví přesně v pořadí, jaké měla stará smyčka while, takže pole Dependents a Precedents se plní ve stejném sledu a topologické pořadí zůstává deterministické. Totéž platí pro oba druhy hran: hard edge zapsaná dřív dál potlačí pozdější LookupScan hranu pro tentýž pár, zatímco scan edge zapsaná před hard hranou si udrží své místo — tenhle rozdíl brání lookup range produkovat falešné kruhové reference. Na referenci cena klesne z velikosti window na O((k + 1) log n), kde k je počet vzorců, jejichž výstup doopravdy dosáhne odkazovaných řádků

Co index výstupů garantuje a jak se to ověřuje?

TXLSDepGraph produkuje stejné hrany ve stejném pořadí jako dřív a nová vlastnost EdgeCandidateChecks počítá, kolik výstupních obdélníků poslední stavba doopravdy otestovala, takže tvrzení je měřitelné, ne rétorické. Regresní test EdgeBuildDeepChainsCheckOneCandidatePerDependency postaví řetězy bodových referencí o 1 024 a 100 000 uzlech, vložené v opačném pořadí, aby vynutilo prostorové řazení, a assertuje přesně N − 1 testů — pro dlouhý řetěz 99 999 — plus očekávané precedent, dependent a topologické pořadí pro každý uzel. Doprovodné testy pokrývají kořeny matic vkládané neuspořádaně napříč rozsahy listů, duplicitní hard a lookup-scan reference (10 testů, s pravidly potlačení výše) a přestavbu po AddNode, které smaže sort flag, takže další BuildEdges nebo NodeIndexOf strom přestaví a counter resetuje místo hromadění

Změřené výsledky: z 18,5 sekundy na zhruba 0,1 sekundy

Trace před opravou, uchovaný v performance baseline projektu pro verzi 2.383.0, zaznamenal dva vynucené přepočty, 18 488 ms a 19 578 ms. Po zavedení indexu změřily tři sériové focused runy na architekturu 102,332–109,429 ms na Win32 a 116,990–133,995 ms na Win64, zhruba 170 až 180krát rychleji na Win32; žádný pre-fix Win64 baseline se nezaznamenal, takže se žádné zrychlení Win64 netvrdí. Tytéž runy prošly stávající branou, která drží audit přepočtu jen pro čtení do 1,35násobku vynuceného přepočtu. Absolutní čísla závisí na stroji a jeho zátěži, takže si workload na vlastním hardwaru reprodukujte, než je budete citovat

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                     // řetěz o 49 999 článcích ve sloupci A
      Sh.Cells[I, 1].Formula := '=A' + IntToStr(I - 1) + '+1';
    for I := 1 to 50000 do                     // 50 000 závislých ve sloupci B
      Sh.Cells[I, 2].Formula := '=A' + IntToStr(I) + '*2';

    Watch := TStopwatch.StartNew;
    Failed := Wb.Recalculate;                  // první volání staví graf
    Watch.Stop;
    Writeln(Format('%d formulas not evaluated, %.1f ms',
      [Failed, Watch.Elapsed.TotalMilliseconds]));
  finally
    Wb.Free;
  end;
end;

Kde index výstupů přestává pomáhat?

Strom prořezává jen po řádcích a to zanechává pár poctivých mezí, které stojí za to znát, než okolo něj navrhnete velmi velký model

• Netrefy ve sloupcích se pořád platí na listech stromu: 2 626 vzorců plnících A100:Z200 všechny dosahují řádku 100, takže reference na AA100:AA200 každý z nich otestuje, než ho odmítne
• Široké reference jako range přes celé sloupce doopravdy mají mnoho precedentů; index odstraňuje plýtvavé testy, ne reálné hrany, a stavba těch hran je dál úměrná jejich počtu
• U referencí přesahujících více listů ukládané maximum list ignoruje, takže vzorce na mezilehlých listech s hlubokými výstupy dosáhnou testu listů; výsledky zůstávají správné, jen prořezávání je slabší
• Strom stojí čtyři integery na uzel vzorce, zhruba 1,6 MB pro 100 000 uzlů, a jakékoli AddNode ho zneplatní, takže změny topologie platí plné přetřídění O(n log n) plus stavbu stromu O(n) při příští stavbě hran

Tentýž kvadratický tvar v klonování názvů report bandů

Verze 2.383.2 opravila sourozeněcký problém v TXLSXDefinedNames.UniqueCloneName: každý kopírovaný defined name restartoval hledání přípony na _2, takže opakované kopie report bandů rostly kvadraticky ve vyhledáváních názvů. Index scoped názvů si teď drží suffix hint per základní název a per scope a znovu zkontroluje posledního vráceného kandidáta, protože ho volající nemusí doopravdy přidat; smazání, přejmenování nebo přesunutí názvu do jiného scope index zneplatní, čímž se obnoví pojmenování první dostupné. V regresní sadě potřebuje 1 024 sekvenčních klonů 5 088 vyhledání kandidátů a čtyři střídavé základní názvy 5 039, zatímco minima report benchmarku klesla ze zhruba 240 ms na 18–20 ms. Časovací brána report bandů sama pořád není stabilní — tři ze šesti runů v prvním pokusu po opravě překročily její poměr 1.05 — a performance historie tyhle faily nechává v záznamu místo ladění prahu, dokud neprojde

Pokud vaše aplikace v Delphi nebo C++Builderu generuje nebo přepočítává velké Excel sešity, Excel komponenta HotXLS pro Delphi a C++Builder dodává tenhle indexovaný graf závislostí v přepočetním engine pro obě své třídy sešitů, classic i XLSX