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 "complexity.h"
19
20 #include <algorithm>
21 #include <cmath>
22
23 #include "benchmark/benchmark.h"
24 #include "check.h"
25
26 namespace benchmark {
27
28 // Internal function to calculate the different scalability forms
FittingCurve(BigO complexity)29 BigOFunc* FittingCurve(BigO complexity) {
30 static const double kLog2E = 1.44269504088896340736;
31 switch (complexity) {
32 case oN:
33 return [](IterationCount n) -> double { return static_cast<double>(n); };
34 case oNSquared:
35 return [](IterationCount n) -> double { return std::pow(n, 2); };
36 case oNCubed:
37 return [](IterationCount n) -> double { return std::pow(n, 3); };
38 case oLogN:
39 /* Note: can't use log2 because Android's GNU STL lacks it */
40 return [](IterationCount n) {
41 return kLog2E * std::log(static_cast<double>(n));
42 };
43 case oNLogN:
44 /* Note: can't use log2 because Android's GNU STL lacks it */
45 return [](IterationCount n) {
46 return kLog2E * static_cast<double>(n) *
47 std::log(static_cast<double>(n));
48 };
49 case o1:
50 default:
51 return [](IterationCount) { return 1.0; };
52 }
53 }
54
55 // Function to return an string for the calculated complexity
GetBigOString(BigO complexity)56 std::string GetBigOString(BigO complexity) {
57 switch (complexity) {
58 case oN:
59 return "N";
60 case oNSquared:
61 return "N^2";
62 case oNCubed:
63 return "N^3";
64 case oLogN:
65 return "lgN";
66 case oNLogN:
67 return "NlgN";
68 case o1:
69 return "(1)";
70 default:
71 return "f(N)";
72 }
73 }
74
75 // Find the coefficient for the high-order term in the running time, by
76 // minimizing the sum of squares of relative error, for the fitting curve
77 // given by the lambda expression.
78 // - n : Vector containing the size of the benchmark tests.
79 // - time : Vector containing the times for the benchmark tests.
80 // - fitting_curve : lambda expression (e.g. [](ComplexityN n) {return n; };).
81
82 // For a deeper explanation on the algorithm logic, please refer to
83 // https://en.wikipedia.org/wiki/Least_squares#Least_squares,_regression_analysis_and_statistics
84
MinimalLeastSq(const std::vector<ComplexityN> & n,const std::vector<double> & time,BigOFunc * fitting_curve)85 LeastSq MinimalLeastSq(const std::vector<ComplexityN>& n,
86 const std::vector<double>& time,
87 BigOFunc* fitting_curve) {
88 double sigma_gn_squared = 0.0;
89 double sigma_time = 0.0;
90 double sigma_time_gn = 0.0;
91
92 // Calculate least square fitting parameter
93 for (size_t i = 0; i < n.size(); ++i) {
94 double gn_i = fitting_curve(n[i]);
95 sigma_gn_squared += gn_i * gn_i;
96 sigma_time += time[i];
97 sigma_time_gn += time[i] * gn_i;
98 }
99
100 LeastSq result;
101 result.complexity = oLambda;
102
103 // Calculate complexity.
104 result.coef = sigma_time_gn / sigma_gn_squared;
105
106 // Calculate RMS
107 double rms = 0.0;
108 for (size_t i = 0; i < n.size(); ++i) {
109 double fit = result.coef * fitting_curve(n[i]);
110 rms += std::pow((time[i] - fit), 2);
111 }
112
113 // Normalized RMS by the mean of the observed values
114 double mean = sigma_time / static_cast<double>(n.size());
115 result.rms = std::sqrt(rms / static_cast<double>(n.size())) / mean;
116
117 return result;
118 }
119
120 // Find the coefficient for the high-order term in the running time, by
121 // minimizing the sum of squares of relative error.
122 // - n : Vector containing the size of the benchmark tests.
123 // - time : Vector containing the times for the benchmark tests.
124 // - complexity : If different than oAuto, the fitting curve will stick to
125 // this one. If it is oAuto, it will be calculated the best
126 // fitting curve.
MinimalLeastSq(const std::vector<ComplexityN> & n,const std::vector<double> & time,const BigO complexity)127 LeastSq MinimalLeastSq(const std::vector<ComplexityN>& n,
128 const std::vector<double>& time, const BigO complexity) {
129 BM_CHECK_EQ(n.size(), time.size());
130 BM_CHECK_GE(n.size(), 2); // Do not compute fitting curve is less than two
131 // benchmark runs are given
132 BM_CHECK_NE(complexity, oNone);
133
134 LeastSq best_fit;
135
136 if (complexity == oAuto) {
137 std::vector<BigO> fit_curves = {oLogN, oN, oNLogN, oNSquared, oNCubed};
138
139 // Take o1 as default best fitting curve
140 best_fit = MinimalLeastSq(n, time, FittingCurve(o1));
141 best_fit.complexity = o1;
142
143 // Compute all possible fitting curves and stick to the best one
144 for (const auto& fit : fit_curves) {
145 LeastSq current_fit = MinimalLeastSq(n, time, FittingCurve(fit));
146 if (current_fit.rms < best_fit.rms) {
147 best_fit = current_fit;
148 best_fit.complexity = fit;
149 }
150 }
151 } else {
152 best_fit = MinimalLeastSq(n, time, FittingCurve(complexity));
153 best_fit.complexity = complexity;
154 }
155
156 return best_fit;
157 }
158
ComputeBigO(const std::vector<BenchmarkReporter::Run> & reports)159 std::vector<BenchmarkReporter::Run> ComputeBigO(
160 const std::vector<BenchmarkReporter::Run>& reports) {
161 typedef BenchmarkReporter::Run Run;
162 std::vector<Run> results;
163
164 if (reports.size() < 2) return results;
165
166 // Accumulators.
167 std::vector<ComplexityN> n;
168 std::vector<double> real_time;
169 std::vector<double> cpu_time;
170
171 // Populate the accumulators.
172 for (const Run& run : reports) {
173 BM_CHECK_GT(run.complexity_n, 0)
174 << "Did you forget to call SetComplexityN?";
175 n.push_back(run.complexity_n);
176 real_time.push_back(run.real_accumulated_time /
177 static_cast<double>(run.iterations));
178 cpu_time.push_back(run.cpu_accumulated_time /
179 static_cast<double>(run.iterations));
180 }
181
182 LeastSq result_cpu;
183 LeastSq result_real;
184
185 if (reports[0].complexity == oLambda) {
186 result_cpu = MinimalLeastSq(n, cpu_time, reports[0].complexity_lambda);
187 result_real = MinimalLeastSq(n, real_time, reports[0].complexity_lambda);
188 } else {
189 const BigO* InitialBigO = &reports[0].complexity;
190 const bool use_real_time_for_initial_big_o =
191 reports[0].use_real_time_for_initial_big_o;
192 if (use_real_time_for_initial_big_o) {
193 result_real = MinimalLeastSq(n, real_time, *InitialBigO);
194 InitialBigO = &result_real.complexity;
195 // The Big-O complexity for CPU time must have the same Big-O function!
196 }
197 result_cpu = MinimalLeastSq(n, cpu_time, *InitialBigO);
198 InitialBigO = &result_cpu.complexity;
199 if (!use_real_time_for_initial_big_o) {
200 result_real = MinimalLeastSq(n, real_time, *InitialBigO);
201 }
202 }
203
204 // Drop the 'args' when reporting complexity.
205 auto run_name = reports[0].run_name;
206 run_name.args.clear();
207
208 // Get the data from the accumulator to BenchmarkReporter::Run's.
209 Run big_o;
210 big_o.run_name = run_name;
211 big_o.family_index = reports[0].family_index;
212 big_o.per_family_instance_index = reports[0].per_family_instance_index;
213 big_o.run_type = BenchmarkReporter::Run::RT_Aggregate;
214 big_o.repetitions = reports[0].repetitions;
215 big_o.repetition_index = Run::no_repetition_index;
216 big_o.threads = reports[0].threads;
217 big_o.aggregate_name = "BigO";
218 big_o.aggregate_unit = StatisticUnit::kTime;
219 big_o.report_label = reports[0].report_label;
220 big_o.iterations = 0;
221 big_o.real_accumulated_time = result_real.coef;
222 big_o.cpu_accumulated_time = result_cpu.coef;
223 big_o.report_big_o = true;
224 big_o.complexity = result_cpu.complexity;
225
226 // All the time results are reported after being multiplied by the
227 // time unit multiplier. But since RMS is a relative quantity it
228 // should not be multiplied at all. So, here, we _divide_ it by the
229 // multiplier so that when it is multiplied later the result is the
230 // correct one.
231 double multiplier = GetTimeUnitMultiplier(reports[0].time_unit);
232
233 // Only add label to mean/stddev if it is same for all runs
234 Run rms;
235 rms.run_name = run_name;
236 rms.family_index = reports[0].family_index;
237 rms.per_family_instance_index = reports[0].per_family_instance_index;
238 rms.run_type = BenchmarkReporter::Run::RT_Aggregate;
239 rms.aggregate_name = "RMS";
240 rms.aggregate_unit = StatisticUnit::kPercentage;
241 rms.report_label = big_o.report_label;
242 rms.iterations = 0;
243 rms.repetition_index = Run::no_repetition_index;
244 rms.repetitions = reports[0].repetitions;
245 rms.threads = reports[0].threads;
246 rms.real_accumulated_time = result_real.rms / multiplier;
247 rms.cpu_accumulated_time = result_cpu.rms / multiplier;
248 rms.report_rms = true;
249 rms.complexity = result_cpu.complexity;
250 // don't forget to keep the time unit, or we won't be able to
251 // recover the correct value.
252 rms.time_unit = reports[0].time_unit;
253
254 results.push_back(big_o);
255 results.push_back(rms);
256 return results;
257 }
258
259 } // end namespace benchmark
260