git-bisect is a command within Git. It checks out commits so that you can find the one where a problem was introduced. As the title says, it’s a great debugging tool– even if you’re not using it!
How Bisect Works
See, what it does is a binary search. Cut the sequence of commits in half and test the commit between them. Does that commit have the problem? If so, it started in that commit or earlier. Otherwise, it started in the later half. Repeat.
When the list is only one commit long, there’s your culprit.
Why is this genius? Well, binary search runs in a logarithmic number of steps. If you have 100 commits, the most you’ll have to test is (log base 2 of 100) 7.
1000 commits? 10.
1,000,000 commits? 20
But What if I’m Not Using Git?
Well, what if you’re using Subversion or some other VCS without bisect? While bisect semi-automates the process for you (or totally if you have the right kind of test script) this isn’t a hard algorithm to do by hand.
Manually checking out and testing 20 commits (or revisions, or whatever they’re called in your mesozoic VCS) is going to be annoying, but probably something you can do in an hour or so, especially if management is mad at you because stuff’s broken, and no one knows why.
Not Just for Finding the Bad Commit
And this goes for other things besides a list of commits (log2 of a billion is just 30, by the way. Thirty!). Let’s say you have a set of programs that more or less act as a data pipeline. And something’s going wrong in that pipeline.
Check the bit in the middle.
Is the middle program misbehaving in a way that would indicate your problem? If yes, the problem’s there or upstream, else it’s downstream. Take that half and look at the one in the middle. Repeat until your suspect list has only the culprit.
You can do this for anything where you can divide the search space into groups, and test each group as a whole. If you just have the source code of a program, maybe you can divide it into subsystems, sub-sub-systems, modules, lines, etc.
Does It Always Work?
Sometimes there are confounding factors. Maybe there are complex interactions between components of the pipeline. Maybe the test is non-deterministic. At this point, you’ll have to use logic, intuition, and your knowledge of the system to approximate the process.
Still, this technique can help in a *lot* of cases. It’s what makes me really good at debugging. Maybe too good, as far as my career is concerned, so that’s something to keep in mind if you don’t want to always be fixing others’ shit.
Anyway, now you have my superpower too.
This was originally a Twitter thread. Credit goes to Steve Yegge for saying effectively this in a blog post way back when (I don’t remember what post it was; it wasn’t specifically about debugging), and Julia Evans‘ recent debugging tweets that got me thinking about how I debug.