作者FRAXIS (喔喔)
看板C_and_CPP
標題[心得] Google benchmark library
時間Mon Jul 18 03:48:37 2016
有時候會需要比較各種不同實作法的效能。
以前我都是自己使用 gettimeofday，然後自己寫測試資料和輸出，
不過重複了幾次之後就厭煩了，就上網找 library。
到最後我挑了 google 的 benchmark library，跟大家分享一下心得。
https://github.com/google/benchmark
這 library 可以方便的統計執行時間，同時可以支援參數化的測試，
甚至是 template 參數。而且使用起來跟 unit test 很類似，所以容易上手。
我以 binary search 為例子，簡單介紹一下如何使用。
我有兩個 function : binary_search 和 biased_search 。
都是 binary search ，只是 biased_search 不挑中點來比較而是挑 1/4 處。
測試方法很簡單，對於長度為 2^10, 2^12, ..., 2^20 的整數陣列，
測試前先生成一組隨機整數放到陣列中並加以排序。
測試的時候是在此有序陣列中搜尋一個隨機數字。
最後統計平均的執行時間。
現在介紹如何使用此 library 來作 benchmark 。
首先要宣告一個 class ，且該 class 繼承 benchmark::Fixture。
然後把所有的測試資料都宣告成此 class 的 member 。
接著把測試資料的生成程式碼寫在 SetUp 函數裡，這函數會在每組測試之前被呼叫。
舉例來說，宣告一個 class SearchBenchmark : public benchmark::Fixture，
此 class 有一個 test 陣列，我想在每組測試之前先取得要測試的陣列長度，
產生指定數量的隨機整數，放到此陣列中並排序，那 SetUp 可以寫成
void SetUp(const ::benchmark::State& state) {
generator.seed();
for (int32_t i = 0; i < state.range_x(); ++i)
test[i] = distribution(generator);
std::sort(test, test + state.range_x());
}
來生成測試資料。
其中 state.range_x() 代表是測試參數，也就是陣列的長度。
因為在 SetUp 中 reset 亂數產生器的 seed ，所以每組同陣列長度的
測試都會使用一樣的資料和隨機查詢。
而測試的時候，則是使用 BENCHMARK_DEFINE_F 的 macro 來告訴 library 所要測試
的部分。以測試 binary_search 的效能為例：
BENCHMARK_DEFINE_F(SearchBenchmark, BinarySearch)(benchmark::State& state) {
while (state.KeepRunning()) {
int32_t r = distribution(generator);
benchmark::DoNotOptimize(binary_search(test, state.range_x(), r));
}
}
在 loop 之中需要先 check state.KeepRunning() ，如果 benchmark 還在繼續
那就呼叫 binary_search 。而 state.range_x() 代表測試的參數，也就是陣
列的長度。
BENCHMARK_DEFINE_F 的第一個參數是 fixture 的 class 名字，第二個參數是
這個測試的名字。
呼叫 DoNotOptimize 是為了避免 compiler 把結果最佳化掉而導致
binary_search 沒有被呼叫。
而測試參數的給定是透過 BENCHMARK_REGISTER_F 的 macro 。
以 BinarySearch 測試為例：
BENCHMARK_REGISTER_F(SearchBenchmark, BinarySearch)
->RangeMultiplier(4)->Range(1 << 10, 1 << 20);
會產生 6 組測試，參數分別是 2^10, 2^12, 2^14, 2^16, 2^18, 2^20 。
每一個測試會被執行大約數秒 (使用者可調整）。
測試結束時會統計實際所花的時間和 iterations 的數量。
我設定每組測試跑至少五秒，擷取部份的結果如下：
Benchmark Time CPU Iterations
-------------------------------------------------------------------------
SearchBenchmark/Random/1024k 64 ns 64 ns 109865274
SearchBenchmark/BinarySearch/256k 305 ns 304 ns 22751716
SearchBenchmark/BinarySearch/1024k 517 ns 516 ns 13595401
SearchBenchmark/BiasedSearch/256k 231 ns 231 ns 29824178
SearchBenchmark/BiasedSearch/1024k 348 ns 347 ns 19306835
SearchBenchmark/STLSearch/256k 298 ns 298 ns 23643489
SearchBenchmark/STLSearch/1024k 506 ns 505 ns 13852965
SearchBenchmark/BSearch/256k 348 ns 347 ns 20436083
SearchBenchmark/BSearch/1024k 584 ns 582 ns 11745972
其中
Random: 生成隨機數的時間
BinarySearch: 正常的二分搜尋
BiasedSearch: 挑 1/4 處來比較的二分搜尋
STLSearch: std::lower_bound
BSearch: C library 裡面的 bsearch 。
（BinarySearch 和 BiasedSearch 是跟 std::lower_bound 一樣，
如果要搜尋的元素不在陣列中，就會回傳第一個不比搜尋元素小的位置）
而 Time 和 CPU 分別平均每次函式呼叫所用的時間，所以越小表示速度越快。
以結果來看， 一般的 binary search 和 biased search 在長度小於 256k 時
速度是沒有差別的。
但是當長度大於 256k 之後，挑 1/4 處來比較是會比挑中點稍微快一點的。
這現象已經被發現很久了，據說原因是 CPU 的 branch prediction 的機制，
如果每次都挑中點來比較，搜尋的元素又是隨機的，那每次比較的結果都很難預測。
如果挑 1/4 處， 那比較的結果就是 biased 的，所以比較好預測。
但是效能的差別大概只會有 3~5 % 。
只是我也不知道要怎麼驗證這個說法就是了，希望以後 library 可以提供
performance counter 的資訊。
當然這是因為整數之間比較非常的快， misprediction rate 才變得重要。
如果元素之間比較很慢，又或是陣列很大導致 cache miss penalty 很大，
那 misprediction rate 就不重要了。
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 24.23.200.172
※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1468784920.A.41D.html
推 longlongint: 感謝分享。用 profiling tool 就可以拿到效能分析資 07/18 04:45
→ longlongint: 料，但是我還沒學會怎麼用，提供關鍵字給你參考。 07/18 04:45
→ FRAXIS: profiling toll 可以拿到 performance counter 資訊 07/18 05:36
→ FRAXIS: 但是 benchmark library 的好處是提供簡便的方式根據參數 07/18 05:37
→ FRAXIS: 生成想要的測試 07/18 05:38
推 damody: 讚 07/18 08:17
推 Ommm5566: 07/18 11:32
推 Caesar08: 推 07/18 13:10
推 ilikekotomi: 感謝分享 07/18 20:27
→ longlongint: 了解 省工夫是重點 07/18 22:26
推 lunastorm: 可以看這個CppCon2015的talk, 講得蠻仔細～ 07/19 07:59
推 Sidney0503: 推樓上那個 07/19 09:18
推 Sidney0503: 那個影片好好笑XDDDDDD 07/19 10:54
→ FRAXIS: CppCon 看起來不錯 還有什麼跟 optimization 相關的 talk? 07/19 21:19