Incremental computing

Incremental computing, also known as incremental computation, is a software feature which, whenever a piece of data changes, attempts to save time by only recomputing those outputs which depend on the changed data.[1][2][3] When incremental computing is successful, it can be significantly faster than computing new outputs naively. For example, a spreadsheet software package might use incremental computation in its recalculation features, to update only those cells containing formulas which depend (directly or indirectly) on the changed cells.

When incremental computing is implemented by a tool that can implement it for a variety of different pieces of code automatically, that tool is an example of a program analysis tool for optimization.

Incremental computing provides a means of computing a new input/output pair (I2,O2), based on an old input output pair (I1,O1). The key technique is represented by a function ΔP, which relates changes in the input to changes to the output.
Incremental computing derives a new input/output pair from one or more old input/output relationships. To do so, ΔP must relate a change in the input to a change in the output. The consumer of the result may be interested in the full updated output, or the delta output, or both.
  1. ^ Carlsson, Magnus (2002). "Monads for incremental computing". Proceedings of the seventh ACM SIGPLAN international conference on Functional programming. New York: ACM. pp. 26–35. doi:10.1145/581478.581482. ISBN 1-58113-487-8.
  2. ^ Umut A. Acar (2005). Self-Adjusting Computation (PDF) (Ph.D. thesis).
  3. ^ Camil Demetrescu; Irene Finocchi; Andrea Ribichini (2011). "Reactive Imperative Programming with Dataflow Constraints". Proceedings of the 26th ACM International Conference on Object-Oriented Programming Systems Languages and Applications (OOPSLA 2011). ACM. pp. 407–426. arXiv:1104.2293. doi:10.1145/2048066.2048100. ISBN 978-1-4503-0940-0.