• 关注官方微信 微信公众号 添加方式:
    1:搜索微信号(gogolinux
    2:扫描左侧二维码
  • 登录 注册
  • 一起学LINUX - GOGOLINUX

    查看: 484|回复: 0
    打印 上一主题 下一主题

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

    [复制链接]

    2

    主题

    2

    帖子

    4

    积分

    新手上路

    Rank: 1

    积分
    4
    跳转到指定楼层
    楼主
    发表于 2019-12-10 06:45:53 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式


    编译:奇安信代码卫士团队
    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 > byteCount) i++ printf("%.1f %s", byteCount / magnitudes, suffixes)
    一般来说,如果已经发布的正确答案的分数为正,那么别人很难追上。在 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
    更多深入讲解可见:。
    这里存在两个有问题的计算:

    • 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: http://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 上复制的情况。
    • 浮点运算很难。
    • 复制代码时请包括适当的归属说明。不然可能有人会找你哟。
    原文链接:

    本帖子中包含更多资源

    您需要 登录 才可以下载或查看,没有帐号?立即注册

    x
    分享到:
    您需要登录后才可以回帖 登录 | 立即注册

    本版积分规则

    官方微博:

    官方头条号:

    官方微信

    手机访问:

    官方微信

    QQArchiver 手机版 小黑屋 一起学LINUX - GOGOLINUX 闽ICP备18025837号-1 Discuz! X3.4 Powered by © 2001-2013 Comsenz Inc. 

    本站资源均来自互联网或会员发布,如果侵犯了您的权益请与我们联系,我们将在24小时内删除!谢谢!

    快速回复 快速发帖 返回顶部 返回列表