Daten dynamisch mit impliziter Inkrementalisierung anpassen – ein C#-Beispiel

Computerprogramme nehmen eine Eingabe entgegen und produzieren eine Ausgabe. Dieses sehr alte Grundprinzip ist immer noch gültig, hat aber schon seit jeher die Frage aufgeworfen, wie das System reagieren soll, wenn sich die Eingabe im Nachhinein ändert.

Georg Hinkel

Georg Hinkel forscht und lehrt an der Hochschule RheinMain zu den Themenschwerpunkten Softwaretechnik, modellgetriebene Softwareentwicklung und verteilte Systeme. Er ist außerdem Maintainer des Open-Source-Projekts NMF.

Bei den großen Datenmengen und der Vielzahl an Analysen und Transformationen, die heutige Systeme berechnen, stellen sich angesichts von Änderungen der zugrundeliegenden Daten viele Fragen: Ist das Analyseergebnis noch valide? Muss das System wirklich alles neu berechnen? Gibt es von der Änderung nicht betroffene Zwischenergebnisse, die gecacht und wiederverwendet werden können? Cache-Invalidierung gehört nach Phil Karlton zu den schwierigsten Herausforderungen der Informatik. Wie stellt man folglich sicher, alles richtig gemacht zu haben?

Algorithmen und Datenstrukturen, die sich an Änderungen der zugrundeliegenden Daten anpassen können, werden entweder als inkrementell oder als voll dynamisch bezeichnet, wobei sich der Unterschied darauf bezieht, ob die Daten immer nur wachsen und inkrementell neue Daten hinzukommen oder ob auch bestehende Daten wegfallen. Da in der Praxis häufig immer nur neue Änderungen inkrementell an den Daten auftreten, spricht man häufig von inkrementeller Änderungsausbreitung. Der Prozess, einen bestehenden Algorithmus in einen umzuwandeln, der inkrementelle Änderungsausbreitung unterstützt, heißt Inkrementalisierung.

Die Universität Budapest hat dazu ein Schienennetzwerkmodell veröffentlicht [1], anhand dessen sich das Problem als Beispiel gut erklären lässt. Es enthält Elemente für Schienen, Weichen und Signale sowie Routen, die durch das Schienennetzwerk führen. Jede Route beginnt und endet an einem Signal und führt entlang mehrerer Weichen. Ein kleiner Ausschnitt eines solchen Modells ist in Abbildung 1 dargestellt:

Eine wichtige Analyse in so einem Netzwerk überprüft, ob alle Weichen entlang einer auf GO geschalteten Route so eingestellt sind, wie von der Route vorgesehen. Im Beispiel sollte das Eingangssignal der in Abbildung 1 blau markierten Route besser STOP zeigen, da die Weichen zum Teil nicht so eingestellt sind, dass sie ans Ziel der Route führen.

Algorithmen ohne inkrementelle Änderungsausbreitung

Gibt es eine typsichere API zum Zugriff auf die Modellelemente, so lässt sich oft einfach ein Prüfalgorithmus ohne inkrementelle Änderungsausbreitung formulieren. Eine Implementierung mit der Query-Syntax in C# zeigt folgendes Listing 1:

from route in routes
where route.Entry != null && route.Entry.Signal == Signal.GO
from swP in route.Follows
where swP.Switch.CurrentPosition != swP.Position
select swP

Das Listing filtert zunächst in der Auflistung der relevanten Routen nach denen, deren Eingangssignal auf GO steht. Anschließend ermittelt es für diejenigen Routen alle Weichenpositionen, bei denen die referenzierte Weiche anders eingestellt ist als von der Route vorgesehen. An einer solchen Implementierung ist nichts auszusetzen, sie ist kurz, leicht verständlich und gut wartbar. In anderen Programmiersprachen ließe sich der Algorithmus ähnlich formulieren, die Streams-API von Java erfordert beispielsweise nur geringfügig mehr Boilerplate-Code.

Einziges Problem: Der Algorithmus unterstützt keine inkrementelle Änderungsausbreitung, und da jede Änderung des Netzwerkmodells das Ergebnis beeinflussen kann, muss der Algorithmus nach jeder Änderung neu ausgeführt werden. Da die allermeisten Änderungen aber nur sehr wenige Elemente betreffen, ist eine komplette Neuberechnung bei größeren Modellen ineffizient.

Repräsentation von Änderungen und Inkrementalisierung

Wollen Entwickler diesen Algorithmus inkrementalisieren, stellt sich zuerst die Frage, wie das System überhaupt mitbekommt, dass sich Teile des Modells geändert haben. Je nach Plattform gibt es hierfür mehr oder weniger standardisierte Schnittstellen. In .NET haben sich mit dem Aufkommen von WPF die Schnittstellen INotifyPropertyChanged und INotifyCollectionChanged etabliert. Für Java existiert das Framework EMF, das eine standardisierte Schnittstelle für Änderungen eines Modells bereithält.

Die zweite Frage ist, wie das Ergebnis einer Inkrementalisierung aussehen soll, also wie man einen Wert beschreibt, der sich – wenn sich die Eingabedaten entsprechend ändern – ändern kann.

Mathematisch lässt sich Inkrementalisierung am besten mit einem Funktor aus der Kategorientheorie beschreiben [2]: Ein Funktor I besteht aus zwei Teilen. Zum einen wird ein Typ A auf einen Typen I(A) abgebildet, der einen inkrementellen Wert vom Typ A beschreibt. Zum anderen bildet ein Funktor eine Funktion f:A ⇾ B auf eine Funktion I(f):I(A) ⇾ I(B) ab. Außerdem benötigen wir eine natürliche Transformation val:I ⇾ id, die für jeden Typen eine Komponente val_A:I(A) ⇾ A beinhaltet, die den aktuellen Wert eines inkrementellen Werts liefert, sowie eine Transformation const:id ⇾ I, die einen Wert eines beliebigen Typen als Konstante (die sich nie ändert) auffasst.

In vielen Programmiersprachen werden Funktoren mit generischen Schnittstellen wie in .NET IEnumerable implementiert. Die Abbildung, wie man eine Funktion von f:A ⇾ B auf I(f): IEnumerable_A ⇾ IEnumerable_B abbildet, heißt in .NET beispielsweise Select, in anderen Programmiersprachen häufig map.

Um einen inkrementellen Wert im Speicher zu repräsentieren, ist also eine generische Schnittstelle erforderlich, nennen wir sie INotifyValue. Sie könnte beispielsweise wie folgt in Listing 2 aussehen:

public interface INotifyValue<out T>
{
    T Value { get; }
    INotifyValue<U> Select<U>(Func<T, U> selector);
    event EventHandler ValueChanged;
}

Die Schnittstelle weist noch ein Event auf, das eine Nachricht sendet, sobald sich der Wert geändert hat.

Ein Sonderfall sind Collections, da hier typischerweise nicht nur interessant ist, dass sich die Collection geändert hat, sondern auch wie sie sich geändert hat. In .NET gibt es dafür die Schnittstelle INotifyCollectionChanged. Die ist allerdings nicht generisch, weshalb man sie noch mit der bestehenden, typsicheren Schnittstelle IEnumerable kombinieren sollte. Folgendes Listing 3 zeigt das Ergebnis mit dem Namen INotifyEnumerable:

public interface INotifyEnumerable<out T>
 : IEnumerable<T>, INotifyCollectionChanged { }

Manuelle Inkrementalisierung

Die dritte Frage bei der Inkrementalisierung ist, welche Arten von Änderungen Auswirkungen auf das Ergebnis des Algorithmus haben, verbunden mit der Frage, welche Zwischenergebnisse man speichern und wann man sie wie invalidieren könnte. Meist gibt es viele Arten von Änderungen, die den Algorithmus und die Zwischenergebnisse auf unterschiedliche Art beeinflussen. Wenn sich die Position einer Weiche ändert, ist das nur dann relevant, wenn die Weiche auch entlang einer Route mit Eingangssignal auf GO steht. Ändert sich hingegen das Eingangssignal einer Route, müssen alle Weichenpositionen entlang der Route analysiert werden.

Wer den Algorithmus zur Inkrementalisierung manuell implementiert, muss für jede mögliche Änderung explizit Code schreiben, um das Endergebnis des Algorithmus oder die Zwischenergebnisse zu aktualisieren. Das Ergebnis ist deutlich umfangreicher als der Code aus Listing 1 und zudem wesentlich unverständlicher und schwieriger zu warten. Hinzu kommt das, was Phil Karlton zur Aussage veranlasst hat, Cache-Invalidierung sei eines der schwierigsten Probleme der Informatik: Wenn man die Zwischenergebnisse zu häufig verwirft, reduzieren sich die erhofften Performance-Vorteile oder verkehren sich sogar ins Gegenteil. Schlimmer noch: Wenn man die Zwischenergebnisse an einer Stelle vergisst zu invalidieren, dann kommt häufig ein geringfügig falsches Ergebnis heraus und damit ein subtiler, schwer zu findender Bug, den Tests mit hoher Wahrscheinlichkeit nicht aufspüren.

Dynamische Abhängigkeitsgraphen

Das Ziel von impliziter Inkrementalisierung ist es nun, eine inkrementelle Änderungsausbreitung für Algorithmen zu erreichen, ohne die Spezifikation des Algorithmus zu ändern. Hierzu bedient man sich eines Dynamischen Abhängigkeitsgraphen [3], der die Berechnungsschritte des Algorithmus mit den aktuellen Werten als Knoten zeigt. Im einfachsten und zugleich umfangreichsten Fall ist also jede Instruktion, die für den Algorithmus ausgeführt wird, ein Knoten im Graphen. Die Knoten können dann je nach Art der Instruktion typisiert werden, beispielsweise als explizite Knotentypen für den Zugriff auf Konstanten, binäre Operationen, Zugriff auf Properties etc. Jeder Knoten speichert außerdem seinen aktuellen Wert.

Die Kanten (also die Pfeile) kennzeichnen Datenabhängigkeiten zwischen den Berechnungsschritten. Ziel ist, dass es für jeden einzelnen Knoten möglich ist, zu bestimmen, wann sich der Berechnungsschritt wiederholen muss und was dann der aktuelle Wert ist. Der Umfang der einzelnen Schritte ist abhängig vom Inkrementalisierungssystem, meist auf der Abstraktionsebene eines Syntaxbaums: Knoten repräsentieren einzelne binäre Ausdrücke, Referenzen auf Properties oder Funktionsaufrufe.

Abbildung 2 zeigt einen Dynamischen Abhängigkeitsgraphen auf Instruktionsebene (in dem also jeder Knoten für die Ausführung genau einer Instruktion steht) für den Teilausdruck, dass das Eingangssignal einer Route auf GO steht. In dieser Abbildung ist auch die Änderungsausbreitung angedeutet, wenn das angezeigte Eingangssignal der Route von STOP auf FAILURE wechselt: Der Knoten, der den Zugriff auf die Property repräsentiert, wird neu ausgewertet, meldet weiter, dass sich sein Wert geändert hat, und benachrichtigt nachfolgende Knoten wie den anschließenden Gleichheitsoperator. Dieser Knoten prüft die Gleichheit, und da der Wert sich nicht ändert, ist die Änderungsausbreitung damit beendet.

Dynamische Abhängigkeitsgraphen können sich durch das Verarbeiten einer Änderung selbst umgestalten, beispielsweise können die rechten Seiten eines logischen Shorthand-Operators (also && oder ||) wegfallen oder neu entstehen, je nachdem, wie sich der Wert der linken Seite entwickelt.

Während für binäre Operatoren klar ist, wie sich das Ergebnis bei geänderten Eingabedaten ändert, ist das für Funktionsaufrufe zunächst unklar. Um auch Funktionsaufrufe in Dynamische Abhängigkeitsgraphen für eigene Funktionen zu integrieren, kann man für diese Funktionen Templates für Dynamische Abhängigkeitsgraphen anlegen und sie beim Aufruf der Funktion kopieren. Die Platzhalter für die Parameter werden dabei jeweils durch die Knoten des Arguments ersetzt.

Dynamische Abhängigkeitsgraphen können schnell sehr groß werden. Gleichzeitig ist der beste dynamische Algorithmus für ein Problem häufig ganz anders als ein Algorithmus, der das Problem ohne Berücksichtigung von Änderungen löst. Daher ist es vorteilhaft, für häufig verwendete Funktionen jeweils gezielt einen dynamischen Algorithmus zu hinterlegen, um so einen kleineren Dynamischen Abhängigkeitsgraphen zu erlangen, der weniger Speicher verbraucht, dabei aber Änderungen effizienter verarbeitet.

Um beispielsweise dynamisch die Summe einer Collection von Zahlen zu berechnen, ist es effizienter, eine hinzugefügte Zahl einfach zur letzten Summe zu addieren, als ab dem Index der eingefügten Zahl die Summe neu zu berechnen. Gerade wenn man Queries wie in Listing 1 betrachtet, ist klar, für welche Funktionen ein expliziter dynamischer Algorithmus besonders interessant ist: die Query-Operatoren, die die Syntax aus Listing 1 erst ermöglichen.

Implizite Inkrementalisierung in C#

Abbildung 2 zeigt ferner, dass die Erstellung eines Dynamischen Abhängigkeitsgraphen das Wissen um den Aufbau einer Funktion benötigt, idealerweise in Form eines abstrakten Syntaxbaums. Viele Ansätze zu impliziter Inkrementalisierung (zum Beispiel Self-adjusting Computation [3]) arbeiten daher als Compiler. Andere (beispielsweise Active Operations [4]) stellen lediglich eine API bereit, die es erlaubt, einen Dynamischen Abhängigkeitsgraphen zu erstellen, indem Entwickler den abstrakten Syntaxbaum dafür als Objektmodell angeben. C# erlaubt es, zur Laufzeit über die Expression-API einen abstrakten Syntaxbaum einer Funktion zu bekommen: Damit eine Funktion statt einer kompilierten Methode den Ausdrucksbaum eines Funktionsarguments bekommt, muss dieser als Expression deklariert sein.

Der C#-Compiler erlaubt es nun, Lambda-Ausdrücke implizit sowohl in einen passenden Delegattypen als auch einen Ausdruck dieses Delegattypen umzuwandeln, siehe Listing 4:

void Process(Func<T, bool> predicate); // kein Zugriff auf AST möglich
void Process(Expression<Func<T, bool>> predicate); // erlaubt Zugriff auf AST von predicate

Dieselbe Sprachtechnologie wird auch in LINQ eingesetzt, um C#-Queries nach SQL zu übersetzen.

Mit NMF Expressions [5] existiert eine Open-Source-Bibliothek, die das Erstellen solcher Dynamischer Abhängigkeitsgraphen über die Expressions-API implementiert. Aus historischen Gründen heißt die API dazu Observable.Expression. Um beispielsweise einen Dynamischen Abhängigkeitsgraphen zu erzeugen, der für eine gegebene Route prüft, ob das Eingangssignal auf GO steht, eignet sich der Code aus Listing 5:

var expression = Observable.Expression(
  () => route.Entry != null && route.Entry.Signal == Signal.GO);

expression.ValueChanged += …

Das Ergebnis dieses Aufrufs ist eine Instanz von INotifyValue, was sehr ähnlich definiert ist wie in Listing 2. Insbesondere bietet diese Instanz einen Property Value, über den sich der jeweils aktuelle Wert abrufen lässt (der durch einen Dynamischen Abhängigkeitsgraphen stets aktuell gehalten wird) sowie ein Event, das ausgelöst wird, sobald sich das zugrundeliegende Modell so ändert, dass die Auswertung des Ausdrucks ein anderes Ergebnis haben würde.

Um das Erstellen der Dynamischen Abhängigkeitsgraphen zu beschleunigen und den Einsatz flexibler zu gestalten, definiert NMF Expressions äquivalent zu den Delegattypen Func eine Familie von Klassen ObservingFunc, die jeweils einen Funktionsausdruck bekommen und daraus ein Template für einen Dynamischen Abhängigkeitsgraphen erstellen, der wieder über die Schnittstellen INotifyPropertyChanged und INotifyCollectionChanged Änderungen am Datenmodell abruft und diese dann inkrementell propagiert.

Dazu kann man mittels der Methode Observe etwaige Platzhalter für Parameter im Graphen entweder mit einem eigenen Knoten oder mit einer Konstante ersetzen lassen. Um die Syntax zu vereinfachen, existiert auch hier eine API, die mit statischen Methoden die Typinferenz verbessert.

Alternativ zu Listing 5 bietet sich daher der Code aus Listing 6 an, um einen Dynamischen Abhängigkeitsgraphen zu erstellen, der prüft, ob das Eingangssignal auf GO steht. Diese Form hat zudem den Vorteil, dass das Framework Optimierungen treffen kann und Analysen von Methoden nur einmal durchführen muss. Listing 6:

var entryCheck = Observable.Func(
    (IRoute route) => route.Entry != null && route.Entry.Signal == Signal.GO);

var expression = entryCheck.Observe(route);

NMF Expressions implementiert außerdem dynamische Algorithmen für viele der Query-Operatoren der C#-Query-Syntax. Damit ist es möglich, die Beispielanalyse aus Listing 1 beizubehalten und aus der Spezifikation dieser Query einen inkrementellen Algorithmus zu bekommen, der einen Dynamischen Abhängigkeitsgraphen erzeugt. Damit lassen sich Änderungen der Ergebnisse nicht nur schnell berechnen, sondern auch Events auslösen, sobald sich Änderungen des Modells auf das Ergebnis einer Query auswirken.

Ungewisser Performancegewinn

Leider lässt sich keine allgemeine Aussage zur Performance von inkrementalisierten Algorithmen treffen. Sie und die algorithmische Komplexität hängen wesentlich von den verwendeten dynamischen Algorithmen, aber auch von der Art und Implikationen der Änderungen ab. Manche Änderungen betreffen einen dynamischen Algorithmus gar nicht und verursachen daher auch keinen Aufwand, andere betreffen hingegen eine Verzweigung, die die Neuberechnung eines großen Teils erfordert. Um den Aufwand abschätzen zu können, muss man daher klären, wie viel die jeweilige Änderung bewirkt. Wenn ein großer Teil einer Berechnung sehr häufig wiederholt werden muss, lohnt sich die Wartung eines Dynamischen Abhängigkeitsgraphen vielleicht nicht.

Gerade bei Queries auf Aufzählungen, bei denen die Reihenfolge keine Rolle spielt, gibt es sehr viele sehr effiziente dynamische Algorithmen. Wenn sich für ein Element die Filterbedingung oder das Selektionsergebnis ändert, hat das auf die Berechnung der Filterbedingung der anderen Elemente keine Auswirkungen, sofern die Berechnung keine Seiteneffekte erzeugt. Hier lassen sich oft hohe Beschleunigungen erreichen, weil die Änderungen nur die Teile der Analyse neu berechnen, die tatsächlich von der Änderung betroffen sind. Sind das nur wenige Elemente im Vergleich zur Gesamtzahl, sind den möglichen Beschleunigungen kaum Grenzen gesetzt.

Das haben auch Benchmarks gezeigt [2], [5]. Bei der Analyse aus Listing 1 wurden so Beschleunigungen mit Faktor 100 und mehr gemessen. Bei anderen Analysen kann es jedoch zu Schmetterlingseffekten kommen, dass also bestimmte Arten von Änderungen dazu führen, dass so oder so die komplette Analyse neu berechnet werden muss.

Der Preis dieser Beschleunigungen drückt sich in der Regel durch einen höheren Speicherverbrauch für viele Zwischenergebnisse aus. Da aber für die implizite Inkrementalisierung kaum ein Entwicklungsaufwand entsteht und Speicher einfacher skaliert als insbesondere sequenzielle Rechenleistung, ergeben sich große Vorteile.

Eigene Funktionen

NMF Expressions erlaubt es, eigene Funktionen zu definieren und sie durch geeignete dynamische Algorithmen manuell zu inkrementalisieren – auf diese Weise sind viele der bestehenden Query-Operatoren darin umgesetzt. Hierzu arbeitet NMF Expressions mit dem Attribute ObservableProxy. Soll beispielsweise die Prüfung, ob ein Eingangssignal GO zeigt, in eine eigene Funktion ausgelagert sein, muss über das ObservableProxy-Attribut eine Funktion angegeben werden, die die eigene Funktion manuell inkrementalisiert. Der Hauptgrund dafür ist, dass NMF Expressions keinen Zugriff mehr auf den abstrakten Syntaxbaum bekommt. Listing 7 zeigt ein Beispiel:

[ObservableProxy(nameof(IsEntrySignalGoInc))]
public bool IsEntrySignalGo(IRoute route)
 => route.Entry != null && route.Entry.Signal == Signal.GO;

public INotifyValue<bool> IsEntrySignalGoInc(IRoute route) { … }

Daher ist die manuelle Inkrementalisierung nicht optional: Fehlt das ObservableProxy-Attribut an einer Methode, wertet NMF Expressions die Methode nur neu aus, wenn sich die Argumente geändert haben. Die einzige Ausnahme ist, wenn die Argumente die Schnittstelle INotifyCollectionChanged unterstützen. Für die meisten Bibliotheken der Standardbibliothek ist diese Heuristik ausreichend, da viele Basisdatentypen wie Zeichenketten, Zeitstempel oder Zahlen in .NET unveränderlich sind. Bei eigenen Funktionen muss jedoch häufig ein Proxy über das Attribut ObservableProxy angegeben werden, der die eigene Funktion manuell inkrementalisiert.

Fazit

Implizite Inkrementalisierung, beispielsweise über Dynamische Abhängigkeitsgraphen, erlauben es, sehr einfach inkrementelle Änderungsausbreitung zu implementieren, indem man den Algorithmus aus dynamischen Algorithmen mit einem Dynamischen Abhängigkeitsgraphen zusammensetzt. Dadurch lassen sich Events implementieren, die automatisch ausgelöst werden, sobald sich ein Wert ändert. Die inkrementelle Änderungsausbreitung ist zudem häufig sehr viel schneller als eine komplette Neuberechnung. Diese Performance-Vorteile sind aber abhängig von der Analyse, und Entwicklerinnen und Entwickler sollten abwägen, ob sich der Einsatz lohnt. Der Nachteil: Es wird mehr Speicher benötigt und eigene Funktionen erfordern eine explizite Annotierung.

Literatur

1. G. Szárnyas, O. Semeráth und I. Ráth, "The TTC 2015 Train Benchmark Case for Incremental Model Validation", in Proceedings of the 8th Transformation Tool Contest, L'Aquila, 2015, S. 129-141.
2. G. Hinkel, Implicit Incremental Model Analyses and Transformations, Karlsruhe: KIT Scientific Publishing, 2018.
3. U. Acar, "Self-adjusting computation:(an overview)", in Proceedings of the 2009 ACM SIGPLAN workshop on Partial evaluation and program manipulation, ACM, 2009, S. 1-6.
4. T. Le Calvar, F. Jouault, F. Chhel und M. Clavreul, "Efficient ATL Incremental Transformations", Journal of Object Technology, Bd. 18, Nr. 3, S. 1-17, 2019.
5. G. Hinkel, R. Heinrich und R. Reussner, "An extensible approach to implicit incremental model analyses", Software & Systems Modeling, Nr. 18, S. 3151-3187, 2019.

(who)