讓我印象深刻并很喜歡的一個bug
譯文【51CTO.com快譯】那是在2013年11月初，我和朋友在準備參加一年一度的美國計算機協會（ACM）主辦的國際大學生程序設計競賽（ICPC）區域賽，選擇的項目是各種算法和數據結構。據我了解，跳表并不經常用于編程比賽，但是它是一種用戶維護有序元素的數據結構。我們認為將跳表添加到自己的庫也許是個好主意。（注意：我們選擇的編程語言C++已經通過其標準庫，提供了平衡二進制搜索樹，但是不支持擴增（augmentation），編程比賽中經常需要用到擴增。）
于是，我們晚上就開始行動，將跳表添加到自己的庫。我的朋友找到了舊的實現方法，將低級C編寫的程序轉換成更易使用的高級C++。完成后就開始測試它，首先我們做了幾個小小的手動測試，沒有發現問題。然后進行更全面測試，開始生成大量的隨機性測試用例（test case），將跳表的結果與C++的set進行比較。看了看一些舊的Github提交代碼后，我發現這個程序看起來基本上是這樣：
因代碼中某個地方有錯誤（bug），引起了這個內存損壞。我們花了好長時間分析代碼，查找可能解釋得通的原因，但是結果一無所獲。后來想到也許是轉換過程中犯了錯誤，我們就回過頭去檢查原始的實現方法，修改了測試生成器，然后使用低級接口再次運行程序。這回運行起來很順暢，沒有錯誤！我們更加確定是轉換過程中犯了某個錯誤，接著我們回到轉換后的代碼，更細致地分析代碼，但由于毫無進展。***我們決定掏出大家伙用GDB調試器（https://en.wikipedia.org/wiki/GNU_Debugger）來運行程序。
我的朋友在GDB方面比較有經驗，就讓他來帶路。我的記憶有點模糊，但這大約發生了什么。我們觀察到的***件事情是錯誤出現在一個節點的析構函數中，接著在那里釋放一些內存。遺憾的是，并沒有查出為何會出現這樣的情況。在反復的調試器中，我們得到了一個大突破。跳表的析構函數似乎被調用了不止一次。這就可以解釋我們看到節點的析構函數出現奇怪的行為以及內存錯誤。在修改了代碼輸出一些調試信息后，我們證實了情況就是這樣，但是那也很奇怪。我們沒有顯式調用析構函數，所以它唯一被（隱式）調用的地方是在程序末尾。
于是從頭查閱代碼，終于明白了析構函數為什么莫名其妙地被調用了多次。我還記得，我和朋友同時發現了這點，我們互相對視一秒鐘之后哈哈大笑，意識到我們有多可笑。
根源就出在size()函數上。不是跳躍表的size()函數，而是我在代碼開頭定義的那個size()函數，如下所示：
我之前定義這個便利函數是為了消除關于帶符號整數和無符號整數之間的比較的一些警示信息，在測試代碼中用了它幾次。比如說，確保跳躍表中的元素數量 (t1)等于set中的元素數量（t2）時，我們是這么做的：
那么，這個函數到底錯在哪里呢？問題在于，參數x由值傳遞（這是C++中的默認模式），而不是由引用傳遞。這意味著每當我們調用函數，給它傳遞某個對象（這里是跳躍表），就會發生下列情況：
1. 對象被拷貝
2. 副本被傳遞給函數。
3. 函數使用對象的這個副本來執行；當函數終結時，
4. 副本（通過調用析構函數）被銷毀。
所以，每當測試代碼調用size(t1)，它就會使用拷貝構造函數，對跳躍表作一份拷貝，然后調用副本的析構函數。
未實現拷貝構造函數或析構函數函數時，C++會提供一個健全的默認實現。實際上，如果我們剛使用了默認的實現，就不會有這個錯誤。然而，當對象分配內存（使用跳躍板就是這樣），用戶通常想自定義實現拷貝構造函數，以便拷貝已分配內存的實際值（而不是默認的實現那樣僅僅拷貝指針）。但是我們剛實現了析構函數，而不是拷貝構造函數。于是當跳躍表的副本被拷貝后（為了size()函數），默認的拷貝構造函數只是將指針拷貝過去。然后，副本的析構函數被調用后，它釋放指針的內存。而由于這是跳躍板的原始副本使用的內存，現在它不可以被使用。但測試代碼繼續下去，因而遇到許多內存錯誤，最終崩潰。
但是這不是size()函數引起的唯一不良反應。不妨考慮下面這段代碼：
它創建了100萬個整數的向量，然后迭代處理這個向量，將每個值設為42。這通常會在你的普通計算機上運行幾毫秒（我的計算機上實際用了4毫秒）。然而，由于ize()的參數由值傳遞，100萬個元素的向量拷貝到循環的每次迭代。又由于有100萬次迭代，這要花很長的時間。實際上，這在我的計算機上耗時13分鐘38秒。
不管怎樣，不妨回到我和朋友認識到什么引起內存錯誤的那一刻。我不僅認識到當前編寫的size()函數可能有什么影響，我還明白：由于這個函數實際上來自默認C++模板（我將編輯器配置成這樣每當創建一個新的C++文件，自動導入該模板），這個錯誤就會出現在我長期以來編寫的基本上所有C++代碼里面。至少幾個月來是這樣！
當然，這解決起來輕而易舉，從提交的這段代碼（https://github.com/SuprDewd/CompetitiveProgramming/commit/a72e4ec132d595beb7614c11e41bebf76e12f937）可以看出，我們的測試程序在解決了這個問題后運行起來毫無問題。
后記
很高興發現了這個問題，這是一次很好的學習過程。自那以后，我對于如何聲明函數很謹慎。但愿這是好事。
不過，我對這件事做了反思。
為何這個錯誤會出現？正如前所述，我開始使用這個size()函數的原因是為了消除編譯器警告信息。在C++的標準庫中，大多數容器的size()函數返回類型size_t的整數，這是無符號整數。所以，如果你編譯下面這樣的一段代碼：
- for (int i = 0; i < v.size(); i++) {
- }
編譯器就會給出關于帶符號整數和無符號整數之間的比較的警告信息。看到大量這樣的警告信息很快會讓人乏味。另一個相關問題如下。比如說你想迭代處理除容器***一個元素之外的所有部分。你可能這樣來實現這個部分：
- for (int i = 0; i < v.size() - 1; i++) {
- }
但是容器為空時，這段代碼無法正確運行。由于v.size()返回的是無符號整數（這里值為零），減1會下溢，給出size_t的***表示值，而不是預期的-1。這反過來會導致***循環。
要解決上述兩個問題，一個明顯的簡單辦法就是將結果轉換為整數，如下所示：
- for (int i = 0; i < (int)v.size() - 1; i++) {
- }
但是由于經常為循環編寫這種代碼，每次編寫會很煩人。我認為在編程比賽界很常見的另一個辦法是，定義諸如下列宏命令之類的命令：
- #define SZ(c) (int)(c).size()
然而像下面這樣使用它：
- for (int i = 0; i < SZ(v) - 1; i++) {
- }
當我開始參加編程比賽時，可能見過這個宏命令好幾次；有時我決定編寫自己的版本。我覺得SZ不好看，更習慣于鍵入size，于是我想繼續這么做。但是用名稱size創建宏命令會有點危險，因為size是個常見的變量名稱，這會引起麻煩。于是，我走另一條路，創建了下列函數，而不是宏命令：
- template <class T> int size(T x) { return x.size(); }
我不確信為什么沒有讓參數由引用傳遞，但是確信在我開始參加編程比賽之前（因而在我編寫這個函數之前）知道區別所在。但是很容易犯這個錯誤，哪怕是經驗豐富的編程人員，要是他在實現這種看似微不足道的函數時沒有高度集中注意力的話。
我還想知道為什么之前沒有遇到問題。一個原因可能是，我缺乏經驗，不知道這種循環會運行多快。另一個因素也是這個事實，參加編程比賽的程序員通常沒必要為編寫拷貝構造 函數和析構函數而操心。進程終結時，通常我們就讓C++運行時環境釋放所有的內存。至少我確信我在發現這個錯誤時，我在庫中的數據結構沒有一個實現這些構造函數。
我試著準確查明何時開始使用這個函數。我查看了在TopCoder和Codeforces上的提交歷史。在TopCoder上，我發現沒有在2011年10月26日的比賽中使用這個函數（遺憾的是，你不得不登錄到TopCoder才能訪問鏈接）。然而，我在2011年11月12日的比賽中使用了那個函數。發覺這一點讓我崩潰。這個錯誤出現在了我從2011年11月12日直到2013年11月3日的所有編程比賽解決方案當中。那可是我參加編程比賽的頭兩年！
舉例說，我發現了提交的這個代碼（http://codeforces.com/contest/134/submission/914840），當時是為了解決參與Codeforces的第二場比賽的***個問題。我試圖解決頭兩個問題，但結果證明我的兩個解決方法都速度太慢了。然而，就我提交的解決***個問題的方案而言，我只是增添了那個字母（&），讓size()函數由引用傳遞，提交的內容通過了。我為自己過去的愚蠢而感到可笑。
最近我又分析了幾年前解決不了的一個問題，不過試著實現一種解決辦法。我仔細閱讀了問題，提出了解決辦法。我還記得，那是我***次想到的同一個解決方法。由于有點懶，我找到了原來的代碼，而不是從頭開始實現一切。我分析了代碼，似乎很正常。于是我提交了，但結果運行速度太慢了。我花了好長時間來檢查代碼，但是不明白為何這么慢。但突然之間，我發現了問題之所在。那個舊的、壞的size()函數，我添加了&，重新提交了，通過了！
盡管我以為自己在多年前解決了這個錯誤，但直到今天它仍在為我敲警鐘！
原文標題：My favorite bug
作者：Bjarki Ágúst Guðmundsson
【51CTO譯稿，合作站點轉載請注明原文譯者和出處為51CTO.com】
