Categories
程式開發

複製粘貼一時爽:傳播最廣的一段Java代碼曝出Bug


複製粘貼一時爽,頻出bug火葬場。對開發者而言,Stack Overflow和GitHub是最為熟悉不過的兩大平台,這些平台充斥著大量開源項目信息和解決各類問題的代碼片段。最近,一位叫做Aioobe的開發者在一項調查中發現了一段自己十年前寫的代碼,這段代碼成為了Stack Overflow上複製次數最多、傳播範圍最廣的答案,GitHub的眾多項目中也存在這段代碼。然而,這位開發者表示這段代碼其實是有bug的,並於近日更新了答案並作出說明。

這段代碼是乾啥的?

2010年的時候,我整天泡在Stack Overflow上回答問題,希望可以提高自己的知名度。當時,有一個問題吸引了我的注意:如何以人類可讀的格式輸出字節數?舉個例子,將“123456789字節”轉換為“123.5 MB”的格式輸出。

複製粘貼一時爽:傳播最廣的一段Java代碼曝出Bug 1

這是現在的截圖,但問題確實是這個

這裡的隱含範式在於所得到的字符串值應該在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  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 = 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 = 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。

複製粘貼一時爽:傳播最廣的一段Java代碼曝出Bug 2

這也就意味著,這段有問題的代碼被無數的項目和開發者引用,要驗證這段代碼是否也在自己的本地存儲庫內,請執行以下操作:

$ git grep humanReadableByteCount

心得摘要

最後,我希望告訴廣大開發者Stack Overflow 上的代碼片段可能存在bug,即使得到無數好評也改變不了這一事實;一定要對所有極端情況做出測試,特別是測試那些複製自Stack Overflow的代碼;浮點運算很複雜,也很困難,在復制代碼時,請確保了解代碼背後的邏輯和使用規範。

原文鏈接:

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