How Build Systems Work: Dependency Graphs, Incremental Builds and Caching

A build system takes source files and produces the artifacts a project needs, such as libraries, executables, bundled web assets or documentation. A small project can be built by typing one compiler command. A large one may contain thousands of files, generated code, code generators and tests, all with different inputs. Build systems exist to answer one question quickly and correctly: which outputs are out of date, and what is the smallest set of steps needed to bring them up to date? This post explains the core ideas behind that answer.

The rule and the recipe

Most build tools share a simple model. A target is a file the build should produce, such as app or libmath.a. Each target lists its prerequisites, which are the files it depends on. Each target also has a recipe, which is the command that creates it from the prerequisites. The classic make tool, which dates back to the 1970s, expresses this as rules in a Makefile:

app: main.o util.o        # app depends on both object files
	cc -o app main.o util.o   # the recipe, indented with a tab

main.o: main.c util.h     # main.o depends on its source and a header
	cc -c main.c -o main.o

When you ask for app, the tool checks each prerequisite. If a prerequisite is itself a target, it is checked first, recursively. If any prerequisite is newer than the target, or the target does not exist, the recipe runs.

The dependency graph

Behind this simple model is a directed graph. Nodes are files and build steps. Edges point from inputs to outputs. Build systems walk this graph in dependency order, which is a topological ordering: every node runs only after its inputs are ready. If two nodes have no path between them, they can run in parallel, which is why modern build tools use multiple cores.

The graph also makes clear what needs rebuilding after a change. If util.h changes, every object that includes it must be rebuilt, but unrelated objects are untouched. Getting the edges right is the central job of the build system. A missing edge, such as forgetting that a header affects a source file, causes the classic bug where a build succeeds but the output is stale.

Timestamps versus content hashes

The oldest approach to deciding freshness is file timestamps. A target is out of date if any input has a newer modification time. Timestamps are cheap to read, but they are fragile. A file touched without a real change triggers unnecessary rebuilds. A clock skew or a restored backup can make an old file look new, or a new file look old.

Modern systems often compare content hashes instead. The tool records the hash of each input and each output. A rebuild happens when an input hash differs from the recorded one. This is slower to compute, since every input must be read, but it gives correct results when timestamps lie. Bazel uses content-based keys for this reason. Ninja, a fast backend for other generators, still relies on file timestamps and recorded command lines.

Incremental builds

An incremental build reuses the outputs of earlier runs and recompiles only what changed. The benefit grows with project size. A change in one leaf file of a large program may need one compile and one link step, while a full clean build could take minutes. The difference is what makes fast edit-and-run cycles possible.

Incremental correctness depends on recording what each step read. Compilers help here by emitting dependency files that list every header included by a source file. The build system reads these lists and adds the edges automatically, so developers do not have to maintain them by hand. Without this step, header changes are a common source of confusing failures.

Caching across machines

A cache stores outputs keyed by the hash of their inputs and the exact command that produced them. If a later build computes the same key, it can copy the stored output instead of running the step. Local caches help one developer, while remote caches share results across a team and across continuous integration runs.

Remote caching only works when the build is hermetic, meaning the output depends only on declared inputs. A step that reads the current time, a random value, an environment variable or a file outside its declared inputs can produce different results on different machines. Hermetic builds pin tool versions, declare every input and run in controlled sandboxes. These rules are strict, but they turn caching from a risky shortcut into a reliable speedup.

A comparison of approaches

The table below shows how common designs differ on the properties most teams care about. Real tools vary, and the entries describe typical behavior rather than exact rankings.

Approach	Freshness check	Typical strength	Typical weakness
Timestamp rules (classic make)	File modification time	Simple, widely available	False rebuilds, clock issues
Content hashing (Bazel)	Hash of inputs	Accurate, cache friendly	Must read every input
Generated build files	Depends on generator	Fast incremental runs	Extra tool to maintain
Remote cache	Hash key lookup	Shares work across machines	Needs hermetic steps

Generated build files

Many large projects do not write the build rules by hand. A configuration tool reads a description of the project and generates a low-level file for a fast backend. CMake is a well-known example, producing build files for several backends. The generated layer lets the high-level description stay readable while the backend stays quick. The trade-off is one more layer to understand when something goes wrong.

Common pitfalls

Several mistakes appear again and again. Stale outputs usually come from missing dependency edges, so check that headers and generated files are declared. Non-reproducible builds usually come from embedded timestamps, absolute paths or unordered directory listings, so normalize these when packaging. Slow builds often come from one large step that could be split, or from a serial chain that could run in parallel. Measure with the tool's trace or profiling option before changing anything, because the bottleneck is often not where you expect.

Also keep the build script itself under the same care as application code. A build that only one person understands is a single point of failure for the whole team.

Practical habits

Declare all inputs explicitly. Keep generated files out of source control unless they are needed for reproducibility. Run a clean build regularly on a fresh checkout so that hidden state does not hide errors. Compare clean and incremental results when you suspect a stale output. When adding a dependency, check that the build system sees its headers or modules, not only that the code compiles on your machine.

Key takeaways

A build system models a project as a graph of targets, prerequisites and recipes. It runs steps in dependency order, skips work whose inputs have not changed, and can run independent steps in parallel. Content hashes are more reliable than timestamps, and compiler-generated dependency lists keep incremental builds correct. Hermetic steps make caching safe across machines. The payoff is faster feedback for every developer, but only when the graph of dependencies is complete and honest.