Every clone and every fetch negotiation starts with the same question, and for most of Git’s history that question was answered the expensive way. The server has to figure out which objects the client doesn’t already have — and the only correct way to enumerate “everything reachable from these commits” is to walk the DAG: parse a commit, read its tree, recurse into every subtree, touch every blob, repeat for every parent. Git reachability bitmaps exist to replace that walk with a lookup. Instead of traversing the graph at request time, Git precomputes one bit-vector per selected commit — one bit per object, marking whether that object is reachable — compresses it, and turns the whole question into a handful of bitwise OR and AND-NOT operations over vectors that already exist.
This article works the mechanism from the ground up: why the naive walk is expensive, how the bitmap format encodes a reachable set cheaply enough to store thousands of them, the GitHub fleet numbers that show what switching from “walk” to “lookup” is actually worth, and where bitmaps sit alongside the commit-graph and the multi-pack-index — three different acceleration structures solving three different queries, not one structure replacing another. The mechanism generalizes past Git entirely: precomputing a monotonic invariant so a full traversal becomes an early-exit comparison is a move that shows up anywhere a system is built on a DAG or a partial order.
The Question Every Clone and Fetch Has to Answer
Strip away the CLI and a git fetch is a negotiation between two peers over a set difference. The client advertises which refs it wants; optionally, in the smart-HTTP and v2 protocols, it can tell the server which commits it already has. The server’s job is to compute reachable(wants) − reachable(haves) — every object reachable from the wanted tips, minus everything already reachable from what the client reports having — and pack exactly that set for transfer. Get this wrong in either direction and you either ship objects the client already owns (wasted bandwidth) or omit objects the client needs (a broken clone).
The naive way to compute reachable(commit) is a full graph traversal: inflate the commit object, read its tree pointer and parent pointers, recurse into the tree to enumerate every subtree and blob it points to, then repeat for every parent commit back to the roots. Nothing about the object model makes this fast by default — a commit object is just compressed bytes on disk, and “what does this commit make reachable” is not a fact Git stores anywhere until something computes it. On a small repository that traversal is instant and nobody notices. On a repository with years of history and hundreds of thousands of objects, it’s the single most expensive step in the entire negotiation, and it scales with the size of the history, not the size of the changes the client is actually asking for.
It’s worth being precise here because this is where packfile mechanics get credited for the wrong thing: cheap branching and instant checkout of an old tree come from Git’s content-addressed snapshot model, not from delta compression. Deltas are a storage optimization layered on top of that model — they change how many bytes a given, already-defined set of objects costs on disk or on the wire. They say nothing about how fast you can determine which objects belong to that set in the first place. That’s a separate problem, and it’s the one reachability bitmaps solve.
Walking the DAG the Slow Way
To see why the walk is expensive, it helps to know what it’s walking through. A .pack file is a 12-byte header (a PACK magic number, a version, and an object count), a stream of object entries, and a trailing checksum. Each object is stored either whole and zlib-compressed, or as a delta against a base object — referenced either by full object name (OBJ_REF_DELTA, needed when the base lives outside the pack) or by a negative byte offset to an earlier object in the same pack (OBJ_OFS_DELTA, more space-efficient). A companion .idx file holds a 256-entry fan-out table, a sorted list of object IDs, and an offset table, giving binary-search lookup by object ID without touching the pack’s contents at all (git-scm.com, Pack format).
None of that indexing helps with reachability, though — the .idx answers “where is object X,” not “is object X reachable from commit C.” Before bitmaps, answering the second question meant Git’s revision-walking machinery actually doing the traversal above: zlib-inflating and text-parsing every commit object it touched, just to read two pointers (tree and parents) back out of it. GitHub’s own numbers make the cost concrete: walking every object in the Linux kernel repository — a large, real, long-lived history — took more than 33 seconds without a bitmap (GitHub Engineering, “Scaling monorepo maintenance,” 2022). That’s the tax clone, fetch, git rev-list --objects, and any server-side check that has to compute a reachable set were paying on every single invocation, before bitmaps existed to shortcut it.
The Fix: One Bitmap Per Commit, Compressed
The technique that closes that gap originated in JGit, credited to a 2013 Google-hosted Git hackathon; GitHub ported the design to C Git, landing the pack.writeBitmaps config option in Git 2.0 (2014) (GitHub Engineering, “Counting Objects,” 2015). The idea: for a well-chosen set of commits — recent tips, tagged releases, anything likely to be requested — precompute a bitmap with one bit per object in the pack, set to 1 if that object is reachable from the commit the bitmap belongs to.
Two encoding tricks make storing thousands of these bitmaps cheap instead of wasteful. First, each bitmap is compressed with EWAH (Enhanced Word-Aligned Hybrid), a run-length scheme: rather than storing one bit per object literally, EWAH stores chunks that are either a repeated-bit run (long stretches of “reachable” or “not reachable” collapse to a few bytes) or a literal word when the bits don’t run cleanly. Second, because most commits’ reachable sets barely differ from their immediate parent’s — a single commit rarely reorganizes the whole tree — each stored bitmap is XOR-delta-encoded against up to 160 preceding entries, so a bitmap for commit C often stores little more than “same as this earlier bitmap, except for these bits” (Git documentation, Bitmap format).
Once those bitmaps exist, answering reachable(wants) − reachable(haves) stops being a traversal and becomes a bitwise operation: OR together the bitmaps for the wanted commits (or the nearest ancestor that has one, walking a short distance if needed), OR together the bitmaps for the haves, and AND-NOT the second result out of the first. A handful of word-level bitwise operations over precomputed vectors, instead of re-deriving the same reachable sets from scratch on every request. GitHub reports the resulting bitmap index costs roughly 5–10% of the pack’s own size, and that the reachability query itself dropped from “several minutes of CPU time” to under 3 milliseconds — an aggregate greater than 90% reduction in average CPU time spent on network operations after rollout, which GitHub itself described as “roughly a century of waiting for their fetches to complete” saved, fleet-wide (GitHub Engineering, “Counting Objects,” 2015).
What the Fleet Numbers Actually Show
Bitmaps didn’t stop improving after 2015, and GitHub’s own operational numbers quantify each increment — worth reading with dates attached, since these are vendor-reported figures from GitHub’s own fleet and specific repositories, not universal constants for an arbitrary repo.
| Metric | Before | After | Source / date |
|---|---|---|---|
| Full reachability walk, Linux kernel repo | > 33 seconds | 1.57 seconds (~21×) | GitHub Engineering, “Scaling monorepo maintenance,” 2022 |
| Reachability query cost (general) | Several minutes of CPU time | Under 3 ms | GitHub Engineering, “Counting Objects,” 2015 |
| CPU time on network operations, aggregate | Baseline | > 90% reduction | GitHub Engineering, “Counting Objects,” 2015 |
homebrew/homebrew-core fetch CPU, after adding .rev reverse-index files | Baseline | ~80% reduction | GitHub Engineering, “Scaling monorepo maintenance,” 2022 |
| Fleet-wide daily peak CPU | ~10.8 s | ~7 s (35% reduction) | GitHub Engineering, “Scaling monorepo maintenance,” 2022 |
| Average repack duration (multi-pack bitmaps + geometric repack vs. prior single-pack strategy) | ~1 minute | ~15 seconds (4×), saving ~5.67 CPU-days/hour fleet-wide | GitHub Engineering, “Scaling monorepo maintenance,” 2022 |
| Bitmap generation time, one large repository | ~612 s | ~294 s | GitHub Engineering, “Highlights from Git 2.55,” 2026 |
The .rev files in that table are on-disk pack reverse indexes — they let Git map a pack offset back to an object identity without rebuilding that mapping in memory on every operation, and they’re a good example of the same general move as bitmaps: precompute something once, on disk, instead of re-deriving it per request. Bitmaps were extended to cover multiple packs simultaneously in Git 2.34 (2021), which is what made pairing them with geometric repacking (below) worthwhile at fleet scale. And the write side kept getting cheaper too: Git 2.55 (2026) cut bitmap-generation time on one large repository roughly in half by skipping redundant tree recursion and reusing bitmaps that had already been computed, rather than only ever making the read side faster (GitHub Engineering, “Highlights from Git 2.55,” 2026).
The Complementary Stack: Commit-Graph and the Multi-Pack-Index
Reachability bitmaps answer one specific question — “what’s reachable from this commit” — extremely fast, but they don’t answer every graph question, and they aren’t the only acceleration structure Git built on top of the object model. Two others matter here, and the accuracy guardrail from the research behind this article is explicit: describe these as a stack, not as competitors. Each solves a different query, and they increasingly compute over each other rather than duplicating work.
The commit-graph file, shipped in Git 2.18 (2018), exists so that “get me this commit’s parents, tree, and date” never again requires zlib-inflating and text-parsing a raw commit object. It stores, per commit: the object ID, parent pointers as integer indices into the same file (not full 40-character hashes), the root tree’s object ID, the commit date, and a generation number — chunked into files chained together so incremental writes don’t require rewriting the whole structure from scratch (Git documentation, Commit-graph format).
Generation numbers are the actual algorithmic trick, and they’re the cleanest illustration of this article’s motif: version 1 assigns each commit a generation of 1 + max(parents' generation) — its topological level, counting up from the roots. The property that makes this useful is simple to state and powerful to use: if gen(A) < gen(B), then A cannot possibly be an ancestor of B. A walk searching from B for A can stop the instant it reaches commits whose generation has already fallen below A’s generation — no further traversal can produce a match. merge-base walks in descending-generation order instead of trusting commit timestamps, which can be skewed by clock drift or rebasing; --ancestry-path gets the same pruning; git log --graph uses a lazy dual-walk keyed on generation so it can start printing history before the full graph has been processed. A later refinement, sometimes called generation number v2 or “corrected commit date,” tightens those bounds further by folding each commit’s own date into the calculation instead of relying on pure topological level — the commit-graph documentation and Git’s release notes don’t cleanly pin which exact release made that refinement the default, so this piece states the mechanism without guessing at a version number (Microsoft DevOps Blog, “Supercharging the Git Commit Graph” series).
The multi-pack-index (MIDX), landing in Git 2.21 (August 2019) with generation performance improved in 2.24 (November 2019), solves a problem that repacking-everything-into-one-pack was originally invented to avoid: once a repository accumulates many packs, every object lookup or hash abbreviation has to fan out across every individual pack’s .idx file, and the cache misses stack up. MIDX stores one sorted object-ID table plus pack-and-offset metadata for the union of objects across every tracked pack, giving O(log N) lookup regardless of how many packs exist. When the same object exists in more than one pack — common after incremental repacks — MIDX prefers a designated “preferred pack,” falling back to the most recently modified pack otherwise. It also defines a pseudo-pack order: a deduplicated concatenation of every pack’s own object ordering. That pseudo-pack order is what let reachability bitmaps be computed over the MIDX rather than tied to one physical pack, once multi-pack bitmap support landed in Git 2.34 — the point where these two structures stopped being separate and became one integrated system (Git documentation, Multi-pack-index format).
| Structure | Shipped | Query it accelerates | What it precomputes | Relationship to the others |
|---|---|---|---|---|
| Reachability bitmaps | Git 2.0 (2014); multi-pack support Git 2.34 (2021) | “What objects are reachable from this commit (or set of commits)?” — the core of clone/fetch negotiation | One EWAH-compressed, XOR-delta bit-vector per selected commit | Since 2.34, computed over the MIDX’s pseudo-pack order rather than one physical pack |
| Commit-graph + generation numbers | Git 2.18 (2018) | “Is A an ancestor of B?” / topological walks — merge-base, log --graph, --ancestry-path | A monotonic generation number per commit, letting a walk exit early | Speeds the graph walk used to reach a commit whose bitmap must be located or extended |
| Multi-pack-index (MIDX) | Git 2.21 (2019) | “Which pack and offset holds this object ID?” across many packs | One sorted-OID table plus pack/offset metadata for the union of all tracked packs | Provides the pseudo-pack order that multi-pack bitmaps compute over |
Read that table as one system with three entry points, not a menu of alternatives. A clone negotiation that hits a commit without its own bitmap still benefits from generation-number pruning to reach a nearby commit that does have one; a repository with many small packs still gets O(log N) object lookups from MIDX regardless of whether bitmaps are enabled at all; and multi-pack bitmaps only became possible once MIDX gave them a stable, unified ordering to compute against.
Geometric Repacking: Keeping the Stack Cheap to Maintain
None of this is useful if keeping it up to date is as expensive as the problem it solves. The traditional approach — repack the entire repository into one giant pack, periodically — gets more expensive every time the repository grows, because a full repack has always required a full reachability walk to decide what belongs in the new pack.
git repack --geometric=<factor> sidesteps that. It arranges existing packs so each successively larger pack holds at least factor times as many objects as the next-smaller one, then computes the minimal “roll-up” of small packs needed to restore that progression. Critically, it determines which objects to repack purely from which packs are being rolled up — no reachability walk required — and folds in any loose objects unconditionally (git-scm.com, git-repack). That’s what makes frequent, incremental, cheap maintenance viable on a repository too large to fully repack often. Paired with multi-pack bitmaps, geometric repacking is what took GitHub’s fleet-wide average repack duration from about a minute down to roughly 15 seconds — a 4× improvement — while saving an average of 5.67 CPU-days per hour, fleet-wide, against the prior single-giant-pack strategy (GitHub Engineering, “Scaling monorepo maintenance,” 2022).
The Transferable Lesson: Precompute a Monotonic Invariant
Step back from Git entirely and the pattern underneath all three structures is the same move, repeated three times against three different queries: precompute a cheap-to-check invariant so a full traversal becomes an early-exit comparison. A reachability bitmap turns “walk the graph and mark everything you touch” into “read a bit that was already set.” A generation number turns “walk until you find the answer, or prove there isn’t one” into “stop the instant a scalar comparison rules a branch out.” Neither trick requires changing the underlying data model — the commit DAG is exactly the same DAG either way — they just refuse to re-derive, on every query, a fact that changes rarely and can be computed once.
This is the identical logic behind a B-tree’s ordering invariant, which lets a lookup descend and discard half the remaining search space at every level instead of scanning; an LSM-tree’s Bloom filter, which lets a read skip an entire SSTable without opening it, at the cost of a small, tunable false-positive rate; and a materialized view, which pays the cost of a heavy join once, on write or on a refresh schedule, so that reads never pay it at all. In every case the win depends on the same three conditions holding: the query runs far more often than the underlying data changes, the precomputed invariant is genuinely monotonic under the operations that matter (a generation number is only useful because “ancestor of” is a strict partial order compatible with topological level — it would be meaningless if history could cycle), and staleness is either impossible or cheap to repair incrementally, the way geometric repacking keeps bitmaps and the MIDX current without a full rebuild.
The question worth carrying into a different system is concrete: if a graph or partial-order traversal is dominating your profile, what auxiliary, monotonic-under-your-operations value could you precompute per node — the way Git precomputes a generation number per commit — that would let most queries exit early instead of walking the whole structure every time?
What This Stack Doesn’t Fix
It’s worth being precise about the boundary of what bitmaps, the commit-graph, and MIDX actually buy you, because it’s easy to conflate two separate budgets. This entire stack makes Git faster at determining which objects a given query touches — the reachability question. It does nothing to shrink how many bytes those objects cost once determined; that remains packfile compression’s job, and packfile compression remains a storage-layer optimization on top of the snapshot data model, not a substitute for it. A system can have an excellent reachability index and a poorly compressed pack, or the reverse — the two problems are solved by different mechanisms and can be profiled separately. Nor does any of this touch working-tree costs — how long checkout or status takes once objects are already on disk — which is a third, separate budget solved by different tools entirely.
It’s also worth noting that this speed isn’t free to produce, only cheap to consume once it exists. Building bitmaps, maintaining the commit-graph incrementally, and keeping MIDX current all cost real CPU on the write side — the Git 2.55 improvement to bitmap-generation time exists precisely because that write-side cost was itself worth optimizing, seven years after the read-side win first shipped.
❓ Frequently Asked Questions
Do reachability bitmaps replace the commit-graph or the multi-pack-index? No. They solve different queries. Bitmaps answer “what’s reachable from this commit” in a lookup instead of a walk; the commit-graph’s generation numbers make ancestor-and-topological walks exit early instead of running to completion; MIDX makes object lookups across many packs O(log N) instead of fanning out per pack. Since Git 2.34, bitmaps are computed over MIDX’s pseudo-pack order, making the three increasingly one integrated system rather than three competing ones.
Why does a reachability query need a precomputed bitmap — isn’t the commit graph small enough to just walk? On a small, young repository, walking it is genuinely fast enough that nobody notices. The cost scales with the size of a repository’s full history, not with the size of any individual request, so it’s exactly the repositories that matter most operationally — long-lived, high-traffic ones like the Linux kernel or a large company’s monorepo — where the walk becomes the dominant cost. GitHub measured that exact walk at over 33 seconds on the Linux kernel repository before bitmaps, versus 1.57 seconds with one (2022 figures).
What is EWAH compression, and why not just store the raw bit-vector? EWAH (Enhanced Word-Aligned Hybrid) is a run-length encoding for bitmaps: long stretches of identical bits — which are common, since a typical commit’s reachable set is either “everything old” or “everything old plus one new blob” — collapse into a short run descriptor instead of being stored bit-by-bit. Combined with XOR-delta encoding against up to 160 preceding bitmap entries, this is what keeps the whole bitmap index down to roughly 5–10% of the pack’s own size instead of ballooning it.
Do reachability bitmaps make packfile deltas unnecessary? No — they solve unrelated problems. Deltas are a packfile storage optimization that reduces bytes on disk and on the wire for objects that already exist as full logical snapshots; they have nothing to do with determining which objects belong in a transfer in the first place. Bitmaps solve that second problem. A repack still deltifies objects for size even when bitmaps make the reachability computation itself instant.
Does every commit in a repository get its own bitmap? No — bitmaps are computed for a selected set of commits, generally recent tips and other commits likely to be requested directly, not the entire history. A request that lands on a commit without its own bitmap still benefits from the surrounding acceleration structures — generation-number pruning helps the walk reach a nearby commit that does have one — rather than falling all the way back to an unindexed traversal.
Is generation number v2 (“corrected commit date”) the default in current Git? The mechanism is real and documented — it tightens generation-number bounds by folding in each commit’s own date rather than relying purely on topological level — but the exact release that made it the default is not something this article states, because Git’s own commit-graph documentation and release notes don’t unambiguously pin it down. Verify against the currently installed Git’s own documentation before relying on the specific version behavior.
📚 Further Reading
- Mastering Graph Cloning: A Beginner’s Guide to Solving the Clone Graph Challenge on LeetCode — the same reachable-set problem bitmaps solve at Git’s scale, worked by hand on a small graph.
- Learning the Brilliance of Graph Theory: From Mazes to Complex Networks — the graph-theory foundations behind DAG traversal and topological ordering.
- Postgres as a Vector Database: What Benchmarks Say — another case study in measuring what a system actually costs, honestly, with sources.
- Measuring Network Performance — the general discipline of turning “this feels slow” into a measured, dated number.
- The Best Books on Distributed Systems (Beginner to Expert) — the indexing and storage-engine literature the B-tree and LSM-tree comparisons above are drawn from.
- Primary sources: Pack format, Bitmap format, Commit-graph format, Multi-pack-index format, git-repack, GitHub Engineering, “Counting Objects” (2015), GitHub Engineering, “Scaling monorepo maintenance” (2022), GitHub Engineering, “Highlights from Git 2.55” (2026), Microsoft DevOps Blog, “Supercharging the Git Commit Graph”.
📚 Recommended Resources
Disclosure: some links below are Amazon affiliate links. If you buy through them, I earn a small commission — at no extra cost to you — which helps keep this site running.
Designing Data-Intensive Applications
Martin Kleppmann & Chris Riccomini · Book · 2nd edition
The book that makes the B-tree, LSM-tree, and materialized-view comparisons in this article click into place. Bitmaps, generation numbers, and the commit-graph are all instances of the same move DDIA spends several hundred pages on: precompute an invariant once so reads don’t pay a traversal cost every time.
Pro Git
Scott Chacon & Ben Straub · Book · 2nd edition
The canonical Git reference, and the book whose “Git Internals” chapter covers the object model, packfiles, and refs this article builds on. The full text is free online at git-scm.com/book under CC BY-NC-SA 3.0 — buy the print edition if you want it on the shelf.
Software Engineering at Google
Titus Winters, Tom Manshreck & Hyrum Wright · Book
The best account of why a company the size of GitHub or Google invests engineering time in things like bitmap indexes and geometric repacking — the economics of tooling at fleet scale, not just at the scale of one repository. Also free in full as HTML at abseil.io/resources/swe-book under CC BY-NC-ND 4.0 — buy the print copy if you’d rather annotate it.
Accelerate
Nicole Forsgren, Jez Humble & Gene Kim · Book · Hardcover
The research behind measuring engineering performance honestly — the same discipline this article applies to Git itself: dated, sourced, vendor-attributed numbers instead of vague claims that a system “feels faster.” A natural next read for anyone who wants GitHub’s fleet numbers to mean something beyond a marketing blog post.