HotXLS-Dependency-Graph: Array-Formel-Ausgaben indexieren

HotXLS 2.383.1, die native Excel-Bibliothek für Delphi und C++Builder, baut Formel-Dependency-Kanten über einen Output-Intervall-Index auf: Die Formelknoten bleiben nach Ankerzelle sortiert, und ein Segmentbaum, der die größte Ausgabezeile (OutRow2) jedes Teilbaums hält, lässt TXLSDepGraph.BuildEdges ganze Blöcke von Formeln überspringen, die einen referenzierten Bereich nicht erreichen können. In einer Win32-Arbeitsmappe mit rund 100,000 Formeln fiel die erzwungene Neuberechnung von 18.488 Sekunden auf 102–109 Millisekunden

Niemand profiliert den Dependency-Graph, bis ein Batch-Job, der früher eine Sekunde brauchte, auf einmal zwanzig braucht. Der Graph wird immer dann neu gebaut, wenn sich die Formel-Topologie ändert – beim ersten Recalculate nach dem Laden oder Generieren einer Arbeitsmappe, oder bei jedem Durchlauf, nachdem der Graph invalidiert wurde – und im Trace vor dem Fix brauchte allein dieser erste Durchlauf 16,074 ms. Die Auswertung war nie das Problem; zu entscheiden, wer von wem abhängt, war es

Warum brauchte die Neuberechnung von 100,000 Formeln 18 Sekunden?

Der alte Edge-Builder war quadratisch in der Anzahl der Formeln auf einem Sheet. Für jeden Dependency-Bereich suchte BuildEdges per Binärsuche ein Fenster aus Kandidatenknoten heraus und testete dann jeden einzelnen mit RangeIntersectsOutput, und dieses Fenster begann ganz oben auf dem referenzierten Sheet. Die Knotenschlüssel stammen aus XLSDepMakeKey, das den Sheet-Index ab Bit 34 aufwärts packt, die Zeile in die Bits 14–33 und die Spalte in die Bits 0–13, sodass die untere Grenze (Sheet1, 0, 0) bedeutete: „jede Formel von Zeile 1 bis zum unteren Rand des referenzierten Bereichs“

// Vor 2.383.1 – TXLSDepGraph.BuildEdges, für den Dependency-Bereich r von Knoten d
LowerKey := XLSDepMakeKey(FRanges[r].Sheet1, 0, 0);   // oberste Stelle des Sheets
UpperKey := XLSDepMakeKey(FRanges[r].Sheet2, FRanges[r].Row2, 16383);
// ...zwei binäre Suchen über FNodeOrder erzeugen das Fenster [i, Lo)...
while i < Lo do
begin
  NodeIndex := FNodeOrder[i];
  if RangeIntersectsOutput(FRanges[r], FNodes[NodeIndex]) then
  begin
    // harte Kante oder LookupScan-Kante, dedupliziert über EdgeStamp / ScanStamp
  end;
  Inc(i);
end;

Das Performance-Fixture, das das aufdeckte, ist ein gewöhnliches Kaskadenmodell: A2:A50000 addiert jeweils eins auf die Zelle darüber, und B1:B50000 verdoppelt jeweils den Nachbarn in Spalte A. Eine Referenz auf Zeile r schleppte also etwa 2r Kandidaten durch den Rechtecktest, ein einzelner Graph-Aufbau führte damit in der Größenordnung von fünf Milliarden Schnittprüfungen durch – eine grobe Überschlagsrechnung, aber sie passt zu den 18.5 Sekunden auf der Uhr. Jede Prüfung sagte „nein“, ein oder zwei ausgenommen

Warum kann der Edge-Builder die Suche nicht an der referenzierten Zeile beginnen?

Weil eine Array-Formel, die über einem Bereich verankert ist, Zellen darin besitzen kann. Jeder TXLSDepNode beschreibt ein Ausgabe-Rechteck von seinem Anker (Row, Col) bis (OutRow2, OutCol2), und eine CSE-Array-Formel bekommt einen Knoten für ihr gesamtes Rechteck, wie der Artikel zu inkrementeller Neuberechnung und dem Dependency-Graph erklärt. Eine bei A1 verankerte Wurzel, die A1:A10 füllt, muss weiterhin eine Kante von einer Formel bekommen, die nur A5 liest; beginnt man die Binärsuche bei Zeile 5, verschwindet diese Kante stillschweigend – das heißt dann ein veralteter Cached-Wert in einem ausgelieferten Report statt eines langsamen. Die Abfrage ist in Wahrheit zweiseitig – Anker an oder vor Row2, Ausgabe erreicht mindestens Row1 – und eine einzige Sortierreihenfolge kann beide Hälften nicht beantworten. Multi-Zellen-Ergebnisse tauchen auch in modernen Arbeitsmappen auf, und der Artikel zu Dynamic-Array-Spill-Formeln erklärt, wie sich Spill-Bereiche in HotXLS verhalten

Ein Segmentbaum größter Ausgabezeilen

HotXLS behält die Ankersortierung für die obere Grenze und ergänzt einen angereicherten Segmentbaum für die untere Grenze. BuildNodeIndex sortiert FNodeOrder wie bisher nach Knotenschlüssel, danach füllt BuildMaxOutRowTree FNodeMaxOutRow2 (alloziert mit vier Einträgen pro Knoten) mit dem größten OutRow2, das unter jedem Teilbaum zu finden ist. QueryNodeTree steigt nur innerhalb des Schlüsselfensters hinab und gibt jeden Teilbaum auf, dessen maximale Ausgabezeile über FRanges[r].Row1 liegt, weil keine Formel darin die referenzierten Zeilen erreichen kann. Überlebende Blätter laufen weiterhin durch den vollständigen RangeIntersectsOutput-Test, sodass Sheet-Spans und Spalten exakt wie bisher geprüft werden

// TXLSDepGraph.BuildNodeIndex / BuildEdges seit 2.383.1 (leicht kondensiert)
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
  // außerhalb des Schlüsselfensters, oder keine Ausgabe dieses Teilbaums erreicht 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
      // unverändert: EdgeStamp-/ScanStamp-Unterdrückung, AddDependent / AddScanDependent
    end;
    Exit;
  end;
  Split := (ALeft + ARight) shr 1;
  QueryNodeTree(ATreeIndex * 2, ALeft, Split, ALower, AUpper);           // linker Teilbaum zuerst
  QueryNodeTree(ATreeIndex * 2 + 1, Split + 1, ARight, ALower, AUpper);  // hält die alte Reihenfolge ein
end;

Die Links-vor-rechts-Rekursion ist keine Stilentscheidung. Überlebende Blätter werden in genau der Reihenfolge besucht, in der die alte while-Schleife sie besuchte, sodass die Arrays Dependents und Precedents in derselben Sequenz gefüllt werden und die topologische Ordnung deterministisch bleibt. Dasselbe gilt für die beiden Kantentypen: Eine zuerst eingetragene harte Kante unterdrückt weiterhin eine spätere LookupScan-Kante für dasselbe Paar, während eine vor einer harten eingetragene Scan-Kante ihren Platz behält – die Unterscheidung, die verhindert, dass Lookup-Bereiche falsche zirkuläre Referenzen produzieren. Pro Referenz sinken die Kosten von der Größe des Fensters auf O((k + 1) log n), wobei k die Anzahl der Formeln ist, deren Ausgabe die referenzierten Zeilen tatsächlich erreicht

Was garantiert der Output-Index, und wie wird das verifiziert?

TXLSDepGraph erzeugt dieselben Kanten in derselben Reihenfolge wie zuvor, und die neue Property EdgeCandidateChecks zählt, wie viele Ausgabe-Rechtecke der letzte Build tatsächlich getestet hat – die Behauptung ist also messbar statt rhetorisch. Der Regressionstest EdgeBuildDeepChainsCheckOneCandidatePerDependency baut Punkt-Referenzketten aus 1,024 und 100,000 Knoten, eingefügt in umgekehrter Reihenfolge, um die räumliche Sortierung zu erzwingen, und fordert exakt N − 1 Prüfungen ein – 99,999 für die lange Kette – plus die erwartete Precedent-, Dependent- und topologische Ordnung für jeden Knoten. Begleitende Tests decken außer der Reihe eingefügte Array-Wurzeln über Sheet-Spans hinweg ab, duplizierte harte und Lookup-Scan-Referenzen (10 Prüfungen, mit den obigen Unterdrückungsregeln) und einen Neuaufbau nach AddNode, der das Sortier-Flag löscht, sodass der nächste BuildEdges oder NodeIndexOf den Baum neu aufbaut und den Zähler zurücksetzt, statt ihn aufzusummieren

Gemessene Ergebnisse: von 18.5 Sekunden auf etwa 0.1 Sekunden

Der Win32-Trace vor dem Fix, in der Performance-Baseline des Projekts für Version 2.383.0 aufbewahrt, verzeichnete zwei erzwungene Neuberechnungen mit 18,488 ms und 19,578 ms. Nach der Indexierung maßen drei serielle fokussierte Läufe pro Architektur 102.332–109.429 ms auf Win32 und 116.990–133.995 ms auf Win64, rund 170- bis 180-mal schneller auf Win32; es wurde keine Win64-Baseline vor dem Fix aufgezeichnet, also wird keine Win64-Beschleunigung behauptet. Dieselben Läufe bestanden das bestehende Gate, das ein Read-only-Neuberechnungs-Audit innerhalb des 1.35-Fachen einer erzwungenen Neuberechnung hält. Absolute Zahlen hängen von der Maschine und ihrer Last ab, reproduzieren Sie die Workload also auf Ihrer eigenen Hardware, bevor Sie sie zitieren

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                     // Kette mit 49,999 Gliedern in Spalte A
      Sh.Cells[I, 1].Formula := '=A' + IntToStr(I - 1) + '+1';
    for I := 1 to 50000 do                     // 50,000 Abhängige in Spalte B
      Sh.Cells[I, 2].Formula := '=A' + IntToStr(I) + '*2';

    Watch := TStopwatch.StartNew;
    Failed := Wb.Recalculate;                  // erster Aufruf baut den Graphen
    Watch.Stop;
    Writeln(Format('%d formulas not evaluated, %.1f ms',
      [Failed, Watch.Elapsed.TotalMilliseconds]));
  finally
    Wb.Free;
  end;
end;

Wo hört der Output-Index auf zu helfen?

Der Baum prunt nur über Zeilen, und das lässt ein paar ehrliche Grenzen, die man kennen sollte, bevor man ein sehr großes Modell darum herum entwirft

• Spalten-Fehltreffer werden weiterhin an den Blättern bezahlt: Die 2,626 Formeln, die A100:Z200 füllen, erreichen alle Zeile 100, sodass eine Referenz auf AA100:AA200 jede davon testet, bevor sie sie verwirft
• Breite Referenzen wie ganze Spaltenbereiche haben tatsächlich viele Precedents; der Index entfernt verschwendete Prüfungen, keine echten Kanten, und der Aufbau dieser Kanten bleibt proportional zu ihrer Anzahl
• Bei Referenzen über mehrere Sheets hinweg ignoriert das gespeicherte Maximum das Sheet, sodass Formeln auf Zwischen-Sheets mit tiefen Ausgaben bis zum Blatttest kommen; die Ergebnisse bleiben korrekt, nur das Pruning ist schwächer
• Der Baum kostet vier Integer pro Formelknoten, etwa 1.6 MB für 100,000 Knoten, und jedes AddNode invalidiert ihn, sodass Topologie-Änderungen ein volles O(n log n) Re-Sorting plus einen O(n)-Baumaufbau beim nächsten Edge-Build zahlen

Dieselbe quadratische Form beim Report-Band-Namen-Klonen

Version 2.383.2 reparierte ein verwandtes Problem in TXLSXDefinedNames.UniqueCloneName: Jeder kopierte definierte Name startete seine Suffixsuche erneut bei _2, sodass wiederholte Report-Band-Kopien quadratisch in Namenslookups wuchsen. Der Scoped-Name-Index hält jetzt einen Suffix-Hinweis pro Basisname und Scope und prüft den zuletzt zurückgegebenen Kandidaten nach, denn der Aufrufer fügt ihn möglicherweise gar nicht hinzu; Löschen, Umbenennen oder Umscopen eines Namens invalidiert den Index, was die First-Available-Benennung wiederherstellt. In der Regressionssuite brauchen 1,024 sequenzielle Klone 5,088 Kandidaten-Lookups und vier alternierende Basisnamen 5,039, während die Report-Benchmark-Minima von rund 240 ms auf 18–20 ms fielen. Das Report-Band-Timing-Gate selbst ist weiterhin nicht stabil – drei von sechs Läufen überschritten sein 1.05-Verhältnis beim ersten Versuch nach dem Fix – und die Performance-Historie hält diese Fehlschläge im Protokoll fest, statt am Threshold zu drehen, bis er durchläuft

Wenn Ihre Delphi- oder C++Builder-Anwendung große Excel-Arbeitsmappen generiert oder neu berechnet, liefert die HotXLS-Excel-Komponente für Delphi und C++Builder diesen indexierten Dependency-Graph in der Neuberechnungs-Engine mit, für beide Workbook-Klassen, Classic wie XLSX