Incremental - biblioteca para cálculo incremental

• Incremental es una biblioteca que permite actualizar de forma eficiente cálculos complejos cuando cambian las entradas
• Está inspirada en la investigación sobre self-adjusting computation de Umut Acar y otros
• Puede usarse para que cálculos a gran escala, como los de una hoja de cálculo, reaccionen eficientemente a cambios en los datos
• Puede reflejar de forma eficiente nuevos datos en las vistas de aplicaciones GUI
• Puede garantizar que los datos derivados sigan sincronizados continuamente con los datos originales, como en la transformación inversa de filtrados o mapeos

---

Áreas de uso

• Actualiza de forma eficiente cálculos complejos en respuesta a cambios en las entradas
• Puede configurarse para que cálculos masivos con formato de hoja de cálculo reaccionen a cambios en los datos
• Puede integrar eficientemente nuevos datos en vistas GUI
• Mantiene sincronizados de forma continua los datos derivados calculados a partir del original
  • Filtrado de datos
  • Transformación inversa de mapeos

Contexto de diseño y documentación

• Está inspirada en la investigación sobre self-adjusting computation de Umut Acar y otros
• La API detallada y la forma de uso pueden consultarse en incremental/src/incremental_intf.ml
• Como material introductorio no oficial, ofrece una publicación de blog y un video de introducción

[GN⁺]

Comentarios de Hacker News

• Este tipo de programación reactiva se usa mucho hoy en los frameworks de UI de JavaScript bajo el nombre de signals, y también está en marcha una propuesta de estandarización
  Vue, SolidJS, Svelte, Ember y Angular lo usan, y en React hay implementaciones como MobX y Jotai. También existen varios algoritmos de propagación de cambios y evaluación de grafos acíclicos dirigidos (DAG), y tengo entendido que SolidJS 2 usa un algoritmo basado en alturas parecido a Incremental
  Estoy experimentando con una implementación que asigna nodos en una arena Int32Array y los enlaza con listas ligadas para evitar una carga de GC proporcional al número de aristas de dependencia
  En Rust también hay varias implementaciones; como framework de UI está Leptos, y como sistema general de cálculo incremental usado por rust-analyzer está Salsa. Esto también puede verse como un sistema de build con seguimiento automático de dependencias: tup instrumenta las tareas de build para detectar qué archivos se leen y establecer relaciones de dependencia. También vale la pena leer el artículo del autor y el clásico Build Systems à la Carte

  • Se puede crear un grafo de dependencias ligero que pueda vaciarse rápidamente. No hace falta describir siquiera cómo cambió una signal; basta con marcar que pudo haber cambiado, vaciar los objetivos dependientes cuando haya cambios y volver a registrarlos al pedir los datos nuevos. En este proceso, algunos suscriptores podrían recibir notificaciones de cambios que ya no les interesan
    Aun así, el cálculo incremental y la programación reactiva funcional (FRP) en realidad son áreas distintas. El cálculo incremental deriva explícitamente funciones que operan sobre deltas, mientras que FRP también puede usar solo un enfoque de detectar y reparar las partes dañadas
  • Otro ejemplo importante es JetBrains Noria. El núcleo de Noria no es un framework de UI sino una plataforma de cálculo incremental, pero actualmente se usa para optimizar el renderizado GUI del IDE JetBrains Air
  • Parece haber diferencias importantes en el manejo de actualizaciones de objetos complejos, y probablemente también en la planificación

• La librería Incremental parece intentar resolver el problema de reconcretizar parcialmente el grafo de cálculo cuando cambian los datos originales. Es un enfoque útil, parecido a un sistema de build bien diseñado, y también muy usado en programación funcional
  En el área del cálculo incremental también están Differential Dataflow, la tecnología vecina Timely Dataflow y DBSP. Feldera está basado en DBSP y Materialize está liderado por gente de Differential Dataflow
  Yo estoy desarrollando modolap, un enfoque aparte especializado en datos y cargas de trabajo financieras. Hay muchos problemas grandes e importantes por resolver. Sobre esto también vale la pena revisar el episodio sobre sistemas de build de Signals and Threads

  • Es bastante atrevido que al presionar el botón principal de modolap te mande a un pago de Stripe de 2,000 dólares sin ninguna explicación
  • openivm es un compilador SQL-to-SQL que implementa una amplia gama de operaciones de agregación como operaciones incrementales, y también ofrece una extensión de DuckDB que mantiene automáticamente vistas materializadas

• Goldman también usó este mismo enfoque para fijar precios de instrumentos financieros hace unos 30 años. Recuerdo largas discusiones sobre Node Purpling durante mis aproximadamente 13 años trabajando ahí
  La informática ha avanzado y, a mi parecer, esto no es un enfoque basado en grafos, pero cálculos como las derivadas son costosos, así que hay que reducir la cantidad de ejecuciones lo más cerca posible del mínimo teórico. También hay una discusión en HN relacionada

  • Esto llevó a la aparición de un entorno conocido informalmente como bank python, y este artículo lo explica bien
    La parte que mejor describe el problema es cuando dice que, en cuanto ves el IDE interno dedicado, te dan ganas de renunciar; incluso si no lo haces, a un nuevo le toma un tiempo inusualmente largo adaptarse, y aun después de varios meses sigue aprendiendo elementos fundamentalmente distintos. A mí también me tomó unos dos años y medio entender por completo en qué trabajaba
    Casi no había capacitación moderna hasta que se dieron cuenta de que tenían que volver a capacitar. Lo peor era programar para construir la UI, y su uso no estaba aprobado para proyectos nuevos

• Una de mis charlas técnicas favoritas es Seven Implementations of Incremental: https://www.janestreet.com/tech-talks/seven-implementations-of-incremental/

• Hace unos años tenía mucho interés en la programación de flujo de datos, y parece que mucha gente abordó este problema desde varias direcciones. Al ver esta librería, de inmediato pensé en Javelin de Clojure

• Si te interesa, también vale la pena ver la librería de UI Bonsai, construida sobre Incremental
  Librerías como React omiten eficientemente trabajo innecesario con un DOM virtual, pero construir ese DOM virtual también toma tiempo. Bonsai incluso incrementaliza el DOM virtual, y también es divertido trabajar con él
  Yo hice una librería de UI de escritorio para Revery, que ahora ya no tiene mantenimiento, pero usa una versión de Bonsai bastante antigua

• No entendía del todo en qué se diferencia esto del patrón observable, donde se emite un nuevo valor en la entrada, pasa por el cálculo y se entrega un nuevo resultado al suscriptor.
  Habrá detección de cambios y optimizaciones para detener la propagación cuando el valor siga igual, pero eso también es posible con observables. La parte de agrupar cambios antes de recalcular con stabilize también es interesante, pero igualmente podría implementarse con observables.
  Me pregunto si la diferencia clave está en construir automáticamente el grafo de cómputo mediante introspección interna, o si hay algo más fundamental.

  • Depende de cómo definas el patrón observable. Aquí lo fundamental es la evaluación diferida y el acoplamiento débil entre nodos del grafo. Los valores de los nodos solo se materializan cuando se observan, y los cambios en la estructura del grafo durante la ejecución se manejan con flexibilidad.
    Si solo observas algunos nodos, no hace falta materializar todo el grafo. Puedes detener el cálculo en cualquier momento, dejar el grafo en un estado parcialmente actualizado, cambiar más las entradas y luego continuar la materialización de los nodos que te interesan; el algoritmo se encarga de ordenar todos los cambios.
    El cómputo incremental es, en esencia, un término que abarca estas propiedades, y el mismo sistema también puede componerse con un modelo de observadores y suscriptores. La hoja de cálculo clásica de Excel es un buen ejemplo, y también vale la pena revisar la explicación del algoritmo Salsa.
  • Más o menos, los observables consisten en suscribirse a algo y escuchar valores, mientras que Incremental se parece más a una caché a lo largo de todo el DAG de cómputo y estado. Puede optimizarse recalculando solo lo necesario.
    La charla de Ron Minsky es muy buena.
  • Este texto ayuda a entender el panorama de los sistemas incrementales y de streaming.
  • Yo pensaba algo parecido. A primera vista se ve muy cercano a la programación reactiva con seguimiento de dependencias. Me pregunto si la verdadera ventaja está en la usabilidad de la API o en optimizaciones internas que en la práctica son difíciles de lograr con una implementación general de observables.
  • En el fondo sí es un grafo, pero se trata de una forma de calcular cambios con precisión y eficiencia en un grafo enorme y dinámico.
    Puedes imaginar un subgrafo en forma de diamante que se divide en cientos de nodos intermedios y luego vuelve a unirse tras recorrer caminos de distintas longitudes. En algunos caminos podría haber un min(A, B) y cambiar solo el lado del valor máximo.
    Un enfoque simple de observadores puede hacer que el costo de cómputo explote potencialmente de forma exponencial y también provocar problemas de concurrencia. Esta biblioteca sigue siendo correcta y cercana al óptimo incluso cuando la estructura del grafo cambia dinámicamente. También podrías lograr el mismo resultado con observadores u otros mecanismos, pero implementarlo correctamente evitando precipicios de rendimiento es mucho más difícil.

• La ventaja de los proyectos de Jane Street es que empaquetan ideas que antes estaban en investigación o en sistemas de nicho en una forma que los desarrolladores realmente pueden usar. Aunque no adoptes la biblioteca, sus documentos de diseño casi siempre valen la pena.

• Electric Clojure ofrece renderizado incremental a través del límite entre cliente y servidor. Lo más parecido, en mi opinión, es SolidJS, aunque SolidJS aplica solo al frontend.

• Hace tiempo construí algo parecido y casi no encontré antecedentes. El proyecto se cerró porque desapareció el caso de uso, pero me gustaría volver a revisarlo; todavía sigue en npm con el nombre data-rambler.
  La idea era alimentar flujos de datos a un lenguaje específico de dominio (DSL) que podía cargarse en el runtime de JavaScript. Los módulos transformaban los datos en varios flujos de salida, que luego se pasaban a una biblioteca de reportes separada para generar informes dinámicos basados en plantillas.
  Ya desde la primera versión era bastante potente, pero también había un gran plan para mejorarla con una sintaxis más propia de JavaScript y así reducir la complejidad.