ceph/src/boost/libs/math/reporting/performance/test_fibonacci.cpp

   1 //  Copyright Madhur Chauhan 2020.
   2 //  Use, modification and distribution are subject to the
   3 //  Boost Software License, Version 1.0. (See accompanying file
   4 //  LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
   5
   6 #include <benchmark/benchmark.h>
   7 #include <boost/math/special_functions/fibonacci.hpp>
   8 #include <boost/multiprecision/gmp.hpp>
   9 #include <utility>
  10
  11 using T = boost::multiprecision::mpz_int;
  12
  13 auto fib_rec(unsigned long long n) -> std::pair<T, T> {
  14     if (n == 0) return {0, 1};
  15     auto p = fib_rec(n >> 1);
  16     T c = p.first * (2 * p.second - p.first);
  17     T d = p.first * p.first + p.second * p.second;
  18     return (n & 1) ? std::make_pair(d, c + d) : std::make_pair(c, d);
  19 }
  20
  21 static void recursive_slow(benchmark::State &state) {
  22     for (auto _ : state)
  23         benchmark::DoNotOptimize(fib_rec(state.range(0)).first);
  24     state.SetComplexityN(state.range(0));
  25 }
  26 constexpr int bm_start = 1 << 3, bm_end = 1 << 22;
  27 BENCHMARK(recursive_slow)->Range(bm_start, bm_end)->Complexity();
  28
  29 static void iterative_fast(benchmark::State &state) {
  30     for (auto _ : state)
  31         benchmark::DoNotOptimize(boost::math::fibonacci<T>(state.range(0)));
  32     state.SetComplexityN(state.range(0));
  33 }
  34 BENCHMARK(iterative_fast)->Range(bm_start, bm_end)->Complexity();
  35
  36 BENCHMARK_MAIN();
  37
  38 /*
  39 Expected output:
  40
  41 CPU Caches:
  42   L1 Data 32K (x4)
  43   L1 Instruction 32K (x4)
  44   L2 Unified 256K (x4)
  45   L3 Unified 8192K (x4)
  46 Load Average: 0.96, 0.80, 0.74
  47 -----------------------------------------------------------------
  48 Benchmark                       Time             CPU   Iterations
  49 -----------------------------------------------------------------
  50 recursive_slow/8             3669 ns         3594 ns       190414
  51 recursive_slow/64            6213 ns         6199 ns       116423
  52 recursive_slow/512           8999 ns         8990 ns        78773
  53 recursive_slow/4096         14529 ns        13984 ns        51206
  54 recursive_slow/32768        74183 ns        73039 ns         8539
  55 recursive_slow/262144     1297806 ns      1291304 ns          569
  56 recursive_slow/2097152   23166565 ns     22751898 ns           30
  57 recursive_slow/4194304   47038831 ns     46546938 ns           16
  58 recursive_slow_BigO          0.51 NlgN       0.51 NlgN
  59 recursive_slow_RMS              5 %             5 %
  60 iterative_fast/8             1413 ns         1399 ns       493692
  61 iterative_fast/64            2408 ns         2394 ns       298417
  62 iterative_fast/512           4181 ns         4132 ns       170957
  63 iterative_fast/4096          7627 ns         7558 ns        93554
  64 iterative_fast/32768        65080 ns        64791 ns        11289
  65 iterative_fast/262144     1207873 ns      1200725 ns          557
  66 iterative_fast/2097152   19627331 ns     19510132 ns           36
  67 iterative_fast/4194304   42351871 ns     42240620 ns           17
  68 iterative_fast_BigO          0.46 NlgN       0.45 NlgN
  69 iterative_fast_RMS              5 %             5 %
  70 */