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. 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. An automated incremental computing tool is a specialised program analysis tool for optimization.

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. 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. An automated incremental computing tool is a specialised program analysis tool for optimization. ==Static versus dynamic== Incremental computing techniques can be broadly classified into two types of approaches: Static approaches attempt to derive an incremental program from a conventional program P using, e.g., either manual design and refactoring, or automatic program transformations. These program transformations occur before any inputs or input changes are provided. Dynamic approaches record information about executing program P on a particular input (I1) and use this information when the input changes (to I2) in order to update the output (from O1 to O2). The figure shows the relationship between program P, the change calculation function ΔP, which constitutes the core of the incremental program, and a pair of inputs and outputs, I1, O1 and I2, O2. Given a computation C = f(x_1, x_2, \dots x_n) and a potential change x_j := \Delta_{x_j} , we can insert code before the change occurs (the pre-derivative) and after the change (the post-derivative) to update the value of C faster than rerunning f . Paige has written down a list of rules for formal differentiation of programs in SUBSETL. ===Compiler and language support=== Automatic Incrementalization (also called "Self-Adjusting Computation", and "Adaptive Functional Programming"), Delta ML, Haskell Adaptive Cornell Synthesizer Generator IceDust - a custom domain-specific language. ===Frameworks and libraries=== Adapton - with implementations in several languages One-way Dataflow Constraints (Reactive Computation in C++) Differential Dataflow Jane Street Incremental Incremental Datalog (LogicBlox) Incremental Prolog (XSB) FSharp.Data.Adaptive Domain-Specific Approaches: Incremental Type Checking.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1374756857 under CC BY-SA 4.0; modifications have been made.