Incremental – Eine Bibliothek für inkrementelle Berechnungen

• Incremental ist eine Bibliothek, die dabei unterstützt, komplexe Berechnungen effizient zu aktualisieren, wenn sich Eingaben ändern
• Inspiriert von der Forschung zu self-adjusting computation von Umut Acar und anderen
• Große Berechnungen wie in Tabellenkalkulationen lassen sich so aufbauen, dass sie effizient auf Datenänderungen reagieren
• Neue Daten lassen sich effizient in die Views von GUI-Anwendungen übernehmen
• Es kann sichergestellt werden, dass abgeleitete Daten fortlaufend mit den Quelldaten synchron bleiben, etwa bei der Umkehrung von Filterungen oder Mappings

---

Einsatzgebiete

• Komplexe Berechnungen als Reaktion auf sich ändernde Eingaben effizient aktualisieren
• Große Berechnungen in Tabellenkalkulationsform so aufbauen, dass sie auf Datenänderungen reagieren
• Neue Daten effizient in GUI-Views integrieren
• Aus dem Original berechnete abgeleitete Daten kontinuierlich synchron halten
  • Datenfilterung
  • Umkehrung von Mappings

Designhintergrund und Dokumentation

• Inspiriert von der Forschung zu self-adjusting computation von Umut Acar und anderen
• Detaillierte API und Nutzung sind in incremental/src/incremental_intf.ml zu finden
• Als inoffizielles Einstiegsmaterial werden ein Blogbeitrag und ein Einführungsvideo angeboten

[GN⁺]

Hacker-News-Kommentare

• Diese Art von reaktiver Programmierung wird in JavaScript-UI-Frameworks heutzutage weithin unter dem Namen Signals verwendet, und es gibt auch einen Standardisierungsvorschlag
  Vue, SolidJS, Svelte, Ember und Angular verwenden sie, und für React gibt es Implementierungen wie MobX und Jotai. Es gibt auch verschiedene Algorithmen für Änderungspropagation und die Auswertung gerichteter azyklischer Graphen (DAGs), und soweit ich weiß, verwendet SolidJS 2 einen höhenbasierten Algorithmus ähnlich wie Incremental
  Ich experimentiere mit einer Implementierung, die Knoten in einer Int32Array-Arena allokiert und über verkettete Listen verbindet, um GC-Last proportional zur Anzahl der Abhängigkeitskanten zu vermeiden
  Auch in Rust gibt es mehrere Implementierungen; als UI-Framework etwa Leptos und als allgemeines System für inkrementelle Berechnung, das von rust-analyzer genutzt wird, Salsa. Man kann das auch als Build-System mit automatischer Verfolgung von Abhängigkeiten sehen; tup instrumentiert Build-Jobs, erkennt, welche Dateien gelesen werden, und richtet Abhängigkeitsbeziehungen ein. Lesenswert sind auch der Artikel des Autors und der Klassiker Build Systems à la Carte

  • Man kann einen leichtgewichtigen Abhängigkeitsgraphen bauen, der sich schnell leeren lässt. Man muss nicht einmal beschreiben, wie sich ein Signal verändert hat, sondern nur markieren, dass es sich möglicherweise geändert hat; bei einer Änderung leert man das Abhängigkeitsziel und registriert es neu, wenn neue Daten angefordert werden. Dabei kann es vorkommen, dass manche Subscriber Benachrichtigungen über Änderungen erhalten, die sie nicht mehr interessieren
    Allerdings sind inkrementelle Berechnung und Functional Reactive Programming (FRP) tatsächlich unterschiedliche Bereiche. Inkrementelle Berechnung leitet explizit Funktionen her, die auf Deltas arbeiten, während FRP auch nur den Ansatz verwenden kann, beschädigte Teile zu finden und zu reparieren
  • Ein weiteres wichtiges Beispiel ist JetBrains Noria. Das Wesentliche an Noria ist nicht ein UI-Framework, sondern eine Plattform für inkrementelle Berechnung; derzeit wird sie jedoch zur Optimierung des GUI-Renderings in JetBrains Air IDE eingesetzt
  • Bei der Verarbeitung von Aktualisierungen komplexer Objekte scheint es erhebliche Unterschiede zu geben, und auch das Scheduling dürfte anders sein

• Die Incremental-Bibliothek scheint das Problem lösen zu wollen, den Berechnungsgraphen teilweise neu zu konkretisieren, wenn sich die Quelldaten ändern. Das ähnelt einem gut entworfenen Build-System und ist auch in der funktionalen Programmierung ein nützlicher, häufig verwendeter Ansatz
  Im Bereich inkrementeller Berechnung gibt es außerdem Differential Dataflow, die benachbarte Technologie Timely Dataflow und DBSP. Feldera basiert auf DBSP, und Materialize wird von Beteiligten aus dem Umfeld von Differential Dataflow geführt
  Ich entwickle einen separaten Ansatz namens modolap, der auf Finanzdaten und entsprechende Workloads spezialisiert ist. Es gibt viele große und wichtige Probleme zu lösen. In diesem Zusammenhang ist auch die Episode über Build-Systeme von Signals and Threads hörenswert

  • Es ist ziemlich gewagt, dass ein Klick auf den Hauptbutton von modolap ohne jede Erklärung direkt zu einer Stripe-Zahlung über 2.000 Dollar führt
  • openivm ist ein SQL-zu-SQL-Compiler, der umfangreiche Aggregationsoperationen als inkrementelle Operationen implementiert, und bietet außerdem eine DuckDB-Erweiterung zur automatischen Pflege materialisierter Sichten

• Goldman nutzte denselben Ansatz schon vor etwa 30 Jahren für die Preisberechnung von Finanzprodukten. Während meiner rund 13 Jahre dort erinnere ich mich an lange Diskussionen über Node Purpling
  Die Informatik hat Fortschritte gemacht, und soweit ich das sehe, ist das kein Graph-Ansatz, aber Berechnungen wie Differenzierung sind teuer, daher muss man die Anzahl der Ausführungen so weit wie möglich an das theoretische Minimum heranbringen. Dazu gibt es auch eine HN-Diskussion

  • Dadurch entstand informell eine Umgebung, die als bank python bekannt war, und dieser Artikel beschreibt sie gut
    Die Passage, dass schon der Anblick der proprietären internen IDE einen so wütend macht, dass man kündigen möchte, und dass Neue ungewöhnlich lange brauchen, um sich einzuarbeiten, wobei sie selbst nach Monaten noch grundlegend andere Dinge lernen müssen, beschreibt das Problem am treffendsten. Auch ich brauchte etwa zweieinhalb Jahre, um vollständig zu verstehen, woran ich arbeitete
    Moderne Schulungen gab es fast gar nicht, bis man erkannte, dass neu geschult werden musste. Am schlimmsten war das Coding zum Erstellen von UIs, und für neue Projekte wurde der Einsatz nicht genehmigt

• Einer meiner liebsten Tech-Talks ist Seven Implementations of Incremental: https://www.janestreet.com/tech-talks/seven-implementations-of-incremental/

• Ich hatte vor einigen Jahren großes Interesse an Dataflow-Programmierung, und es scheint, als hätten viele dieses Problem aus verschiedenen Richtungen angegangen. Als ich diese Bibliothek sah, musste ich sofort an Javelin aus Clojure denken

• Wenn es dich interessiert, ist auch die auf Incremental aufgebaute UI-Bibliothek Bonsai einen Blick wert
  Bibliotheken wie React überspringen mit einem virtuellen DOM effizient unnötige Arbeit, aber auch das Erzeugen des virtuellen DOM kostet Zeit. Bonsai arbeitet sogar daran, selbst das virtuelle DOM inkrementell zu machen, und das macht Spaß
  Ich habe eine Desktop-UI-Bibliothek für das inzwischen nicht mehr gepflegte Revery gebaut, sie verwendet jedoch eine ziemlich alte Version von Bonsai

• Ich habe noch nicht ganz verstanden, worin sich das von dem Observable-Pattern unterscheidet, bei dem neue Werte an den Input veröffentlicht, durch die Berechnung geleitet und neue Ergebnisse an Abonnenten weitergegeben werden.
  Es gäbe zwar Optimierungen durch Änderungserkennung und das Stoppen der Weitergabe, wenn ein Wert unverändert bleibt, aber das ist auch bei Observables möglich. Auch der Teil mit stabilize, bei dem Änderungen vor der Neuberechnung gebündelt werden, ist interessant, lässt sich aber ebenfalls mit Observables umsetzen.
  Ich frage mich, ob der entscheidende Unterschied in der automatischen Konstruktion des Berechnungsgraphen durch interne Analyse liegt oder ob es etwas Grundsätzlicheres gibt.

  • Das hängt davon ab, wie man das Observable-Pattern definiert. Das Grundlegende hier sind Lazy Evaluation und schwache Verbindungen zwischen den Graphknoten. Knotenwerte werden nur beim Beobachten materialisiert, und auch Änderungen an der Graphstruktur zur Laufzeit lassen sich flexibel handhaben.
    Wenn nur einige Knoten beobachtet werden, muss nicht der gesamte Graph materialisiert werden. Man kann die Berechnung jederzeit unterbrechen, den Graphen nur teilweise aktualisiert lassen, anschließend die Inputs weiter ändern und dann die Materialisierung der interessierenden Knoten fortsetzen; der Algorithmus räumt alle Änderungen korrekt auf.
    Inkrementelle Berechnung ist im Kern ein Oberbegriff für Eigenschaften dieser Art, und dasselbe System kann auch als Beobachter-/Subscriber-Modell aufgebaut sein. Ein klassisches Excel-Spreadsheet ist ein gutes Beispiel; siehe auch Erklärung des Salsa-Algorithmus.
  • Grob gesagt abonniert man bei Observables ein Objekt und lauscht auf Werte, während Incremental eher einem Cache über die gesamte DAG aus Berechnung und Zustand ähnelt. So lässt sich optimieren, indem nur die benötigten Teile neu berechnet werden.
    Der Vortrag von Ron Minsky ist sehr gut.
  • Dieser Artikel hilft dabei, die Landschaft inkrementeller und Streaming-Systeme zu verstehen.
  • Ich hatte einen ähnlichen Eindruck. Auf den ersten Blick wirkt es reaktivem Programmieren mit Abhängigkeitsverfolgung sehr ähnlich. Ich frage mich, ob der eigentliche Vorteil in der API-Benutzbarkeit liegt oder in internen Optimierungen, die mit einer allgemeinen Observable-Implementierung praktisch schwer zu erreichen sind.
  • Im Kern geht es tatsächlich um einen Graphen, aber darum, Änderungen in einem riesigen und dynamisch veränderlichen Graphen korrekt und effizient zu berechnen.
    Man kann sich einen diamantförmigen Teilgraphen vorstellen, der sich in Hunderte Zwischenknoten verzweigt und nach unterschiedlich langen Pfaden wieder zusammenläuft. Auf einigen Pfaden könnte min(A, B) liegen, wobei sich nur die Maximal-Seite ändert.
    Ein einfacher Observer-Ansatz kann dann potenziell exponentiell im Rechenaufwand explodieren und außerdem Konkurrenzprobleme verursachen. Diese Bibliothek bleibt auch bei dynamischen Änderungen der Graphstruktur korrekt und nahe am Optimum. Mit Observers oder Ähnlichem kann man zwar zum selben Ergebnis kommen, aber es ist deutlich schwerer, das korrekt umzusetzen, ohne in Performance-Klippen zu geraten.

• Der Vorteil von Jane-Street-Projekten besteht darin, dass sie Ideen aus Forschung oder Nischensystemen in eine Form verpacken, die Entwickler tatsächlich nutzen können. Selbst wenn man die Bibliothek nicht einführt, sind die Design-Dokumente meist lesenswert.

• Electric Clojure bietet inkrementelles Rendering über die Client-Server-Grenze hinweg. Am ähnlichsten ist aus meiner Sicht SolidJS, wobei SolidJS nur das Frontend abdeckt.

• Ich hatte früher einmal etwas Ähnliches gebaut und dabei kaum Vorläufer gefunden. Der Anwendungszweck ist weggefallen, deshalb habe ich das Projekt eingestellt, würde es mir aber gern noch einmal ansehen; auf npm existiert es noch unter dem Namen data-rambler.
  Die Idee war, Datenströme in eine domänenspezifische Sprache (DSL) einzuspeisen, die sich in eine JavaScript-Laufzeit laden ließ. Module wandelten Daten in mehrere Ausgabeströme um, die dann an eine separate Reporting-Bibliothek weitergegeben wurden, um vorlagenbasierte dynamische Berichte zu erzeugen.
  Schon die erste Version war ziemlich leistungsfähig, aber es gab große Pläne, sie mit einer JavaScript-artigeren Syntax zu verbessern, um die Komplexität zu reduzieren.