2010年3月4日 星期四

Multiarray and View

最近有個東西需要用到一個四維陣列,其實本來是用四層的 hash table 下去做的,當然 hash 是不慢,但是因為取值的次數太頻繁,在跑過 profiling 之後確定這邊是一個瓶頸,所以嘗試要重構這個部分。如果為了效能考量,最好的作法就是用一個四維陣列來作。

因為本來 的 code 是有類似 indexed-view 的用法,就是我要固定某一個或是某兩個維度,然後把剩下的維度當作陣列來迭代。之前的 code 在這邊是去迭代那些 hash table,然後把需要的值取出來放到另外一個 hash table 裡面去,所以也不是真的 view,而是重新蒐集值。很慢,但是這份 code 最早是只有兩個維度的,所以當初設計的人這樣做也很合理,只是隨著時間過去,需求的追加,這部分才越來越複雜。

為了效能上的考量,我在考慮這個部分是不是不該重新串值,而是直接使用 view 的手法來取得需要的值,想到這個需求時,我開始思考我要什麼東西,這個過程在我的腦海裡面一直改版。

第一個版本是我要設計一個四維陣列類別,然後另外設計四個 view 類別,分別針對四個維度來 view 那個四維陣列。當然,可想而知,這四個 view 類別的實作會很相似,所以我是不是應該把這四個設計成一個?

所以第二個版本是我要設計一個四維陣列,還有一個 view 類別,接一個參數,用來 view 那個四維陣列,而參數可以指定我要固定的那一個維度。但是如果我想要固定兩個維度怎麼辦?我是不是應該讓這個 view class 可以套用在自己身上,也就是 templating 這個 view class?但是一旦這樣作,view 的維度就不一定是三維,而有可能是一維、二維。所以我應該用個 recursive class template 手法來做這件事?

那第三個版本就是我要設計一個四維陣列,還有一個 resursive class template 的 view 類別,用來 view 我的陣列,還有我的陣列的 view,還有 view 的 view。這樣我幹嘛不把陣列也設計成 recursive class template?這樣以後還可以重複使用,那為了重複使用,我也應該把這個陣列的型別也設計成 template。

所以第四個版本是我 要設計一個 resursive class template 可以用來定義任意維度的陣列,還有一個 view 可以用來 view 任意維度的陣列或是 view(只要我的陣列跟 view 提供相同的 interface)。這樣的話,那我幹嘛不直接用 boost::multiarray 呢?這樣我只需要設計 view 的部份就可以了。ㄟ……等等,如果我是 multiarray 的作者,我應該會想提供 view 的功能,不知道 boost::multiarray 有沒有 view 可以用?查一下好了……嗯……有。

第五個版本:

#include <boost/multi_array.hpp>

心得是那些偉大的心智真的看的很遠很遠。當我想到這個可能性的時候,他們已經做完了。

2010年2月28日 星期日

物理學家在大強子碰撞機中找到反重力物質

(法新社日內瓦)歐洲科學家公佈,去年 11 月 21 日啟動的大強子對撞機,在碰撞之後找到了許多理論中預測存在但是以前沒被觀察到的粒子,其中之一就是「反重力粒子」。

研究中心主任霍爾(Rolf Heuer)表示:「這是最令人興奮的成就之一!人類的運輸方式將從此改變!」一般帶有質量的物質都具有互相吸引的力,稱作「萬有引力」,而反引力物質具有負的質量,根據紐頓提出的萬有引力公式 F = GMm/r^2,這個反引力物質將會與其他物質互斥。「也就是說我們可以利用他來飛行」哈佛大學理論物理學系教授約翰賀蘭(John Holland)表示。

賀蘭表示:「順利的話,利用反重力飛行的技術將在三十年之內成熟。唯一的問題是,我們沒辦法證明這個成果的真實性,因為唯一的那一顆反重力粒子,因為跟重力互斥的關係,已經飛出地球了。根據我們的計算,他現在正越過冥王星的軌道。」

2010年1月21日 星期四

Valgrind Tutorial

有個老笑話說「99% 難纏的 C++ bug 都是來自於動態記憶體配置,剩下那 1% 還是來自動態記憶體配置」。很多程式設計師應該都遇過 access violation 或是 segmentation fault 這樣的記憶體錯誤。這中間絕大部分都是來自於指標的操作不當。要嘛你根本沒去 new 記憶體就直接拿來用,要嘛 new 了沒有 delete,要嘛沒有 newdelete,不然就是 delete 兩次,又或是有 new 也有 delete,但是忘記了又拿來用。雖然每一本 C/C++ 教科書都會耳提面命的、像是催眠一般的不斷喊叫「有 new 就要 delete!」但是程式設計師也是人,難免會犯錯,而且有的時候不是我們故意忘記,而是某些記憶體的所有權錯綜複雜,難以追蹤。一條路是不要使用動態記憶體,但是 C/C++ 不用動態記憶體的話,其實也做不了什麼事情。於是 C/C++ 程式設計師只好每次 new 了記憶體,都得另外消耗幾個腦細胞去記憶這些記憶體什麼時候該被放掉,結果這幾個腦細胞不小心掛啦,程式設計師也忘記要釋放這些記憶體了。而當記憶體錯誤發生的時候,程式設計師就得浪費更多的腦細胞去進行除錯的工作。日復一日的在記憶體錯誤的無間道裡面輪迴。

其實程式設計師的日子可以不用過的這麼苦。除了「眼睛用力看」以外,我們的生命還可以過的輕鬆一點。而 Valgrind 就是這樣一個工具,可以幫助我們抓出程式碼裡面關於動態記憶體的錯誤。

這篇文章會用一個簡單的範例程式,介紹 Valgrind 的用法,一步一步的,一次除去一個記憶體錯誤。而因為 Valgrind 用起來很簡單,所以文章內容也不會多,所以看完大概也學不到太多東西,但是話說回來,simple is good,Valgrind 的簡單就是他的優點,像我這樣腦損傷的人也可以順利使用。

因為 Valgrind 其實已經是很普遍的工具了,大部分的 linux dist 都內含有 Valgrind,所以這邊就跳過安裝 Valgrind 的過程,直接開始使用它。如果你發現你的機器上面沒有 Valgrind 的話,請自己另外先安裝起來。那使用 Windows 的使用者請注意到這裡,因為 Valgrind 沒有支援 Windows,出口在左手邊。

下面這個短短的程式就是我們要用來示範用的程式,裡面包含很多錯誤,而且寫的很蠢,但是因為這只是個範例,所以我們就不要太計較了。

 1 #include  <iostream>
 2 
 3 int main(int argc, char *argv[])
 4 {
 5     // new an array to store the random value
 6     int *a = new int[10] ;
 7     for ( size_t i=1; i<=10; ++i ) {
 8         a[i] = rand() ;
 9     }
10 
11     // calculate the sum the those number
12     int sum ;
13     for ( size_t i=1; i<=10; ++i ) {
14         sum += a[i] ;
15     }
16 
17     // output the result
18     std::cout << sum << std::endl ;
19 }


眼尖的人可能已經看到所有的錯誤了,那太好啦,你也可以先把這個錯誤修好再繼續下一步。下一步就是要編譯這個原始檔並且執行它,編譯的時候記得加上 -g 產生除錯訊息,這樣 valgrind 輸出的報告會給出錯誤的行號,方便我們修正程式碼。

[yoco_xiao@yoco yoco_xiao/test]$ g++ -g test.cc
[yoco_xiao@yoco yoco_xiao/test]$


現在編譯完成之後,就可以使用 Valgrind 來進行除錯的部份。Valgrind 本質上是一個 virtual machine,工作原理就是模擬一個機器來執行你的程式碼,並且監控每一行程式,如果這段碼跟記憶體的使用有關,valgrind 就會對他進行檢錯,並且在有錯誤的時候回報出來。使用 Valgrind 的方法很簡單,你不需要重新 compile,不需要定義什麼新的 macro,不需要重新 link 額外的函式庫,你只要直接使用 Valgrind 去執行你的程式。

[yoco_xiao@yoco yoco_xiao/test]$ valgrind --leak-check=full --log-file=vglog ./a.out
[yoco_xiao@yoco yoco_xiao/test]$ 


這邊 Valgrind 接了兩個參數,一個是 --leak-check=full,這是用來告訴 Valgrind 要進行完整的 memory leak 檢查,valgrind 看到這個參數的話,就會 backtrace memory leak 發生的點,有這些資訊我們比較好進行除錯。如果沒有這個參數,Valgrind 就只會輸出 memory leak 的 summary(總共漏失了多少記憶體),不會有詳細的報告。

另外一個參數是 --log-file=vglog,這是讓 Valgrind 把結果輸出到我們指定的檔案,以這個例子來說,我就把報告輸出到 vglog 這個檔案。如果不給這個參數,Valgrind 預設會把報告輸出到螢幕上。我比較推薦輸出到檔案,一來是 log 可能很長,在螢幕上可能不容易看,二來是 vim 有支援 Valgrind 的 syntax highlight,閱讀起來比較清楚。關於 Valgrind 完整的參數設定說明可以參考這邊

下面就是 Valgrind 輸出的報告。

 1 ==12723== Memcheck, a memory error detector
 2 ==12723== Copyright (C) 2002-2009, and GNU GPL'd, by Julian Seward et al.
 3 ==12723== Using Valgrind-3.5.0 and LibVEX; rerun with -h for copyright info
 4 ==12723== Command: a.out
 5 ==12723== Parent PID: 12641
 6 ==12723== 
 7 ==12723== Invalid write of size 4
 8 ==12723==    at 0x400A2B: main (test.cc:8)
 9 ==12723==  Address 0x4a3f068 is 0 bytes after a block of size 40 alloc'd
10 ==12723==    at 0x4905A9D: operator new[](unsigned long) (vg_replace_malloc.c:264)
11 ==12723==    by 0x400A00: main (test.cc:6)
12 ==12723== 
13 ==12723== Invalid read of size 4
14 ==12723==    at 0x400A56: main (test.cc:14)
15 ==12723==  Address 0x4a3f068 is 0 bytes after a block of size 40 alloc'd
16 ==12723==    at 0x4905A9D: operator new[](unsigned long) (vg_replace_malloc.c:264)
17 ==12723==    by 0x400A00: main (test.cc:6)
18 ==12723== 
19 ==12723== Conditional jump or move depends on uninitialised value(s)
20 ==12723==    at 0x3744B81589: std::ostreambuf_iterator<char, std::char_traits<char> > std::num_put<char, std::ostreambuf_iterator<char, std::char_traits<char> > >::_M_insert_int<long>(std::ostreambuf_iterator<char, std::char_traits<char> >, std::ios_base&, char, long) const (in /usr/lib64/libstdc++.so.6.0.3)
21 ==12723==    by 0x3744B816F8: std::num_put<char, std::ostreambuf_iterator<char, std::char_traits<char> > >::do_put(std::ostreambuf_iterator<char, std::char_traits<char> >, std::ios_base&, char, long) const (in /usr/lib64/libstdc++.so.6.0.3)
22 ==12723==    by 0x3744B86F3F: std::ostream::operator<<(long) (in /usr/lib64/libstdc++.so.6.0.3)
23 ==12723==    by 0x400A74: main (test.cc:18)
24 ==12723== 
25 ==12723== Use of uninitialised value of size 8
26 ==12723==    at 0x3744B74554: ??? (in /usr/lib64/libstdc++.so.6.0.3)
27 ==12723==    by 0x3744B81597: std::ostreambuf_iterator<char, std::char_traits<char> > std::num_put<char, std::ostreambuf_iterator<char, std::char_traits<char> > >::_M_insert_int<long>(std::ostreambuf_iterator<char, std::char_traits<char> >, std::ios_base&, char, long) const (in /usr/lib64/libstdc++.so.6.0.3)
28 ==12723==    by 0x3744B816F8: std::num_put<char, std::ostreambuf_iterator<char, std::char_traits<char> > >::do_put(std::ostreambuf_iterator<char, std::char_traits<char> >, std::ios_base&, char, long) const (in /usr/lib64/libstdc++.so.6.0.3)
29 ==12723==    by 0x3744B86F3F: std::ostream::operator<<(long) (in /usr/lib64/libstdc++.so.6.0.3)
30 ==12723==    by 0x400A74: main (test.cc:18)
31 ==12723== 
32 ==12723== Conditional jump or move depends on uninitialised value(s)
33 ==12723==    at 0x3744B74565: ??? (in /usr/lib64/libstdc++.so.6.0.3)
34 ==12723==    by 0x3744B81597: std::ostreambuf_iterator<char, std::char_traits<char> > std::num_put<char, std::ostreambuf_iterator<char, std::char_traits<char> > >::_M_insert_int<long>(std::ostreambuf_iterator<char, std::char_traits<char> >, std::ios_base&, char, long) const (in /usr/lib64/libstdc++.so.6.0.3)
35 ==12723==    by 0x3744B816F8: std::num_put<char, std::ostreambuf_iterator<char, std::char_traits<char> > >::do_put(std::ostreambuf_iterator<char, std::char_traits<char> >, std::ios_base&, char, long) const (in /usr/lib64/libstdc++.so.6.0.3)
36 ==12723==    by 0x3744B86F3F: std::ostream::operator<<(long) (in /usr/lib64/libstdc++.so.6.0.3)
37 ==12723==    by 0x400A74: main (test.cc:18)
38 ==12723== 
39 ==12723== 
40 ==12723== HEAP SUMMARY:
41 ==12723==     in use at exit: 40 bytes in 1 blocks
42 ==12723==   total heap usage: 1 allocs, 0 frees, 40 bytes allocated
43 ==12723== 
44 ==12723== 40 bytes in 1 blocks are definitely lost in loss record 1 of 1
45 ==12723==    at 0x4905A9D: operator new[](unsigned long) (vg_replace_malloc.c:264)
46 ==12723==    by 0x400A00: main (test.cc:6)
47 ==12723== 
48 ==12723== LEAK SUMMARY:
49 ==12723==    definitely lost: 40 bytes in 1 blocks
50 ==12723==    indirectly lost: 0 bytes in 0 blocks
51 ==12723==      possibly lost: 0 bytes in 0 blocks
52 ==12723==    still reachable: 0 bytes in 0 blocks
53 ==12723==         suppressed: 0 bytes in 0 blocks
54 ==12723== 
55 ==12723== For counts of detected and suppressed errors, rerun with: -v
56 ==12723== Use --track-origins=yes to see where uninitialised values come from
57 ==12723== ERROR SUMMARY: 22 errors from 6 contexts (suppressed: 4 from 4)


很長一串,很煩,但是沒關係,很多東西可以跳過,比方說開頭那幾行摘要,不用鳥他,還有每一行前面的 ==12723== 這是 process id,現在也不用鳥他,等你有多執行緒的時候再來鳥他。我們一個一個看,一次對付一個。就從第一個開始,讓我們看到第 7 行。

 7 ==12723== Invalid write of size 4
 8 ==12723==    at 0x400A2B: main (test.cc:8)
 9 ==12723==  Address 0x4a3f068 is 0 bytes after a block of size 40 alloc'd
10 ==12723==    at 0x4905A9D: operator new[](unsigned long) (vg_replace_malloc.c:264)
11 ==12723==    by 0x400A00: main (test.cc:6)


Valgrind 跟我們說我們有一個非法的寫入,他還很佛心的告訴我們這個非法的寫入是在 test.cc 這個檔案的第 8 行。Valgrind 還知道我們在第 6 行配置了一塊大小是 40 個 byte 的記憶體,而這個非法的寫入的位置,剛剛好超過了這塊記憶體 0 個 byte!(超過 0 byte 不是沒有超過,而是剛剛好超過。)那我們就去看 test.cc 的第 8 行……

 6     int *a = new int[10] ;
 7     for ( size_t i=1; i<=10; ++i ) {
 8         a[i] = rand() ;
 9     }


這個錯誤實在太明顯啦,連我都覺得不好意思了。就是 off by one 啦。大小為 n 的陣列,其索引範圍是 0~n-1,不是 1~n。不要笑,很多人幫字元陣列結尾的時候就是會寫 str[len] = '\0' ; 我老實承認很多人其實就是我自己。把它修好吧。

 6     int *a = new int[10] ;
 7     for ( size_t i=0; i<10; ++i ) {
 8         a[i] = rand() ;
 9     }


現在讓我們把修好的 code 重新編譯執行一次……

[yoco_xiao@yoco yoco_xiao/test]$ g++ -g test.cc
[yoco_xiao@yoco yoco_xiao/test]$ valgrind --leak-check=full --log-file=vglog ./a.out


 1 ==12723== Memcheck, a memory error detector
 2 ==12723== Copyright (C) 2002-2009, and GNU GPL'd, by Julian Seward et al.
 3 ==12723== Using Valgrind-3.5.0 and LibVEX; rerun with -h for copyright info
 4 ==12723== Command: a.out
 5 ==12723== Parent PID: 12641
 6 ==12723== 
13 ==12723== Invalid read of size 4
14 ==12723==    at 0x400A56: main (test.cc:14)
15 ==12723==  Address 0x4a3f068 is 0 bytes after a block of size 40 alloc'd
16 ==12723==    at 0x4905A9D: operator new[](unsigned long) (vg_replace_malloc.c:264)
17 ==12723==    by 0x400A00: main (test.cc:6)
18 ==12723== 
19 ==12723== Conditional jump or move depends on uninitialised value(s)
20 ==12723==    at 0x3744B81589: std::ostreambuf_iterator<char, std::char_traits<char> > std::num_put<char, std::ostreambuf_iterator<char, std::char_traits<char> > >::_M_insert_int<long>(std::ostreambuf_iterator<char, std::char_traits<char> >, std::ios_base&, char, long) const (in /usr/lib64/libstdc++.so.6.0.3)
21 ==12723==    by 0x3744B816F8: std::num_put<char, std::ostreambuf_iterator<char, std::char_traits<char> > >::do_put(std::ostreambuf_iterator<char, std::char_traits<char> >, std::ios_base&, char, long) const (in /usr/lib64/libstdc++.so.6.0.3)
22 ==12723==    by 0x3744B86F3F: std::ostream::operator<<(long) (in /usr/lib64/libstdc++.so.6.0.3)
23 ==12723==    by 0x400A74: main (test.cc:18)
24 ==12723== 
25 ==12723== Use of uninitialised value of size 8
26 ==12723==    at 0x3744B74554: ??? (in /usr/lib64/libstdc++.so.6.0.3)
27 ==12723==    by 0x3744B81597: std::ostreambuf_iterator<char, std::char_traits<char> > std::num_put<char, std::ostreambuf_iterator<char, std::char_traits<char> > >::_M_insert_int<long>(std::ostreambuf_iterator<char, std::char_traits<char> >, std::ios_base&, char, long) const (in /usr/lib64/libstdc++.so.6.0.3)
28 ==12723==    by 0x3744B816F8: std::num_put<char, std::ostreambuf_iterator<char, std::char_traits<char> > >::do_put(std::ostreambuf_iterator<char, std::char_traits<char> >, std::ios_base&, char, long) const (in /usr/lib64/libstdc++.so.6.0.3)
29 ==12723==    by 0x3744B86F3F: std::ostream::operator<<(long) (in /usr/lib64/libstdc++.so.6.0.3)
30 ==12723==    by 0x400A74: main (test.cc:18)
31 ==12723== 
32 ==12723== Conditional jump or move depends on uninitialised value(s)
33 ==12723==    at 0x3744B74565: ??? (in /usr/lib64/libstdc++.so.6.0.3)
34 ==12723==    by 0x3744B81597: std::ostreambuf_iterator<char, std::char_traits<char> > std::num_put<char, std::ostreambuf_iterator<char, std::char_traits<char> > >::_M_insert_int<long>(std::ostreambuf_iterator<char, std::char_traits<char> >, std::ios_base&, char, long) const (in /usr/lib64/libstdc++.so.6.0.3)
35 ==12723==    by 0x3744B816F8: std::num_put<char, std::ostreambuf_iterator<char, std::char_traits<char> > >::do_put(std::ostreambuf_iterator<char, std::char_traits<char> >, std::ios_base&, char, long) const (in /usr/lib64/libstdc++.so.6.0.3)
36 ==12723==    by 0x3744B86F3F: std::ostream::operator<<(long) (in /usr/lib64/libstdc++.so.6.0.3)
37 ==12723==    by 0x400A74: main (test.cc:18)
38 ==12723== 
39 ==12723== 
40 ==12723== HEAP SUMMARY:
41 ==12723==     in use at exit: 40 bytes in 1 blocks
42 ==12723==   total heap usage: 1 allocs, 0 frees, 40 bytes allocated
43 ==12723== 
44 ==12723== 40 bytes in 1 blocks are definitely lost in loss record 1 of 1
45 ==12723==    at 0x4905A9D: operator new[](unsigned long) (vg_replace_malloc.c:264)
46 ==12723==    by 0x400A00: main (test.cc:6)
47 ==12723== 
48 ==12723== LEAK SUMMARY:
49 ==12723==    definitely lost: 40 bytes in 1 blocks
50 ==12723==    indirectly lost: 0 bytes in 0 blocks
51 ==12723==      possibly lost: 0 bytes in 0 blocks
52 ==12723==    still reachable: 0 bytes in 0 blocks
53 ==12723==         suppressed: 0 bytes in 0 blocks
54 ==12723== 
55 ==12723== For counts of detected and suppressed errors, rerun with: -v
56 ==12723== Use --track-origins=yes to see where uninitialised values come from
57 ==12723== ERROR SUMMARY: 22 errors from 6 contexts (suppressed: 4 from 4)


Invalid write 那行錯誤果然不見了!這個錯誤被我們修好啦!那有人可能會問:「為什麼這次執行的 process id 跟之前的一樣呢?」太神奇了!原因當然是因為我根本沒有去跑阿,我直接把之前那個 log 檔拿來改一改而已,你看那個不連續的行號就漏餡了。但是真的修好了啦,你們要自己動手做看看就知道了,不能只依賴我。接下來要看第二個錯誤……

13 ==12723== Invalid read of size 4
14 ==12723==    at 0x400A56: main (test.cc:14)
15 ==12723==  Address 0x4a3f068 is 0 bytes after a block of size 40 alloc'd
16 ==12723==    at 0x4905A9D: operator new[](unsigned long) (vg_replace_malloc.c:264)
17 ==12723==    by 0x400A00: main (test.cc:6)


Valgrind 說 test.cc 的第 14 行有一個 Invalid read。這個錯誤也很明顯,跟上一個一樣是 off by one,請自己嘗試把它修好,然後重新編譯,再用 Valgrind 執行一次……

[yoco_xiao@yoco yoco_xiao/test]$ g++ -g test.cc
[yoco_xiao@yoco yoco_xiao/test]$ valgrind --leak-check=full --log-file=vglog ./a.out


 1 ==12723== Memcheck, a memory error detector
 2 ==12723== Copyright (C) 2002-2009, and GNU GPL'd, by Julian Seward et al.
 3 ==12723== Using Valgrind-3.5.0 and LibVEX; rerun with -h for copyright info
 4 ==12723== Command: a.out
 5 ==12723== Parent PID: 12641
 6 ==12723== 
19 ==12723== Conditional jump or move depends on uninitialised value(s)
20 ==12723==    at 0x3744B81589: std::ostreambuf_iterator<char, std::char_traits<char> > std::num_put<char, std::ostreambuf_iterator<char, std::char_traits<char> > >::_M_insert_int<long>(std::ostreambuf_iterator<char, std::char_traits<char> >, std::ios_base&, char, long) const (in /usr/lib64/libstdc++.so.6.0.3)
21 ==12723==    by 0x3744B816F8: std::num_put<char, std::ostreambuf_iterator<char, std::char_traits<char> > >::do_put(std::ostreambuf_iterator<char, std::char_traits<char> >, std::ios_base&, char, long) const (in /usr/lib64/libstdc++.so.6.0.3)
22 ==12723==    by 0x3744B86F3F: std::ostream::operator<<(long) (in /usr/lib64/libstdc++.so.6.0.3)
23 ==12723==    by 0x400A74: main (test.cc:18)
24 ==12723== 
25 ==12723== Use of uninitialised value of size 8
26 ==12723==    at 0x3744B74554: ??? (in /usr/lib64/libstdc++.so.6.0.3)
27 ==12723==    by 0x3744B81597: std::ostreambuf_iterator<char, std::char_traits<char> > std::num_put<char, std::ostreambuf_iterator<char, std::char_traits<char> > >::_M_insert_int<long>(std::ostreambuf_iterator<char, std::char_traits<char> >, std::ios_base&, char, long) const (in /usr/lib64/libstdc++.so.6.0.3)
28 ==12723==    by 0x3744B816F8: std::num_put<char, std::ostreambuf_iterator<char, std::char_traits<char> > >::do_put(std::ostreambuf_iterator<char, std::char_traits<char> >, std::ios_base&, char, long) const (in /usr/lib64/libstdc++.so.6.0.3)
29 ==12723==    by 0x3744B86F3F: std::ostream::operator<<(long) (in /usr/lib64/libstdc++.so.6.0.3)
30 ==12723==    by 0x400A74: main (test.cc:18)
31 ==12723== 
32 ==12723== Conditional jump or move depends on uninitialised value(s)
33 ==12723==    at 0x3744B74565: ??? (in /usr/lib64/libstdc++.so.6.0.3)
34 ==12723==    by 0x3744B81597: std::ostreambuf_iterator<char, std::char_traits<char> > std::num_put<char, std::ostreambuf_iterator<char, std::char_traits<char> > >::_M_insert_int<long>(std::ostreambuf_iterator<char, std::char_traits<char> >, std::ios_base&, char, long) const (in /usr/lib64/libstdc++.so.6.0.3)
35 ==12723==    by 0x3744B816F8: std::num_put<char, std::ostreambuf_iterator<char, std::char_traits<char> > >::do_put(std::ostreambuf_iterator<char, std::char_traits<char> >, std::ios_base&, char, long) const (in /usr/lib64/libstdc++.so.6.0.3)
36 ==12723==    by 0x3744B86F3F: std::ostream::operator<<(long) (in /usr/lib64/libstdc++.so.6.0.3)
37 ==12723==    by 0x400A74: main (test.cc:18)
38 ==12723== 
39 ==12723== 
40 ==12723== HEAP SUMMARY:
41 ==12723==     in use at exit: 40 bytes in 1 blocks
42 ==12723==   total heap usage: 1 allocs, 0 frees, 40 bytes allocated
43 ==12723== 
44 ==12723== 40 bytes in 1 blocks are definitely lost in loss record 1 of 1
45 ==12723==    at 0x4905A9D: operator new[](unsigned long) (vg_replace_malloc.c:264)
46 ==12723==    by 0x400A00: main (test.cc:6)
47 ==12723== 
48 ==12723== LEAK SUMMARY:
49 ==12723==    definitely lost: 40 bytes in 1 blocks
50 ==12723==    indirectly lost: 0 bytes in 0 blocks
51 ==12723==      possibly lost: 0 bytes in 0 blocks
52 ==12723==    still reachable: 0 bytes in 0 blocks
53 ==12723==         suppressed: 0 bytes in 0 blocks
54 ==12723== 
55 ==12723== For counts of detected and suppressed errors, rerun with: -v
56 ==12723== Use --track-origins=yes to see where uninitialised values come from
57 ==12723== ERROR SUMMARY: 22 errors from 6 contexts (suppressed: 4 from 4)


當然,這次的 process id 也是一樣的。

我們還剩下好幾個錯誤訊息,接下來看第三個:Conditional jump or move depends on uninitialised value(s) 在 test.cc 第 18 行。

18     std::cout << sum << std::endl ;


看不出來為什麼錯,也看不是很懂那個錯誤訊息,不知道他在講啥,不過沒關係,看的懂 "uninitialised value" 就好了。重點就是有人沒有初始化就被拿來用了。是誰勒,這邊的話當然就是 sum。可以看看 log 的最後,他還有告訴你如果打開選項 --trace-originals=yes 的話就可以 dump 出當初這塊記憶體是哪裡來的。不過因為這個例子很簡單,我們知道 sum 這個變數是哪裡來的。


12     int sum ;


把它修好……

12     int sum = 0 ;


重新編譯再執行……

[yoco_xiao@yoco yoco_xiao/test]$ g++ -g test.cc
[yoco_xiao@yoco yoco_xiao/test]$ valgrind --leak-check=full --log-file=vglog ./a.out


 1 ==12174== Memcheck, a memory error detector
 2 ==12174== Copyright (C) 2002-2009, and GNU GPL'd, by Julian Seward et al.
 3 ==12174== Using Valgrind-3.5.0 and LibVEX; rerun with -h for copyright info
 4 ==12174== Command: a.out
 5 ==12174== Parent PID: 12091
 6 ==12174== 
 7 ==12174== 
 8 ==12174== HEAP SUMMARY:
 9 ==12174==     in use at exit: 40 bytes in 1 blocks
10 ==12174==   total heap usage: 1 allocs, 0 frees, 40 bytes allocated
11 ==12174== 
12 ==12174== 40 bytes in 1 blocks are definitely lost in loss record 1 of 1
13 ==12174==    at 0x4905A9D: operator new[](unsigned long) (vg_replace_malloc.c:264)
14 ==12174==    by 0x400A00: main (test.cc:6)
15 ==12174== 
16 ==12174== LEAK SUMMARY:
17 ==12174==    definitely lost: 40 bytes in 1 blocks
18 ==12174==    indirectly lost: 0 bytes in 0 blocks
19 ==12174==      possibly lost: 0 bytes in 0 blocks
20 ==12174==    still reachable: 0 bytes in 0 blocks
21 ==12174==         suppressed: 0 bytes in 0 blocks
22 ==12174== 
23 ==12174== For counts of detected and suppressed errors, rerun with: -v
24 ==12174== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 4 from 4)


來看這個 log,剛剛一堆錯誤都不見了,因為那些錯誤都因為來自於那個沒有初始化的變數,所以修好一個就少掉一堆錯誤訊息。看起來只剩下一個錯誤啦 40 bytes in 1 blocks are definitely lost in loss record 1 of 1。重點來啦!這是一個沒有被釋放的記憶體!這塊記憶體是在 test.cc 的第 6 行被配置的!沒有初始化的變數所造成的錯誤都可以很快被發現,因為他通常會有錯誤的結果,比方說如果你們剛剛真的有下去跑的話,就會發現每次輸出的總和值都很明顯是錯的。而且沒有初始化的變數通常編譯器都會給予警告。但是沒有被釋放的記憶體不有什麼立即的錯誤,編譯器也會一聲不吭的就放行。所以我們才需要記憶體除錯工具來幫助我們抓到這類 bug。現在讓我們動手來釋放他……

13     for ( size_t i=1; i<=10; ++i ) {
14         sum += a[i] ;
15     }
16 
17     // output the result
18     std::cout << sum << std::endl ;


13     for ( size_t i=0; i<10; ++i ) {
14         sum += a[i] ;
15     }
16     
17     delete a ;
18 
19     // output the result
20     std::cout << sum << std::endl ;


重新編譯再執行……

[yoco_xiao@yoco yoco_xiao/test]$ g++ -g test.cc
[yoco_xiao@yoco yoco_xiao/test]$ valgrind --leak-check=full --log-file=vglog ./a.out


 7 ==25463== Mismatched free() / delete / delete []
 8 ==25463==    at 0x4906174: operator delete(void*) (vg_replace_malloc.c:346)
 9 ==25463==    by 0x400B07: main (test.cc:17)
10 ==25463==  Address 0x4a3f040 is 0 bytes inside a block of size 40 alloc'd
11 ==25463==    at 0x4905A9D: operator new[](unsigned long) (vg_replace_malloc.c:264)
12 ==25463==    by 0x400A90: main (test.cc:6)


Memory leak 的錯誤不見了,但是又多了一個本來沒看過的錯誤,Mismatched free() / delete / delete []。Valgrind 說這個錯誤發生在 test.cc 的第 17 行,而且這個記憶體是在第 6 行被配置的,讓我們看一下第 17 行跟第 6 行是啥。

 6     int *a = new int[10] ;


17     delete a ;


忘記了,new[] 的記憶體要用 delete[] 來釋放,不能單純只用 delete,C++ 標準說這樣的用法會導致未定義的行為,就是在不同的編譯器上面會有不同的結果,比方說:雖然這塊記憶體被釋放了,但是可能只有第一個物件呼叫了建構子,剩下的都沒有,而這不會是我們希望的結果。讓我們修好他,然後重新編譯再執行……

17     delete[] a ;


[yoco_xiao@yoco yoco_xiao/test]$ g++ -g test.cc
[yoco_xiao@yoco yoco_xiao/test]$ valgrind --leak-check=full --log-file=vglog ./a.out


 1 ==26986== Memcheck, a memory error detector
 2 ==26986== Copyright (C) 2002-2009, and GNU GPL'd, by Julian Seward et al.
 3 ==26986== Using Valgrind-3.5.0 and LibVEX; rerun with -h for copyright info
 4 ==26986== Command: a.out
 5 ==26986== Parent PID: 26904
 6 ==26986== 
 7 ==26986== 
 8 ==26986== HEAP SUMMARY:
 9 ==26986==     in use at exit: 0 bytes in 0 blocks
10 ==26986==   total heap usage: 1 allocs, 1 frees, 40 bytes allocated
11 ==26986== 
12 ==26986== All heap blocks were freed -- no leaks are possible
13 ==26986== 
14 ==26986== For counts of detected and suppressed errors, rerun with: -v
15 ==26986== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 4 from 4)


總算!終於功德圓滿修成正果啦~全部的錯誤都不見啦~可喜可賀!可喜可賀!才怪。

其實呢,記憶體偵錯只是 Valgrind 的其中一個功能,Valgrind 是一個 virtual machine,可以透過掛上不同的 tool 來執行,目前為止我們用的都是 Valgrind 內建的一個叫做 memcheck 的 tool,Valgrind 還有像是 callgrind(用來做 profiling),cachegrind(用來模擬 CPU cache hit/miss)的功能,這個以後再說,當然,等不及的人直接 Google 就有一堆教學啦。

有錯不要罵我。