git bisect skip如何选择下一个要尝试的提交？

Question

使用 git bisect 时，可以运行 git bisect skip 将当前的提交标记为无法构建/无法测试的提交，以尝试让 Git 选择其他提交来代替测试。

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

编辑：我知道基本的 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

- me_and

---

你有读过文档吗？它说使用了二分查找。https://git-scm.com/docs/git-bisect - crashmstr

你是在问@crashmstr是否了解这个子命令skip，实际上这个命令并不是很清楚。 - Margaret Bloom

我知道git bisect的基本用法是二分查找。但git bisect skip不能仅仅是二分查找，因为这不是二分查找的作用。我已经查看了文档并尝试查看源代码，但是在问这里之前找不到任何解释git bisect skip之后如何选择下一个提交的地方。 - me_and

请注意，由于合并提交，git bisect 会执行一些相当神奇的操作。 - o11c

Answer 1

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

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

我不能说我完全理解算法本身（截至v2.8.1，它似乎自首次添加以来基本上没有被修改过），但提交消息对正在发生的事情做出了合理的解释:

bisect: 当跳过无法测试的提交时使用带有偏差的PRNG

使用带有偏差的PRNG（伪随机数生成器）应该比在三个固定比率之间交替更好。

在有许多无法测试的提交的存储库中，应该防止在许多提交无法测试的区域之间交替。偏向于能够提供更多信息的提交，使得二分搜索过程的效率不会降低。

HPA建议使用PRNG，并发现最佳偏差是将PRNG产生的介于0和1之间的比率取1.5次幂。

因此，Git似乎随机选择要尝试的下一个提交，但是随机分布被选择为（希望）选择能够为二进制搜索提供更多信息的提交，并避免可能在无法测试提交的区域中的提交。

- me_and

---

这是很棒的信息！为了增加更多背景，已经提出了一种基于比率的跳过算法，并且H. Peter Anvin提倡使用PRNG的1.5次方（偏离已知的好/坏提交），作为提高信息获取的一种方式。 - Kevinoid

Answer 2

正如Git的名字所暗示的那样，简短的答案是：这不关你的事。

git bisect的想法是您指定两个端点，Git会找到它认为对于减少测试数量有用的提交。正如文档所说，这只是一个二分查找，但没有指定使用什么样的算法。

然后git bisect在这两个端点之间选择一个提交

这可能不是一个直接的选择中间提交二分查找，Git可以使用任何决策算法，并明确表示不希望您知道它，以便您不会对将被选中的提交做出假设。

当涉及更改选定的提交时，它给您两种可能性：

1. 手动选择新提交。例如使用git reset --hard。
2. 告诉Git进行新选择，使用git bisect skip。

在后一种情况下，例如当您使用good和bad更新端点时，Git会按照其自己的方式做出决策。

---

出于好奇心，我创建了一个简单的单分支存储库，并尝试使用 git bisect skip 命令。
我的 Git 版本选择了上一个提交。

- Margaret Bloom

---

这句话的意思是：“这并不是我使用该工具所必需了解的内容，但我不同意开源项目如何运作与我无关的说法；如果是这样的话，那它就不是一个开源项目。我在这里试图满足自己的好奇心，希望有人知道答案而不需要我亲自挖掘源代码。” - me_and