Git Bisect Visualization | Binary Search for the First Bad Commit

The idea: binary search over history

Something worked in v1.0 and is broken on main. Somewhere between them one commit brought the bug in: the first bad commit. git bisect finds it by binary search. Every commit after the good one, up to the bad one, is a suspect. Git checks out the suspect in the middle, you test it, and your answer throws away half of the suspects.

15 suspects #1 to #15 between good v1.0 and bad main. Test #7: good, 8 suspects left. Test #11: bad, 4 left. Test #9: bad, 2 left. Test #8: good, 1 left: #9 is the first bad commit. — Each test halves the suspects: 15 → 8 → 4 → 2 → 1, so 4 tests instead of up to 15.

With 15 suspects that is 4 tests (⌈log₂ 15⌉ = 4). Testing one commit at a time from v1.0 would take up to 15. With 1000 commits bisect needs about 10 tests. On the canvas green commits are good, red ones are bad, orange ones are skipped, the yellow one is HEAD under test, and the blue band shows the suspects left.

Starting a bisect

git bisect start
git bisect bad main        # or just: git bisect bad   (HEAD)
git bisect good v1.0
Bisecting: 7 revisions left to test after this (roughly 3 steps)
[4e70] update deps

Git saves the two ends as refs, refs/bisect/bad and refs/bisect/good-a1f3, and writes each command to .git/BISECT_LOG. Then it checks out the commit in the middle as a detached HEAD. In a linear history the middle is easy: the suspect that has half of the suspects behind it. Git counts, for every suspect, how many suspects it reaches (itself and its suspect ancestors) and picks the one closest to half.

The message counts what is left after this test, in the worse case: of 15 suspects, #7 reaches 7, so if #7 is good, 15 − 7 = 8 remain, one of which (#15) is already known bad: 7 revisions left to test. The roughly 3 steps is Git's estimate of the tests still needed after this one. (Demo: find the bad commit by hand, step by step)

good, bad and skip

git bisect good: this commit and everything before it are fine. The left edge moves up to it.
git bisect bad: the bug is here or earlier. refs/bisect/bad moves here and everything after it is out.
git bisect skip: this commit cannot be tested (it does not build, the test cannot run). Git keeps it as a suspect but checks out a nearby commit instead.

When one suspect is left, its parent is good and it is bad: Git prints 05ca is the first bad commit with its message and diff stat.

git bisect run: let a script decide

git bisect run ./test.sh runs the script on each commit Git checks out and marks the commit from the script's exit code, until the first bad commit is found. (Demo: git bisect run ./test.sh does it for you)

Exit code	Meaning	Mark
`0`	tests pass	good
`1` … `127`, except 125	tests fail	bad
`125`	cannot test this commit (e.g. the build is broken)	skip
`128` or more	the script itself broke	bisect stops

A script that exits 125 when make fails keeps a broken build from being counted as the bug. (Demo: a broken build: exit 125, git bisect skip)

When skip is not enough

A skipped commit is still a suspect, so if it sits right next to the culprit Git cannot tell the two apart. With the build broken on #8 and the bug in #9, #7 is good and #9 is bad, but #8 could not be tested: either #8 or #9 brought the bug in. Git says "There are only 'skip'ped commits left to test. The first bad commit could be any of: b38f 05ca. We cannot bisect more!" (Demo: a skip next to the culprit: could be any of)

One wrong mark, wrong answer

Bisect trusts every mark. Mark a bad commit good by mistake and it throws away the half that holds the bug, then confidently names a commit that is not the culprit.

Correct: #9 marked bad keeps #8 and #9 as suspects and finds #9. Wrong: #9 marked good by mistake keeps #10 and #11 and names #10, which is not the culprit. — A wrong "good" on #9 moves the search to #10 – #11, and bisect names #10: a wrong answer, given with full confidence.

The fix is the log: git bisect log > fix.txt, delete the wrong line, git bisect reset, then git bisect replay fix.txt replays the good marks without testing them again. A flaky test does the same damage, so make the test repeatable first. (Demo: one wrong mark finds the wrong commit)

Finishing, and real histories

git bisect reset deletes refs/bisect/* and the log and puts HEAD back on the branch you started from. Real histories have merges: Git then weighs each suspect by the number of suspects it reaches through all of its parents and still picks the one closest to half, so the search stays close to log₂ of the number of suspects. If "good" and "bad" read badly (you look for the commit that fixed something), git bisect start --term-old=slow --term-new=fast or old / new rename them.

The search itself is the one from binary search on a sorted array; HEAD, detached HEAD and refs are on Git branches and HEAD, and undoing the bad commit once found is on reset, revert and restore.

What the page leaves out

Merge commits: the history here is one straight line.
How Git picks a commit after a skip: real Git uses a fixed pseudo-random offset away from skipped commits; the page takes the next-closest suspect to half.
The working tree change on each checkout, git bisect visualize, --first-parent and limiting the search to paths (git bisect start -- src/).
Full 40-digit hashes and the diff stat printed with the first bad commit.