有時候會需要比較各種不同實作法的效能。
以前我都是自己使用 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