LWN: Git 二分法查找中使用概率论！

关注了就能看到更多这么棒的文章哦～

Stochastic bisection in Git

By Jonathan Corbet
December 10, 2021
DeepL assisted translation
https://lwn.net/Articles/877964/

代码质量出现回退的话都不是什么好事。此外，要想在成千上万的改动中找出来导致质量回退的根源，就像是大海捞针。git bisect 命令在这种情况下就可以提供帮助了。它是用来从大量的提交中筛选出引入回归的那一个 commit 的相对比较简单的方法。如果这个命令运行良好的话，它就可以迅速指出是哪个改动导致了特定的问题。不过，git bisect 二分法命令并不是一个完美的工具。如果无法可靠地重现所关注的 bug 的话，它可能就会给出错误的信息。为了让 bisect 在这种情况下也能有用，Jan Kara 提议为 Git 增加一个 "stochastic bisection"（随机二分法） 的支持。

bisect 就是通过二分法搜索来寻找导致问题的 commit。开发者们可以用 git bisect good 来标记出已知的最新一个正确 commit，用 git bisect bad 来标记出一个已知最早出现问题的 commit。然后，Git 会在这两者之间的中间位置附近找到一个 commit，把它 checkout 出来，提供给开发者来尝试重现这个 bug。然后根据测试结果再用 git bisect 命令将该 commit 也标记为 "good" 或 "bad"，然后一直重复这个过程，每次都将怀疑有问题的 commit 的范围分成两半，直到最后只剩下一个 commit 为止。这个提交必定就是引入相关错误的那个罪魁祸首。

这种技术其实很好用。在 12,000 个提交的一次内核合并窗口中引入的 bug 可以在 14 轮 besect 操作内就确定到是哪一个 commit，这可以使得查清实际 bug 的过程更加容易。但是，当处理那些难以重现的错误时，它的效果就不那么好了，毕竟这些错误可能不会在那一次特定的测试中表现出来。分割成 14 个步骤，就意味着开发人员有 14 次机会可能会不正确结果，只要其中有任何一次真的提供了错误的结果，那么这个 bisect 过程就无法给出正确结果了。在邮件列表中有时候就能看到一些无法理解的 bisect 结果，往往就是由这种问题引起的。

Stochastic bisection （随机二分法）是一种试图让 bisect 也能适应于这种情况的方法：在 git 历史中的某一点上是否存在 bug 并不是 100% 确定的。它无法确定哪个提交导致了 bug，但它可以找到可能存在 bug 的那些 commit。要使用这个功能的话，开发者需要在 git bisect start 的 –confidence 选项中提供所需的置信度（是一个 0 到 1 之间的数字）。这个过程将持续进行，直到有一个 commit 被判定为是最有可能的 bug 来源，并达到所要求的置信度（confidence level）。

接下来可以像往常一样开始进行 bisect，会在指定范围的中间位置选取一个 commit。不过每次测试，开发者都会同样需要使用 –confidence 参数来表明他们对报告结果的信心。触发了 bug 的 commit 几乎可以肯定是 bad 的，所以就可以使用下面这样的命令：

git bisect bad --confidence 1.0

然而，如果某次测试中未能复现 bug，那么这个结果就可能不那么清晰了。也许是因为触发该 bug 的那个 race condition 在这次没有触发而已。如果开发者怀疑这个 bug 可能还是存在的，尽管测试中并没有复现，那么他们可以设置一个较低的置信度。

Kara 在这组 patch 的封面邮件中提供了一个例子，展示了这个过程是如何工作的。它从下面这样的 commit 历史开始的：

有问题的提交是 I，但开发者只知道 A 是没问题的，K 则偶尔会出现问题。他们就按部就班用 0.7 的置信度来设置了这些测试结果（其中有一些测试结果就是不准确的）。最终 Git 报告说提交 I 可能是罪魁祸首，达到了置信度 0.9 的标准。

在这个例子中，有一件事会让过去使用过 bisect 命令的开发者眼前一亮。一个正常的 bisect 过程不会把同一个 commit 第二次再提交给开发者来进行测试。过去，一旦对某个特定的 commit 作出判定了，就不会再改变。而 stochastic bisect 则会要求开发者对之前的 commit 重新进行测试，有时会连续多次。这样就会导致一个相当长的 bisect 过程。针对上面显示的 11 个 commit 的历史，正常的二分法只需要四步就能完成了。而使用 stochastic bisect 则需要 14 步才能完成。扩展到更大范围的 commit 历史时，bisect 次数的相对增加比例可能就会大大减少了，但仍然必定会增加 bisect 次数的。不过，使用一个更长的测试过程，总比产生一个无意义的结果要好。

回应这组 patch 的最实质性的评论也许是来自 Taylor Blau 的。Kara 的 patch 试图在正常二分法和随机二分法之间尽可能多地共享代码逻辑，这确实是一个值得追求的目标。但在将两者结合起来的过程中，Kara 导致有些 Git test 测试集中达到的 bisection point 位置发生了变化，新的 bisection point 也确实是有效的，但它们是不同的位置，所以 Kara 也不得不去改变 test 测试集。Blau 希望能看到新功能加入的时候，不会影响到那些不使用它的开发者，也就是过去的行为一点都不会改变。Kara 回应说，他觉得他的解决方案是正确的，但他也表示，如果 Git 开发者要求的话，他愿意修改这里的做法。这个问题目前还没有人给他答复。

当然，还有其他一些需要修改的地方，对于一个复杂的 patch set 来说，通常都是会经过几轮改动的。所以在今后某个时候应该至少会有一个修改过的版本发布到 mailing list 中。随机二分法不会对所有的开发者都有用，但显然有一些情况下更需要这种概率论的方法。因此，如果这项工作的最终改动版本没能进入 Git mainline 的话，那就出乎我们的意料了。

全文完
LWN 文章遵循 CC BY-SA 4.0 许可协议。

欢迎分享、转载及基于现有协议再创作～

长按下面二维码关注，关注 LWN 深度文章以及开源社区的各种新近言论～