rakulang

rakulang

第二十三天 - Blin，很快就到圣诞节了！

Sun Dec 23, 2018

两年前我已经在出现一篇 advent 文章里提到过 Bisectable，但自那时以来发生了很多变化，所以我觉得是时候简要介绍一下 bisectable 机器人和它的朋友们了。

首先，让我们来定义正在解决的问题。有时会发生提交引入意外更改行为（错误）。通常我们称之为回归，在某些情况下，找出错误并修复它的最简单方法是首先找到引入回归的提交。

Rakudo 2015.12 和 2018.12 之间有9000个提交，尽管它不超过9000，但仍然很多。

幸运的是，我们不需要测试所有修改。假设行为不是一直来回变化，我们可以使用二分法查找。

`git bisect` 和二分法查找 #

基本上，给定任何提交范围，我们在范围的“中间”取一个提交提交并测试它。如果它是“坏”或者它显示“新”（现在是不正确的）行为，那么我们就可以抛弃我们范围的后半部分（因为我们知道更改必须在该提交之前发生或完全在该提交之后）。同样，如果它是“好”（或“旧”），我们会扔掉另一半。因此，我们只需检查log n个修改（≈13），而不是测试所有 9000 次提交。

Git 附带了git bisect为您实现二分法查找逻辑的命令。你所要做的就是给它一些起点，然后对于每次提交它跳转过去，告诉它是好还是坏。如果你做了足够多次，它会告诉你哪个提交有问题。

这一切都很好，但有两个问题。

问题❶：跳过 #

让我们想象一下2 + 2用来返回的情况4（正确！），但现在返回42（……也正确，但不完全对）。

所以你启动了 bisection 过程，git 在修改之间跳转，你测试它们。如果它是4那么good（或old），如果它是42那么它是bad（或new）。但后来你偶然发现了这种行为：

> 2 + 2

Merry Christmas!

… 怎么办？显然，那个具体修改有点特殊。我们无法判断我们的错误是否存在，我们根本无法知道。是的，它不会打印4，但我们正在寻找一个非常具体的错误，因此它也不会被归类为“新”行为。当然，我们可以抛硬币并随机标记为old或者new，并希望圣诞节奇迹……但是有50％的概率（如果我们只看到其中一个）将二分法查找转移到错误的方向。

对于这些情况，git 提供了一个特殊skip命令。

如果你是手动测试，那么处理这些修改就有点简单（只要你记得你应该跳过(skip)他们）。但是，由于问题❷，很多人都倾向于使用git bisect run脚本自动化过程。也可以使用脚本跳过修改（使用退出代码125），但是如何确定应该跳过哪些修改并不是那么明显。

问题❷：构建时间 #

让我们用乐观的数字13来估计我们要测试的修改量。请记住，它不包括我们必须跳过的提交，以及可能需要测试的其他额外构建。

构建rakudo所需的时间因硬件而异，但我们乐观地说，在特定的提交中构建rakudo需要2分钟时间并对其进行测试。

13 × 2 = 26 (minutes)

那不是很方便，对吧？如果在此过程中出现问题……你重新开始，然后等待。

Bisectable #

在2016年，在看到那些必须手动运行 git bisect 的人（实际上，大部分是我自己）的痛苦之后，我想知道：

有没有人想过为每一次提交构建rakudo，以便你可以快速运行git bisect？

该想法的成本效益分析受到了迅速质疑：

AlexDaniel：你认为未来二分法将会很普遍吗？

我提供了非常详细的理由：

perlpilot：是的

三天后，机器人加入了频道。这些反应非常有趣：

哇哦 OooOOOoooh Cooooool

当时我们很少知道结果会怎样。即使我不知道它会变得多么有用。快进2年：

关于提交的大小：我尽量保持它们尽可能小，并且尽可能地包含它们，以便在这种意义上更容易二分，bisectable6 也改变了我编码的方式还有：bisectable6 让我更少担心我提交的更改因为它通常限制很多地点寻找以修复问题，他们可以在几分钟而不是几小时内修复或至少很快显示原因（所以短时间修复可能意味着 revert） \ o /

但它并不总是完美的。引入机器人大约一小时后，它被用于其目的：

bisect：try { NaN.Rat == NaN; exit 0 }; exit 1 moritz：（2016-05-02）https://github.com/rakudo/rakudo/commit/949a7c7

但是，由于一个off-by-one，它返回了错误的提交。实际提交是e2f1fa7，而949a7c7是其父级。

老实说，那时机器人非常糟糕。例如，它完全依赖于退出代码，所以你不能只是把 2 + 2抛给它并期望它检查输出。最终，实施了不同的模式，现在机器人首先检查起点上的行为（例如2015.12和HEAD），并确定执行二分法的最佳策略。例如，如果信号不同（例如SEGV），则它基于信号一分为二。如果信号相同，但退出代码不同，则使用退出代码。如果无法使用其他所有内容，则使用输出进行一分为二。

请记住，如果raku无法构建二进制文件，则可以检查二分法。这意味着在大多数情况下，您不需要添加自己的逻辑来跳过。它不仅将二分法时间从几十分钟缩短到几秒钟，而且还提供更可靠/正确的结果。

存储 #

一段时间之后，提交范围扩展到2014.01…… HEAD，意味着所有提交都是从第一个有关Moar的Rakudo发布开始的。目前它有超过17000个构建。它可能听起来很多，但每个rakudo安装只需≈28MB，这不是太多。拥有几TB存储空间可以让您在未来几年内继续使用。

话虽如此，我的服务器上没有那么奢侈。它有一个120 GB SSD的RAID，因此整个事情不仅要适应这么小的空间，而且还应该为系统的其余部分留出足够的空间。

有很多实验（一，二）涉及找出节省空间的最佳策略，但长话短说，我们可以低至每个版本大约半兆字节！当然，它总是在压缩比和解压缩速度之间进行权衡，但使用现代压缩算法（zstd，lrzip）一切都相对容易。

好的，现在怎么样？ #

因此，bisectable可以在很短的时间内将数千个提交一分为二。它占用的存储空间非常小，并且用户不需要完全理解二分过程。既然二分是免费且容易的，我们可以做更多吗？

是的，Blin！ #

你可能听说过Toaster。Toaster是一种尝试在两个或多个修订版中安装生态系统中的每个模块的工具。例如，假设最后一个版本是2018.12，发布经理即将从主HEAD中删除rakudo版本。然后，您可以在 2018.12和master 上运行 toaster，它会显示哪些模块用于干净安装，但不再做。

这给了我们Rakudo可能出错的信息，但并没有告诉我究竟是什么。鉴于此帖主要是关于Bisectable，你可能会猜到这是怎么回事。

Blin 项目- 重新发明了 Toasting #

Blin是Rakudo版本的质量保证工具。它用于在rakudo中查找回归，但与Toaster不同，它不仅告诉哪些模块不再可安装，还将rakudo一分为二，以找出导致问题的提交。当然，它是围绕Whateverable构建的，因此额外的功能不会花费太多（甚至不需要很多代码）。作为奖励，它生成了很好的图形来可视化问题如何从模块依赖性传播（虽然这不是很常见）。

Blin的一个重要特性是它只尝试安装每个模块一次。因此，如果模块B依赖于模块A，A将被测试并安装一次，然后重新用于B的测试。因为这个过程是并行化的，您可能想知道它是如何实现的。基本上，它使用被低估的react/whenever功能：

# slightly simplified
react {
    for @modules -> $module {
        whenever Promise.allof($module.depends.keys».done) {
            start { process-module $module, … }
        }
    }
}

对于每个模块（我们现在有超过1200个），它会创建自己的whenever块，在满足其依赖关系时触发。在我看来，这是Blin中主要逻辑的全部实现，其他一切只是粘合剂以获得Whateverable和Zef协同工作以实现我们所需要的，+一些输出生成。

在某种程度上，Blin对我们为Rakudo做质量保证的方式没有太大的改变。Toaster已经能够给我们一些基本的信息（尽管速度较慢），以便我们可以开始调查，而在过去，我知道将奇怪的东西（例如带有依赖关系的完整模块）推入二分法。只是现在它变得更容易了，当The Day到来时，我不会因机器人滥用而受到惩罚。

未来 #

Whateverable和Blin一起有243个未解决的问题。这两个项目都非常有用，而且非常有用，但正如我们所说，它们不是很棒。大多数问题相对容易和有趣，但它们需要时间。如果您有任何帮助，或者您想维护这些项目，请随时这样做。如果你想基于Whateverable构建自己的工具（我们可能需要很多！），请参阅这个hello world gist。

🎅🎄， 🥞

git bisect 和二分法查找 #