tech-sjh

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 sort 的實作 bugJoshua Bloch 發現 Jon Bentley 的 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,也可能要花上幾十年才解掉。因此寫程式必須小心、防衛並時時警覺。



沒有留言:

張貼留言

版權宣告、免責聲明


創用 CC 授權條款
本著作係採用創用 CC 姓名標示-非商業性-相同方式分享 4.0 國際 授權條款授權.
免責聲明: 本文所載資料僅供參考,並不構成投資建議,
讀者閱讀或使用該資料所導致結果需要自擔風險與責任,
作者概不承擔閱讀人行為之任何風險與責任。
除非有特別宣稱,作者言論並不代表所屬任何團體、公司、或其他人意見。