bisect and your cheatsheet

git bisect: binary search for bugs

The app worked last month, and somewhere in the 500 commits since, a bug crept in. Checking commits one at a time means 500 tests.

Bisect is smarter. It runs a binary search over the history, where each test you perform eliminates half of the remaining commits, the same halving that makes a number-guessing game winnable in a handful of guesses.

$ git bisect start
$ git bisect bad
$ git bisect good a1b2c3d
Bisecting: 250 revisions left to test after this

The bad marks your current commit as broken and the good marks an old commit that was fine, which gives Git the range to search.

Git then checks out the commit halfway between them, leaving you in the detached HEAD state from lesson 9-3. You test the app and report git bisect good or git bisect bad. Either answer eliminates half the remaining suspects, and Git jumps to the middle of what is left. When one commit remains, that is your culprit, and git show from lesson 3-1 reads it. git bisect reset returns you to normal.

The halving is what makes this practical at any scale. 500 commits need about 9 tests, 1024 need 10, and a million need 20, because each test cuts the range in half and log₂ 1024 = 10.

Small commits with honest messages, the habits from lessons 2-3 and 3-3, are what make the result useful once found. Bisect can point at a commit, but only a focused commit with a clear message tells you immediately what went wrong.

For a bug somewhere in the last 1024 commits, git bisect needs about 10 test runs.

Each test halves the suspects, so the range shrinks 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1. That is ten halvings, which is another way of saying log₂ 1024 = 10.

Binary search is the reason bisect scales to enormous histories. Doubling the number of commits adds one test rather than doubling the work, so a repository with a decade of history is barely harder to search than one with a month of it.

Counting the halvings

This counts how many halvings it takes to shrink a suspect list down to one commit, which is the number of tests a bisect costs.

for commits in [8, 500, 1024, 1000000]:
    remaining = commits
    tests = 0
    while remaining > 1:
        remaining = remaining // 2
        tests += 1
    print(f"{commits} commits -> {tests} tests")

Output

8 commits -> 3 tests
500 commits -> 8 tests
1024 commits -> 10 tests
1000000 commits -> 19 tests

The // is Python's whole-number division, so 500 // 2 is 250, and each pass of the loop stands for one bisect test halving the pool of suspects.

Read the four lines together and the shape of the cost is obvious. Going from 500 commits to a million, 2000 times as many, moves the count from 8 tests to 19, barely more than double.

A real bisect can need one test more or fewer than this, depending on how the midpoints round, but the order of magnitude is exactly right.

A recorded session

A final recovery drill, combining lesson 4-3's safety net. You ran git reset --hard one commit too far and an afternoon of work vanished from git log. Get it back.

Each step below shows the command and the output it printed.

Step 1. List every position HEAD has been, to find the lost commit.

~/recipe-book $ git reflog
a1b2c3d HEAD@{0}: reset: moving to HEAD~1
c7d8e9f HEAD@{1}: commit: Add photo of finished pancakes
a1b2c3d HEAD@{2}: commit: Add pancake recipe

Step 2. There it is, c7d8e9f, the commit the reset threw away. Move the branch back onto it.

~/recipe-book $ git reset --hard c7d8e9f
HEAD is now at c7d8e9f Add photo of finished pancakes

Step 3. Verify the history is whole again.

~/recipe-book $ git log --oneline
c7d8e9f Add photo of finished pancakes
a1b2c3d Add pancake recipe

Note that the tool which caused the problem is also the tool that fixed it. --hard moved the branch off the commit, and --hard with the recovered hash moved it back, because the commit itself was never deleted.

Your cheatsheet

Everything from the course, by task:

The right command is git revert <hash>, which adds a new commit that cancels the broken one.

Shared history rules this out of the reset and rebase territory entirely. Teammates have already pulled that commit, so rewriting history would rip commits out from under everyone, which is lesson 9-1's golden rule.

Revert, from lesson 4-3, cancels the change by appending the opposite change. The record stays honest about what happened, everyone's existing commits remain valid, and the next pull is an ordinary fast-forward rather than a reconciliation.

Choosing revert here on the reasoning rather than the recipe is the point. You are now weighing safety on shared history against convenience, which is how a Git user with taste thinks about undo.

The subcommand is git bisect.

You mark one good commit and one bad commit, then test whatever midpoint Git checks out and report the result, and it narrows the range by half each time.

For 300 commits the arithmetic is log₂ 300 ≈ 8.2, so about 8 or 9 tests corner the culprit, which is a few minutes of work in place of a day of guessing.

The name means cutting in two, which is exactly the operation: each answer bisects the remaining suspects and throws half of them away.