有时候会需要比较各种不同实作法的效能。
以前我都是自己使用 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