浏览器中的浮点,第2部分:错误的Epsilon

2020-10-12 20:51:20

几年前,我做了很多关于浮点数学的思考和写作。这很有趣,我在这个过程中学到了很多,但有时我很长一段时间都没有真正使用那些来之不易的知识。因此,当我最终处理一个需要一些专业知识的bug时,我总是非常高兴。下面是我在Chromium中调查过的(至少)三个浮点错误故事中的第二个。这一次,我实际上修复了这个错误,既有Chromium版本,也有googletest版本,这样后代就不会感到困惑了。

这个bug是一个突然开始发生的不可靠的测试失败。我们讨厌不及格的测试。当它们开始发生在一项多年没有改变的测试中时,它们尤其令人困惑。几周后我被拉去调查。错误消息(对行长度进行了一些编辑)开始如下所示:

井。听起来很糟糕。这是一条googletest错误消息,指出本应在1.0范围内的两个浮点值实际上被512分隔。

浮点数之间的差异是一条直接的线索。这两个数字正好相差2^9,这似乎非常可疑。巧合吗?不是的。消息的其余部分列出了被比较的两个值,这让我更确定了根本原因:

如果你在IEEE754战壕里花了足够的时间,你会立即意识到正在发生什么。

如果你读了上周的那一集,你可能会觉得这些数字的大小是一样的,这可能是似曾相识的感觉。这纯属巧合--我只是在用我收到的号码。这一次它们是用科学记数法印刷的,这样就有了一些多样性。阅读上一集了解更多背景信息。

基本问题是上周问题的变体:计算机中的浮点数与数学家使用的实数不同。它们越大,精度就越低,在测试失败的数字范围内,处理的所有双精度值必然是512的倍数。双精度数的精度为53位,而这些数字远远大于2^53,因此精度大大降低是不可避免的。现在我们可以理解这个问题了。

测试使用两种不同的方法计算相同的值。然后,它正在验证结果是否接近,其中“接近”的定义是在1.0以内。计算方法产生非常相似的答案,因此大多数情况下结果会舍入为相同的双精度值。但是,正确的答案时不时地会出现在一个尖点附近,一个计算会向一个方向取整,另一个计算会向另一个方向取整。

剔除指数后,我们可以更容易地看到它们之间的距离是512。测试函数生成的两个无限精确的结果始终相差小于1.0%,因此当它们的值为429时,如429…。10653.5和429…。10654.3,它们都会四舍五入到429…。10688。当无限精确的结果接近4293431141623410944这样的值时,麻烦就来了。该值正好是两个双精度之间的一半。如果一个函数生成429个…。10943.9,另一个函数生成429…。10944.1,然后这些结果--它们之间只有0.2%的距离--在不同的方向四舍五入,最终得到512%的距离!

这是尖点或阶跃函数的本质。你可以有两个结果,这两个结果是任意接近的,但是它们在一个尖点的两边-恰好是两个双精度之间的一个点-因此它们在相反的方向上舍入。经常建议更改舍入模式,但没有什么帮助-它只会移动尖端。

这就像是在午夜时分出生--最微小的变化都可能永远改变你出生的日期(也许是年份、世纪或千年)。

我的提交消息可能过于戏剧化,但它没有错。我觉得自己是唯一有资格处理这种情况的人:

我的意思是,我多久才能通过提交消息(相当合理地包含指向两(2!)个链接的提交消息来实现对Chromium的更改!)。我的博客帖子。

这种情况下的修复方法是按照计算值的大小计算相邻双精度之间的差值。这是使用很少使用的nextafter函数完成的,如下所示:

Nextafter函数查找下一个双精度值(在本例中为无穷大),然后减法(这是准确的,非常方便)找出该量级的双精度值之间的差值。正在测试的算法可能会固有地给出1.0的误差,因此ε必须至少有那么大。这种epsilon计算使得检查这些值要么在1.0范围内,要么是相邻的双精度数变得很琐碎。

我从来没有调查过为什么测试突然开始失败,但我怀疑计时器频率或计时器起始点已经改变,从而使数字变得更大。

它困扰着我,因为它需要深奥的浮点知识才能理解这个问题,所以我想修复googletest。我的第一次尝试失败了。

我最初试图修复googletest,以便每当通过一个毫无意义的小epsilon时都会使Expect_Near失败,但显然Google内部有很多测试-想必还有更多Google外部的测试-滥用Expect_Near on Double。它们传递的epsilon值太小而没有用,但是它们比较的数字是相同的,因此测试通过。我修复了12个Expect_Near的用法,但没有对问题产生任何影响,然后就放弃了。

直到我开始写这篇博客文章(几乎在错误发生三年后!)。我意识到如何安全、轻松地修复谷歌测试。如果代码使用带有太小epsilon值的EXPENCE_NEAR,并且测试通过(意味着这些值实际上是相等的),那么这不是真正的问题。只有在测试失败时才会出现问题,所以我需要做的就是在失败的情况下查找过小的epsilon值,然后显示一条信息性消息。

我进行了更改,现在2017年失败的错误消息如下所示:

Expect_Microsec和Converted_MicroSecond之间的差值为512,其中Expect_MicroSecond的计算结果为4.2934311416234112e+18,Converted_Microsec的计算结果为4.2934311416234107e+18。abs_error参数1.0的计算结果为1,该值小于此量级数字的双精度之间的最小距离512,从而使此EXPEART_NEAR检查等同于EXPERT_EQUAL。请考虑改用EXPECT_DOUBLE_EQ。

请注意,EXPECT_DOUBLE_EQ实际上并不检查是否相等-它检查双精度数是否在最后一个位置(ULP)的四个单位内相等。有关此概念的详细信息,请参阅我的比较浮点数帖子。

我希望大多数软件开发人员都能看到新的错误消息,并被送上正确的道路,我认为googletest修复最终比修复Chromium测试更重要。

这篇文章发表在Chromium,Computers and Internet,Floating Point和标记为Googletest,Precision的网站上。为固定链接添加书签。