HotXLS afhængighedsgraf: array-formula-outputs indekseres

HotXLS 2.383.1, det native Excel-bibliotek til Delphi og C++Builder, bygger formelafhængighedskanter gennem et output-interval-indeks: formelnoder forbliver sorteret efter ankercelle, og et segment tree, der holder den største output-række (OutRow2) af hvert subtree, lader TXLSDepGraph.BuildEdges springe hele blokke af formler over, som ikke kan nå et refereret område. På en Win32-arbejdsbog med omkring 100.000 formler faldt tvungen genberegning fra 18.488 sekunder til 102–109 millisekunder

Ingen profilerer afhængighedsgrafen, før et batch-job, der plejede at tage ét sekund, begynder at tage tyve. Grafen genopbygges, når formeltopologien ændrer sig — den første Recalculate efter indlæsning eller generering af en arbejdsbog, eller ethvert gennemløb efter, at grafen er blevet invalideret — og i pre-fix-sporet tog det første gennemløb alene 16.074 ms. Evaluering var aldrig problemet; at afgøre, hvem der afhænger af hvem, var det

Hvorfor tog genberegning af 100.000 formler 18 sekunder?

Den gamle kant-bygger var kvadratisk i antallet af formler på et ark. For hvert afhængighedsområde binary-searchede BuildEdges et vindue af kandidatnoder og testede derefter hver enkelt med RangeIntersectsOutput, og det vindue startede helt i toppen af det refererede ark. Node-nøgler kommer fra XLSDepMakeKey, som pakker arkindeks fra bit 34 og op, rækken ind i bits 14–33 og kolonnen ind i bits 0–13, så nedre grænse (Sheet1, 0, 0) betød "enhver formel fra række 1 og ned til bunden af det refererede område"

// Før 2.383.1 - TXLSDepGraph.BuildEdges, for afhængighedsområde r af node d
LowerKey := XLSDepMakeKey(FRanges[r].Sheet1, 0, 0);   // toppen af arket
UpperKey := XLSDepMakeKey(FRanges[r].Sheet2, FRanges[r].Row2, 16383);
// ...to binary searches over FNodeOrder producerer vinduet [i, Lo)...
while i < Lo do
begin
  NodeIndex := FNodeOrder[i];
  if RangeIntersectsOutput(FRanges[r], FNodes[NodeIndex]) then
  begin
    // hård kant eller LookupScan-kant, deduplikeret gennem EdgeStamp / ScanStamp
  end;
  Inc(i);
end;

Performance-fixturen, der eksponerede dette, er en almindelig kaskadende model: A2:A50000 lægger én til cellen ovenover, og B1:B50000 fordobler hver naboen i kolonne A. En reference til række r trak derfor omkring 2r kandidater gennem rektangeltesten, så et enkelt graf-build udførte i størrelsesordenen fem milliarder skæringskontroller — et tommelfingerregnskab, men det stemmer med de 18,5 sekunder på uret. Hver kontrol svarede "nej" bortset fra én eller to

Hvorfor kan kant-byggeren ikke starte søgningen ved den refererede række?

Fordi en array-formula forankret over et område kan eje celler inde i det. Hver TXLSDepNode beskriver et output-rektangel fra sit anker (Row, Col) til (OutRow2, OutCol2), og en CSE array-formula får én node for hele sit rektangel, som artiklen om inkrementel genberegning og afhængighedsgrafen forklarer. En rod forankret i A1, der fylder A1:A10, skal stadig modtage en kant fra en formel, der kun læser A5; starter man binary search ved række 5, forsvinder den kant lydløst, hvilket betyder en forældet cached værdi i en leveret rapport i stedet for en langsom en. Forespørgslen er reelt tosidet — anker ved eller før Row2, output der når mindst Row1 — og én enkelt sorteringsrækkefølge kan ikke besvare begge halvdele. Multi-celle-resultater dukker også op i moderne arbejdsbøger, og artiklen om dynamic array spill-formler dækker, hvordan spilled ranges opfører sig i HotXLS

Et segment tree over maksimale output-rækker

HotXLS beholder ankersorteringen til den øvre grænse og tilføjer et augmented segment tree til den nedre grænse. BuildNodeIndex sorterer FNodeOrder efter node-nøgle som før, og derefter fylder BuildMaxOutRowTree FNodeMaxOutRow2 (allokeret til fire entries pr. node) med den største OutRow2 fundet under hvert subtree. QueryNodeTree går kun nedad inde i nøglevinduet og opgiver ethvert subtree, hvis maksimale output-række ligger over FRanges[r].Row1, fordi ingen formel i det kan nå de refererede rækker. Blade, der overlever, går stadig gennem den fulde RangeIntersectsOutput-test, så ark-spænd og kolonner tjekkes præcis som før

// TXLSDepGraph.BuildNodeIndex / BuildEdges siden 2.383.1 (let komprimeret)
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
  // uden for nøglevinduet, eller intet output i dette subtree når 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
      // uændret: EdgeStamp / ScanStamp-undertrykkelse, AddDependent / AddScanDependent
    end;
    Exit;
  end;
  Split := (ALeft + ARight) shr 1;
  QueryNodeTree(ATreeIndex * 2, ALeft, Split, ALower, AUpper);           // venstre subtree først
  QueryNodeTree(ATreeIndex * 2 + 1, Split + 1, ARight, ALower, AUpper);  // bevarer den gamle rækkefølge
end;

Venstre-før-højre-rekursionen er ikke et stilvalg. Overlevende blade besøges i præcis den rækkefølge, den gamle while-løkke besøgte dem, så Dependents- og Precedents-arrays fyldes i samme sekvens, og topologisk rækkefølge forbliver deterministisk. Det samme gælder de to kant-typer: en hård kant registreret først undertrykker stadig en senere LookupScan-kant for samme par, mens en scan-kant registreret før en hård beholder sin plads — den skelnen, der forhindrer lookup-områder i at producere falske cirkulære referencer. Pr. reference falder omkostningen fra vinduets størrelse til O((k + 1) log n), hvor k er antallet af formler, hvis output reelt når de refererede rækker

Hvad garanterer output-indekset, og hvordan verificeres det?

TXLSDepGraph producerer de samme kanter i samme rækkefølge som før, og den nye EdgeCandidateChecks-egenskab tæller, hvor mange output-rektangler det seneste build reelt testede, så påstanden er målelig frem for retorisk. Regressionstesten EdgeBuildDeepChainsCheckOneCandidatePerDependency bygger punktreference-kæder på 1.024 og 100.000 noder, indsat i omvendt rækkefølge for at tvinge den rumlige sortering frem, og assert'er præcis N − 1 kontroller — 99.999 for den lange kæde — plus den forventede precedent-, dependent- og topologiske rækkefølge for hver node. Companion-teste dækker array-rødder indsat i uorden på tværs af ark-spænd, duplikerede hårde og lookup-scan-referencer (10 kontroller, med undertrykkelsesreglerne ovenfor) og et rebuild efter AddNode, som klarer sorteringsflaget, så næste BuildEdges eller NodeIndexOf genopbygger træet og nulstiller tælleren i stedet for at akkumulere den

Målte resultater: fra 18,5 sekunder til omkring 0,1 sekunder

Pre-fix Win32-sporet, bevaret i projektets performance-baseline for version 2.383.0, registrerede to tvungne genberegninger på 18.488 ms og 19.578 ms. Efter indekseringen målte tre serielle fokuserede kørsler pr. arkitektur 102,332-109,429 ms på Win32 og 116,990-133,995 ms på Win64, omkring 170 til 180 gange hurtigere på Win32; ingen pre-fix Win64-baseline blev registreret, så ingen Win64-speedup påstås. De samme kørsler bestod den eksisterende gate, der holder en read-only genberegningsrevision inden for 1,35 gange en tvungen genberegning. Absolutte tal afhænger af maskinen og dens load, så genskab arbejdsbyrden på dit eget hardware, før du citerer dem

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                     // kæde med 49.999 led i kolonne A
      Sh.Cells[I, 1].Formula := '=A' + IntToStr(I - 1) + '+1';
    for I := 1 to 50000 do                     // 50.000 dependents i kolonne B
      Sh.Cells[I, 2].Formula := '=A' + IntToStr(I) + '*2';

    Watch := TStopwatch.StartNew;
    Failed := Wb.Recalculate;                  // første kald bygger grafen
    Watch.Stop;
    Writeln(Format('%d formulas not evaluated, %.1f ms',
      [Failed, Watch.Elapsed.TotalMilliseconds]));
  finally
    Wb.Free;
  end;
end;

Hvor holder output-indekset op med at hjælpe?

Træet beskær kun på rækker, og det efterlader nogle ærlige grænser, der er værd at kende, før du designer en meget stor model omkring det

• Kolonne-fejl betales stadig ved bladene: de 2.626 formler, der fylder A100:Z200, når alle række 100, så en reference til AA100:AA200 tester hver enkelt, før den afviser den
• Brede referencer som helkolonne-områder har reelt mange precedents; indekset fjerner spildte kontroller, ikke rigtige kanter, og at bygge de kanter er stadig proportionalt med deres antal
• For referencer, der spænder over flere ark, ignorerer det gemte maksimum arket, så formler på mellemark med dybe outputs når bladtesten; resultaterne forbliver korrekte, kun beskæringen er svagere
• Træet koster fire heltal pr. formelnode, omkring 1,6 MB for 100.000 noder, og enhver AddNode invaliderer det, så topologiændringer betaler en fuld O(n log n)-gensortering plus et O(n)-træbuild ved næste kant-build

Samme kvadratiske form i report-band navne-kloning

Version 2.383.2 rettede et søsterproblem i TXLSXDefinedNames.UniqueCloneName: hvert kopieret defined name genstartede sin suffiks-søgning ved _2, så gentagne report-band-kopier voksede kvadratisk i navne-opslag. Det scopede navneindeks holder nu et suffix-hint pr. basisnavn og pr. scope og genkontrollerer den sidst returnerede kandidat, fordi kalderen muligvis ikke rent faktisk tilføjer den; sletter, omdøber eller rescoper man et navn, invalideres indekset, hvilket genopretter first-available-navngivning. I regressionssuiten kræver 1.024 sekventielle kloner 5.088 kandidat-opslag, og fire skiftende basisnavne kræver 5.039, mens report-benchmark-minima faldt fra omkring 240 ms til 18–20 ms. Report-band timing-gaten er selv stadig ikke stabil — tre af seks kørsler overskred dens 1,05-ratio i det første post-fix forsøg — og performance-historikken fører de fejlagtige kørsler til protokols i stedet for at tune tærsklen, indtil den består

Genererer eller genberegner din Delphi- eller C++Builder-applikation store Excel-arbejdsbøger, leverer HotXLS Excel component til Delphi og C++Builder denne indekserede afhængighedsgraf i genberegningsmotoren for både sine klassiske og XLSX arbejdsbogsklasser