Incremental — une bibliothèque pour le calcul incrémental

• Incremental est une bibliothèque qui permet de mettre à jour efficacement des calculs complexes lorsque les entrées changent
• Elle s’inspire des travaux d’Umut Acar et d’autres sur le calcul auto-ajustable (self-adjusting computation)
• Elle permet d’organiser de grands calculs, comme des feuilles de calcul, afin qu’ils réagissent efficacement aux changements de données
• Elle peut refléter efficacement de nouvelles données dans les vues d’applications GUI
• Elle permet de garantir que des données dérivées, comme le filtrage ou l’inversion de transformations de mapping, restent synchronisées avec les données d’origine

---

Domaines d’utilisation

• Met à jour efficacement des calculs complexes en réponse à des entrées changeantes
• Permet d’organiser de grands calculs de type feuille de calcul pour qu’ils réagissent aux changements de données
• Permet d’intégrer efficacement de nouvelles données dans des vues GUI
• Synchronise en continu les données dérivées calculées à partir des données d’origine
  • Filtrage de données
  • Inversion de transformations de mapping

Contexte de conception et documentation

• Inspiré des travaux d’Umut Acar et d’autres sur le calcul auto-ajustable
• L’API détaillée et son utilisation sont disponibles dans incremental/src/incremental_intf.ml
• Des ressources d’introduction non officielles sont proposées sous forme de billet de blog et de vidéo de présentation

[GN⁺]

Avis sur Hacker News

• Ce type de programmation réactive est aujourd’hui largement utilisé dans les frameworks d’UI JavaScript sous le nom de signals, et une proposition de standardisation est en cours
  Vue, SolidJS, Svelte, Ember et Angular les utilisent, et React dispose d’implémentations comme MobX et Jotai. Il existe aussi plusieurs algorithmes de propagation des changements et d’évaluation de graphes orientés acycliques (DAG), et il me semble que SolidJS 2 utilise un algorithme fondé sur la hauteur, similaire à Incremental
  J’expérimente une implémentation où les nœuds sont alloués dans une arène Int32Array et reliés par des listes chaînées afin d’éviter une charge de GC proportionnelle au nombre d’arêtes de dépendance
  Il existe aussi plusieurs implémentations en Rust ; côté frameworks d’UI, il y a Leptos, et, comme système généraliste de calcul incrémental utilisé par rust-analyzer, Salsa. On peut aussi voir cela comme un système de build qui suit automatiquement les dépendances : tup instrumente les tâches de build pour détecter les fichiers lus et établir les relations de dépendance. L’article de son auteur et le classique Build Systems à la Carte valent aussi la lecture

  • On peut construire un graphe de dépendances léger, facile à vider rapidement. Il n’est pas nécessaire de décrire précisément comment un signal a changé : il suffit d’indiquer qu’il a peut-être changé, puis, lors d’un changement, de vider ses dépendants et de les réenregistrer quand de nouvelles données sont demandées. Dans ce processus, certains abonnés peuvent être notifiés de changements qui ne les intéressent plus
    Cela dit, le calcul incrémental et la programmation réactive fonctionnelle (FRP) relèvent en réalité de domaines différents. Le calcul incrémental dérive explicitement des fonctions qui opèrent sur des deltas, tandis que la FRP peut se contenter de trouver les parties invalidées et de les réparer
  • Un autre exemple majeur est JetBrains Noria. Le cœur de Noria n’est pas un framework d’UI, mais une plateforme de calcul incrémental ; aujourd’hui, elle sert toutefois à optimiser le rendu de l’interface graphique de JetBrains Air IDE
  • Il semble y avoir des différences importantes dans la gestion des mises à jour d’objets complexes, et l’ordonnancement est probablement différent lui aussi

• La bibliothèque Incremental semble chercher à résoudre le problème de rematérialisation partielle d’un graphe de calcul lorsque les données sources changent. C’est une approche utile, proche de celle des systèmes de build bien conçus, et courante aussi en programmation fonctionnelle
  Dans le domaine du calcul incrémental, on trouve aussi Differential Dataflow, la technologie voisine Timely Dataflow, ainsi que DBSP. Feldera repose sur DBSP, et Materialize est dirigé par des personnes issues de Differential Dataflow
  Je développe modolap, une approche distincte spécialisée dans les données et charges de travail financières. Il reste beaucoup de problèmes importants à résoudre. À ce sujet, l’épisode sur les systèmes de build de Signals and Threads mérite aussi d’être consulté

  • Cliquer sur le bouton principal de modolap et être envoyé sans explication vers un paiement Stripe de 2 000 dollars, c’est assez audacieux
  • openivm est un compilateur SQL-to-SQL qui implémente un large éventail d’opérations d’agrégation sous forme d’opérations incrémentales, et fournit aussi une extension DuckDB pour maintenir automatiquement des vues matérialisées

• Goldman utilisait déjà une approche similaire il y a environ 30 ans pour la valorisation de produits financiers. Pendant les quelque 13 ans que j’y ai passés, je me souviens de longues discussions autour du Node Purpling
  L’informatique a progressé et, à mon avis, ce n’est pas une approche par graphe, mais les calculs comme les dérivées sont coûteux, donc il faut réduire le nombre d’exécutions aussi près que possible du minimum théorique. Il existe aussi une discussion HN à ce sujet

  • Cela a donné naissance à un environnement officieusement appelé bank python, que cet article décrit bien
    Le passage qui décrit le mieux le problème est celui où, même si l’on ne démissionne pas de rage à la vue de l’IDE interne dédié, il faut anormalement longtemps aux nouveaux arrivants pour s’adapter, et même après plusieurs mois ils doivent encore apprendre des éléments fondamentalement différents. Il m’a fallu environ deux ans et demi pour comprendre pleinement ce sur quoi je travaillais
    Il n’y avait quasiment pas non plus de formation moderne, jusqu’à ce qu’ils se rendent compte qu’il fallait reformer les gens. Le pire était le code à écrire pour créer l’UI, et il n’était pas approuvé pour les nouveaux projets

• L’une de mes présentations techniques préférées est Seven Implementations of Incremental : https://www.janestreet.com/tech-talks/seven-implementations-of-incremental/

• Il y a quelques années, je m’intéressais beaucoup à la programmation dataflow, et j’ai l’impression que beaucoup de gens ont abordé ce problème par différents angles. En voyant cette bibliothèque, j’ai immédiatement pensé à Javelin de Clojure

• Si le sujet vous intéresse, la bibliothèque d’UI Bonsai, construite au-dessus d’Incremental, vaut aussi le détour
  Les bibliothèques comme React évitent efficacement du travail inutile grâce au DOM virtuel, mais la création du DOM virtuel elle-même prend aussi du temps. Bonsai rend même le DOM virtuel incrémental, et il est aussi agréable à utiliser
  J’ai créé une bibliothèque d’UI desktop pour Revery, qui n’est plus maintenu aujourd’hui, mais elle utilise une version assez ancienne de Bonsai

• Je n’ai pas entièrement compris en quoi cela diffère du patron observable, qui publie une nouvelle valeur en entrée, effectue le calcul puis transmet le nouveau résultat aux abonnés.
  Il y a sans doute de la détection de changements et une optimisation qui interrompt la propagation quand la valeur reste identique, mais les observables peuvent aussi le faire. Le fait de regrouper les changements avant le recalcul avec stabilize est intéressant, mais là encore c’est implémentable avec des observables.
  Je me demande si la différence clé tient à la construction automatique du graphe de calcul par introspection interne, ou s’il y a quelque chose de plus fondamental.

  • Cela dépend de la façon dont on définit le patron observable. Ici, l’élément fondamental est l’évaluation paresseuse et le couplage faible entre les nœuds du graphe. La valeur d’un nœud n’est matérialisée que lorsqu’elle est observée, et les changements de structure du graphe pendant l’exécution sont gérés avec souplesse.
    Quand seuls certains nœuds sont observés, il n’est pas nécessaire de matérialiser tout le graphe. On peut aussi interrompre le calcul à tout moment, laisser le graphe dans un état seulement partiellement mis à jour, modifier encore les entrées, puis poursuivre la matérialisation des nœuds qui nous intéressent ; l’algorithme se charge de remettre de l’ordre dans tous les changements.
    Le calcul incrémental est, par nature, un terme qui englobe ce type de propriétés, et on pourrait aussi construire le même système avec un modèle observateur/abonné. Un tableur Excel classique en est un bon exemple, et l’explication de l’algorithme Salsa vaut aussi le détour.
  • En gros, les observables consistent à s’abonner à une cible et à écouter ses valeurs, tandis qu’Incremental ressemble davantage à un cache à l’échelle d’un DAG de calculs et d’états. On peut l’optimiser en ne recalculant que les parties nécessaires.
    La présentation de Ron Minsky est excellente.
  • Cet article aide à comprendre le paysage des systèmes incrémentaux et de streaming.
  • J’ai pensé un peu la même chose. À première vue, cela paraît très proche de la programmation réactive avec suivi des dépendances. Je me demande si le vrai avantage réside dans l’ergonomie de l’API, ou dans des optimisations internes qui seraient difficilement réalisables en pratique avec une implémentation classique d’observables.
  • Fondamentalement, c’est bien un graphe, mais il s’agit de calculer les changements correctement et efficacement dans un graphe immense et dynamique.
    On peut imaginer un sous-graphe en diamant qui se divise en centaines de nœuds intermédiaires, puis se rejoint après des chemins de longueurs différentes. Certains chemins peuvent contenir min(A, B), avec uniquement la valeur maximale qui change.
    Une approche simple par observateurs risque de faire exploser la quantité de calcul de manière potentiellement exponentielle et de provoquer aussi des problèmes de concurrence. Cette bibliothèque reste correcte et proche de l’optimal même quand la structure du graphe change dynamiquement. On peut obtenir le même résultat avec des observateurs ou autre, mais l’implémenter correctement tout en évitant les falaises de performance est beaucoup plus difficile.

• L’intérêt des projets de Jane Street, c’est qu’ils emballent des idées venues de la recherche ou de systèmes de niche sous une forme réellement utilisable par les développeurs. Même si l’on n’adopte pas la bibliothèque, les documents de conception valent généralement la peine d’être lus.

• Electric Clojure fournit du rendu incrémental à travers la frontière client-serveur. Ce qui s’en rapproche le plus est, à mon avis, SolidJS, mais SolidJS ne concerne que le front-end.

• J’avais créé quelque chose de similaire il y a quelque temps, sans presque trouver de précédents. L’usage prévu a disparu, donc j’ai arrêté le projet, mais j’aimerais y rejeter un œil ; il reste sur npm sous le nom data-rambler.
  L’idée était d’alimenter des flux de données dans un langage spécifique au domaine (DSL) chargeable dans un runtime JavaScript. Le module transformait les données en plusieurs flux de sortie, transmis ensuite à une bibliothèque de rapports séparée pour générer des rapports dynamiques à base de templates.
  Dès la première version, c’était déjà assez puissant, mais j’avais aussi de grands projets pour améliorer la syntaxe dans un style plus JavaScript afin de réduire la complexité.