2012年2月8日 星期三

解 bug 的心理陷阱:我的可以動

昨天又遇到鬼打牆的解 bug 問題,一開始是自己寫的 AP +
 JNI shared library 可以用,但是給同事的 AP call 就有
錯誤,於是卡在我的可以動的迷思中 XD。所以先請同事幫忙
 debug,但是除了一個 static access warning 外,在應用
程式端也沒別的線索了。自己才真正開始回去追 JNI shared
 library,結果確定是該用 jintArray 的型態用錯為 jint
 *。於是修改過後今天給同事確定可以解掉這個問題。但現
在問題變成是,為何原本的寫法我的應用程式可以存取 JNI
 integer array ? XD

另外昨天看到一篇 Joshua Bloch 的 binary search, merge
 Programming Pearls 書(1986, second edition 2000 )中
的演算法,跟他在 JDK 實作 java.util.Array 的 binarySearch (存在九年的 bug) 同樣犯了 divide and
 conquer 取中間數的錯誤:

 6:             int mid =(low + high) / 2;

mid 可能遇到太大的 low 跟 high 造成 mid 發生 integer overflow,大於最大正整數 (2^31 - 1),這個 bug 可以藏
這麼久的原因是之前沒有人測過這麼大量的 binary search 或
 merge sort 解法是

 6:             int mid = low + ((high - low) / 2);

或用 Java 的 unsigned right shift, ">>>", (最高位補 0
 確保為正整數)取代除以 2 較快些

 6:             int mid = (low + high) >>> 1;

C/C++ 參考解法如下:(參考 Nokia 的 Antonie Trux 指出
 C89/90 跟 C++、C99 說明 signed integer 相加 overflow
 的話是未定義行為,因此先轉型為 unsigned int)

 6:             mid = ((unsigned int)low + (unsigned int)high)) >> 1;

該文後面 Joshua Bloch 說明的是這個 bug 讓他學會謙虛,
即使是我們認為理所當然的取平均都可能出錯,細心的設計
、測試的重要性、正規方法、檢視程式碼、靜態分析都是很
棒的,任何單一方法絕對無法保證沒有 bug。即使我們竭盡
全力解一個 bug,也可能要花上幾十年才解掉。因此寫程式
必須小心、防衛並時時警覺。