Incremental Computing
   HOME

TheInfoList



OR:

Incremental computing, also known as incremental computation, is a
software feature In software, the term feature has several definitions. The Institute of Electrical and Electronics Engineers defines the term ''feature'' in IEEE 829 as " distinguishing characteristic of a software item (e.g., performance, portability, or functio ...
which, whenever a piece of
data In the pursuit of knowledge, data (; ) is a collection of discrete Value_(semiotics), values that convey information, describing quantity, qualitative property, quality, fact, statistics, other basic units of meaning, or simply sequences of sy ...
changes, attempts to save
time Time is the continued sequence of existence and events that occurs in an apparently irreversible succession from the past, through the present, into the future. It is a component quantity of various measurements used to sequence events, ...
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 A spreadsheet is a computer application for computation, organization, analysis and storage of data in tabular form. Spreadsheets were developed as computerized analogs of paper accounting worksheets. The program operates on data entered in c ...
software package might use incremental computation in its recalculation feature, 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 In computer science, program analysis is the process of automatically analyzing the behavior of computer programs regarding a property such as correctness, robustness, safety and liveness. Program analysis focuses on two major areas: program op ...
tool for
optimization Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. It is generally divided into two subfi ...
.


Static versus dynamic

Incremental computing techniques can be broadly separated 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.


Specialized versus general-purpose approaches

Some approaches to incremental computing are specialized, while others are general purpose. Specialized approaches require the programmer to explicitly specify the
algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
s and data structures that will be used to preserve unchanged sub-calculations. General-purpose approaches, on the other hand, use language, compiler, or algorithmic techniques to give incremental behavior to otherwise non-incremental programs.


Static methods


Program derivatives

Given a computation C = f(x_1, x_2, \dots x_n) and a potential change x_j := \Delta_, we can insert code before the change (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.


View maintenance

In database systems such as DBToaster, views are defined with relational algebra. Incremental view maintenance statically analyzes relational algebra to create update rules that quickly maintain the view in the presence of small updates, such as insertion of a row.


Dynamic methods

Incremental computation can be achieved by building a
dependency graph In mathematics, computer science and digital electronics, a dependency graph is a directed graph representing dependencies of several objects towards each other. It is possible to derive an evaluation order or the absence of an evaluation order t ...
of all the data elements that may need to be recalculated, and their dependencies. The elements that need to be updated when a single element changes are given by the
transitive closure In mathematics, the transitive closure of a binary relation on a set is the smallest relation on that contains and is transitive. For finite sets, "smallest" can be taken in its usual sense, of having the fewest related pairs; for infinite ...
of the dependency relation of the graph. In other words, if there is a path from the changed element to another element, the latter may be updated (depending on whether the change eventually reaches the element). The dependency graph may need to be updated as dependencies change, or as elements are added to, or removed from, the system. It is used internally by the implementation, and does not typically need to be displayed to the user. Capturing dependencies across all possible values can be avoided by identifying subset of important values (e.g., aggregation results) across which dependencies can be tracked, and incrementally recomputing other dependent variables, hence balancing the amount of dependency information to be tracked with the amount of recomputation to be performed upon input change. Partial evaluation can be seen as a method for automating the simplest possible case of incremental computing, in which an attempt is made to divide program data into two categories: that which can vary based on the program's input, and that which cannot (and the smallest unit of change is simply "all the data that can vary"). Partial evaluation can be combined with other incremental computing techniques. With cycles in the dependency graph, a single pass through the graph may not be sufficient to reach a fixed point. In some cases, complete reevaluation of a system is semantically equivalent to incremental evaluation, and may be more efficient in practice if not in theory.


Existing systems


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 Stree
Incremental
* Incremental Datalog (Logicblox) * Incremental Prolog (XSB) * Domain-Specific Approaches: ** Incremental Type Checking


Applications

* Databases (view maintenance) * Build systems * Spreadsheets * Development Environments * Financial Computations * Attribute Grammar Evaluation * Graph Computations and Queries * GUIs (e.g., React and DOM diffing) * Scientific applications


See also

*
Reactive programming In computing, reactive programming is a declarative programming paradigm concerned with data streams and the propagation of change. With this paradigm, it's possible to express static (e.g., arrays) or dynamic (e.g., event emitters) data streams ...
**
Functional reactive programming Functional reactive programming (FRP) is a programming paradigm for reactive programming ( asynchronous dataflow programming) using the building blocks of functional programming (e.g. map, reduce, filter). FRP has been used for programming graphi ...
* Memoization *
Bidirectional transformation In computer programming, bidirectional transformations (bx) are programs in which a single piece of code can be run in several ways, such that the same data are sometimes considered as input, and sometimes as output. For example, a bx run in the fo ...


References

{{reflist