git bisect如何跳过选择下一次提交尝试？

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开始(具体来说,从提交ebc9529f开始),Git使用"具有偏差的PRNG(伪随机数生成器)"来确定在跳过一个提交后尝试下一个提交.

我不能说我遵循算法本身(从第一次添加到v2.8.1开始,它看起来基本上没有被触及),但是提交消息可以合理地解释发生了什么:

bisect:在跳过不可测试的提交时使用带有偏见的PRNG

使用具有偏差的PRNG(伪随机数发生器)应该优于在3个固定比率之间交替.

在具有许多不稳定提交的存储库中,它应该防止在许多提交不可测试的区域之间交替.偏见应该有利于可以提供更多信息的提交,因此二分过程不应该失去很多效率.

HPA建议使用PRNG并发现最佳偏差是将PRNG给出的0到1之间的比率提高到1.5.

因此看起来Git选择下一次提交尝试随机,但随机分布被选中(希望)选择提交更多二进制搜索信息的提交,并避免可能在不稳定提交区域中的提交.