10 Dependency Graph System

The Dependency Graph System (DGS) keeps calculated results up to date efficiently. A significant part of software development involves caching the results of time-consuming calculations and only recalculating them when their inputs change. Examples include textures uploaded to a graphics card, rasterised fonts and vector graphics, decompressed images, user-interface layout calculations, and database queries.

As a calculation runs, CEDA automatically discovers which pieces of data it reads. This forms a dependency graph connecting calculated results to their inputs. The graph changes automatically as the calculations and data change, avoiding the error-prone work of manually wiring notifications between parts of an application.

When an input changes, the DGS remembers which results may now be out of date. It waits until a result is actually needed before recalculating it, and only performs the calculations affected by the change. If a recalculation produces the same value as before, the change does not need to propagate any further.

Calculations can also run asynchronously, which allows expensive work to take place without blocking a user interface. This is useful for applications that must remain responsive while loading, decompressing, querying, laying out, or rendering data in the background.

Calculated results need not remain in memory forever. CEDA can discard cached results when memory is needed and calculate them again if they are requested later.

The Dependency Graph System specification describes its language support, public interface, implementation, and cache-eviction system.