HotXLS-avhengighetsgraf: indeksering av arrayformel-output

HotXLS 2.383.1, det native Excel-biblioteket for Delphi og C++Builder, bygger formelavhengighetskantsjer gjennom en output-intervalindeks: formelnoder forblir sortert etter anker celle, og et segmenttre som holder den største utdataraden (OutRow2) i hvert subtree lar TXLSDepGraph.BuildEdges hoppe over hele blokker med formler som ikke kan nå et referert område. På en Win32-arbeidsbok med rundt 100 000 formler falt tvungen rekalkulering fra 18,488 sekunder til 102–109 millisekunder

Ingen profilerer avhengighetsgrafen før en batchjobb som pleide å ta ett sekund, begynner å ta tjue. Grafen bygges på nytt når formeltopologien endres — den første Recalculate etter innlesing eller generering av en arbeidsbok, eller ethvert pass etter at grafen er ugyldiggjort — og i sporet fra før fiksen tok det første passet alene 16 074 ms. Evalueringen var aldri problemet; det å avgjøre hvem som avhenger av hvem, var det

Hvorfor tok rekalkulering av 100 000 formler 18 sekunder?

Den gamle kantbyggeren var kvadratisk i antall formler på et ark. For hvert avhengighetsområde binærsøkte BuildEdges et vindu av kandidatnoder og testet deretter hver av dem med RangeIntersectsOutput, og det vinduet startet helt på toppen av det refererte arket. Node-nøkler kommer fra XLSDepMakeKey, som pakker arkindeksen fra bit 34 og oppover, raden inn i bit 14–33 og kolonnen inn i bit 0–13, så nedre grense (Sheet1, 0, 0) betydde «hver formel fra rad 1 og ned til bunnen av det refererte området»

// Før 2.383.1 - TXLSDepGraph.BuildEdges, for avhengighetsområdet r til node d
LowerKey := XLSDepMakeKey(FRanges[r].Sheet1, 0, 0);   // toppen av arket
UpperKey := XLSDepMakeKey(FRanges[r].Sheet2, FRanges[r].Row2, 16383);
// ...to binærsøk over FNodeOrder gir vinduet [i, Lo)...
while i < Lo do
begin
  NodeIndex := FNodeOrder[i];
  if RangeIntersectsOutput(FRanges[r], FNodes[NodeIndex]) then
  begin
    // hard kant eller LookupScan-kant, deduplisert gjennom EdgeStamp / ScanStamp
  end;
  Inc(i);
end;

Ytelsestesten som avslørte dette, er en helt vanlig kaskademodell: A2:A50000 legger én til cellen over, og B1:B50000 dobler naboen i kolonne A. En referanse til rad r dro deretter omkring 2r kandidater gjennom rektangeltesten, så et enkelt grafbygg utførte i størrelsesorden fem milliarder snittpunktsjekker — et overslagsregnestykke, men det stemmer med de 18,5 sekundene på klokka. Hver sjekk svarte «nei» bortsett fra én eller to

Hvorfor kan ikke kantbyggeren starte søket ved den refererte raden?

Fordi en matriseformel forankret over et område kan eie celler inne i det. Hver TXLSDepNode beskriver et utdatarektangel fra ankeret sitt (Row, Col) til (OutRow2, OutCol2), og en CSE-matriseformel får én node for hele rektangelet sitt, som artikkelen om inkrementell rekalkulering og avhengighetsgrafen forklarer. En rot forankret i A1 som fyller A1:A10, må fortsatt få en kant fra en formel som bare leser A5; start det binærsøket ved rad 5, så forsvinner den kanten stille, noe som betyr en foreldet cachet verdi i en levert rapport i stedet for en treg en. Spørringen er i virkeligheden tosidet — anker ved eller før Row2, utdata som når minst Row1 — og én sorteringsrekkefølge kan ikke svare på begge halvdeler. Flercelle-resultater dukker opp i moderne arbeidsbøker også, og artikkelen om dynamic array spill-formler dekker hvordan spillte områder oppfører seg i HotXLS

Et segmenttre over maksimale utdatarader

HotXLS beholder ankorsorteringen for øvre grense og legger til et augmentert segmenttre for nedre grense. BuildNodeIndex sorterer FNodeOrder etter node-nøkkel som før, og BuildMaxOutRowTree fyller så FNodeMaxOutRow2 (allokert med fire oppføringer per node) med den største OutRow2 funnet under hvert subtree. QueryNodeTree går bare nedover inne i nøkkelvinduet og forlater ethvert subtree hvis maksimale utdatarad ligger over FRanges[r].Row1, fordi ingen formel i det kan nå de refererte radene. Blader som overlever, går fortsatt gjennom hele RangeIntersectsOutput-testen, så arkspenn og kolonner sjekkes nøyaktig som før

// TXLSDepGraph.BuildNodeIndex / BuildEdges siden 2.383.1 (lett komprimert)
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
  // utenfor nøkkelvinduet, eller ingen utdata i dette subtree-et 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
      // uendret: EdgeStamp / ScanStamp-undertrykking, 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);  // beholder den gamle rekkefølgen
end;

Venstre-før-høyre-rekursjonen er ikke et stilvalg. Overlevende blader besøkes i nøyaktig den rekkefølgen den gamle while-løkken besøkte dem, så Dependents- og Precedents-matrisene fylles i samme sekvens, og topologisk rekkefølge forblir deterministisk. Det samme gjelder de to kanttypene: en hard kant registrert først undertrykker fortsatt en senere LookupScan-kant for samme par, mens en skannekant registrert før en hard beholder sin plass — skillet som stopper oppslagsområder fra å produsere falske sirkulære referanser. Per referanse faller kostnaden fra vindusstørrelsen til O((k + 1) log n), der k er antall formler hvis utdata faktisk når de refererte radene

Hva garanterer output-indeksen, og hvordan verifiseres den?

TXLSDepGraph produserer de samme kantene i samme rekkefølge som før, og den nye egenskapen EdgeCandidateChecks teller hvor mange utdatarektangler det nyeste bygget faktisk testet, så påstanden er målbar i stedet for retorisk. Regressionstesten EdgeBuildDeepChainsCheckOneCandidatePerDependency bygger punktreferanse-kjeder på 1 024 og 100 000 noder, satt inn i omvendt rekkefølge for å fremtvinge den romlige sorteringen, og hevder nøyaktig N − 1 sjekker — 99 999 for den lange kjeden — pluss forventet precedent-, dependent- og topologirekkefølge for hver node. Følgende tester dekker matriserøter satt inn ute av rekkefølge over arkspenn, dupliserte harde og lookup-scan-referanser (10 sjekker, med undertrykkingsreglene over), og et gjenoppbygg etter AddNode, som nullstiller sorteringsflagget slik at neste BuildEdges eller NodeIndexOf bygger treet på nytt og nullstiller telleren i stedet for å akkumulere den

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

Win32-sporet fra før fiksen, tatt vare på i prosjektets ytelsesgrunnlinje for versjon 2.383.0, registrerte to tvungne rekalkuleringer på 18 488 ms og 19 578 ms. Etter indeksering målte tre serielle fokuskjøringer per arkitektur 102,332–109,429 ms på Win32 og 116,990–133,995 ms på Win64, omkring 170 til 180 ganger raskere på Win32; ingen Win64-grunnlinje fra før fiksen ble registrert, så ingen Win64-oppfølging hevdes. De samme kjøringene besto den eksisterende gaten som holder en skrivebeskyttet rekalkuleringsrevisjon innenfor 1,35 ganger en tvungen rekalkulering. Absolutte tall avhenger av maskinen og belastningen dens, så gjenskap arbeidsmengden på din egen maskinvare før du siterer 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                     // kjede med 49 999 ledd i kolonne A
      Sh.Cells[I, 1].Formula := '=A' + IntToStr(I - 1) + '+1';
    for I := 1 to 50000 do                     // 50 000 dependentere i kolonne B
      Sh.Cells[I, 2].Formula := '=A' + IntToStr(I) + '*2';

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

Hvor slutter output-indeksen å hjelpe?

Treet beskjærer bare på rader, og det etterlater noen ærlige grenser verdt å kjenne før du designer en svært stor modell rundt det

• Kolonnebommer koster fortsatt ved bladene: de 2 626 formalene som fyller A100:Z200, når alle rad 100, så en referanse til AA100:AA200 tester hver av dem før den avviser den
• Brede referanser som helkolonne-områder har faktisk mange precedents; indeksen fjerner bortkastede sjekker, ikke ekte kanter, og å bygge de kantene er fortsatt proporsjonalt med antallet deres
• For referanser som spenner over flere ark, ignorerer det lagrede maksimumet arket, så formler på mellomliggende ark med dype utdata når bladtesten; resultatene forblir korrekte, bare beskjæringen er svakere
• Treet koster fire heltall per formelnode, omkring 1,6 MB for 100 000 noder, og enhver AddNode ugyldiggjør det, så topologiendringer betaler en full O(n log n)-omsortering pluss et O(n)-trebygg ved neste kantbygging

Samme kvadratiske form i kloning av rapportbåndnavn

Versjon 2.383.2 fikset et søskenproblem i TXLSXDefinedNames.UniqueCloneName: hvert kopierte definerte navn startet suffikssøket sitt på _2 igjen, så gjentatte rapportbåndkopier vokste kvadratisk i navneoppslag. Indeksen for scopede navn holder nå et suffikshint per basenavn og per scope og sjekker den sist returnerte kandidaten på nytt, fordi kalleren ikke nødvendigvis legger den til; å slette, gi nytt navn til eller rescope et navn ugyldiggjør indeksen, noe som gjenoppretter navngivning av første ledige. I regressionsuiten trenger 1 024 sekvensielle kloner 5 088 kandidatoppslag og fire vekslende basenavn trenger 5 039, mens minimumene i rapportbenchmarken falt fra omkring 240 ms til 18–20 ms. Tidsgaten for rapportbånd er selv fortsatt ikke stabil — tre av seks kjøringer overskred forholdet 1,05 i det første forsøket etter fiksen — og ytelseshistorien tar vare på de feilene på protokoll i stedet for å skru på terskelen til den passerer

Genererer eller rekalkulerer Delphi- eller C++Builder-applikasjonen din store Excel-arbeidsbøker, følger denne indekserte avhengighetsgrafen med i rekalkuleringsmotoren i HotXLS Excel-komponenten for Delphi og C++Builder, for både de klassiske og XLSX-baserte arbeidsbokklassene