HotXLS dependency graph: array-formule-uitvoer indexeren

HotXLS 2.383.1, de native Excel-library voor Delphi en C++Builder, bouwt formule-afhankelijkheidsranden via een output-intervalindex: formuleknooppunten blijven gesorteerd op ankercel, en een segment tree die de grootste uitvoerrij (OutRow2) van elke subtree bevat laat TXLSDepGraph.BuildEdges hele blokken formules overslaan die een gerefereerd bereik niet kunnen bereiken. Op een Win32-werkboek met zo'n 100.000 formules zakte een gedwongen herberekening van 18.488 milliseconden naar 102–109 milliseconden

Niemand profileert de dependency graph totdat een batchtaak die vroeger een seconde kostte er twintig begint te kosten. De graaf wordt herbouwd zodra de formuletopologie verandert — de eerste Recalculate na het laden of genereren van een werkboek, of elke pas nadat de graaf ongeldig is verklaard — en in de trace vóór de fix kostte alleen die eerste pas al 16.074 ms. Evalueren was nooit het probleem; uitzoeken wie van wie afhankelijk is, wel

Waarom kostte het herberekenen van 100.000 formules 18 seconden?

De oude edge-builder was kwadratisch in het aantal formules op een werkblad. Voor elk afhankelijkheidsbereik zocht BuildEdges met binair zoeken een venster van kandidaatknooppunten bijeen en testte er daarna elk één mee met RangeIntersectsOutput, en dat venster begon helemaal bovenaan het gerefereerde werkblad. Knooppuntsleutels komen uit XLSDepMakeKey, dat de sheetindex vanaf bit 34 omhoog verpakt, de rij in bits 14–33 en de kolom in bits 0–13, dus de ondergrens (Sheet1, 0, 0) betekende "elke formule van rij 1 tot aan de onderkant van het gerefereerde bereik"

// Vóór 2.383.1 - TXLSDepGraph.BuildEdges, voor afhankelijkheidsbereik r van node d
LowerKey := XLSDepMakeKey(FRanges[r].Sheet1, 0, 0);   // bovenaan het werkblad
UpperKey := XLSDepMakeKey(FRanges[r].Sheet2, FRanges[r].Row2, 16383);
// ...twee binaire zoekacties over FNodeOrder leveren het venster [i, Lo)...
while i < Lo do
begin
  NodeIndex := FNodeOrder[i];
  if RangeIntersectsOutput(FRanges[r], FNodes[NodeIndex]) then
  begin
    // harde edge of LookupScan-edge, gededupliceerd via EdgeStamp / ScanStamp
  end;
  Inc(i);
end;

De performancefixture die dit aan het licht bracht is een doodgewoon cascademodel: A2:A50000 telt er telkens één op bij de cel erboven, en B1:B50000 verdubbelt telkens de buur in kolom A. Een verwijzing naar rij r sleepte dus zo'n 2r kandidaten door de rechthoektest, dus één enkele graafbouw deed in de orde van vijf miljard snijpuntcontroles — een globale schatting, maar die sluit aan bij de 18,5 seconden op de klok. Elke controle zei "nee", op een of twee na

Waarom kan de edge-builder de zoektocht niet bij de gerefereerde rij beginnen?

Omdat een array-formule die boven een bereik verankerd is cellen erbinnen kan bezitten. Elke TXLSDepNode beschrijft een uitvoerrechthoek van zijn anker (Row, Col) tot (OutRow2, OutCol2), en een CSE-array-formule krijgt één knooppunt voor zijn hele rechthoek, zoals het artikel over incrementele herberekening en de dependency graph uitlegt. Een wortel die op A1 verankerd is en A1:A10 vult, moet nog steeds een edge ontvangen van een formule die alleen A5 leest; begin de binaire zoektocht bij rij 5 en die edge verdwijnt geruisloos, wat een verouderde cachewaarde in een verstuurd rapport betekent in plaats van een trage. De query is echt tweezijdig — anker op of vóór Row2, uitvoer die minstens Row1 bereikt — en één enkele sorteervolgorde kan niet beide helften beantwoorden. Multi-cell-resultaten duiken ook in moderne werkboeken op, en het artikel over dynamic array spill-formules behandelt hoe uitgespatte bereiken zich in HotXLS gedragen

Een segment tree van maximale uitvoerrijen

HotXLS houdt de ankorsortering voor de bovengrens aan en voegt een uitgebreide segment tree voor de ondergrens toe. BuildNodeIndex sorteert FNodeOrder zoals eerst op knooppuntsleutel, daarna vult BuildMaxOutRowTree FNodeMaxOutRow2 (toegewezen op vier invoeren per knooppunt) met de grootste OutRow2 die onder elke subtree te vinden is. QueryNodeTree daalt alleen binnen het sleutelvenster af en geeft elke subtree op waarvan de maximale uitvoerrij boven FRanges[r].Row1 ligt, want geen enkele formule daarin bereikt de gerefereerde rijen. Bladeren die overleven gaan nog steeds door de volledige RangeIntersectsOutput-test, dus sheetoverspanningen en kolommen worden precies zo gecontroleerd als eerst

// TXLSDepGraph.BuildNodeIndex / BuildEdges sinds 2.383.1 (enigszins ingekort)
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
  // buiten het sleutelvenster, of geen uitvoer in deze subtree bereikt 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
      // ongewijzigd: EdgeStamp / ScanStamp-onderdrukking, AddDependent / AddScanDependent
    end;
    Exit;
  end;
  Split := (ALeft + ARight) shr 1;
  QueryNodeTree(ATreeIndex * 2, ALeft, Split, ALower, AUpper);           // eerst de linker subtree
  QueryNodeTree(ATreeIndex * 2 + 1, Split + 1, ARight, ALower, AUpper);  // behoudt de oude volgorde
end;

De linker-vóór-rechterrecursie is geen stijlkeuze. Overlevende bladeren worden bezocht in precies de volgorde waarin de oude while-lus ze bezocht, dus de arrays Dependents en Precedents worden in dezelfde reeks gevuld en de topologische volgorde blijft deterministisch. Hetzelfde geldt voor de twee edge-soorten: een eerst geregistreerde harde edge onderdrukt nog steeds een latere LookupScan-edge voor hetzelfde paar, terwijl een scan-edge die vóór een harde werd geregistreerd zijn plek houdt — het onderscheid dat voorkomt dat opzoekbereiken valse circulaire verwijzingen opleveren. Per verwijzing zakt de kostprijs van de grootte van het venster naar O((k + 1) log n), waarbij k het aantal formules is waarvan de uitvoer de gerefereerde rijen werkelijk bereikt

Wat garandeert de uitvoerindex, en hoe wordt dat geverifieerd?

TXLSDepGraph produceert dezelfde edges in dezelfde volgorde als eerst, en de nieuwe eigenschap EdgeCandidateChecks telt hoeveel uitvoerrechthoeken de meest recente bouw werkelijk heeft getest, dus de claim is meetbaar in plaats van retorisch. De regressietest EdgeBuildDeepChainsCheckOneCandidatePerDependency bouwt puntverwijzingsketens van 1.024 en 100.000 knooppunten, in omgekeerde volgorde ingevoegd om de ruimtelijke sortering af te dwingen, en controleert exact N − 1 controles — 99.999 voor de lange keten — plus de verwachte precedent-, dependent- en topologische volgorde voor elk knooppunt. Begeleidende tests dekken arraywortels die ongeordend over sheetoverspanningen heen zijn ingevoegd, dubbele harde en lookup-scan-verwijzingen (10 controles, met de onderdrukkingsregels hierboven) en een herbouw na AddNode, dat de sorteerflag wist zodat de volgende BuildEdges of NodeIndexOf de tree herbouwt en de teller reset in plaats van op te tellen

Gemeten resultaten: van 18,5 seconden naar ongeveer 0,1 seconden

De Win32-trace vóór de fix, bewaard in de performancebaseline van het project voor versie 2.383.0, registreerde twee gedwongen herberekeningen van 18.488 ms en 19.578 ms. Na de indexering maten drie seriematige gerichte runs per architectuur 102,332–109,429 ms op Win32 en 116,990–133,995 ms op Win64, ruwweg 170 tot 180 keer sneller op Win32; er is geen baseline op Win64 vóór de fix vastgelegd, dus er wordt geen versnelling op Win64 geclaimd. Dezelfde runs doorstonden de bestaande gate die een alleen-lezen herberekeningsaudit binnen 1,35 keer een gedwongen herberekening houdt. Absolute getallen hangen van de machine en zijn belasting af, dus reproduceer de workload op uw eigen hardware voordat u ze citeert

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                     // keten van 49.999 schakels in kolom A
      Sh.Cells[I, 1].Formula := '=A' + IntToStr(I - 1) + '+1';
    for I := 1 to 50000 do                     // 50.000 dependents in kolom B
      Sh.Cells[I, 2].Formula := '=A' + IntToStr(I) + '*2';

    Watch := TStopwatch.StartNew;
    Failed := Wb.Recalculate;                  // eerste aanroep bouwt de graaf
    Watch.Stop;
    Writeln(Format('%d formulas not evaluated, %.1f ms',
      [Failed, Watch.Elapsed.TotalMilliseconds]));
  finally
    Wb.Free;
  end;
end;

Waar houdt de uitvoerindex op te helpen?

De tree snoeit alleen op rijen, en dat laat een paar eerlijke grenzen na die goed om te weten voordat u er een heel groot model omheen ontwerpt

• Kolommissers worden nog steeds aan de bladeren betaald: de 2.626 formules die A100:Z200 vullen bereiken allemaal rij 100, dus een verwijzing naar AA100:AA200 test ze allemaal voordat hij ze afwijst
• Brede verwijzingen zoals hele-kolom-bereiken hebben echt veel precedents; de index schrapt verspilde controles, geen echte edges, en het bouwen van die edges blijft evenredig met hun aantal
• Voor verwijzingen die over meerdere sheets lopen negeert de opgeslagen maximum de sheet, dus formules op tussenliggende sheets met diepe uitvoeren bereiken de bladtest; de resultaten blijven correct, alleen het snoeien is zwakker
• De tree kost vier integers per formuleknooppunt, zo'n 1,6 MB voor 100.000 knooppunten, en elke AddNode maakt hem ongeldig, dus topologiewijzigingen betalen bij de volgende edge-bouw een volledige hersortering van O(n log n) plus een treebouw van O(n)

Dezelfde kwadratische vorm in report-band-naamkloning

Versie 2.383.2 heeft een zusterprobleem in TXLSXDefinedNames.UniqueCloneName verholpen: elke gekopieerde gedefinieerde naam begon zijn achtervoegselzoektocht opnieuw bij _2, dus herhaalde report-band-kopieën groeiden kwadratisch in naamopzoekingen. De scoped name index houdt nu een suffixhint per basisnaam en per scope bij en controleert de laatst teruggegeven kandidaat opnieuw, want de aanroeper kan hem uiteindelijk toch niet toevoegen; een naam verwijderen, hernoemen of van scope veranderen maakt de index ongeldig, wat de eerst-beschikbaar-naamgeving herstelt. In de regressiesuite hebben 1.024 sequentiële klonen 5.088 kandidaatopzoekingen nodig en vier alternerende basisnamen 5.039, terwijl de minima van de rapportbenchmark zakte van ruwweg 240 ms naar 18–20 ms. De timing-gate van de report-band zelf is nog steeds niet stabiel — drie van zes runs overschreden zijn ratio van 1,05 in de eerste poging na de fix — en de performancegeschiedenis houdt die mislukkingen in de administratie in plaats van de drempel bij te stellen tot hij slaagt

Als uw Delphi- of C++Builder-applicatie grote Excel-werkboeken genereert of herberekent, levert de HotXLS Excel-component voor Delphi en C++Builder deze geïndexeerde dependency graph mee in de herberekeningsengine voor zowel zijn klassieke als zijn XLSX-werkboekklassen