Git: the basics of git bisect

The binary search algorithm

The name “bisect” comes from the binary search algorithm that the command employs. The search repeatedly divides in two, or bisects, the list of commits until the responsible one is found.

For example, say you know that a certain bug appeared at some point between the v8 tag and the latest commit on main:

v8 ----------------------- main

After you start git bisect, the first step in its binary search tests the halfway point, which we’ll call commit A:

v8 -----------A----------- main

Say the bug does not exist in commit A. You tell git bisect that it exhibits the old bug-free behaviour, from which it assumes that every commit between v8 and A is clear. The search continues by testing the commit halfway between A and main:

v8 -----------A-----B----- main

The algorithm repeatedly subdivides until it narrows in on the single responsible commit. If B turns out to show the new buggy behaviour, the next commit will be C:

v8 -----------A--C--B----- main

And if C shows the new buggy behaviour, the search would test D:

v8 -----------A-DC--B----- main

If D turns out to be bug-free, the bisect session will be finished, concluding that C introduced the bug.

A binary search is way faster than a linear search, which tests all commits one by one. Whilst a linear search can be so slow as to be impractical, a binary search never takes that many steps. Mathematically, a binary search only needs to test log₂(n) commits:

This slow growth makes it feasible to run git bisect even on huge commit ranges.

Subcommands and workflow

git bisect has several subcommands, but for basic usage, you’ll only need these four:

The typical workflow is:

1. Start
   1. Run start to initialize the session.
   2. Run old to mark a previous commit as old.
   3. Run new to mark a commit as new, typically the latest one.
2. Binary search
   1. git bisect selects a commit, switches to it, and asks you to test it.
   2. You run your test command.
   3. If the commit exhibits the old behaviour, run old, else, run new.
   4. Loop to step 2a, as git bisect runs the binary search algorithm, until it reports the responsible commit.
3. Finish
   1. Run reset to end the session and return to the branch you were on.
   2. Decide how to act on the result. For example, you might revert the responsible commit.

Let’s look at an example, after a quick note on terms.

The “old” and “new” terms

Originally, git bisect focused on finding regressions, so it used the terms good and bad. Those terms are confusing in other situations though, for example when finding when a bug was fixed, you’d need to use them backwards. Because of this, Git 2.7 (2016) introduced the more neutral old and new terms.

good and bad are still supported subcommands, and they often appear in other tutorials. But here, we’ll stick to old and new, since they are universal.

(It’s also possible to pick custom terms, such as slow and fast, but we won’t cover that.)

An example git bisect session

Imagine you are building a website about your boat-spotting passion. You get the site up and online and proudly screenshot it:

After a couple more days of work, you look at the home page again. You realize in shock that you’ve accidentally made the footer text massive!

Oops.

Looking at the code, you struggle to see the issue. It’s not even clear which file is responsible - it could be HTML, CSS, or maybe something else.

You check the log since the first deployment, which has the tag deploy-1:

$ git log --oneline deploy-1~..
cbd08bc (HEAD -> main, tag: deploy-3) Nav spacing
9b27483 Add 'Avoid huge ships' page
4833ad2 Extra welcome paragraph
611aa1c Add emoji
a514f80 Tweak font sizes
1378388 (tag: deploy-2) Increase <a> underline gap
e0df7a4 Add 'Anchor guide' page
8bd9715 Use blue colours
c5e04d8 Add 'Best boats' page
08b974c Add favicon
8a8d3d2 Add 'Boat or ship?' page
ced2603 (tag: deploy-1) Home page and styles

There are 11 commits to check. You decide to use git bisect to find the responsible commit.

First, you start the session:

$ git bisect start
status: waiting for both good and bad commits

Note that Git uses the legacy terms good and bad for these initial “status” messages.

You tell Git that the commit tagged deploy-1 exhibits the old behaviour (small footer text):

$ git bisect old deploy-1
status: waiting for bad commit, 1 good commit known

Then, you tell Git that the current commit exhibits the new behaviour (large footer text):

$ git bisect new
Bisecting: 5 revisions left to test after this (roughly 3 steps)
[e0df7a4c1176d5d591dc9012b20d117ffd8e94bc] Add 'Anchor guide' page

There’s no need to provide a commit reference as new defaults to the latest commit (HEAD).

Second, you go through the binary search loop. After being told both the old and new commits, git bisect has already started the search.

The above output reports that five more commits (“revisions“) will need testing, which will take about three steps. It then tells you that it switched to a commit halfway between the two points, with its full commit SHA and message “Add 'Anchor guide' page”.

You test this commit by checking the page in your browser:

The footer text is still small, so this commit exhibits the old behaviour. You tell Git this by running git bisect old:

$ git bisect old
Bisecting: 2 revisions left to test after this (roughly 2 steps)
[611aa1c48f18c83fb69ff8b3533197df6f3847a5] Add emoji

The next step of the search is this “Add emoji” commit. You check your browser again:

Aha, large footer text! That’s the new behaviour, so you run:

$ git bisect new
Bisecting: 0 revisions left to test after this (roughly 1 step)
[a514f80fbba3b1b3b08e62d37233cdbfc8c979d0] Tweak font sizes

You check in your browser once more:

Yup, the large footer text, which you record with:

$ git bisect new
Bisecting: 0 revisions left to test after this (roughly 0 steps)
[1378388b4a6860b005f65b17de51d07fe86ba4a7] Increase <a> underline gap

Nearly there: “roughly 0 steps” left. Checking again, you see small footer text:

When you run git bisect old this time, it finishes the search:

$ git bisect old
a514f80fbba3b1b3b08e62d37233cdbfc8c979d0 is the first new commit
commit a514f80fbba3b1b3b08e62d37233cdbfc8c979d0
Author: A Hacker <hacker9001@funmail.example>
Date:   ...

    Tweak font sizes

 style.css | 13 +++++++------
 1 file changed, 7 insertions(+), 6 deletions(-)

git bisect reports the SHA of the “first new commit“, the one that introduced the change. It then gives more details with the output of git show --stat for that commit.

Third, you finish the bisect session and act on the information. “Bisecting“ is a special status for your repository, shown in git status:

$ git status
HEAD detached at 1378388
You are currently bisecting, started from branch 'main'.

nothing to commit, working tree clean

You need to exit this special status, and “reattach your HEAD“ (return to a branch), before making commits. Do so with git bisect reset:

$ git bisect reset
Previous HEAD position was 1378388 Increase <a> underline gap
Switched to branch 'main'

Git has returned to the branch you were on before starting the bisect session. From here you can fix the issue.

One good idea is to look at the problematic commit in detail with git show:

$ git show a514f80fbba3b1b3b08e62d37233cdbfc8c979d0

In the displayed diff, you spot the commit changed the footer’s styles like so:

@@ -39,5 +40,5 @@ h1 {
 }

 footer {
-  font-size: 0.7em;
+  font-size: var(--size-step-1);
 }

This looks like a typo, using step “1” instead of step “-1”, which requires two hyphens. You try adding the extra hyphen:

@@ -44,5 +44,5 @@ nav a {
 }

 footer {
-  font-size: var(--size-step-1);
+  font-size: var(--size-step--1);
 }

…and the footer is fixed:

Great work. Time to commit, push, and deploy.

Thanks git bisect!

Further sections

After this introduction to the basics, the book covers more advanced git bisect usage:

• Mark a commit as untestable with git bisect skip
• Automate testing with git bisect run
• Automate testing of performance regressions

Check it out to read these sections and many more.

Fin

Boldly bisect and be a bug bane,

—Adam