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_api.h"
19
20#include <algorithm>
21#include <cmath>
22#include "check.h"
23#include "complexity.h"
24#include "stat.h"
25
26namespace benchmark {
27
28// Internal function to calculate the different scalability forms
29BigOFunc* FittingCurve(BigO complexity) {
30 switch (complexity) {
31 case oN:
32 return [](int n) -> double { return n; };
33 case oNSquared:
34 return [](int n) -> double { return std::pow(n, 2); };
35 case oNCubed:
36 return [](int n) -> double { return std::pow(n, 3); };
37 case oLogN:
38 return [](int n) { return std::log2(n); };
39 case oNLogN:
40 return [](int n) { return n * std::log2(n); };
41 case o1:
42 default:
43 return [](int) { return 1.0; };
44 }
45}
46
47// Function to return an string for the calculated complexity
48std::string GetBigOString(BigO complexity) {
49 switch (complexity) {
50 case oN:
51 return "N";
52 case oNSquared:
53 return "N^2";
54 case oNCubed:
55 return "N^3";
56 case oLogN:
57 return "lgN";
58 case oNLogN:
59 return "NlgN";
60 case o1:
61 return "(1)";
62 default:
63 return "f(N)";
64 }
65}
66
67// Find the coefficient for the high-order term in the running time, by
68// minimizing the sum of squares of relative error, for the fitting curve
69// given by the lambda expresion.
70// - n : Vector containing the size of the benchmark tests.
71// - time : Vector containing the times for the benchmark tests.
72// - fitting_curve : lambda expresion (e.g. [](int n) {return n; };).
73
74// For a deeper explanation on the algorithm logic, look the README file at
75// http://github.com/ismaelJimenez/Minimal-Cpp-Least-Squared-Fit
76
77LeastSq MinimalLeastSq(const std::vector<int>& n,
78 const std::vector<double>& time,
79 BigOFunc* fitting_curve) {
80 double sigma_gn = 0.0;
81 double sigma_gn_squared = 0.0;
82 double sigma_time = 0.0;
83 double sigma_time_gn = 0.0;
84
85 // Calculate least square fitting parameter
86 for (size_t i = 0; i < n.size(); ++i) {
87 double gn_i = fitting_curve(n[i]);
88 sigma_gn += gn_i;
89 sigma_gn_squared += gn_i * gn_i;
90 sigma_time += time[i];
91 sigma_time_gn += time[i] * gn_i;
92 }
93
94 LeastSq result;
95 result.complexity = oLambda;
96
97 // Calculate complexity.
98 result.coef = sigma_time_gn / sigma_gn_squared;
99
100 // Calculate RMS
101 double rms = 0.0;
102 for (size_t i = 0; i < n.size(); ++i) {
103 double fit = result.coef * fitting_curve(n[i]);
104 rms += pow((time[i] - fit), 2);
105 }
106
107 // Normalized RMS by the mean of the observed values
108 double mean = sigma_time / n.size();
109 result.rms = sqrt(rms / n.size()) / mean;
110
111 return result;
112}
113
114// Find the coefficient for the high-order term in the running time, by
115// minimizing the sum of squares of relative error.
116// - n : Vector containing the size of the benchmark tests.
117// - time : Vector containing the times for the benchmark tests.
118// - complexity : If different than oAuto, the fitting curve will stick to
119// this one. If it is oAuto, it will be calculated the best
120// fitting curve.
121LeastSq MinimalLeastSq(const std::vector<int>& n,
122 const std::vector<double>& time, const BigO complexity) {
123 CHECK_EQ(n.size(), time.size());
124 CHECK_GE(n.size(), 2); // Do not compute fitting curve is less than two
125 // benchmark runs are given
126 CHECK_NE(complexity, oNone);
127
128 LeastSq best_fit;
129
130 if (complexity == oAuto) {
131 std::vector<BigO> fit_curves = {oLogN, oN, oNLogN, oNSquared, oNCubed};
132
133 // Take o1 as default best fitting curve
134 best_fit = MinimalLeastSq(n, time, FittingCurve(o1));
135 best_fit.complexity = o1;
136
137 // Compute all possible fitting curves and stick to the best one
138 for (const auto& fit : fit_curves) {
139 LeastSq current_fit = MinimalLeastSq(n, time, FittingCurve(fit));
140 if (current_fit.rms < best_fit.rms) {
141 best_fit = current_fit;
142 best_fit.complexity = fit;
143 }
144 }
145 } else {
146 best_fit = MinimalLeastSq(n, time, FittingCurve(complexity));
147 best_fit.complexity = complexity;
148 }
149
150 return best_fit;
151}
152
153std::vector<BenchmarkReporter::Run> ComputeStats(
154 const std::vector<BenchmarkReporter::Run>& reports) {
155 typedef BenchmarkReporter::Run Run;
156 std::vector<Run> results;
157
158 auto error_count =
159 std::count_if(reports.begin(), reports.end(),
160 [](Run const& run) { return run.error_occurred; });
161
162 if (reports.size() - error_count < 2) {
163 // We don't report aggregated data if there was a single run.
164 return results;
165 }
166 // Accumulators.
167 Stat1_d real_accumulated_time_stat;
168 Stat1_d cpu_accumulated_time_stat;
169 Stat1_d bytes_per_second_stat;
170 Stat1_d items_per_second_stat;
171 // All repetitions should be run with the same number of iterations so we
172 // can take this information from the first benchmark.
173 int64_t const run_iterations = reports.front().iterations;
174
175 // Populate the accumulators.
176 for (Run const& run : reports) {
177 CHECK_EQ(reports[0].benchmark_name, run.benchmark_name);
178 CHECK_EQ(run_iterations, run.iterations);
179 if (run.error_occurred) continue;
180 real_accumulated_time_stat +=
181 Stat1_d(run.real_accumulated_time / run.iterations, run.iterations);
182 cpu_accumulated_time_stat +=
183 Stat1_d(run.cpu_accumulated_time / run.iterations, run.iterations);
184 items_per_second_stat += Stat1_d(run.items_per_second, run.iterations);
185 bytes_per_second_stat += Stat1_d(run.bytes_per_second, run.iterations);
186 }
187
188 // Get the data from the accumulator to BenchmarkReporter::Run's.
189 Run mean_data;
190 mean_data.benchmark_name = reports[0].benchmark_name + "_mean";
191 mean_data.iterations = run_iterations;
192 mean_data.real_accumulated_time =
193 real_accumulated_time_stat.Mean() * run_iterations;
194 mean_data.cpu_accumulated_time =
195 cpu_accumulated_time_stat.Mean() * run_iterations;
196 mean_data.bytes_per_second = bytes_per_second_stat.Mean();
197 mean_data.items_per_second = items_per_second_stat.Mean();
198 mean_data.time_unit = reports[0].time_unit;
199
200 // Only add label to mean/stddev if it is same for all runs
201 mean_data.report_label = reports[0].report_label;
202 for (std::size_t i = 1; i < reports.size(); i++) {
203 if (reports[i].report_label != reports[0].report_label) {
204 mean_data.report_label = "";
205 break;
206 }
207 }
208
209 Run stddev_data;
210 stddev_data.benchmark_name = reports[0].benchmark_name + "_stddev";
211 stddev_data.report_label = mean_data.report_label;
212 stddev_data.iterations = 0;
213 stddev_data.real_accumulated_time = real_accumulated_time_stat.StdDev();
214 stddev_data.cpu_accumulated_time = cpu_accumulated_time_stat.StdDev();
215 stddev_data.bytes_per_second = bytes_per_second_stat.StdDev();
216 stddev_data.items_per_second = items_per_second_stat.StdDev();
217 stddev_data.time_unit = reports[0].time_unit;
218
219 results.push_back(mean_data);
220 results.push_back(stddev_data);
221 return results;
222}
223
224std::vector<BenchmarkReporter::Run> ComputeBigO(
225 const std::vector<BenchmarkReporter::Run>& reports) {
226 typedef BenchmarkReporter::Run Run;
227 std::vector<Run> results;
228
229 if (reports.size() < 2) return results;
230
231 // Accumulators.
232 std::vector<int> n;
233 std::vector<double> real_time;
234 std::vector<double> cpu_time;
235
236 // Populate the accumulators.
237 for (const Run& run : reports) {
238 CHECK_GT(run.complexity_n, 0) << "Did you forget to call SetComplexityN?";
239 n.push_back(run.complexity_n);
240 real_time.push_back(run.real_accumulated_time / run.iterations);
241 cpu_time.push_back(run.cpu_accumulated_time / run.iterations);
242 }
243
244 LeastSq result_cpu;
245 LeastSq result_real;
246
247 if (reports[0].complexity == oLambda) {
248 result_cpu = MinimalLeastSq(n, cpu_time, reports[0].complexity_lambda);
249 result_real = MinimalLeastSq(n, real_time, reports[0].complexity_lambda);
250 } else {
251 result_cpu = MinimalLeastSq(n, cpu_time, reports[0].complexity);
252 result_real = MinimalLeastSq(n, real_time, result_cpu.complexity);
253 }
254 std::string benchmark_name =
255 reports[0].benchmark_name.substr(0, reports[0].benchmark_name.find('/'));
256
257 // Get the data from the accumulator to BenchmarkReporter::Run's.
258 Run big_o;
259 big_o.benchmark_name = benchmark_name + "_BigO";
260 big_o.iterations = 0;
261 big_o.real_accumulated_time = result_real.coef;
262 big_o.cpu_accumulated_time = result_cpu.coef;
263 big_o.report_big_o = true;
264 big_o.complexity = result_cpu.complexity;
265
266 double multiplier = GetTimeUnitMultiplier(reports[0].time_unit);
267
268 // Only add label to mean/stddev if it is same for all runs
269 Run rms;
270 big_o.report_label = reports[0].report_label;
271 rms.benchmark_name = benchmark_name + "_RMS";
272 rms.report_label = big_o.report_label;
273 rms.iterations = 0;
274 rms.real_accumulated_time = result_real.rms / multiplier;
275 rms.cpu_accumulated_time = result_cpu.rms / multiplier;
276 rms.report_rms = true;
277 rms.complexity = result_cpu.complexity;
278
279 results.push_back(big_o);
280 results.push_back(rms);
281 return results;
282}
283
284} // end namespace benchmark
285