复制粘贴一时爽:传播最广的一段Java代码曝出Bug

复制粘贴一时爽,频出bug火葬场。对开发者而言,Stack Overflow和GitHub是最为熟悉不过的两大平台,这些平台充斥着大量开源项目信息和解决各类问题的代码片段。最近,一位叫做Aioobe的开发者在一项调查中发现了一段自己十年前写的代码,这段代码成为了Stack Overflow上复制次数最多、传播范围最广的答案,GitHub的众多项目中也存在这段代码。然而,这位开发者表示这段代码其实是有bug的,并于近日更新了答案并作出说明。

这段代码是干啥的?

2010年的时候,我整天泡在Stack Overflow上回答问题,希望可以提高自己的知名度。当时,有一个问题吸引了我的注意:如何以人类可读的格式输出字节数?举个例子,将“123456789字节”转换为“123.5 MB”的格式输出。

这是现在的截图,但问题确实是这个

这里的隐含范式在于所得到的字符串值应该在1到999.9之间,后面再跟上一个大小合适的单位。当时已经有人给了一条回应。答案中的代码以循环为基础,基本思路非常简单:尝试所有单位,从最大(EB,即1018字节)到最小(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上,这就叫“拔枪最快的赢”。不过,我认为这个答案有缺陷,所以准备重新改改。我意识到,无论是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也可能在一定程度上影响执行效率,但至少这里没有循环,几乎不涉及分支,我觉得还是比较整洁的。

这里面使用的数学方法非常简单。字节计数表示为byeCount=1000s ,其中的s代表小数点后的位数(以二进制表示,则使用1024为基数),求解s,即可得出s=log1000(byteCount)。

API里没有现成的log1000可以直接使用,但我们不妨用自然对数来表示,即s = log(byteCount) / log(1000)。接下来,我们取s的底(即取整数),因为假如我们得出的结果超过1 MB(但不足1 GB),则希望继续使用MB作为表示单位。

此时,如果s=1,则单位为KB;如果s=2,则单位为MB;依此类推,我们将byteCount值除以1000s ,然后取对应的单位。

接下来,我能做的就是等待,看看社区是否喜欢这个答案。那时候的我,绝对想不到它会成为Stack Overflow上复制最多的代码片段。

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);
}

在EB,即1018之后,接下来的单位应该是ZB,即1021。难道是输入量过大导致“kMGTPE”字符串的索引超出范围?不是的,long的最大值是263 - 1 ≈ 9.2 × 1018,因此任何long值都不会超出EB范围。

那么,是SI与二进制之间存在混杂吗?也不是。答案的早期版本中确实有这个问题,但很快就得到了修复。

那么,是不是exp可以为0会导致charAt(exp-1)发生错误?不是的。第一个if语句也涵盖了这种情况,因此exp值将始终至少为1。

那就只剩最后一种情况了,输出结果中是否存在某些奇怪的舍入错误?这正是我们接下来要讨论的部分……

太多个9

这套解决方案一直运作良好,直到字节数量达到1 MB。假定输入为999999字节,那么结果(在SI模式下)将为“1000.0 kB”。尽管999999比999.9 x 10001更接近于1000 x 10001,但根据规范,1000的“有效位数”超出了范围。正确的结果应该是“1.0 MB”。

无论如何,在这个帖子的所有22个答案中(包括使用Apache Commons以及Android库的答案)截至本文撰稿之时都存在这个错误(或者其变体)。那么,我们该如何解决?

首先,我们会注意到,一旦字节数比999.9 x 10001(999.9 k)更接近于1 x 10002(1 MB),则指数(exp)就应由“k”变更为“M”。例如,9999950就符合这种情况。同样的,当我们输入999950000时,我们应该从“M”切换为“G”,依此类推。为了达成这一目标,我们会计算该阈值,一旦字节数超过阈值,则增加exp:

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

调整之后,代码即可正常工作,直到字节数接近1 EB。以输入为999,949,999,999,999,999为例,其目前的结果为1000.0 PB,但正确结果应该是999.9 PB。但从数学上讲,代码结果又是准确的,这又是怎么回事?这里,我们就遇到了double(双)精度机制的局限性。

浮点运算基础知识

由于采用IEEE 754表示方式,因此近零浮点值会非常密集,但大值则非常稀疏。实际上,所有浮点值中的一半都位于-1与1之间;而在谈到大双精度浮点数时,像Long.MAX_VALUE那么大的值已经没有任何意义了。

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

下面来看两项有问题的计算:

  • String.format参数中的除法;
  • exp进位阈值

我们当然可以切换为BigDecimal,但这么干就没意思了。另外,由于标准API中没有BigDecimal log函数,所以问题其实仍然存在。

缩小中间值

对于第一个问题,我们可以将字节值缩小至更合理的精度范围,同时相应调整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,我们最好还是把这个问题考虑进来。现在,如果输入为-10000,那么结果为-10000 B。这里我们引入absBytes:

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

这里的表达之所以如此复杂,是基于-Long.MIN_VALUE == Long.MIN_VALUE这一事实。现在,我们利用absBytes替代bytes执行所有与exp相关的计算。

最终版本

以下是代码片段的最终版本,其中已经对最初版本做了精心调整与改进:

// 来自: 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);
}

请注意,这段代码最初的目标是避免由循环以及大量分支带来的复杂性。在解决了所有极端情况之后,新代码的可读性要比原始版本更差。我个人是肯定不会把这段代码复制到生产代码中的。

这段代码被复制到了哪里?

2018年,一位名叫Sebastian Baltes的博士生在《Empirical Software Engineering》上发表了一篇论文,标题为《GitHub项目中Stack Overflow代码片段的用法与归因》,文章探讨的核心议题只有一个:用户对代码片段的引用是否遵循Stack Overflow的CC BY-SA 3.0许可,即从Stack Overflow上复制代码时,用户应保证何等程度的归因水平?

在分析当中,作者从Stack Overflow数据转储中提取出代码片段,并将其与公共GitHub存储库中的代码进行匹配。下面来看论文的基本发现:

我们进行了一项大规模实证研究,分析了来自各公共GitHub项目中的非常规Java代码片段,对其中实际上源自Stack Overflow的代码片段进行了用法与归因调查。

这篇文章给出了一份表格,而其中ID为3758880的答案正是我八年前发布的那一条。截至目前,这条答案获得了几十万次查看外加一千多个好评。只要在GitHub上随便搜搜,就能找到成千上万条 humanReadableByteCount。

这也就意味着,这段有问题的代码被无数的项目和开发者引用,要验证这段代码是否也在自己的本地存储库内,请执行以下操作:

$ git grep humanReadableByteCount

心得摘要

最后,我希望告诉广大开发者Stack Overflow 上的代码片段可能存在bug,即使得到无数好评也改变不了这一事实;一定要对所有极端情况做出测试,特别是测试那些复制自Stack Overflow的代码;浮点运算很复杂,也很困难,在复制代码时,请确保了解代码背后的逻辑和使用规范。

原文链接:

https://programming.guide/worlds-most-copied-so-snippet.html

  • 发表于:
  • 本文为 InfoQ 中文站特供稿件
  • 首发地址https://www.infoq.cn/article/85S4ENv0M560FI8Yvqkk
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券