我摸鱼写的Java代码意外称霸StackOverflow十年:有bug!

阅读量    86381 |

分享到: QQ空间 新浪微博 微信 QQ facebook twitter

 

编译:奇安信代码卫士团队

Stack Overflow 上有一个 Java 代码片段称霸十年,是 Java 开发人员最爱复制的片段。超过6000个 GitHub Java 项目中复制并内嵌了该代码,远超 Stack Overflow 上的其它Java 片段。该片段的作者本尊Andreas Lundblad 刚刚发布博客文章来修 bug 了……

 

很久以前,久到离谱……

那还是在2010年,当时我在办公室摸鱼,去Stack Overflow 上精简精简代码,看看自己得到多少小星星。

突然,我看到了一个提问:如何才能把 Java 中的字节数数变成人类可读的格式呢?通俗地讲一下,就是如何把 123,456,789 字节这样的格式转化成“123.5MB”?

这里的隐含规范是,格式化后的字符串的值应该介于1到999.9之间,然后跟一个大小适当的后缀。

当时已经有人给出了一个答案。答案中的代码基于循环。它的思路很简单:try 所有大小,从最大(EB=1-18字节)到最小(B=1字节),然后使用小于字节数的第一个数。用伪代码表示一下就是:

suffixes   = [ "EB", "PB", "TB", "GB", "MB", "kB", "B" ]
magnitudes = [ 1018, 1015, 1012, 109, 106, 103, 100 ]
i = 0
while (i < magnitudes.length && magnitudes[i] > byteCount)
    i++
printf("%.1f %s", byteCount / magnitudes[i], suffixes[i])

一般来说,如果已经发布的正确答案的分数为正,那么别人很难追上。在 Stack Overflow 术语中,这种情况被叫做“西部问题快枪手 (Fastest Gun in the West Problem)”。从本案例来看,因为现有答案确实存在一些缺陷,因此我还有机会反超。至少我还可以大幅度清理下循环代码。

 

代数神助攻

灵感来了。kB、MB、GB等等什么的不就是1000的幂(或者 IEC 标准中的1024)吗?也就是说我可以使用对数而不是循环来计算正确的后缀是什么。

基于这个思路,我给出了自己的答案:

public static String humanReadableByteCount(long bytes, boolean si) {
    int unit = si ? 1000 : 1024;
    if (bytes < unit) return bytes + " B";
    int exp = (int) (Math.log(bytes) / Math.log(unit));
    String pre = (si ? "kMGTPE" : "KMGTPE").charAt(exp-1) + (si ? "" : "i");
    return String.format("%.1f %sB", bytes / Math.pow(unit, exp), pre);
}

当然,我写的代码可读性并不高,而且 log/pow 可能使效率逊色于其它解决方案。但它的优点在于没有循环、几乎没有分支,所以我觉得挺整洁的。

解释下背后的数学知识,其实挺简单的。字节计数表示为 byteCount = 1000s,其中s 表示比例尺(二进制表示法中,使用基数1024)。求解 s 得出 s = log1000 (byteCount)。API 中没有现成可用的 log1000,但是我们可以用自然对数表示为 s=log(byteCount)/log(1000)。之后给出s的下限(转换为整型),因为如果出现的情况是,比如大于1的兆字节 (MB)(但并非完整的千兆字节),则希望使用 MB 作为大小。

此时,如果 s=1,则比例尺为千字节,如果s=2则比例尺为兆字节,以此类推。我们将 byteCount 除以1000,然后在相应的字母前缀上做文章。

提交答案后,我只要静等大家对它的满意度就行了。然而,我万万没料到它之后竟然能成为 Stack Overflow 上被复制次数最多的代码片段。

 

研究代码署名问题的论文来了

时间快进到2018年。一位名叫Sebastian Baltes 的博士在《实证性软件工程》期刊上发表了一篇名为《GitHub 项目对 Stack Overflow 代码片段的使用和署名问题》的论文,它解决的是这样一个问题:复制代码时是否尊重Stack Overflow 的 CC BY-SA 3.0 许可证?也就是说从 Stack Overflow 上复制代码时,应该如何分配署名情况?

他们在分析中从Stack Overflow 数据转出中提取了一些代码片段,并将其和 GitHub 公开库中的代码进行匹配。论文摘要如下:

“我们分析了GitHub (GH) 项目中源自 Stack Overflow 上大量 Java 代码片段的使用和署名问题,并给出大规模的实证研究结果。”(提前剧透:多数人在使用时候并未给出署名。)

他们在论文中给出如下表格:

排在第一名的id 为3758880的答案碰巧就是我在8年前给出的那个答案。此时答案的浏览量已经超过10万次,收获的赞也超过1000个。

在GitHub 上搜一下确实能看到数千次有关 humanReadableByteCount 的结果。

你可以在本地发出的仓库中查看下自己是否用了这段代码:

$ git grep humanReadableByteCount

插播有趣的相遇故事:我是怎么了解到这项研究的?Sebastian 从 OpenJDK 仓库中找到一个匹配结果。其中并没有署名来源而且 OpenJDK 许可证并不兼容 CC BY-SA 3.0。他于是找到运维邮件列表询问 Stack Overflow 上的这段代码是否是从 OpenJDK 复制的,还是有其它情况。

有意思的是,我曾在甲骨文工作,碰巧也是在 OpenJDK 项目组。于是我的前同事也是朋友就回复他说:

你好,

你为啥不直接问Stack Overflow 帖子的作者 (aioobe) 呢?他也是 OpenJDK 的奉献者而且他在甲骨文工作时把这段代码写在了 OpenJDK 源仓库中。

甲骨文并未掉以轻心。我碰巧知道甲骨文的一些人看到这个答复时松了一口气,而且在受到“指责”后简直可以说是喜上眉梢。

Sebastian 之后就直接找我询问,我答复他说:我发布帖子时还未入职甲骨文,而且我并未负责那个补丁。和甲骨文开玩笑啦。之后不久这个问题就被提交给 OpenJDK,代码也被移除了。

 

Bug 来了

我猜你肯定在想,这个代码片段中的 bug 到底是什么啊?

我们再来看下:

public static String humanReadableByteCount(long bytes, boolean si) {
    int unit = si ? 1000 : 1024;
    if (bytes < unit) return bytes + " B";
    int exp = (int) (Math.log(bytes) / Math.log(unit));
    String pre = (si ? "kMGTPE" : "KMGTPE").charAt(exp-1) + (si ? "" : "i");
    return String.format("%.1f %sB", bytes / Math.pow(unit, exp), pre);
}

1018兆兆字节之后是1021泽字节。有没有这样一种可能:输入一个很大很大的数时,会导致“Kmgtpe”字符串索引超出范围?并不会。因为最大的 long 值是 263-1≈9.2×1018 ,因此任何 long值都不会超出 EB范围。

那 SI 和二进制之间会不会混淆?也不会。早期的答案版本有混淆情况但很快就被修复了。

那么 exp 以0 结尾会不会导致charAt(exp-1) 失败?也不会。第一个 if 语句涵盖了这种情况。 exp 的值将始终至少为1。

那么是不是输出结果中出现了诡异的舍入错误?好吧,我们来看看……

 

很多个9

这个答案一直都运行正常,直到 1MB时出问题了。当输入是999,999时,结果(SI 模式)是“1000.0kB”。虽然999,999确实更接近1,000x 10001而不是999.9 x10001 ,但根据标准要求,1,000 的“有效位数”超出了范围。正确的结果应该是“1.0MB”。

不管咋样,所有发布的22个答案,包括使用 Apache Commons 和 Android 库的答案中在本文成文时都存在这个 bug(或其变体)。

那么我们如何修复这个问题呢?首先我们注意到,一旦字节数更接近1×1,0002 (1 MB)而非999.9×10001 (999.9 k),那么指数 (exp) 就应该尽快从“k”转变为“M”。这种情况会在 999,950 时发生。同样,我们应该在超过 999,959,000时,将“M”切换为“G”,以此类推。

为此,我们计算得出这个阈值并且如果 bytes 更大时,则增加exp:

if (bytes >= Math.pow(unit, exp) * (unit - 0.05))
    exp++;

更改后,代码运行正常,但到了 1EB 又出问题了。

 

更多的9

如果输入999,949,999,999,999,999,那么现在的结果就是1000.0 PB,但正确结果应该是999.9 PB。从数学上来说,这个代码结果是准确的,但到底出啥问题了?

这时就有必要看看double 的精度局限性了。

浮点算术101

按照IEEE 754 标准表示的接近0的浮点数值非常密集而大值非常稀疏。实际上超过一半的值都介于-1和1之间,当谈论大的 double 时,实际上像Long.MAX_VALUE 这样的值毫无意义。

double l1 = Double.MAX_VALUE;
double l2 = l1 - Long.MAX_VALUE;
System.err.println(l1 == l2);  // prints true

更多深入讲解可见:https://programming.guide/bits-of-a-floating-point-value.html

这里存在两个有问题的计算:

  • String.format 参数中的除法,以及
  • 增加 exp 的阈值

我们可以切换到BigDecimal,但这样做还有啥乐趣!另外,由于标准 API 中并不存在BigDecimal 日志函数,因此会搞得一团糟。

 

缩小中间值

对于第一个问题,我们将字节值缩小到精度更好的范围,并且对exp 进行相应的调整。最终结果都是四舍五入的,因此我们丢掉最低的有效数字也没事。

if (exp > 4) {
    bytes /= unit;
    exp--;
}

 

调整最低有效位

至于第二个问题,我们确实需要注意最低有效位(999,949,99…9 和999,950,00…0应该以不同的指数结尾),因此该问题要求使用其它解决方案。

首先,我们注意到阈值有12种不同的可能值(每种模式为6种),并且其中只有一个会出现问题。我们可以通过以 D0016 结尾的事实来唯一识别这个出问题的值。如果真是这样,那么我们只要将其调整为正确的值即可。

long th = (long) (Math.pow(unit, exp) * (unit - 0.05));
if (exp < 6 && bytes >= th - ((th & 0xFFF) == 0xD00 ? 52 : 0))
    exp++;

由于我们依赖浮点结果中的特定位模式,因此我们调整了 strictfp 来确保其不受硬件运行代码的影响。

 

负值输入

目前尚不清楚在什么情况下会输入负的字节计数,但既然 Java 中并没有无符号的 long,那么我们最好也把这个问题解决了。现在,如果输入 -10,000,那么结果是 -10000 B。

我们来看下absBytes:

long absBytes = bytes == Long.MIN_VALUE ? Long.MAX_VALUE : Math.abs(bytes);

这个复杂的表达式是由 -Long.MIN_VALUE == Long.MIN_VALUE 的事实造成的。现在我们使用 absBytes 而非 bytes 来执行和 exp 有关的所有运算。

 

最终版本

这是该代码的最终版,本着原始版本的精神进行了精简:

// From: https://programming.guide/the-worlds-most-copied-so-snippet.html
public static strictfp String humanReadableByteCount(long bytes, boolean si) {
    int unit = si ? 1000 : 1024;
    long absBytes = bytes == Long.MIN_VALUE ? Long.MAX_VALUE : Math.abs(bytes);
    if (absBytes < unit) return bytes + " B";
    int exp = (int) (Math.log(absBytes) / Math.log(unit));
    long th = (long) (Math.pow(unit, exp) * (unit - 0.05));
    if (exp < 6 && absBytes >= th - ((th & 0xfff) == 0xd00 ? 52 : 0)) exp++;
    String pre = (si ? "kMGTPE" : "KMGTPE").charAt(exp - 1) + (si ? "" : "i");
    if (exp > 4) {
        bytes /= unit;
        exp -= 1;
    }
    return String.format("%.1f %sB", bytes / Math.pow(unit, exp), pre);
}

需要注意的是,这个代码片段的初衷是避免使用循环和过多的分支。经过把所有的情况一一考虑进去后,它的可读性更差了。我个人并不会把这个代码片段复制到生产代码中。

不过我更新了一个可以用于生产代码的版本,如下:

SI(1 k = 1,000)

public static String humanReadableByteCountSI(long bytes) {
    String s = bytes < 0 ? "-" : "";
    long b = bytes == Long.MIN_VALUE ? Long.MAX_VALUE : Math.abs(bytes);
    return b < 1000L ? bytes + " B"
            : b < 999_950L ? String.format("%s%.1f kB", s, b / 1e3)
            : (b /= 1000) < 999_950L ? String.format("%s%.1f MB", s, b / 1e3)
            : (b /= 1000) < 999_950L ? String.format("%s%.1f GB", s, b / 1e3)
            : (b /= 1000) < 999_950L ? String.format("%s%.1f TB", s, b / 1e3)
            : (b /= 1000) < 999_950L ? String.format("%s%.1f PB", s, b / 1e3)
            : String.format("%s%.1f EB", s, b / 1e6);
}

Binary (1 K =1,024)

public static String humanReadableByteCountBin(long bytes) {
    long b = bytes == Long.MIN_VALUE ? Long.MAX_VALUE : Math.abs(bytes);
    return b < 1024L ? bytes + " B"
            : b < 0xfffccccccccccccL >> 40 ? String.format("%.1f KiB", bytes / 0x1p10)
            : b < 0xfffccccccccccccL >> 30 ? String.format("%.1f MiB", bytes / 0x1p20)
            : b < 0xfffccccccccccccL >> 20 ? String.format("%.1f GiB", bytes / 0x1p30)
            : b < 0xfffccccccccccccL >> 10 ? String.format("%.1f TiB", bytes / 0x1p40)
            : b < 0xfffccccccccccccL ? String.format("%.1f PiB", (bytes >> 10) / 0x1p40)
            : String.format("%.1f EiB", (bytes >> 20) / 0x1p40);
}

示例

 

几个启发

  • Stack Overflow 上的代码片段可能有 bug,即使获赞数千的答案也不例外。
  • 测试所有边缘情况,尤其对于代码是从 Stack Overflow 上复制的情况。
  • 浮点运算很难。
  • 复制代码时请包括适当的归属说明。不然可能有人会找你哟。
分享到: QQ空间 新浪微博 微信 QQ facebook twitter
|推荐阅读
|发表评论
|评论列表
加载更多