git - git bisect skip 如何选择下一个提交来尝试？

Question

当使用 git bisect 时，可以运行 git bisect skip 将当前提交标记为不可构建/不可测试，尝试让 Git 选择其他提交改为进行测试。

Git 如何决定在 git bisect skip 之后尝试哪个提交？实验表明这不仅仅是一个相邻的提交，但我无法找出模式。

编辑:我知道基本的 git bisect 是二进制搜索，但我对 git bisect skip 很好奇，它显然在做更复杂的事情。

实验表明它不仅仅是选择相邻的提交；下面创建了 100 个编号为 0-99 的提交，然后开始将它们一分为二。 git bisect 选择的第一个提交在中间，但此后的每个 git bisect skip 似乎或多或少都是随机选择的。

$ 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

我深入研究了 Git 源代码并自己找到了大部分答案...

从 Git v1.6.4 开始(具体来说，从 commit ebc9529f 开始)，Git 使用“带有偏差的 PRNG(伪随机数生成器)”来确定在跳过一个提交后接下来要尝试哪个提交。

我不能说我遵循算法本身(从 v2.8.1 开始，它似乎自首次添加以来基本未受影响)，但提交消息合理地解释了正在发生的事情:

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.

所以看起来 Git 似乎随机选择下一个提交来尝试，但是选择随机分布是为了(希望)选择为二进制搜索提供更多信息的提交，并避免提交可能位于不可测试的提交区域.