這幾天有空, 終於把一項幾個月前就開始做的 benchmark 完成了.

---

看過好幾次有同事的 code, 明明就是使用 vector 來管理一串 element, 卻硬要把被管理的 element 的 pointer 取出, 以代替 vector 本身的 iterator 來做迭代. 有些同事說是不熟悉 iterator 的特性與操作方式. 這個理由很難讓人接受. 身為職業 C++ programmer, 標準的 container 與 iterator 是無論如何也要掌握住的技巧. 促成我搞這個 benchmark 的原因是有另外的同事跟我說, 取 pointer 出來迭代是因為 vector 的 iterator 比 pointer 慢很多, 並且是指數級別的差距!

在進行這項 benchmark 之前, 說以 vector 的 iterator 迭代比 pointer 慢, (起碼不會快過 pointer) 我絕對不會意外. 我猜大多數人也預期會看這樣的結果. 即便如此, 我還是很難想像其差異會大到如那位同事告訴我的這麼多. 因此我寫了個程式來 benchmark. 將 pointer 以及各種 STL 的 sequence container¹ 的 iterator 做同樣的迭代, 把所使用的時間紀錄下來, 製作成表格以比較其間差異. 讓數字來說話.

由於我手上沒有機器上有 GNU/Linux 與 Windows 的 dual boot, 也不想在 VM 上測試. 所以只能讓兩個平台的測試跑在不同的機器上. GNU/Linux 上的測試用的是我的手提電腦, Windows 的測試用的是工作的 workstation.

測試程式的內容是將 32 Mega (1024*1024) 個 integer 迭代兩個回合. 第一回先將其全部指派為 1. 第二回再將它們指派為 0. 所有的測試都是跑十次, 然後取平均時間, 順便紀錄這十次中最快的時間與最慢的時間以供參考.

這個測試刻意將 memory allocation 與 container 在被創建時或是 resize() 時, 啟始其管理的 element 的過程排除. 讓這個測試儘量只針對迭代的部份計時.

前兩組 benchmark (Table 1 and Table 2) 是在 GNU/Linux 下產生的結果, 測試環境如下:

CPU:	INTEL CORE DUO T2400/1.83G
RAM:	2G
OS:	Ubuntu 7.10
Compiler:	GCC 4.13

後面兩組 benchmark (Table 3 and Table 4) 是 Windows 的結果, 測試環境如下:

CPU:	INTEL CORE 2 DUO E8400/3.0G
RAM:	2G
OS:	XP
Compiler:	MSVC 2005

Benchmark 1

先來檢視 GNU/Linx 上的第一組測試結果.

OS Compiler Compiler flag(s)	Iterator Type	Average	Fastest	Slowest
Ubuntu 7.10 GCC 4.1.3 -g	pointer	0.581	0.536	0.641
	vector	1.521	1.493	1.552
	deque	1.796	1.185	1.981
	list	1.247	1.168	1.381

這組 benchmark 沒有使用 GCC 的優化 (-O), 沒有定義 NDEBUG, (e.g. 會把 assert() 所花的時間也算進來, if any) 並加使用 -g 以在產出的執行檔加上 debug symbol.²

從這個表上很容易可以看出來, pointer 明顯是最快的. 表中其他三種 iterator 所花的時間則介於 pointer 的 2.15 倍到 3.09 倍之間.

這裡有一個有趣的現象, list iterator 的迭代速度竟然較除了 pointer 之外的其他兩種 random access iterator 都來的快. 除此之外這組結果大都還容易解讀, 接近大部份人對它們的印象.

Benchmark 2

接下來這組測試結果更有意思了. 這次除了編譯時給 GCC 的參數不同之外, 測試方法與測試環境都跟第一組測試相同.

OS Compiler Compiler flag(s)	Iterator Type	Average	Fastest	Slowest
Ubuntu 7.10 GCC 4.1.3 -O -DNDEBUG	pointer	0.273	0.256	0.287
	vector	0.204	0.194	0.211
	deque	0.205	0.191	0.224
	list	0.787	0.763	0.861

在 -O 的加持下, 果然讓所有 iterator 的速度都比上一組測試時得到的成績好了很多.

這次 list 的成績如預期的殿了後. vector 與 deque 幾乎是不相上下, 打了個平手. 叫我跌破眼鏡的是它們居然都比 pointer 還快! 硬是把 pointer 擠到第三名! 雖說 pointer 只比它們慢約 0.068 秒, 但畢竟是穩定的慢上三分之一左右的時間.

一開始觀察到這現象時, 第一個想法就是我那裡做錯了, 接著試了好幾個版本的迭代算法來 benchmark, 結果還是一致. 在後面的第四組測試數字也會看到類似的現象. 這樣的結果讓我不知道該如何解讀. 苦惱中…

Benchmark 3

接下來讓我們轉台到 Windows.

OS Compiler Configuration	Iterator Type	Average	Fastest	Slowest
XP MSVC 2005 w/SP1 Debug Build	pointer	0.324	0.313	0.344
	vector	3.302	3.256	3.360
	deque	3.558	3.529	3.607
	list	19.245	3.876	65.244

這組測試的名次是這次所有測試結果中最符合我預期的, 而且也讓我看到同事說的指數級的差距. Pointer 比 vector 快了十倍! 果然真的是這樣.

這組測試結果最困擾我的地方是 list 的十次測試結果非常不穩定. 最快與最慢的時間的差異幾乎是十六倍. 很遺憾的是我一直沒有機會在其他機器上跑這 list 的測試. 很想知道會不會是機器又或是我的系統的問題, 而造成這樣不穩定的結果.

Benchmark 4

OS Compiler Configuration	Iterator Type	Average	Fastest	Slowest
XP MSVC 2005 w/SP1 Release Build	pointer	0.159	0.156	0.172
	vector	0.130	0.125	0.141
	deque	0.297	0.297	0.297
	list	0.806	0.797	0.813

在第四組測試又看到跟第二組測試一樣的現象. vector 的 iterator 比 pointer 還快. 到底是什麼原因造成這個現象? 我目前可是一點頭緒也沒有.

眼尖的人看到這兩組 Windows 上得到的數字可能會想; MSVC 會不會太猛了? 怎麼 Release build 優化的結果可以比 Debug build 快上這麼多? 差異最少的 pointer 都快了一倍. 進步第二少的 deque 更是快上近 12 倍!

Release build 的優化是會起一定的作用, 但造成這樣的差距更重要的原因是我所使用的這個版本的 MSVC 所附帶的 standard library 在 Debug build 模式下會自動 #define _HAS_ITERATOR_DEBUGGING 1.

在 _HAS_ITERATOR_DEBUGGING 被 define 成 1 的情況下, (Debug build 的預設狀態) MSVC 的 debug runtime library 會在執行時期做如 iterator 越界以及驗證一對用來表示一個 range 的 iterator 是否屬於同一個 sequence 等的檢查. 於是效能就比沒這額外執行時期檢查的 Release build (或是 _HAS_ITERATOR_DEBUGGING 被 define 成 0 的 Debug build) 慢上很多很多. 在我的機器上只要在 project setting 的 Debug build 的 preprocessor 設定加上 _HAS_ITERATOR_DEBUGGING=0, 用這次的 benchmark 程式也可以一樣得到 vector 的 iterator 比 pointer 還快的結果.

Conclusion

這個 benchmark 產生的數字的確釐清了不少事情, 卻也在我心裡留下新的問號.

其中至少有一件事是肯定的, vector 的 iterator 在優化後 (甚至只要 non debug 的 configuration) 的速度是很快的. 別再因為迭代速度考量捨 vector 而就 pointer 了.

寫累了, 晚些時候再把 benchmark 用的 source code 整理一下後放上來, 請有興趣的朋友一起玩玩, 幫忙研究驗證一下.

Update: Source code 可以下載了.

1. 測完後才發現漏掉了 basic_string [↩]
2. 加上 -g 只是方便需要時可以 trace code, 不清楚這會不會對測試產生影響 [↩]