arthrop0d

Brief articles on varied topics.

Git Commit-Graph Files and Generation Numbers

gitperformance

Git’s commit-graph file is an index of commits and their relationships, and generation numbers are values in that index that describe each commit’s position in history. Together, they let Git reject impossible ancestry relationships and prioritize useful commits without repeatedly parsing an entire chain of commit objects.

The problem: history is a graph, not a list

A Git commit contains metadata, a snapshot tree, and one or more parent commit IDs. A normal commit has one parent; a merge commit has two or more. Those parent links form a directed acyclic graph: history can branch and later join again.

To answer “is commit A an ancestor of commit B?”, Git can start at B, read its commit object, follow its parents, and repeat until it finds A or reaches commits with no parents. That works, but a repository may contain millions of commits. The same parsing and object lookups can be repeated for commands such as:

Git already has indexes for locating objects by their IDs. Those indexes answer where an object is stored, not how commits relate to one another. The commit-graph file supplies that missing relationship index.

What the commit-graph records

A commit-graph file has an entry for each indexed commit. Conceptually, an entry contains:

The on-disk format is divided into chunks so Git can look up a commit efficiently. Parent references can be stored as compact positions in the graph rather than repeatedly storing full object IDs. The file is an index and cache: the original commit objects remain authoritative, and Git can fall back to reading them when a commit is not covered by the graph.

Repositories can also use a split commit graph, where newer graph files sit in layers above older ones. This avoids rewriting one large file whenever new commits arrive. Git treats the layers as one logical graph.

You may have encountered this mechanism indirectly through git commit-graph, repository maintenance, or the core.commitGraph configuration. Most commands use it automatically when a suitable graph exists.

Generation numbers: a topological shortcut

A generation number is a value that increases as a commit’s history moves forward. In the original scheme, called generation number version 1, a root commit has generation 1. Every other commit has one more than the largest generation number of its parents:

generation(commit) = 1 + max(generation(parent))

For a linear sequence, the values look like this:

root: 1 -> next: 2 -> next: 3 -> tip: 4

For a merge, the merge’s value is based on the deeper parent path. The value is not the number of commits in all of its history, and it is not an exact distance from the root. It is a topological rank: every parent has a smaller generation number than its child.

That ordering gives Git an immediate impossibility test. If A has a higher generation number than B, A cannot be an ancestor of B; history only follows links toward lower values. Git can reject that case without opening either commit’s full history.

How a reachability walk gets cheaper

Generation numbers do not contain every answer. Git still needs to follow parent links when the answer is not obvious. Their value is that they make those walks selective.

Suppose Git is testing whether A is reachable from B. It walks backward from B, but can avoid exploring commits that cannot lead to A. More generally, when Git is looking for common ancestors of two tips, it can process the candidates in generation order. A commit with a high generation value is closer to the tips; once the walk has reached a suitable lower boundary, commits below that boundary cannot reveal a better result.

The exact algorithms differ by operation, but the pattern is consistent:

  1. Read parent relationships from the commit graph instead of parsing every commit object.
  2. Use generation values to order the pending commits.
  3. Stop or prune when a generation value proves that a candidate cannot affect the result.
  4. Read full commit objects only when the operation actually needs their details.

Without the graph, Git has to discover much of this structure by repeatedly loading commits. With it, the same walk can use compact records and discard large portions of history early.

Corrected commit dates

Generation number version 1 has a practical limitation: its values can become large in deep repositories, and a topological level does not provide a useful estimate of when a commit occurred. Git therefore also supports generation number version 2, commonly represented by a corrected commit date.

A corrected commit date is the later of a commit’s own committer timestamp and the corrected dates of its parents. In effect, it adjusts for a developer’s clock being wrong or for otherwise inconsistent timestamps, while preserving the rule that a child does not appear earlier than its parents.

This value is not merely a display date. Git can use it as an ordering key during history walks while retaining topological safety. The commit-graph format stores the generation data needed by the selected version; Git can choose the available representation and fall back when necessary.

What this does—and does not—guarantee

The commit graph does not precompute every possible ancestor pair. Storing that would be far larger than storing each commit’s immediate parents. It also does not make every history operation constant-time: a query may still need to inspect many commits, especially when branches have very large or tangled histories.

Instead, it provides two high-value improvements:

If the graph is missing, stale, incomplete, or disabled, Git can still operate by reading ordinary commit objects. It is a performance structure, not a second definition of history. Its purpose is to turn repeated, expensive discovery of the commit graph into a compact lookup followed by a much more disciplined walk.

← All articles