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