| 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 |
| 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 |
| 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 |
|
| 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. |
| 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 |
|
| 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 |