Practical Tips for Advanced Git Bisect

Practical Notes on Advanced Git Bisect

This is an adaptation from my Twitter thread:

Recap of Bisect

I assume you’ve used or heard of git bisect. If you’ve neither heard off nor used git bisect before, then I encourage you to give it a try. Franziska Hinkelmann provides a good intro and a test repo to find a bug with git bisect.

Recap:

  1. git bisect start BAD GOOD
  2. <RUN TEST>
  3. label result with git bisect good or ... bad (or skip)
  4. Goto 2 until git bisect tells you it’s done.

This then does a binary search1 through all commits between the GOOD and the BAD commit. After each step you have to label the current commit with good, bad or skip. Because binary search halfs the search range in every step, the number of commits to check is approximately log2(N), where N is the number of commits between GOOD and BAD. This means you can check 1000 commits in just 10 steps!


Do yourself the favor and always start git bisect with the good and bad commits! That way you can “git bisect reset” it later, and start over using your shell history.

git bisect start BAD GOOD

git bisect start main v0.1.0 # Assuming that main is bad and v0.1.0 is good.

This is not necessary.

You can also just start with git bisect start and then git checkout BAD; git bisect bad and the same for the bad commit. But as I always mess up, it is just easier to keep this in the shell command directly.

Of course, you can also inspect what the initial good/bad commits were with git bisect log.

How to remember what comes first in the arguments? Well, git is a naughty program, so BAD comes first. 😉


Ignore Feature Branches

You probably want --first-parent. This has been only available in Git since v2.29 (Q4 2020) 4.

In good Git tradition, it is confusingly named. Essentially it only considers changes directly on main. Feature branches are ignored.

This option is particularly useful in avoiding false positives when a merged branch contained broken or non-buildable commits, but the merge itself was OK. 1

Use it like so: git bisect start --first-parent main v0.1.0

Filter Directories

You can filter directories or files by starting it like this: git bisect start -- <path> . Only commits which modify <path> will be considered.

This is less useful in practice because of the logarithmic nature of binary search. Having only half the commits to search through saves only a single step. -- first-parent will help more.


Fix Your Mistakes

I always mess up, so I save the result:

  1. git bisect log > ../bisect.log
  2. Fix your mistakes in ../bisect.log
  3. Start again: git bisect replay ../bisect.log

(Put the log outside your git dir, otherwise your repo is dirty.)


Run

This is where the advanced usage of git bisect starts.

git bisect run is awesome and plays well with Unix tools.

For example, if you remember make, you can use it like this to find build failures: git bisect run make

git bisect run make -C <build_dir> if you use CMake and have configured it once before. (do yourself a favor and put it completely outside your repo)


This works for almost anything:

However, when it is that easy to run bisect, you should’ve added this to CI long ago.

If the one line does not work, write a script –>

Bisect Scripts

Run scripts like so: git bisect run ~/custom_script.sh

  1. Put them outside the repo.
  2. Test them manually first.
  3. “set -e” is good.
  4. Know about exit codes. 0: good, 1-124: bad. 125: skip. 126-255: abort.
  5. Only one line should return “bad” (1-124).
  6. Exit 125 is for skipping commits!

Use the aborting exit codes to know where the script failed.

cmake -B /tmp/build -S . || exit 128
make -C /tmp/build || exit 129

The exit code will tell you which step failed.

If you want to skip build failures, use exit code 125.

cmake -B /tmp/build -S . || exit 125
make -C /tmp/build || exit 125
make tests

Scripts: “Are we there, yet?”

Some scripts take very long. The below command tells you how many commits remain. You can run it in a second terminal.

git bisect visualize --oneline | wc -l.

The number of remaining scripts is approximately ceil(log2 ( N )) where N is the result from the line before. 2


After your script has run, immediately save the run in a log!

git bisect log > ../bisect_run.log

Again git bisect replay let’s you fix any mistakes.


Check your bisect results! (This literally happened to me while writing this thread.)

Repeat your script and see if the output of the first breaking commit is the same error that you were looking for.

If not, make your check more specific. For example, by piping stderr through grep -q.

Philosophy

Things where git bisect will not work.


Prefer correctness over speed, especially if you wrote a run script.

There will be ~10 steps. If it is automatic and runs in the background it can take twice the time. Having to do it three times because the script found the wrong answer because you messed up takes longer.

Maybe I can convince you that if you have a script that you can trust, you can have a coffee, or work on something else. If you cannot trust your script, then you will have to manually check multiple times.

An easy way to do so is to throw your build artifacts away!

BUILD_DIR=$(mktemp -D)
cmake -B $BUILD_DIR ...

Hilarious things that went wrong WHILE WRITING THIS THREAD.

  1. Did not use cargo clean and regretted it.
  2. Did not grep for the exact error and found a different error.

All your labels are bad or good? Your script is probably broken.

Remember, if the bug introduction is uniformly distributed, binary search should have bad/good 50% each. Even if there’s a heavy skew because you started with a really early version, 100% one way is unlikely.


When Git Bisect Is Helpful

git bisect is mostly good for features that you didn’t have under test.

Bad reason: Unit tests fail. (Just add ‘em to CI.) Good reason: A user reports a regression on a platform you cannot easily have in CI.

Bad reason: (In C++), a new problem cannot be reproduced in a Debug build, or with printf statements added. (You very likely have UB, and the bug won’t be deterministic between builds.)

Another good reason: Working on an unfamiliar code base.

Probabilistic Bisect

And finally, if you ever find a good use case for probabilistic (Bayesian Search) bisect, please, please let me know.

I haven’t had bugs that looked random actually be random. Mostly they’re just depending on something outside “the system”.

https://github.com/siedentop/bbchop https://en.wikipedia.org/wiki/Bayesian_search_theory

Even More Details

Want to learn how the algorithm works? And why it is not simply binary search?

Christian Couder wrote about it: https://mirrors.edge.kernel.org/pub/software/scm/git/docs/git-bisect-lk2009.html


Resources:

1, 2, 3.

https://stackoverflow.com/questions/17267816/git-bisect-with-merged-commits https://twitter.com/chsiedentop/status/1305636746122592256 https://mirrors.edge.kernel.org/pub/software/scm/git/docs/git-bisect-lk2009.html


  1. Below I will explain why this is not exactly binary search in the presence of branches. ↩︎

  2. You could compute that using awk or bc. However, it takes me too long to figure this out, and computing approximate log2 is easy enough. For the record it is echo 65 | awk '{a = log($1)/log(2); printf("%0.1f\n", a)}'. ↩︎