Inkrementelle Formel-Neuberechnung in HotXLS für Delphi

HotXLS, die native Excel-Bibliothek für Delphi und C++Builder, führt über TXLSXWorkbook.Recalculate eine inkrementelle Formel-Neuberechnung durch. Der erste Aufruf erstellt einen Formel-Abhängigkeitsgraphen und wertet jede Formelzelle aus. Jeder nachfolgende Aufruf berechnet nur noch die Zellen neu, die von den seit dem letzten Durchlauf geschriebenen Werten betroffen sind. Dies geschieht in topologischer Reihenfolge und in einem einzigen Durchlauf, dessen Aufwand proportional zur Anzahl der geänderten („schmutzigen“) Zellen und nicht zur Gesamtgröße der Arbeitsmappe ist

Diese Designentscheidung macht den Unterschied aus zwischen einem Finanzmodell, das auf eine geänderte Annahme in Millisekunden reagiert, und einem, das sekundenlang blockiert. Wenn Sie Berichte generieren, bei denen eine Handvoll Eingabezellen Tausende nachgelagerte Formeln speist, erklärt dieser Artikel, was der Graph leistet, welche Funktionen von der Inkrementalität ausgenommen sind und wie zirkuläre Referenzen (Kreisbezüge) gemeldet werden, anstatt zu einer Endlosschleife zu führen

Warum berechnet das Ändern einer Zelle einhunderttausend Formeln neu?

Eine naive Formel-Engine besitzt kein Gedächtnis darüber, wer von wem abhängt. Ihre einzige sichere Maßnahme nach jeder Änderung besteht darin, alles neu zu bewerten. Schlimmer noch: Die klassische rekursive Strategie — wenn Formel A auf Formel B verweist, bewerte B sofort vor Ort — berechnet referenzierte Zellen bedingungslos neu und ignoriert jeden gecachten Wert. Eine Kette von n Formeln, von denen jede auf die vorherige verweist, verursacht bei jedem vollständigen Durchlauf Kosten von O(n²) Auswertungen, und eine zirkuläre Referenz lässt die Rekursion ins Bodenlose stürzen. Jeder Tabellenkalkulationsentwickler, der ein kaskadierendes Modell in einen rekursiven Evaluator eingebunden hat, musste bereits beide Fehlerszenarien miterleben

Excel selbst hat dieses Problem vor Jahrzehnten mit seiner Berechnungskette gelöst: eine Reihenfolge von Formelzellen, die so gepflegt wird, dass eine Änderung nur einen kleinen Satz von Zellen als „schmutzig“ markiert und die Engine nur den betroffenen Teil der Kette durchläuft. HotXLS wendet dieselbe Idee als expliziten Abhängigkeitsgraphen an, der einmalig aus den kompilierten Formelbäumen erstellt und über Berechnungsdurchgänge hinweg wiederverwendet wird. Das ist keine Spielerei; es sorgt dafür, dass die Kosten der Neuberechnung der Größe Ihrer Änderung und nicht der Größe Ihrer Arbeitsmappe entsprechen

Wie der Abhängigkeitsgraph eine Änderung in einen einzigen Durchlauf verwandelt

Der Abhängigkeitsgraph von HotXLS weist jeder Formelzelle einen Knoten zu, wobei die Kanten von der Vorgängerzelle (Precedent) zur Nachfolgerzelle (Dependent) verlaufen. Wenn Ihr Code einen Zellwert schreibt, markiert die Arbeitsmappe diese Zelle als schmutzig. Wenn Recalculate ausgeführt wird, pflanzt sich der Status „schmutzig“ entlang der Kanten zu jeder nachgelagerten Formel fort, und der geänderte Teilgraph wird mithilfe des Kahn-Algorithmus exakt einmal in topologischer Reihenfolge ausgewertet. Da eine Formel niemals vor ihren Vorgängern besucht wird, benötigt jeder Knoten nur eine einzige Auswertung — das macht den Durchlauf O(dirty)

Die topologische Reihenfolge löst das Rekursionsproblem zudem an der Wurzel. Während eines Berechnungsdurchlaufs schaltet die Engine in einen speziellen Modus, in dem jeder Verweis auf eine andere Formelzelle direkt den gecachten Wert dieser Zelle liest, anstatt sie erneut auszuwerten — die Sortierung garantiert, dass dieser Wert bereits aktuell ist. Derselbe Mechanismus sorgt dafür, dass ein Referenzzyklus keine unbegrenzte Rekursion auslösen kann: Nichts innerhalb des Durchlaufs ruft den Evaluator für eine Nachbarzelle erneut auf

var
  Book: TXLSXWorkbook;
  Inputs, Model: TXLSXWorksheet;
begin
  Book := TXLSXWorkbook.Create;
  try
    Inputs := Book.Sheets.Add('Inputs');
    Model  := Book.Sheets.Add('Model');

    Inputs.Cells[2, 2].Value := 0.05;                 // Wachstumsannahme
    Model.Cells[2, 2].Formula := 'Inputs!B2*1000';    // XLSX-Formeln enthalten kein führendes '='
    Model.Cells[3, 2].Formula := 'B2*(1+Inputs!B2)';
    // ... Tausende weitere Zeilen, die auf derselben Annahme basieren ...

    Book.Recalculate;                 // Erster Aufruf: Erstellt den Graphen, vollständige Auswertung
    
    Inputs.Cells[2, 2].Value := 0.07; // Eine Änderung markiert eine Zelle als schmutzig
    Book.Recalculate;                 // Zweiter Aufruf: Nur die nachgelagerte Kette läuft
  finally
    Book.Free;
  end;
end;

Jedes Ergebnis landet im gecachten Value der Zelle, sodass Sie nach der Rückkehr von Recalculate die Ausgaben wie bei jeder anderen Zelle auslesen. In einer Berichtserstellungsschleife entspricht das Muster exakt dem obigen Code: Erstellen oder laden Sie das Modell einmal, wechseln Sie dann zwischen dem Schreiben einiger Eingabezellen und dem Aufruf von Recalculate, und zahlen Sie nur für die Formeln, die tatsächlich von den Änderungen betroffen sind

Welche Excel-Funktionen erzwingen eine Neuberechnung bei jedem Durchlauf?

HotXLS behandelt NOW, TODAY, RAND, OFFSET und INDIRECT als volatile (flüchtige) Funktionen: Jede Formel, die eine dieser Funktionen enthält, wird bei jedem Recalculate-Durchlauf neu ausgewertet, unabhängig davon, ob sich weiter oben im Pfad etwas geändert hat. Die ersten drei sind aus demselben Grund flüchtig wie in Excel — ihr Ergebnis hängt vom Zeitpunkt der Auswertung ab und nicht von anderen Zellen. OFFSET und INDIRECT sind aus einem subtileren Grund flüchtig: Die Zellen, die sie lesen, werden erst zur Laufzeit ermittelt, sodass der Graph nicht statisch wissen kann, welche Kanten er zeichnen soll

Dieselbe konservative Regel gilt für Referenzen, die der Graph-Builder nicht auf einen einzelnen rechteckigen Bereich eingrenzen kann. Eine Formel, die über einen benannten Bereich mit mehreren Bereichen verläuft, oder eine, die auf eine externe Arbeitsmappe verweist, wird ebenfalls als volatil eingestuft und bei jedem Durchgang neu berechnet. Diese Richtlinie ist Absicht: Eine zusätzliche Auswertung kostet etwas Zeit, aber eine fehlende Abhängigkeitskante führt zu einem unbemerkt veralteten Wert in einem ausgegebenen Bericht, was der weitaus schlimmere Fehler ist. Wenn Ihr Modell auf Namen mit Arbeitsmappen-Gültigkeitsbereich basiert, behandelt der Begleitartikel über definierte Namen und blattübergreifende Formeln, wie Namen mit einem einzigen Bereich aufgelöst werden — diese nehmen normal am Graphen teil

Die praktische Empfehlung daraus liegt auf der Hand: Halten Sie die performancekritischen Pfade eines großen Modells auf einfachen Zell- und Bereichsreferenzen, bei denen der Graph seine Arbeit tun kann, und verbannen Sie OFFSET und INDIRECT an die wenigen Stellen, die zwingend eine dynamische Adressierung erfordern. Ein Modell mit tausend volatilen Formeln führt diese tausend bei jedem Durchlauf neu aus, egal wie klein die Änderung war — genau das Verhalten, das Excel-Benutzer von Arbeitsmappen kennen, die „bei jedem Tastendruck neu berechnen“

Wie meldet HotXLS Kreisbezüge?

TXLSXWorkbook.Recalculate gibt bei einem fehlerfreien Durchlauf lxOk und bei Erkennung eines Referenzzyklus lxErrorRef zurück. Die Mitglieder des Zyklus werden während der topologischen Sortierung identifiziert — es sind die Knoten, die der Kahn-Algorithmus niemals freigeben kann — und sie werden übersprungen, anstatt endlos zu kreisen: Ihre gecachten Werte bleiben unverändert, während jede Formel außerhalb des Zyklus weiterhin ordnungsgemäß der Reihe nach ausgewertet wird. Ihr Aufruf erhält einen definierten Fehlercode anstelle eines Programmhängers

case Book.Recalculate of
  lxOk:
    SaveReport(Book);
  lxErrorRef:
    // Ein Referenzzyklus existiert. Zyklusmitglieder behielten ihre vorherigen
    // gecachten Werte und alles außerhalb des Zyklus ist aktuell.
    LogWarning('Kreisbezug erkannt - Modelleingaben überprüfen');
end;

Das Auffinden der Zellen, die den Zyklus bilden, ist eine Debugging-Aufgabe, für die der Formelauswertungs-Tracer das richtige Werkzeug ist: Trägt man die verdächtige Formel ein, wird die sich selbst schließende Referenzkette Schritt für Schritt sichtbar. Zyklen in realen Modellen sind fast immer ein Autorenfehler — eine Summenzeile, die versehentlich in ihren eigenen SUM-Bereich einbezogen wurde — weshalb ein klarer Fehlercode zum Berechnungszeitpunkt genau das ist, was Sie wollen

Matrixformeln, Dirty-Tracking und wann sich der Graph neu aufbaut

CSE-Matrixformeln (Array Formulas) erhalten einen einzigen Knoten für den gesamten verankerten Bereich und nicht einen Knoten pro Zelle. Die Stammformel wird einmal pro Durchgang ausgewertet. Die resultierende Matrix wird direkt in jede Elementzelle geschrieben, und eine Formel, die auf eine beliebige Zelle innerhalb des verankerten Bereichs verweist — nicht nur auf den Anker oben links — erhält eine Abhängigkeitskante von diesem Stammknoten. Skalare Ergebnisse verteilen sich über das Rechteck, wie es die alten Matrixsemantiken von Excel vorschreiben

Das Dirty-Tracking klinkt sich in die normalen Eigenschafts-Setter ein, sodass sich an Ihrem Code nichts ändert. Das Schreiben von Value in eine Zelle benachrichtigt die Arbeitsmappe und markiert Nachfolger als schmutzig. Das Zuweisen einer neuen Formula ist eine strukturelle Änderung und markiert den gesamten Graphen als veraltet, sodass der nächste Aufruf von Recalculate ihn vor der Auswertung neu aufbaut. Das Hinzufügen, Löschen oder Verschieben von Blättern macht den Graphen ebenfalls ungültig, da die Knotenidentität den Blattindex codiert. Ist kein Graph aktiv — bei einer Arbeitsmappe, für die Sie Recalculate nie aufrufen — kosten die Hooks lediglich eine einzige Nil-Prüfung pro Zuweisung, sodass einfache Lese- und Schreib-Workloads unbeeinträchtigt bleiben

Eine Systemgrenze sei ehrlich benannt: Der Graph verfolgt Abhängigkeiten zwischen Zellen. Eine über OnUserFunction registrierte benutzerdefinierte Funktion wird daher neu ausgewertet, wenn sich die Zellen ändern, die ihre Argumente speisen, genau wie jede andere Formel. Wenn Sie die Engine auf diese Weise erweitern, führt der Artikel über benutzerdefinierte Funktionen in der HotXLS-Formel-Engine durch den Callback-Vertrag und zeigt, wie Argumentwerte übergeben werden

Die inkrementelle Neuberechnung ist Teil der standardmäßigen XLSX-Engine im HotXLS Delphi Excel Component, neben dem Formelrechner, definierten Namen und der Import/Export-Pipeline, die sie beschleunigt. Wenn Ihre Delphi- oder C++Builder-Anwendung lebendige Modelle verwaltet — Preiskalkulationen, Konsolidierungsarbeitsmappen oder kaskadierende Berichte — macht Recalculate den Unterschied aus zwischen der Neuberechnung einer gesamten Arbeitsmappe und der Neuberechnung einer einzelnen Änderung