This article is the third edition of the Advent of Patterns series. In this series, running from December 1st to December 24th 2024, I will document one design or programming pattern I have noticed recently. Read the introduction to the series to learn more about the series.
Static site generators commonly have an interactive “incremental” mode. This mode lets you run a local server whose contents change whenever you update a local file on your website. Only the pages affected by the file change will be updated.
Consider a website made of five files: three posts, an index file, and a navigation file referenced on all pages. A static site generator that supports incremental re-generation will first build all five files. If you change the navigation file, all pages will be updated to show the changes. If you change the index file, on which nothing else depends for the sake of this example, only the index file will be updated.
This is an example of incremental computation. Incremental computation involves updating only the information or data that is affected by a change. In the example above, web pages are only re-generated if they have been directly updated or any of its dependencies — or sub-dependencies — have changed.
Incremental computation allows you to run faster computations by re-using what has already been made. For example, suppose it takes 10 seconds to generate a site with 10,000 files using a static site generator. Now, suppose you change one single post that has on dependencies. Ideally, you only want to re-generate the single post. Re-generating one post is faster than all of them.
Materialized views with incremental updates in database software implement this pattern. A materialized view contains the results of a query. If the view can be updated incrementally, the result of the view will change as the data on which it depends changes. This is useful if a query takes a large amount of time to run. Updating a view may include incrementing or decrementing a value depending on whether a new, changed, or deleted record relates to the conditions of the view. For instance, if you delete a record, a view that counts the number of records that meet a condition could be decremented by 1, rather than having to re-compute the value.
Incremental computation relies on having a dependency graph that states how all parts of a system relate. When a value changes, the graph can be traversed to find anything that depends on the value that has changed. Then, the dependencies can be updated. This is a recursive process. For example, if you change a file that depends on a file that depends on a file, all of those files, and their dependencies, need to be updated.
Spreadsheets use incremental computation, too. When a cell is changed, only its dependents and dependencies need to be updated. Execution order can be determined with a topological sort. Incrementally computing the new and changed values ensures the spreadsheet is only doing the work needed to update the state of the sheet instead of re-computing every value.
In what other places does incremental computation pop up in software?
