有时候会需要比较各种不同实作法的效能。 以前我都是自己使用 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://webptt.com/cn.aspx?n=bbs/C_and_CPP/M.1468784920.A.41D.html