260 lines · plain
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 at6//7// http://www.apache.org/licenses/LICENSE-2.08//9// Unless required by applicable law or agreed to in writing, software10// 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 and13// limitations under the License.14 15// Source project : https://github.com/ismaelJimenez/cpp.leastsq16// Adapted to be used with google benchmark17 18#include "complexity.h"19 20#include <algorithm>21#include <cmath>22 23#include "benchmark/benchmark.h"24#include "check.h"25 26namespace benchmark {27 28// Internal function to calculate the different scalability forms29BigOFunc* 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 complexity56std::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, by76// minimizing the sum of squares of relative error, for the fitting curve77// 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 to83// https://en.wikipedia.org/wiki/Least_squares#Least_squares,_regression_analysis_and_statistics84 85LeastSq 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 parameter93 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 RMS107 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 values114 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, by121// 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 to125// this one. If it is oAuto, it will be calculated the best126// fitting curve.127LeastSq 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 two131 // benchmark runs are given132 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 curve140 best_fit = MinimalLeastSq(n, time, FittingCurve(o1));141 best_fit.complexity = o1;142 143 // Compute all possible fitting curves and stick to the best one144 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 159std::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 the227 // time unit multiplier. But since RMS is a relative quantity it228 // should not be multiplied at all. So, here, we _divide_ it by the229 // multiplier so that when it is multiplied later the result is the230 // correct one.231 double multiplier = GetTimeUnitMultiplier(reports[0].time_unit);232 233 // Only add label to mean/stddev if it is same for all runs234 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 to251 // 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 benchmark260