1 // Copyright 2016 Ismael Jimenez Martinez. All rights reserved.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 // Source project : https://github.com/ismaelJimenez/cpp.leastsq
16 // Adapted to be used with google benchmark
17
18 #include "benchmark/benchmark.h"
19
20 #include <algorithm>
21 #include <cmath>
22 #include "check.h"
23 #include "complexity.h"
24
25 namespace benchmark {
26
27 // Internal function to calculate the different scalability forms
FittingCurve(BigO complexity)28 BigOFunc* FittingCurve(BigO complexity) {
29 switch (complexity) {
30 case oN:
31 return [](int64_t n) -> double { return static_cast<double>(n); };
32 case oNSquared:
33 return [](int64_t n) -> double { return std::pow(n, 2); };
34 case oNCubed:
35 return [](int64_t n) -> double { return std::pow(n, 3); };
36 case oLogN:
37 return [](int64_t n) { return log2(n); };
38 case oNLogN:
39 return [](int64_t n) { return n * log2(n); };
40 case o1:
41 default:
42 return [](int64_t) { return 1.0; };
43 }
44 }
45
46 // Function to return an string for the calculated complexity
GetBigOString(BigO complexity)47 std::string GetBigOString(BigO complexity) {
48 switch (complexity) {
49 case oN:
50 return "N";
51 case oNSquared:
52 return "N^2";
53 case oNCubed:
54 return "N^3";
55 case oLogN:
56 return "lgN";
57 case oNLogN:
58 return "NlgN";
59 case o1:
60 return "(1)";
61 default:
62 return "f(N)";
63 }
64 }
65
66 // Find the coefficient for the high-order term in the running time, by
67 // minimizing the sum of squares of relative error, for the fitting curve
68 // given by the lambda expression.
69 // - n : Vector containing the size of the benchmark tests.
70 // - time : Vector containing the times for the benchmark tests.
71 // - fitting_curve : lambda expression (e.g. [](int64_t n) {return n; };).
72
73 // For a deeper explanation on the algorithm logic, look the README file at
74 // http://github.com/ismaelJimenez/Minimal-Cpp-Least-Squared-Fit
75
MinimalLeastSq(const std::vector<int64_t> & n,const std::vector<double> & time,BigOFunc * fitting_curve)76 LeastSq MinimalLeastSq(const std::vector<int64_t>& n,
77 const std::vector<double>& time,
78 BigOFunc* fitting_curve) {
79 double sigma_gn_squared = 0.0;
80 double sigma_time = 0.0;
81 double sigma_time_gn = 0.0;
82
83 // Calculate least square fitting parameter
84 for (size_t i = 0; i < n.size(); ++i) {
85 double gn_i = fitting_curve(n[i]);
86 sigma_gn_squared += gn_i * gn_i;
87 sigma_time += time[i];
88 sigma_time_gn += time[i] * gn_i;
89 }
90
91 LeastSq result;
92 result.complexity = oLambda;
93
94 // Calculate complexity.
95 result.coef = sigma_time_gn / sigma_gn_squared;
96
97 // Calculate RMS
98 double rms = 0.0;
99 for (size_t i = 0; i < n.size(); ++i) {
100 double fit = result.coef * fitting_curve(n[i]);
101 rms += pow((time[i] - fit), 2);
102 }
103
104 // Normalized RMS by the mean of the observed values
105 double mean = sigma_time / n.size();
106 result.rms = sqrt(rms / n.size()) / mean;
107
108 return result;
109 }
110
111 // Find the coefficient for the high-order term in the running time, by
112 // minimizing the sum of squares of relative error.
113 // - n : Vector containing the size of the benchmark tests.
114 // - time : Vector containing the times for the benchmark tests.
115 // - complexity : If different than oAuto, the fitting curve will stick to
116 // this one. If it is oAuto, it will be calculated the best
117 // fitting curve.
MinimalLeastSq(const std::vector<int64_t> & n,const std::vector<double> & time,const BigO complexity)118 LeastSq MinimalLeastSq(const std::vector<int64_t>& n,
119 const std::vector<double>& time, const BigO complexity) {
120 CHECK_EQ(n.size(), time.size());
121 CHECK_GE(n.size(), 2); // Do not compute fitting curve is less than two
122 // benchmark runs are given
123 CHECK_NE(complexity, oNone);
124
125 LeastSq best_fit;
126
127 if (complexity == oAuto) {
128 std::vector<BigO> fit_curves = {oLogN, oN, oNLogN, oNSquared, oNCubed};
129
130 // Take o1 as default best fitting curve
131 best_fit = MinimalLeastSq(n, time, FittingCurve(o1));
132 best_fit.complexity = o1;
133
134 // Compute all possible fitting curves and stick to the best one
135 for (const auto& fit : fit_curves) {
136 LeastSq current_fit = MinimalLeastSq(n, time, FittingCurve(fit));
137 if (current_fit.rms < best_fit.rms) {
138 best_fit = current_fit;
139 best_fit.complexity = fit;
140 }
141 }
142 } else {
143 best_fit = MinimalLeastSq(n, time, FittingCurve(complexity));
144 best_fit.complexity = complexity;
145 }
146
147 return best_fit;
148 }
149
ComputeBigO(const std::vector<BenchmarkReporter::Run> & reports)150 std::vector<BenchmarkReporter::Run> ComputeBigO(
151 const std::vector<BenchmarkReporter::Run>& reports) {
152 typedef BenchmarkReporter::Run Run;
153 std::vector<Run> results;
154
155 if (reports.size() < 2) return results;
156
157 // Accumulators.
158 std::vector<int64_t> n;
159 std::vector<double> real_time;
160 std::vector<double> cpu_time;
161
162 // Populate the accumulators.
163 for (const Run& run : reports) {
164 CHECK_GT(run.complexity_n, 0) << "Did you forget to call SetComplexityN?";
165 n.push_back(run.complexity_n);
166 real_time.push_back(run.real_accumulated_time / run.iterations);
167 cpu_time.push_back(run.cpu_accumulated_time / run.iterations);
168 }
169
170 LeastSq result_cpu;
171 LeastSq result_real;
172
173 if (reports[0].complexity == oLambda) {
174 result_cpu = MinimalLeastSq(n, cpu_time, reports[0].complexity_lambda);
175 result_real = MinimalLeastSq(n, real_time, reports[0].complexity_lambda);
176 } else {
177 result_cpu = MinimalLeastSq(n, cpu_time, reports[0].complexity);
178 result_real = MinimalLeastSq(n, real_time, result_cpu.complexity);
179 }
180 std::string benchmark_name =
181 reports[0].benchmark_name.substr(0, reports[0].benchmark_name.find('/'));
182
183 // Get the data from the accumulator to BenchmarkReporter::Run's.
184 Run big_o;
185 big_o.benchmark_name = benchmark_name + "_BigO";
186 big_o.iterations = 0;
187 big_o.real_accumulated_time = result_real.coef;
188 big_o.cpu_accumulated_time = result_cpu.coef;
189 big_o.report_big_o = true;
190 big_o.complexity = result_cpu.complexity;
191
192 // All the time results are reported after being multiplied by the
193 // time unit multiplier. But since RMS is a relative quantity it
194 // should not be multiplied at all. So, here, we _divide_ it by the
195 // multiplier so that when it is multiplied later the result is the
196 // correct one.
197 double multiplier = GetTimeUnitMultiplier(reports[0].time_unit);
198
199 // Only add label to mean/stddev if it is same for all runs
200 Run rms;
201 big_o.report_label = reports[0].report_label;
202 rms.benchmark_name = benchmark_name + "_RMS";
203 rms.report_label = big_o.report_label;
204 rms.iterations = 0;
205 rms.real_accumulated_time = result_real.rms / multiplier;
206 rms.cpu_accumulated_time = result_cpu.rms / multiplier;
207 rms.report_rms = true;
208 rms.complexity = result_cpu.complexity;
209 // don't forget to keep the time unit, or we won't be able to
210 // recover the correct value.
211 rms.time_unit = reports[0].time_unit;
212
213 results.push_back(big_o);
214 results.push_back(rms);
215 return results;
216 }
217
218 } // end namespace benchmark
219