Commit-Graph Files and Generation Numbers

Answering “is this commit an ancestor of that one” by walking parent links means inflating a compressed object for every step, and each inflation may require applying a delta chain first. On a history with a million commits, a reachability question that visits a large fraction of them touches a large fraction of the pack, in an order determined by ancestry rather than by storage location. The commit-graph file exists to make that traversal sequential and cheap: it is a derived index that stores the same commit metadata in a flat array, and it adds a number that lets a walk skip whole regions of history.

The cost that is not the algorithm

The traversal itself is linear in the number of commits visited, which is asymptotically fine. The constant is the problem. Each commit object is a separate zlib stream inside a pack, and reading one means locating it through the index, seeking, inflating, and possibly walking a delta chain whose base is somewhere else in the file. The access pattern is pointer chasing across a data structure optimised for a different access pattern.

A commit-graph stores, for each commit, its tree identifier, the positions of up to two parents within the same file, its commit timestamp, and its generation number. Because parent references are positions rather than identifiers, following a parent is an array index, not a lookup. Because records are fixed size and sorted by identifier, a traversal touches memory in large sequential runs. A question that used to require a pack read per commit becomes a pass over a compact file.

The file is optional and derived. Every value in it can be recomputed from the objects it describes, and a reader that finds no graph simply falls back to the object store. That is the property that makes it safe to write on a fetch, delete, or rewrite at will.

Generation numbers bound the walk

The generation number of a commit is one plus the maximum generation number of its parents, with roots starting at one. It is the length of the longest path from the commit down to a root, so it is an upper bound on how many steps a walk from that commit can take. The useful property is the contrapositive: if commit A has a smaller generation number than commit B, then A cannot be an ancestor of B. The walk can stop expanding A entirely.

For a question like “which commits contain this fix”, the walk starts from the candidate tips and descends, pruning any commit whose generation number is below the target’s. On a history where the target is recent, the pruned region is almost everything, and the query becomes proportional to the distance from the tips rather than to the size of the history.

Generation number v2 replaces the topological level with a corrected commit date: one plus the maximum corrected date among parents, compared against the commit’s own timestamp, taking whichever is larger. The corrected date is a timestamp, so it distinguishes commits that share a topological level, which the level cannot. Two commits on parallel branches at the same depth have the same v1 number and cannot prune each other; their commit dates usually differ, so v2 prunes one of them. The corrected date also tolerates a clock that runs backwards, because the maximum over parents enforces monotonicity along every path.

Neither number is a proof of reachability. A larger generation number or a later date does not imply that the commit is a descendant, only that the reverse is impossible. The walk still has to follow parents, and the number only removes work.

The file is a chunk table

A commit-graph begins with the signature CGPH, a version, a hash version, a chunk count, and a base graph count for split files. A table of chunk entries follows, each with a four-byte identifier and an eight-byte offset. Readers locate the chunks they understand and ignore the rest, which is how the format has been extended without invalidating old files.

The fanout chunk holds 256 cumulative counts by first identifier byte, the same structure the pack index uses. The lookup chunk holds the sorted identifiers. The data chunk holds the fixed-size records: tree identifier, two parent positions (a sentinel meaning “no parent” or “parent not in this file”), and an eight-byte word packing the generation number and the commit time. The extra-edges chunk holds additional parent positions for merge commits with more than two parents, referenced by an index stored in the data chunk.

Later chunks carry optional acceleration. Generation-data chunks store version 2 numbers separately, so a file written for one generation scheme can be upgraded without rewriting the base records. Bloom filter chunks store, per commit, a probabilistic summary of the paths changed by that commit, which lets a path-limited log skip commits that cannot possibly touch the path. Each of those is a filter with false positives and no false negatives: a skipped commit is definitely irrelevant, a visited one may still turn out not to match.

Split graphs are the incremental form. A base graph holds the bulk of history, and one or more incremental graphs layer newer commits on top, each naming its predecessors. A reader loads the chain and resolves positions across layers. This keeps the cost of writing after a fetch proportional to the new commits rather than to the whole history, at the price of a slightly more complex lookup.

# Topological levels: level(c) = 1 + max(level(p) for p in parents(c)), roots = 1.
# Computed oldest first, so every parent is numbered before its children.
levels = {}
for c in commits:
    levels[c] = 1 + max((levels[p] for p in parents[c]), default=0)

Staleness, shallow boundaries, and the cost of writing

A commit-graph that omits a commit simply does not accelerate paths through it; a graph whose records disagree with the object store is a correctness hazard, which is why the file carries a checksum and why a mismatch causes it to be ignored rather than trusted. Writing is triggered by git gc, by git commit-graph write, and by fetch when configured to do so; each write walks the commits it intends to cover, which is linear and therefore worth deferring.

Shallow clones break the assumption that every parent is present. A commit at the shallow boundary has parents that exist in the origin repository but not locally, and those edges cannot be represented. The graph records the boundary as having no parent, so generation numbers are valid only within the clone: a commit that would be deep in the full history gets a small number locally. Reachability answers computed against the graph are correct for the local history and wrong about anything beyond the boundary, which is why operations that reason about the full history refuse to proceed on a shallow clone rather than producing a confident wrong answer.

Replace refs and grafts create the same kind of divergence from a different direction: they change the parent edges as seen by commands, while the graph records the edges as stored. A rewritten view of history needs a rewritten graph, and the tooling treats a graph built for different edges as invalid.

Where the index stops paying

The commit-graph accelerates ancestry, not content. It cannot answer whether a tree contains a path without reading trees, and its bloom filters only narrow a search. It also adds a file that must be kept consistent with the object store and that must be rewritten when history is rewritten, so a repository that is mostly written and rarely queried gains little and pays the write cost. The benefit is concentrated in the operations that walk history repeatedly: merge base computation, --contains, topological ordering for log, and path-limited history.

The ancestry it indexes is the same graph that merges traverse when searching for a common ancestor, and the same one that reachability analysis walks when deciding which objects are live. In both cases the graph is an optimisation over the object store, and both must remain correct when it is absent.