complexity.cc revision 37ab858e4b245a49805b01358655fab069474a7c 
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/complexity.h"
19#include "check.h"
20#include <math.h>
21#include <functional>
22
23namespace benchmark {
24
25// Internal function to calculate the different scalability forms
26std::function<double(int)> FittingCurve(BigO complexity) {
27  switch (complexity) {
28    case oN:
29      return [](int n) {return n; };
30    case oNSquared:
31      return [](int n) {return n*n; };
32    case oNCubed:
33      return [](int n) {return n*n*n; };
34    case oLogN:
35      return [](int n) {return log2(n); };
36    case oNLogN:
37      return [](int n) {return n * log2(n); };
38    case o1:
39    default:
40      return [](int) {return 1; };
41  }
42}
43
44// Function to return an string for the calculated complexity
45std::string GetBigOString(BigO complexity) {
46  switch (complexity) {
47    case oN:
48      return "* N";
49    case oNSquared:
50      return "* N**2";
51    case oNCubed:
52      return "* N**3";
53    case oLogN:
54      return "* lgN";
55    case oNLogN:
56      return "* NlgN";
57    case o1:
58      return "* 1";
59    default:
60      return "";
61  }
62}
63
64// Find the coefficient for the high-order term in the running time, by
65// minimizing the sum of squares of relative error, for the fitting curve
66// given by the lambda expresion.
67//   - n             : Vector containing the size of the benchmark tests.
68//   - time          : Vector containing the times for the benchmark tests.
69//   - fitting_curve : lambda expresion (e.g. [](int n) {return n; };).
70
71// For a deeper explanation on the algorithm logic, look the README file at
72// http://github.com/ismaelJimenez/Minimal-Cpp-Least-Squared-Fit
73
74// This interface is currently not used from the oustide, but it has been
75// provided for future upgrades. If in the future it is not needed to support
76// Cxx03, then all the calculations could be upgraded to use lambdas because
77// they are more powerful and provide a cleaner inferface than enumerators,
78// but complete implementation with lambdas will not work for Cxx03
79// (e.g. lack of std::function).
80// In case lambdas are implemented, the interface would be like :
81//   -> Complexity([](int n) {return n;};)
82// and any arbitrary and valid  equation would be allowed, but the option to
83// calculate the best fit to the most common scalability curves will still
84// be kept.
85
86LeastSq CalculateLeastSq(const std::vector<int>& n,
87                         const std::vector<double>& time,
88                         std::function<double(int)> fitting_curve) {
89  double sigma_gn = 0.0;
90  double sigma_gn_squared = 0.0;
91  double sigma_time = 0.0;
92  double sigma_time_gn = 0.0;
93
94  // Calculate least square fitting parameter
95  for (size_t i = 0; i < n.size(); ++i) {
96    double gn_i = fitting_curve(n[i]);
97    sigma_gn += gn_i;
98    sigma_gn_squared += gn_i * gn_i;
99    sigma_time += time[i];
100    sigma_time_gn += time[i] * gn_i;
101  }
102
103  LeastSq result;
104
105  // Calculate complexity.
106  result.coef = sigma_time_gn / sigma_gn_squared;
107
108  // Calculate RMS
109  double rms = 0.0;
110  for (size_t i = 0; i < n.size(); ++i) {
111    double fit = result.coef * fitting_curve(n[i]);
112    rms += pow((time[i] - fit), 2);
113  }
114
115  // Normalized RMS by the mean of the observed values
116  double mean = sigma_time / n.size();
117  result.rms = sqrt(rms / n.size()) / mean;
118
119  return result;
120}
121
122// Find the coefficient for the high-order term in the running time, by
123// minimizing the sum of squares of relative error.
124//   - n          : Vector containing the size of the benchmark tests.
125//   - time       : Vector containing the times for the benchmark tests.
126//   - complexity : If different than oAuto, the fitting curve will stick to
127//                  this one. If it is oAuto, it will be calculated the best
128//                  fitting curve.
129LeastSq MinimalLeastSq(const std::vector<int>& n,
130                       const std::vector<double>& time,
131                       const BigO complexity) {
132  CHECK_EQ(n.size(), time.size());
133  CHECK_GE(n.size(), 2);  // Do not compute fitting curve is less than two benchmark runs are given
134  CHECK_NE(complexity, oNone);
135
136  LeastSq best_fit;
137
138  if(complexity == oAuto) {
139    std::vector<BigO> fit_curves = {
140      oLogN, oN, oNLogN, oNSquared, oNCubed };
141
142    // Take o1 as default best fitting curve
143    best_fit = CalculateLeastSq(n, time, FittingCurve(o1));
144    best_fit.complexity = o1;
145
146    // Compute all possible fitting curves and stick to the best one
147    for (const auto& fit : fit_curves) {
148      LeastSq current_fit = CalculateLeastSq(n, time, FittingCurve(fit));
149      if (current_fit.rms < best_fit.rms) {
150        best_fit = current_fit;
151        best_fit.complexity = fit;
152      }
153    }
154  } else {
155    best_fit = CalculateLeastSq(n, time, FittingCurve(complexity));
156    best_fit.complexity = complexity;
157  }
158
159  return best_fit;
160}
161
162}  // end namespace benchmark
163