Every engineer has run git bisect at least once and walked away with the right commit and the wrong mental model. It feels like binary search — mark “good,” mark “bad,” repeat until the range collapses — so most people assume it’s cutting a numbered list in half, the way you’d binary-search a sorted array. It isn’t. Git’s history is a directed acyclic graph: merges give commits more than one parent, topic branches run concurrently, and there is no single line to cut in half. git bisect has to compute a midpoint before it can use one, and the algorithm that computes it — the reachability scoring behind git rev-list --bisect — is the actual clever part, not the “keep halving” framing everyone remembers.
That distinction matters beyond trivia. Once you understand what bisect is really doing, you know exactly when it’s safe to trust, exactly how it degrades, and exactly why the same technique generalizes to problems that have nothing to do with source code.
Why a DAG Doesn’t Have a Middle
In a sorted array, “the middle” is index N/2 — a position, computed by arithmetic on indices. Git’s history has no positions, only a partial order defined by ancestry: commit A precedes commit B only if A is an ancestor of B along some path through the graph. Two commits on different branches, or two commits that both feed into a later merge without either descending from the other, aren’t comparable at all — neither is “before” the other in any total sense. Ordinary binary search’s guarantee — eliminate roughly half the remaining candidates on every test — depends on a comparison operator you can trust to split the search space evenly. On a DAG there is no such < sitting around waiting to be used. Bisect has to build one, from scratch, on every step, out of reachability.
The construction starts by narrowing the field. The candidate set is every commit that could plausibly be the first bad one: reachable from the known-bad commit, but not reachable from any known-good commit. In plumbing terms, that’s precisely git rev-list <bad> --not <good1> <good2>…, the same git-rev-list machinery Git’s revision-walking commands are built on. Call the size of that filtered set N. This is the step most explanations skip past — bisect doesn’t search “all of history,” it searches only the region genuinely still in question, which is why a wide, well-behaved history collapses fast even when the repository behind it is enormous.
git rev-list --bisect: The Scoring That Replaces “The Middle”
For every candidate commit X still in the set, Git counts how many of X’s own ancestors also fall inside the set — call that ancestors(X) — and scores X as:
score(X) = min(ancestors(X), N − ancestors(X))Read it as: the number of commits guaranteed to be eliminated in the worst case, whichever way the next test comes back. If X turns out good, everything among X’s ancestors(X) ancestors is now known good, and drops out of the set. If X turns out bad, everything not among X’s ancestors is now known bad-or-irrelevant, eliminating N − ancestors(X) of them. The score is the smaller of those two guarantees — the worst case Git can promise you, not the best case it hopes for. Git checks out whichever candidate has the highest score, because a higher score means a tighter worst-case guarantee no matter which way the test lands.
That score can never exceed N/2 — you cannot guarantee eliminating more than half of an as-yet-unclassified set with a single yes/no test — so the moment a candidate’s score actually hits N/2, the search has found the DAG’s genuine structural middle for this step, and nothing scores higher. git rev-list --bisect is the plumbing command that runs this exact computation and hands the porcelain git bisect the single commit to check out next. Two flags make the otherwise-invisible math inspectable: --bisect-all lists every remaining candidate annotated with its own dist= score, so you can see the whole ranked field instead of trusting the winner blindly, and --bisect-vars emits the same computation pre-formatted as shell-assignable variables — bisect_rev (the next commit to test), bisect_nr and bisect_all (candidates remaining and total), bisect_good/bisect_bad, and an estimate of remaining steps — which is what the git bisect porcelain itself sources internally to drive the loop, according to gitrevisions and the git-rev-list documentation.
That’s the whole trick, stated plainly: “the middle” isn’t a position bisect looks up, it’s a property of reachability that bisect recomputes from the current candidate set on every single step.
The Bisect Command Surface
| Command | What it does |
|---|---|
git bisect start [<bad> <good>…] | Begin a session, optionally supplying the endpoints immediately |
git bisect bad [<rev>] | Mark a revision (default: current checkout) as exhibiting the problem |
git bisect good [<rev>] | Mark a revision as not exhibiting the problem |
git bisect skip [<rev>…] | Mark the current or named revision untestable; Git picks a different candidate |
git bisect run <cmd> | Automate the good/bad loop by executing <cmd> at every checkout |
git bisect visualize (view) | Open the remaining candidate set in gitk or git log form |
git bisect log / git bisect replay <file> | Save a session to a file, or restore one verbatim from a saved log |
git bisect reset | End the session and return to the branch/commit you started from |
Everything in that table is porcelain wrapped around the same git rev-list --bisect scoring described above — the commands manage state (which commits are known-good, known-bad, or skipped) and delegate the actual “what to test next” decision to the plumbing every time.
Why It Lands Near O(log₂ n) in Practice — and Why That’s Not a Proof
On a linear history the ancestor-counting scoring collapses into ordinary binary search: every commit’s ancestor count is just its position in the line, so the highest-scoring candidate really is the numeric midpoint. That’s the mental model most people carry into bisect, and on a straight line it happens to be correct.
Real repositories aren’t linear — merges branch and rejoin constantly — yet Git’s own write-up on the algorithm, git-bisect-lk2009, reports that real-world bisections at Linux-kernel scale typically resolve in 15 to 20 steps regardless of the size of the range being searched. That’s the empirical signature of roughly logarithmic behavior holding up on genuinely merge-heavy history, not just on toy linear cases.
But “close to O(log n) in practice” and “provably optimal” are different claims, and collapsing them is the single most common overstatement made about bisect. A 2023 paper by Courtiel, Dorbec, and Lecoq, Theoretical analysis of git bisect (arXiv:2312.13644), formalizes the greedy min(ancestors, N−ancestors) strategy as an algorithm and proves it is not globally optimal on general DAGs — there exist adversarially shaped DAGs where the greedy per-step choice forces exponentially more tests than an optimal strategy would need. The same paper is careful to draw the boundary where that matters: on DAGs of bounded in-degree — graphs where no commit has more than a small, fixed number of parents, which is exactly what ordinary merge history looks like, since merges essentially never combine more than a couple of branches at once — the greedy strategy stays within a constant factor of optimal, roughly 1/log₂(3/2) ≈ 1.71×, and the authors propose a provably better alternative specifically for that restricted case.
The honest framing an architect should carry away: git bisect is a very good heuristic, well matched to the shape of DAGs real version-control systems actually produce, not a proven-optimal search algorithm in the general case. That gap between “good heuristic” and “optimal algorithm” is worth internalizing well past Git — it’s the right way to reason about any plausible-sounding greedy strategy headed for production. Characterize the input distribution you actually expect; don’t assume a worst-case guarantee you never proved.
The Assumption Everything Rests On: A Monotone Predicate
Every step above assumes something bisect never checks for you: that “bad” is upward-closed from wherever it was introduced. Once a commit is bad, every descendant of it must also be bad; once a commit is good, every ancestor of it must also be good. That’s a monotone predicate over the DAG — exactly one good-to-bad transition along any path from a known-good commit to the known-bad one.
The classic way to break it: a bug is introduced, then fixed, then reintroduced later. Bisecting across that whole span no longer sees a single transition — it sees good → bad → good → bad — and the ancestor-counting scoring has no way to detect that it’s happening. Depending on which candidates the search happens to land on, bisect can converge on the reintroduction commit, the original introduction commit, or something in between that tested bad purely by which path got walked, and it reports whichever wrong answer it lands on with exactly the same confidence as a right one. The git-bisect documentation describes the workaround directly: graft in a synthetic branch via git replace that removes the confounding fix-and-reintroduce pair from the history bisect actually walks, restoring a single clean transition before you start.
Flaky tests are a related, unsolved gap. If the predicate — usually a test command — is nondeterministic, one unlucky “bad” result on an actually-good commit corrupts the entire session, and core Git has no built-in retesting or confidence tracking to catch it. That’s precisely why external tools exist purpose-built for noisy predicates (Bayesian search that tolerates uncertain results, instead of deterministic reachability scoring that assumes every test result is ground truth) — a signal that “monotone and deterministic” is a hard requirement for handing a search to bisect, not a nice-to-have.
git bisect skip: Falling Back Toward the Center, Not the Next-Best Score
Some commits genuinely can’t be tested: they don’t build, a dependency didn’t exist yet at that point in history, the environment isn’t set up for that revision. git bisect skip marks the current candidate untestable and asks for a different one to try instead. The natural assumption is that Git simply offers the next-highest-scoring commit from the same ranked list. It doesn’t. Untestable commits tend to cluster — a broken build usually stays broken across a run of consecutive commits — so handing you the next-best-scored neighbor would likely land you on another untestable commit immediately, wasting the step. Instead, git-bisect-lk2009 documents a deliberately different fallback: the choice is biased pseudo-randomly, weighted via a square-root transform of a random draw, back toward the center of the remaining candidate range — a purposeful jump clear of the suspected bad neighborhood rather than a creep along its edge.
--first-parent compounds usefully with this. Restricting bisect to first-parent history treats an entire merge as a single unit of blame, which is the practical way to avoid false “untestable” hits from a bisect step that lands mid-way inside someone else’s topic branch — commits that were never meant to build in isolation and were only ever meant to be evaluated as a finished merge.
git bisect run: Full Automation and Its Exit-Code Contract
Once you have a scriptable reproduction of the problem — a failing test, a build check, a benchmark threshold — git bisect run <cmd> checks out every candidate the scoring picks, executes <cmd>, and interprets its exit code without a human anywhere in the loop.
Exit code from <cmd> | What git bisect run does |
|---|---|
0 | Treated as good — the commit does not exhibit the problem |
1–124, 126, 127 | Treated as bad — the commit exhibits the problem |
125 | Treated as untestable — equivalent to git bisect skip |
Anything outside 0–127 (128+, e.g. killed by a signal) | Aborts the bisection entirely — not recorded as a data point |
125 is a deliberate, unusual choice, not an accident of implementation — it sits outside the range most build tools and shells use for their own ordinary pass/fail codes, which keeps a script’s normal exit conventions from accidentally colliding with bisect’s own. A working bisect run command is typically a small wrapper: build, then run the reproduction, exit 0 on success, exit 1 (or anything else in the bad range) on the reproduced failure, and exit 125 whenever the build itself fails, so a broken build never gets miscounted as a bad code change. Left alone, bisect run drives exactly the scoring and skip machinery described above to completion and reports the first bad commit directly — the whole algorithm this article has walked through runs unattended, purely off those exit codes, per the git-bisect documentation.
Once bisect has named a commit, the natural next move is finding out why it changed the behavior — which is a different query with its own machinery. git log -S<string> and -G<regex> (the “pickaxe,” documented alongside rename and copy detection in git-diff) search diff content rather than commit reachability, and pairing a bisect result with a pickaxe search over the same file is a common way to go from “which commit” to “which line, and why.” History-simplification defaults in git-log — the TREESAME pruning that governs what git log -- path shows by default — are worth knowing about here too, since a bisected commit’s own history view can quietly omit contributing commits from a merged-away branch unless you ask for --full-history.
Beyond Source Code: Bisecting Any Monotone Predicate Over a Version DAG
None of the machinery above is actually specific to source code. What git bisect automates is binary search over any monotone predicate defined on an ordered or partially ordered space, driven by a scoring function that computes which candidate splits the remaining uncertainty most evenly — instead of assuming a total order hands you a midpoint for free. Anywhere you’re tempted to binary-search a non-total-order structure, that’s the transferable move: build a “which candidate eliminates the most in the worst case” score, don’t assume sorting by some attribute gives you one automatically.
Any system that produces a version DAG and a testable predicate qualifies. Configuration history — which change to a feature flag or an infrastructure setting crossed a canary threshold. Data-pipeline history — which upstream schema or dataset revision broke a downstream job. Deployment history — which release in a chain introduced a latency regression. The moment that state is checked into Git and the predicate is scriptable, git bisect run can be pointed at any of these exactly as it would be pointed at a failing unit test. That generalization is worth sitting with: automated binary search over a version-controlled DAG is a debugging superpower most engineers only ever apply to one narrow case — source code — when the underlying technique applies to anything monotone and ordered. It pairs naturally with the discipline of reading code as its own skill: bisect tells you which commit, a careful read of the diff tells you why, and neither replaces the other. It’s also the same instinct that makes DAGs worth understanding as graph theory in the first place — a partial order is a graph problem the moment you stop assuming it’s a line.
What This Means for You
- Treat
git bisectas reachability scoring, not sorting. The “middle” it finds on any given step is a property of the DAG, recomputed from the current candidate set — not a cached position. - Don’t cite bisect’s speed as proof of optimality. Cite it as “close to logarithmic in practice on bounded-fan-in DAGs,” and know the 2023 counterexample exists for adversarially shaped ones.
- Before bisecting a suspected fix-then-reintroduce bug, confirm you actually have a single good→bad transition. If you don’t, graft around the confound with
git replacerather than trusting whatever commit the search happens to land on. - Wire
bisect runpredicates to exit125for genuinely untestable states — don’t let a broken build masquerade as a bad code change and pollute the search. - Look past source code. Any monotone predicate over a version DAG — config, data, deploys — is a
bisect runcandidate the moment it’s checked into Git and scriptable, whether or not the “commits” are code at all. If you’re automating that kind of regression hunt as part of a larger test harness, the same discipline that makes test suites trustworthy enough to bisect against is what makes the predicate itself safe to hand to a machine, the same way mutation testing checks whether a test suite would actually catch the regression bisect is hunting for.
📚 Further Reading
- git-bisect — the command reference: subcommands,
--first-parent, terminology options, and the exit-code contract forbisect run. - git-bisect-lk2009 (“Fighting regressions with git bisect”) — the detailed algorithm write-up this article draws its scoring and skip-fallback explanation from.
- Courtiel, Dorbec & Lecoq — “Theoretical analysis of git bisect” (arXiv:2312.13644, 2023) — the proof that greedy bisect is not globally optimal on general DAGs, and the bounded-fan-in result that explains why it works so well in practice anyway.
- git-rev-list — the plumbing bisect runs every step:
--bisect,--bisect-all,--bisect-vars. - gitrevisions and git-log and commit-graph — revision syntax, history-simplification defaults, and the generation-number invariant that makes ancestry checks like bisect’s fast at scale.
- Reading Code Is the New Superpower Skill for Engineers — what to do with the commit bisect hands you.
- Learning the Brilliance of Graph Theory — the DAG intuition underneath everything in this article.
❓ Frequently Asked Questions
Is git bisect actually a binary search?
Yes, but not the array kind. It’s binary search over a partial order: instead of an index arithmetic midpoint, every step computes a score — min(ancestors(X), N − ancestors(X)) for each remaining candidate X — and checks out whichever commit that score says splits the current uncertainty most evenly. On a linear history the two definitions happen to coincide.
How many steps does git bisect actually take?
Close to O(log₂ n) in practice. Git’s own documentation reports real-world bisections on Linux-kernel-scale history typically resolving in 15 to 20 steps, regardless of how large the searched range is. That’s not a worst-case guarantee, though — see the next question.
Is git bisect‘s algorithm provably optimal?
No, and this is the most commonly overstated claim about it. A 2023 paper (arXiv:2312.13644) proves the greedy scoring strategy is not globally optimal on general DAGs — adversarial shapes exist where it needs exponentially more tests than an optimal strategy. On bounded-fan-in DAGs, the shape ordinary merge history actually produces, it stays within roughly a 1.71× factor of optimal, which is why it performs so well on real repositories despite the negative general-case result.
What breaks a git bisect run?
A predicate that isn’t monotone — most commonly a bug that was introduced, then fixed, then reintroduced, which creates more than one good→bad transition along the searched path. Flaky, nondeterministic tests are the other major failure mode: one wrong result corrupts the whole session, and core Git has no built-in mechanism to detect or retry it.
What does git bisect skip actually do?
It marks the current commit untestable and asks for a different candidate — but not simply the next-best-scored one. Because untestable commits cluster (a broken build tends to stay broken for a run of nearby commits), the documented fallback biases the next pick pseudo-randomly back toward the center of the remaining range, deliberately jumping clear of the suspected bad neighborhood.
What exit codes does git bisect run expect from my script?
0 for good, any code from 1 to 127 except 125 for bad, and 125 specifically for “this commit can’t be tested” (treated like git bisect skip). Any other exit code — typically a signal-killed process at 128 or above — aborts the whole bisection instead of being recorded as a result.
📚 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.
Bisect is a search algorithm wearing a debugging tool’s clothes. These are the books for going deeper on both halves of that — the discipline of isolating a regression in code you didn’t write, and the internals git rev-list --bisect is actually built on.
- Working Effectively with Legacy Code — Michael Feathers · Book. The canonical text on getting unfamiliar, undertested code safely under control — the exact situation you’re usually in when a
bisect runpredicate has to be written against code you didn’t author.
- Refactoring: Improving the Design of Existing Code (2nd ed.) — Martin Fowler · Book. A catalog of small, named, safe transformations — the same discipline that keeps a commit history bisectable in the first place, since bisect only works cleanly against a history of small, single-purpose changes.
- Version Control with Git (3rd ed.) — Prem Kumar Ponuthorai & Jon Loeliger · Book. The deepest print treatment of Git’s command surface and plumbing layer, including the revision-walking machinery
git bisectsits on top of.
- Pro Git (2nd ed.) — Scott Chacon & Ben Straub · Book. Also free in full at git-scm.com/book under CC BY-NC-SA 3.0 — read it there first. The print edition is a convenient reference if you’d rather have it off-screen; chapter 10 (“Git Internals”) is the closest match to this article’s register.
For the algorithm itself rather than the porcelain around it, James Coglan’s Building Git rebuilds Git’s internals from scratch in Ruby, chapter by chapter — no Amazon listing exists for it (it’s sold ebook-only, direct from the author). If that angle interests you, it’s worth buying directly from shop.jcoglan.com/building-git — a non-Amazon purchase, no affiliate link here.