Eine Spalte mit 10.000 Formeln, von denen jede den Wert in der Zelle darüber weiterwachsen lässt, ist ungefähr das billigste Modell, das eine Tabellenkalkulation halten kann. In einem Auswerter, der jede referenzierte Formel sofort vor Ort berechnet, kommen die Summen trotzdem richtig heraus, aber die Rechnung stimmt nicht: Die letzte Zelle schleppt 9.999 Vorgänger durch die Auswertung, die darüber 9.998, und ein einziger voller Durchlauf summiert sich auf rund 50 Millionen Auswertungen für 10.000 Multiplikationen. Ändert man oben eine Wachstumsrate, zahlt dieser Auswerter die ganze Rechnung erneut, denn er hält kein Protokoll darüber, welche Zelle welche liest
Warum eine bearbeitete Zelle einen ganzen Arbeitsmappen-Durchlauf kosten kann
Zwei Abkürzungen erzeugen dieses Verhalten, und die meisten selbst gestrickten Formel-Engines nehmen eine davon. Die rekursive Abkürzung wertet jede referenzierte Formel frisch aus und ignoriert jeden bereits gespeicherten Wert, was aus einer Kette quadratische Arbeit und aus einem Zirkelbezug einen Stack Overflow macht. Die Volldurchlauf-Abkürzung ist sicherer: jede Formel in irgendeiner festen Reihenfolge auswerten, so oft, bis sich nichts mehr ändert. Das ist korrekt, und die Kosten richten sich nach der Größe der Arbeitsmappe statt nach der Größe der Änderung
Excel vermeidet beides mit seiner Berechnungskette, einer Ordnung der Formelzellen, die eine Änderung eine kleine Zellmenge markieren lässt und nur den betroffenen Schwanz abläuft. Die XLSX-Engine in HotXLS nutzt dieselbe Idee in Form eines expliziten Abhängigkeitsgraphen hinter TXLSXWorkbook.Recalculate. Der erste Aufruf baut den Graphen aus jeder Formel auf jedem Blatt und wertet alle aus. Jeder spätere Aufruf wertet nur die Formeln aus, die unterhalb von Zellen liegen, deren Werte sich seit dem letzten Durchlauf geändert haben, plus eine kurze Liste von Formeln, die jedes Mal laufen müssen
Wie Recalculate eine Änderung in einen geordneten Durchlauf verwandelt
Jede Formelzelle wird ein Knoten, und eine Kante läuft von jeder Formelzelle, die eine Formel liest, zu der Formel, die sie liest. Eine Referenz wie SUM(Model!B2:B500) erzeugt eine Kante von jeder Formelzelle in diesem Rechteck, und eine 3D-Referenz über eine Folge von Blättern wird gegen jedes Blatt der Folge gematcht. Einfache Konstanten sind gar keine Knoten; sie zählen nur als der Ort, an dem eine Änderung beginnt
Value auf eine Zelle zu schreiben tut im Moment des Schreibens fast nichts. Die Arbeitsmappe stellt die Adresse der Zelle in eine Warteschlange, das war es. Wenn Recalculate startet, wird jede Formel als schmutzig markiert, deren Referenzen eine eingeordnete Adresse abdecken, und die Markierung fließt entlang der Kanten zu allen Nachfolgern dieser Formel, dann zu deren Nachfolgern. Eine Arbeitsmappe, auf die Recalculate nie aufgerufen wurde, hält keinen Graphen, und ihre Schreibvorgänge kosten eine einzige Nil-Prüfung, Code, der nur Werte liest und schreibt, zahlt also nichts für das Feature
Der schmutzige Teil des Graphen wird dann mit Kahns Algorithmus sortiert. Das Detail, das den Durchlauf billig macht, ist, wie die Eingangsgrade gezählt werden: Nur schmutzige Vorgänger zählen. Ein sauberer Vorgänger hält bereits einen gültigen gespeicherten Wert, auf ihn wartet eine Formel also nie. Während des Durchlaufs liest eine Formel, die eine andere Formelzelle referenziert, den gespeicherten Wert dieser Zelle, statt sie erneut auszuwerten; die Sortierung garantiert, dass der Speicher schon frisch ist. Jede schmutzige Formel wird genau einmal ausgewertet
Der Code unten baut die Kette aus dem Eingangsabsatz und bearbeitet ihre einzige Eingabe. Blattindizes beginnen in HotXLS bei 1, Inputs ist also Blatt 1 und Model Blatt 2; Zeilen und Spalten in Cells sind ebenfalls 1-basiert
uses
SysUtils, lxCalc, lxHandleX; // lxOk ist in lxCalc deklariert
var
Book: TXLSXWorkbook;
Inputs, Model: TXLSXWorksheet;
Row: Integer;
Last: Variant;
begin
Book := TXLSXWorkbook.Create;
try
Inputs := Book.Sheets.Add('Inputs'); // Sheets[1]
Model := Book.Sheets.Add('Model'); // Sheets[2]
Inputs.Cells[2, 2].Value := 0.05; // Wachstumsannahme in Inputs!B2
Model.Cells[2, 2].Formula := 'Inputs!B2*1000';
for Row := 3 to 10000 do
Model.Cells[Row, 2].Formula :=
'B' + IntToStr(Row - 1) + '*(1+Inputs!$B$2)';
if Book.Recalculate <> lxOk then // baut den Graphen, wertet 9.999 Formeln aus
Exit;
Inputs.Cells[2, 2].Value := 0.07; // ordnet eine Adresse ein
if Book.Recalculate = lxOk then // von Inputs!B2 gespeiste Formeln laufen erneut (hier: alle 9.999)
Last := Model.Cells[10000, 2].Value; // gespeichertes Ergebnis, gelesen wie jeder Wert
// Einmaliges Lesen: RecalcCell führt Recalculate aus und liefert dann die Zelle
// (Blatt 2 = Model, Zeile 10000, Spalte 2)
Book.RecalcCell(2, 10000, 2, Last);
finally
Book.Free;
end;
end;
In diesem particular Modell liest jede Formel Inputs!$B$2, der zweite Durchlauf fasst also weiterhin alle 9.999 an; der Graph kann eine Änderung nicht schrumpfen, die wirklich alles betrifft. Die Ersparnis zeigt sich in Modellen mit vielen Eingaben, in denen eine Szenario-Schleife drei oder vier Zellen schreibt und der Rest der Arbeitsmappe seine gespeicherten Werte behält
Wert-Schreibvorgänge sind billig, Formel-Schreibvorgänge bauen den Graphen neu
Nur Wert-Änderungen bleiben inkrementell. Alles, was die Menge der Knoten oder Kanten ändern kann, markiert den ganzen Graphen als veraltet, und das nächste Recalculate baut ihn von Null auf und wertet jede Formel aus. Das umfasst das Zuweisen von Formula, das Räumen einer Formelzelle durch Schreiben von Null oder eines leeren Werts, das Hinzufügen, Verschieben oder Löschen von Blättern, das Einfügen oder Löschen von Zeilen und Spalten, das Bearbeiten definierter Namen und das Ändern von Was-wäre-wenn-Datentabellen. Eine Benutzerfunktion zu registrieren oder abzumelden oder OnUserFunction zuzuweisen, erhält den Graphen, markiert aber jeden Knoten als schmutzig
Die praktische Folge für Berichtsgeneratoren ist eine Schleifenform. Formeln einmal anlegen, Recalculate aufrufen und von da an nur Werte anfassen. Eine Schleife, die pro Kunde eine Formelvorlage neu schreibt und dann neu berechnet, bekommt bei jeder Iteration einen vollen Neubau, genau die Kosten, die der Graph vermeiden soll. Ist eine Vorlagenänderung wirklich nötig, alle Formel-Änderungen vor einem Recalculate bündeln, sodass der Neubau einmal passiert. Die Szenario-Schleife selbst schreibt dann nur noch Werte
// Modell einmal gebaut; Recalculate bereits aufgerufen
for I := 0 to High(Scenarios) do
begin
Inputs.Cells[2, 2].Value := Scenarios[I].Growth; // nur Wert-Schreibvorgänge
Inputs.Cells[3, 2].Value := Scenarios[I].Discount;
if Book.RecalcNeeded then // True, wenn Zellen eingeordnet oder schmutzig sind
if Book.Recalculate <> lxOk then
Break;
Results[I] := Model.Cells[10000, 2].Value;
end;
// SaveAs nur dann neu berechnen lassen, wenn noch etwas aussteht
Book.RecalcBeforeSave := xrmIfDirty;
Book.SaveAs('scenarios.xlsx');
RecalcBeforeSave steht per Default auf xrmManual, was beim Speichern nie neu berechnet. xrmIfDirty ist die Einstellung für generierte Dateien: Sie berechnet nur neu, wenn der Graph veraltet ist oder schmutzige Formeln hat, eine in der Schleife bereits neu berechnete Arbeitsmappe wird also unverändert geschrieben, und eine mit einer vergessenen Änderung wird nicht mit veralteten gespeicherten Werten gesichert
Welche Excel-Funktionen erzwingen eine Neuberechnung bei jedem Durchlauf?
Formeln, die NOW, TODAY, RAND, RANDBETWEEN, RANDARRAY, OFFSET, INDIRECT, CELL, INFO oder GETPIVOTDATA aufrufen, sind in HotXLS volatil: Sie werden zu Beginn jedes Durchlaufs als schmutzig markiert, ob sich upstream etwas geändert hat oder nicht, und alle ihre Nachfolger ebenfalls. Die Uhr- und Zufallsfunktionen sind aus dem naheliegenden Grund volatil. OFFSET und INDIRECT sind volatil, weil die Zellen, die sie lesen, zur Laufzeit aus Argumentwerten berechnet werden, und kein statischer Gang durch die Formel kann sagen, welche Kanten zu zeichnen wären
Dieselbe Regel gilt für Referenzen, die der Graph-Builder nicht auf ein konkretes Rechteck pinnen kann, für einen definierten Namen, der sich über andere Namen selbst referenziert, für Dynamic-Array-Spill-Referenzen und für Was-wäre-wenn-Datentabellen. Definierte Namen sind generell kein Problem: Der Builder expandiert einen Namen zu den Bereichen, auf die er verweist, Formeln über Arbeitsmappen- oder Blatt-scope-Namen bekommen also echte Kanten. Der Artikel zu definierten Namen und blattübergreifenden Formeln behandelt, wie diese Namen aufgelöst werden
Die konservative Richtung ist hier die richtige. Eine unnötige Auswertung kostet ein wenig Zeit; eine fehlende Kante bedeutet eine veraltete Zahl in einem Bericht, der fertig aussieht. OFFSET und INDIRECT von den Hot Paths großer Modelle fernhalten und auf die wenigen Zellen beschränken, die wirklich berechnete Adressen brauchen, denn eine volatile Zelle nahe dem Kopf einer Kette macht die ganze Kette in der Praxis volatil
Funktionen über OnUserFunction oder RegisterUserFunction sitzen am anderen Ende. Sie sind nicht volatil, ein Handler wird also nur dann wieder aufgerufen, wenn sich die Zellen ändern, die seine Argumente speisen, wie jede eingebaute Funktion. Ein Handler, der einen Wechselkurs aus einer Datenbank liest, liefert deshalb über Durchläufe hinweg seine letzte Antwort weiter. Den Kurs stattdessen in eine Eingabezelle schreiben und diese Zelle als Argument übergeben; der Graph sieht dann die Abhängigkeit, und die Formel läuft genau dann neu, wenn sich der Kurs ändert. Der Artikel zu benutzerdefinierten Funktionen in der HotXLS-Formel-Engine erklärt, wie Handler-Argumente ankommen
Zirkelbezüge: lxErrorRef oder iterative Berechnung
Mit dem Default Iterate = False liefert TXLSXWorkbook.Recalculate lxErrorRef, wenn die Sortierung einen Zyklus findet. Zyklusmitglieder sind die schmutzigen Knoten, die Kahns Algorithmus nie freigeben kann, und jede schmutzige Formel unterhalb von ihnen ist aus demselben Grund blockiert. Diese Formeln behalten ihre vorherigen gespeicherten Werte, während alles Übrige in der schmutzigen Menge der Reihe nach ausgewertet wird. Ein fehlgeschlagener Durchlauf markiert den Graphen zudem als veraltet, der Aufruf danach baut den Graphen also neu und wertet jede Formel noch einmal aus
case Book.Recalculate of
lxOk:
Book.SaveAs(OutputFile);
lxErrorRef:
// der Zyklus und seine nachgelagerten Formeln halten weiterhin ihre alten Speicher;
// LogWarning ist eine eigene Routine
LogWarning('Circular reference in model, report not written');
else
LogWarning('Recalculation did not complete');
end;
Iterate := True schaltet dieselbe iterative Berechnung ein, die Excel anbietet. Die Engine wertet den Zyklus und seine blockierten Nachfolger wiederholt aus, bis zu IterateCount Durchläufen (Default 100), bis sich kein Wert mehr um IterateDelta (Default 0.001) oder mehr bewegt. Leere Zyklusmitglieder starten bei 0. Das Erreichen des Durchlauf-Limits behält die letzten Ergebnisse und liefert trotzdem lxOk, deshalb sollte Iteration für generierte Berichte ausgeschaltet bleiben: Zirkel in echten Berichtsmodellen sind fast immer Fehler, etwa eine Summenzeile, die in ihrem eigenen SUM-Bereich gelandet ist, und von ihnen will man einen klaren Fehlercode. Einschalten nur für Modelle, die um eine beabsichtigte Schleife gebaut sind, etwa Zinsen auf einen mittleren Saldo, der die Zinsen einschließt
Ein Fall, der zirkulär aussieht, wird nicht als Zyklus gemeldet. Das Sucharray-Argument von VLOOKUP, HLOOKUP, LOOKUP, MATCH, XLOOKUP und XMATCH macht die Formel weiterhin schmutzig, wenn sich eine Zelle in diesem Bereich ändert, zählt aber nicht zur Zykluserkennung, ein in Spalte B geschriebenes VLOOKUP(A1,B:B,1) wird also normal ausgewertet. Für echte Zyklen zeigt der Formelauswertungs-Tracer die Referenzkette, die in sich selbst zurückfaltet, Schritt für Schritt
Matrixformeln und mehrthreadige Durchläufe
Eine klassische CSE-Matrixformel ist ein Knoten für ihr ganzes verankertes Rechteck. Die Wurzelformel wird einmal pro Durchlauf ausgewertet, ihre Matrix wird in jede Mitgliedzelle geschrieben (ein skalares Ergebnis wird über das Rechteck verteilt), und eine Formel, die irgendeine Zelle des Rechtecks referenziert, nicht nur den Anker oben links, bekommt eine Kante von der Wurzel. Dynamic-Array-Formeln werden vorsichtiger behandelt: Sie laufen in jedem Durchlauf, und wenn ein Spill die Größe ändert, baut Recalculate den Graphen neu und wiederholt den Durchlauf, bis sich die Spill-Formen beruhigen. Beruhigen sie sich nie binnen 32 Runden, liefert der Aufruf lxErrorCalc
RecalcThreads über 1 wertet jede topologische Ebene unabhängiger Formeln über Worker-Threads aus, mit einem eigenen Rechner pro Thread. Datentabellen laufen weiterhin seriell, und eine Arbeitsmappe mit dynamischen Arrays bleibt auf dem seriellen Pfad. Jeder Benutzerfunktions-Handler muss thread-safe sein, bevor man diesen Wert anhebt; für einen Handler, der gemeinsamen Zustand anfasst, ist RecalcThreads auf seinem Default 0 die sicherere Wahl
Der Abhängigkeitsgraph, die volatile-Behandlung und die iterative Berechnung sind Teil der XLSX-Engine in der Excel-Komponente HotXLS für Delphi, die auch den Formelrechner, definierte Namen und die Lese- und Schreib-Pipeline darum herum abdeckt. Für Delphi- und C++Builder-Anwendungen, die Preisblätter oder Konsolidierungsarbeitsmappen offen halten und ihnen den Tag über neue Eingaben zuführen, folgt der Aufwand pro Änderung dann den Zellen, die die Änderung tatsächlich erreicht