Denis' Micro Blog

Okay, so you got a bug somewhere.

The tests are all red, and it happened a while back in your commit history, but you can't exactly pinpoint the precise moment.

Inhales... FUUUUUUUUU....

But what do we do now? Well... The faint of heart would now go back to the latest state where you could ensure everything is working as it should be and simply try out every commit from here on. Even writing that one down felt painful. Can we do better?

Actually yes. Let me introduce you to the power of SEARCH ALGORITHMS or to be a bit more precise... BINARY SEARCH.

I mean. If we think about it for a second. We are searching for a certain state in the seas of directly interconnected states, where one ideally comes directly after the last one. What I was describing, in the beginning, was a practical example of a linear search algorithm with a linear complexity. who would've thought...

But if we spend two minutes on Wikipedia, we notice that we can do a lot better, especially when we consider that we have an already "sorted" list of commits, by their commit order.

This is where binary search comes into place since it only has a logarithmic complexity, in its worst case, when we have a sorted list present.

What does that mean strange internet person???

Well, if you know about this stuff, you know that this is pretty good. It means that the amount of time this algorithm needs can be described by a function like this. (Where "n" describes the number of elements)

T(N) = O(log(n))

If you're wondering what the suspicious "O" means. In short, that means that there could be different multipliers and such but the logarithmic function is the most significant factor in this function. If you wanna find out more, look up Big O notation.

Okay. But what does that have to do with our original problem?

If you don't have to look up every element in our list but rather the log(n) elements, this is quite a significant win in my book, which is where git bisect comes into play. It performs a binary search algorithm to look for a faulty commit.

How does it do that? Well... First, we have to define the latest commit, where we can make sure that everything is okay.

We do that by starting out the bisect process. git bisect start

And then, we set the latest good commit. git bisect good <COMMIT HASH>

Finally, we can also describe the earliest commit where the faulty behavior can be found, in a similar fashion. git bisect bad <COMMIT HASH>

Now the "crazy" part starts when we type in... git bisect bad

It picks out the commit which is in the halfway-point between the latest good commit and the earliest bad commit.

We can then manually look if it is a good or a bad commit by whatever testing methods you have. If, by whatever magic you did, you determined that this commit is still bad, then type in git bisect bad. But if it turns out to be a good one, then use git bisect good. Now we have shrunk the possible range where the first faulty commit could be, to be either in the first or the second half, depending on the result of our first check. This means, that we don't have to look through those commits in our bug-hunting adventures anymore. Great.

Now we repeat this process as many times until we find a bad commit with a good commit directly before it and we are done.

Now you should've found the faulty commit in a, for once, efficient manner. Nice.

Stop this wizard by typing git bisect reset and start your bug-fixing adventures. 😅

Good luck on your further quest, and have fun trying out.

See ya.