La computación incremental , también conocida como computación incremental , es una característica de software que, cada vez que cambia un dato , intenta ahorrar tiempo volviendo a calcular únicamente aquellas salidas que dependen de los datos modificados. [1] [2] [3] Cuando la computación incremental tiene éxito, puede ser significativamente más rápido que computar nuevos resultados ingenuamente. Por ejemplo, un paquete de software de hoja de cálculo puede utilizar el cálculo incremental en su función de recálculo, para actualizar solo las celdas que contienen fórmulas que dependen (directa o indirectamente) de las celdas modificadas.
Cuando la computación incremental es implementada por una herramienta que puede implementarla para una variedad de diferentes piezas de código automáticamente, esa herramienta es un ejemplo de una herramienta de análisis de programas para la optimización .
Estático versus dinámico
Las técnicas de computación incremental se pueden dividir en dos tipos de enfoques:
Los enfoques estáticos intentan derivar un programa incremental a partir de un programa convencional P usando, por ejemplo, diseño y refactorización manuales, o transformaciones automáticas de programas. Estas transformaciones del programa ocurren antes de que se proporcionen entradas o cambios de entrada.
Los enfoques dinámicos registran información sobre la ejecución del programa P en una entrada particular (I1) y usan esta información cuando la entrada cambia (a I2) para actualizar la salida (de O1 a O2). La figura muestra la relación entre el programa P, la función de cálculo de cambio ΔP, que constituye el núcleo del programa incremental, y un par de entradas y salidas, I1, O1 e I2, O2.
Enfoques especializados versus de propósito general
Algunos enfoques de la computación incremental son especializados, mientras que otros son de propósito general. Los enfoques especializados requieren que el programador especifique explícitamente los algoritmos y las estructuras de datos que se utilizarán para preservar los subcálculos sin cambios. Los enfoques de propósito general, por otro lado, utilizan el lenguaje, el compilador o técnicas algorítmicas para dar un comportamiento incremental a programas que de otro modo no serían incrementales. [4]
Métodos estáticos
Derivados del programa
Dado un cálculo y un cambio potencial , podemos insertar código antes del cambio (la pre-derivada) y después del cambio (la post-derivada) para actualizar el valor de más rápido que volver a correr . Paige ha escrito una lista de reglas para la diferenciación formal de programas en SUBSETL. [5]
Ver mantenimiento
En sistemas de bases de datos como DBToaster, las vistas se definen con álgebra relacional. El mantenimiento incremental de la vista analiza estáticamente el álgebra relacional para crear reglas de actualización que mantienen rápidamente la vista en presencia de pequeñas actualizaciones, como la inserción de una fila. [6]
Métodos dinámicos
El cálculo incremental se puede lograr construyendo un gráfico de dependencia de todos los elementos de datos que pueden necesitar ser recalculados y sus dependencias. Los elementos que deben actualizarse cuando cambia un solo elemento vienen dados por el cierre transitivo de la relación de dependencia del gráfico. En otras palabras, si hay una ruta desde el elemento cambiado a otro elemento, este último puede actualizarse (dependiendo de si el cambio finalmente llega al elemento). Es posible que el gráfico de dependencias deba actualizarse a medida que cambian las dependencias o cuando se agregan o eliminan elementos del sistema. La implementación lo utiliza internamente y, por lo general, no es necesario que se muestre al usuario.
La captura de dependencias en todos los valores posibles se puede evitar identificando un subconjunto de valores importantes (por ejemplo, resultados de agregación) a través de los cuales se pueden rastrear las dependencias y volviendo a calcular de manera incremental otras variables dependientes, por lo tanto, equilibrando la cantidad de información de dependencia a rastrear con la cantidad de recálculo. a realizar al cambiar la entrada. [7]
La evaluación parcial puede verse como un método para automatizar el caso más simple posible de computación incremental, en el que se intenta dividir los datos del programa en dos categorías: los que pueden variar según la entrada del programa y los que no pueden (y los más pequeños). unidad de cambio es simplemente "todos los datos que pueden variar"). La evaluación parcial se puede combinar con otras técnicas de computación incremental.
Con ciclos en el gráfico de dependencia, una sola pasada por el gráfico puede no ser suficiente para alcanzar un punto fijo. En algunos casos, la reevaluación completa de un sistema es semánticamente equivalente a la evaluación incremental y puede ser más eficiente en la práctica, si no en la teoría. [8]
Sistemas existentes
Compatibilidad con compilador y lenguaje
- Incrementalización automática (también llamada "Computación autoajustable" y "Programación funcional adaptativa"), [9] Delta ML , Haskell Adaptive
- Generador de sintetizador Cornell [10]
- IceDust : un lenguaje personalizado específico de dominio.
Marcos y bibliotecas
- Adapton [11] - con implementaciones en varios idiomas
- Restricciones de flujo de datos unidireccionales (cálculo reactivo en C ++)
- Flujo de datos diferencial
- Jane Street Incremental
- Registro de datos incremental (Logicblox)
- Prólogo incremental (XSB) [12]
- Enfoques específicos de dominio:
- Verificación de tipo incremental
Aplicaciones
- Bases de datos (ver mantenimiento)
- Construir sistemas
- Hojas de cálculo [13]
- Ambientes de desarrollo
- Cálculos financieros
- Evaluación de la gramática de atributos
- Consultas y cálculos de gráficos
- GUI (p. Ej., React y DOM que difieren)
- Aplicaciones científicas
Ver también
Referencias
- ^ Carlsson, Magnus (2002). "Mónadas para computación incremental". Actas de la séptima conferencia internacional ACM SIGPLAN sobre programación funcional . Nueva York: ACM . págs. 26–35. doi : 10.1145 / 581478.581482 . ISBN 1-58113-487-8.
- ^ Umut A. Acar (2005). Computación autoajustable (PDF) (tesis doctoral).
- ^ Camil Demetrescu; Irene Finocchi; Andrea Ribichini (2011). "Programación imperativa reactiva con restricciones de flujo de datos" . Actas de la 26ª Conferencia Internacional ACM sobre lenguajes y aplicaciones de sistemas de programación orientados a objetos (OOPSLA 2011) . ACM . págs. 407–426. arXiv : 1104.2293 . doi : 10.1145 / 2048066.2048100 . ISBN 978-1-4503-0940-0.
- ^ Yan Chen; Joshua Dunfield; Matthew A. Hammer; Umut A. Acar. Cálculo autoajustable implícito para programas puramente funcionales . ICFP '11. págs. 129-141. Archivado desde el original el 30 de octubre de 2016 . Consultado el 12 de marzo de 2018 .
- ^ Paige, Robert (1981). Diferenciación formal: una técnica de síntesis de programas . Prensa de investigación UMI. ISBN 978-0-8357-1213-2.
- ^ Ahmad, Yanif; Kennedy, Oliver; Koch, Christoph; Nikolic, Milos (1 de junio de 2012). "DBToaster: procesamiento delta de orden superior para vistas dinámicas, frecuentemente frescas". Proc. VLDB Endow . 5 (10): 968–979. arXiv : 1207.0137 . doi : 10.14778 / 2336664.2336670 . ISSN 2150-8097 .
- ^ Mugilan Mariappan; Keval Vora (2019). "GraphBolt: procesamiento síncrono basado en dependencia de gráficos de transmisión". En la Conferencia Europea de Sistemas Informáticos (EuroSys'19) . págs. 25: 1–25: 16. doi : 10.1145 / 3302424.3303974 .
- ^ Kimberley Burchett; Gregory H. Cooper; Shriram Krishnamurthi (2007). "Reducción: una técnica de optimización estática para la reactividad funcional transparente". En el Simposio ACM SIGPLAN sobre Evaluación Parcial y Manipulación de Programas Basados en Semántica . págs. 71–80. CiteSeerX 10.1.1.90.5866 . ISBN 978-1-59593-620-2.
- ^ Hammer, Matthew A .; Acar, Umut A .; Chen, Yan (2009). "CEAL". Actas de la conferencia ACM SIGPLAN de 2009 sobre diseño e implementación de lenguajes de programación - PLDI '09 . pag. 25. doi : 10.1145 / 1542476.1542480 . ISBN 9781605583921.
- ^ Representantes, Thomas; Teitelbaum, Tim (1984). "El generador de sintetizadores". Actas del primer simposio de ingeniería de software ACM SIGSOFT / SIGPLAN sobre entornos prácticos de desarrollo de software - SDE 1 . págs. 42–48. doi : 10.1145 / 800020.808247 . ISBN 978-0897911313.
- ^ "Adapton: abstracciones de lenguaje de programación para cálculo incremental" . adapton.org . Consultado el 7 de octubre de 2016 .
- ^ Saha, Diptikalyan; Ramakrishnan, CR (2005). "Evaluación incremental de prólogo en tabla: más allá de los programas de lógica pura". Aspectos prácticos de los lenguajes declarativos . Apuntes de conferencias en informática. 3819 . págs. 215-229. CiteSeerX 10.1.1.111.7484 . doi : 10.1007 / 11603023_15 . ISBN 978-3-540-30947-5. ISSN 0302-9743 .
- ^ Hammer, Matthew; Phang, Khoo; Hicks, Michael; Foster, Jeffrey (2014). ADAPTON: Computación incremental componible y basada en la demanda (PDF) . PLDI.