Incremental computing
Encyclopedia
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.
For example, a spreadsheet
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.
of a seven-digit number in a cell in a spreadsheet is altered, the whole cell will be treated as changed.
For a spreadsheet, the smallest unit is a cell, whereas for make, it is typically an individual file. This means that in
.
Incremental compilers
address the problem of having to recompile an entire compilation unit of a program if any of the source files the unit depends on have changed.
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
of the dependency relation of the graph. In other words, if there is a path from the changed element to another element, the latter will be updated (even if the value does not actually change).
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.
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"). Of course, partial evaluation can be combined with other incremental computing techniques.
Other implementation techniques exist. For example, a topological evaluation order may be used to avoid the precomputation of elements that need to be reevaluated as in FrTime, which also avoids the problem of unnecessary updates. If a language permits cycles in the dependency graph, a single pass through the graph may not be sufficient to reach a fixed point. In many cases, complete reevaluation of a system is semantically equivalent to incremental evaluation, and may be more efficient in practice if not in theory
Data
The term data refers to qualitative or quantitative attributes of a variable or set of variables. Data are typically the results of measurements and can be the basis of graphs, images, or observations of a set of variables. Data are often viewed as the lowest level of abstraction from which...
changes, attempts to save time by only recomputing those outputs which "depend on" the changed data.
For example, a spreadsheet
Spreadsheet
A spreadsheet is a computer application that simulates a paper accounting worksheet. It displays multiple cells usually in a two-dimensional matrix or grid consisting of rows and columns. Each cell contains alphanumeric text, numeric values or formulas...
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.
Explicit versus Implicit
Explicit approaches to incremental computing require the programmer to explicitly specify the algorithms and data structures that will be used to preserve unchanged sub-calculations. Implicit schemes, on the other hand, enable a normal non-incremental program to be evaluated in a manner that preserves unchanged sub-calculations, or to be transformed into a program that does this explicitly.Smallest unit of change
An incremental computing system typically has a predefined smallest unit of change that will be individually tracked. If a change is made that is smaller in scope than this smallest unit, the containing unit will be deemed to have changed. For example, if just one numerical digitNumerical digit
A digit is a symbol used in combinations to represent numbers in positional numeral systems. The name "digit" comes from the fact that the 10 digits of the hands correspond to the 10 symbols of the common base 10 number system, i.e...
of a seven-digit number in a cell in a spreadsheet is altered, the whole cell will be treated as changed.
For a spreadsheet, the smallest unit is a cell, whereas for make, it is typically an individual file. This means that in
make, something can be a dependency of an entire file - but not of elements within files, such as individual functionsSubroutine
In computer science, a subroutine is a portion of code within a larger program that performs a specific task and is relatively independent of the remaining code....
.
Incremental compilers
Incremental compiler
The term incremental compiler may refer to two different types of compiler.-Imperative programming:In imperative programming and software development, an incremental compiler is one that when invoked, takes only the changes of a known set of source files and updates any corresponding output files ...
address the problem of having to recompile an entire compilation unit of a program if any of the source files the unit depends on have changed.
Implementation
A conservative (theoretically sub-optimal) implementation technique for incremental computing is for the software to build a dependency graphDependency graph
In mathematics, computer science and digital electronics, a dependency graph is a directed graph representing dependencies of several objects towards each other...
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
Transitive closure
In mathematics, the transitive closure of a binary relation R on a set X is the transitive relation R+ on set X such that R+ contains R and R+ is minimal . If the binary relation itself is transitive, then the transitive closure will be that same binary relation; otherwise, the transitive closure...
of the dependency relation of the graph. In other words, if there is a path from the changed element to another element, the latter will be updated (even if the value does not actually change).
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.
Partial evaluation
Partial evaluation
In computing, partial evaluation is a technique for several different types of program optimization by specialization. The most straightforward application is to produce new programs which run faster than the originals while being guaranteed to behave in the same way...
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"). Of course, partial evaluation can be combined with other incremental computing techniques.
Other implementation techniques exist. For example, a topological evaluation order may be used to avoid the precomputation of elements that need to be reevaluated as in FrTime, which also avoids the problem of unnecessary updates. If a language permits cycles in the dependency graph, a single pass through the graph may not be sufficient to reach a fixed point. In many cases, complete reevaluation of a system is semantically equivalent to incremental evaluation, and may be more efficient in practice if not in theory