# Git bisect

Go bug hunting armed with a binary search tree

When I started using git as my VCS I skimmed the docs and git-bisect caught my eye. I got acquainted with it rather quickly and have been using it regularly ever since. git-bisect is a little handy git sub-command typically used to quickly narrow down the commit where a bug was introduced in a code base. It uses a simple binary search tree algorithm (BST) to test out different revisions by parting the remaining search space in half.

Basically, one needs just one thing to start bisecting: the last known version that works—where the bug was not there. Then, we start bisecting with:

git bisect start             # start bisecting
git bisect good good-commit  # good-commit revision is last known to work


The system will automatically start the BST and sequentially check out different commits for you to test. Once a commit has been tested we can mark it bad if the bug is still there:

git bisect bad


Or good, if the bug was not yet present:

git bisect good


When we have exhausted the search the system will inform us that we’ve found the offending commit. Then, we can end the process with:

git bisect reset


We can also visualize the current bisect progress with gitk using:

git bisect visualize


Note that this last command only works if a bisect is in progress in the current directory.

The number of steps needed to locate a bug within a list of $$n$$ commits is roughly ~$$\mathcal{O}(\log{}n)$$. This is very good news, especially with projects with long histories and lots of commits. In the following example, we have in the history commits A to I, while main is the current head. In that case, we would find the culprit in 3 steps.


Visiting order:             3     2        1

Commits:               A -> B -> C -> D -> E -> F -> G -> H -> I -> main
^    *                                        ^
|                                             |