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 

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.