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