How does git bisect skip choose the next commit to try?

Question

When using git bisect, one can run git bisect skip to mark the current commit as being an unbuildable / untestable one, to try and get Git to pick some other commit to test instead.

How does Git decide which commit to try after a git bisect skip? Experimenting shows it's not just an adjacent commit, but I can't work out the pattern.

Edit: I'm aware the basic git bisect is a binary search, but I'm curious about git bisect skip, which is clearly doing something more complicated.

Experimentation shows it's not just picking an adjacent commit; the below creates 100 commits numbered 0–99 then starts bisecting them. The first commit git bisect picks is in the middle, but each git bisect skip thereafter seems to be more-or-less randomly selected.

$ git init
Initialized empty Git repository in .git/

$ for (( i=0; i<100; i++ )); do echo $i > file; git add file; git commit -m $i >/dev/null; done  # Create some dummy commits

$ git bisect start HEAD $(git rev-list --max-parents=0 HEAD)  # HEAD is bad, root commit is good.
Bisecting: 49 revisions left to test after this (roughly 6 steps)
[099e5cf2ccde625f92dc369da6cad0bdf2852ce4] 49

$ git bisect skip
Bisecting: 49 revisions left to test after this (roughly 6 steps)
[88c8208a7c4322222124167e49f07c741af7d3d8] 60

$ git bisect skip
Bisecting: 49 revisions left to test after this (roughly 6 steps)
[04695f2e5b2473c3ac72435c0dbfc3ba1375abda] 88

$ git bisect skip
Bisecting: 49 revisions left to test after this (roughly 6 steps)
[1e9bf3d29589bcac2d8c467245ae8d446c195252] 40

$ git bisect skip
Bisecting: 49 revisions left to test after this (roughly 6 steps)
[9459ed79e4112d674681c8f0f921127217c7ebc6] 13

Jaborandi

Did you read the documentation? I says it uses a binary search. git-scm.com/docs/git-bisect – Lyndes

@Lyndes Did you? It's not very clear on the subcommand skip indeed. – Deutzia

@crashmstr: I know basic use of git bisect is a binary search. But git bisect skip can't just be a binary search because that's not what a binary search does. And yes, I've trawled through the documentation and even started trying to look at the source code before asking here, and I can't find anywhere that explains how the next commit after a git bisect skip is chosen. – Jaborandi

Note that, because of merge commits, git bisect does some pretty magic stuff anyway. – Johns

Answer 1

I did some digging into the Git source code and found most of an answer myself...

As of Git v1.6.4 (specifically, as of commit ebc9529f), Git uses "a PRNG (pseudo random number generator) with a bias" to determine which commit to try next after skipping one.

I can't say I follow the algorithm itself (which, as of v2.8.1, appears to be fundamentally untouched since it was first added), but the commit message does a reasonable job of explaining what's going on:

bisect: use a PRNG with a bias when skipping away from untestable commits

Using a PRNG (pseudo random number generator) with a bias should be better than alternating between 3 fixed ratios.

In repositories with many untestable commits it should prevent alternating between areas where many commits are untestable. The bias should favor commits that can give more information, so that the bisection process should not loose much efficiency.

HPA suggested to use a PRNG and found that the best bias is to raise a ratio between 0 and 1 given by the PRNG to the power 1.5.

So it looks as though Git picks the next commit to try at random, but the random distribution was picked to (hopefully) choose commits that give more information for the binary search and to avoid commits likely to be in regions of untestable commits.

Jaborandi

This is great info! To add more context, a ratio-based skip algorithm had been proposed and H. Peter Anvin advocated for a PRNG raised to the power of 1.5 (to bias away from known good/bad commits) as a way to improve information gain. – Chrysoprase

Answer 2

As the name Git would suggest, the short answer is: It's non of your businness.

The idea behind git bisect is that you specify two endpoints and Git figure it a commit, in between, that it thinks is the useful one for the goal of reducing the number of test.

As the documentation says this is just a binary search, but doesn't specify what kind of algorithm is used

Then git bisect picks a commit between those two endpoints

It may not be a straightforward pick-the-middle-commit binary search, Git may employ any decision algorithm it want and it explicitly doesn't want you to know it so that you won't make assumptions on the commit that will be picked up.

When it comes to changing the picked up commit it gives you two possibilities:

1. You manually choose the new commit. For example with git reset --hard.
2. You tell Git to make a new choice, with git bisect skip.

In the latter case, as when you update the endpoints with good and bad, the decision is made by Git, the way it wants.

---

Out of curiosity I made simple single-branch repository and tried the git bisect skip command.
My version of Git picked up the previous commit.

Deutzia

It's certainly not something I need to know to use the tool, but I disagree that how an open source project works is "none of my business"; if that were the case it wouldn't be open source. I was attempting to sate my curiosity here in the hope someone would just know the answer rather than needing me to go digging into the source code itself. – Jaborandi