third-party/benchmark/src/complexity.cc

   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