refactor MinimalLEastSq
diff --git a/README.md b/README.md
index cd78c96..c989e57 100644
--- a/README.md
+++ b/README.md
@@ -127,14 +127,14 @@
benchmark::DoNotOptimize(s1.compare(s2));
}
BENCHMARK(BM_StringCompare)
- ->RangeMultiplier(2)->Range(1<<10, 1<<18)->Complexity(benchmark::O_N);
+ ->RangeMultiplier(2)->Range(1<<10, 1<<18)->Complexity(benchmark::oN);
```
As shown in the following invocation, asymptotic complexity might also be calculated automatically.
```c++
BENCHMARK(BM_StringCompare)
- ->RangeMultiplier(2)->Range(1<<10, 1<<18)->Complexity(benchmark::O_Auto);
+ ->RangeMultiplier(2)->Range(1<<10, 1<<18)->Complexity(benchmark::oAuto);
```
### Templated benchmarks
diff --git a/include/benchmark/benchmark_api.h b/include/benchmark/benchmark_api.h
index d7cf83f..385cbbc 100644
--- a/include/benchmark/benchmark_api.h
+++ b/include/benchmark/benchmark_api.h
@@ -232,17 +232,17 @@
};
// BigO is passed to a benchmark in order to specify the asymptotic computational
-// complexity for the benchmark. In case O_Auto is selected, complexity will be
+// complexity for the benchmark. In case oAuto is selected, complexity will be
// calculated automatically to the best fit.
enum BigO {
- O_None,
- O_1,
- O_N,
- O_N_Squared,
- O_N_Cubed,
- O_log_N,
- O_N_log_N,
- O_Auto
+ oNone,
+ o1,
+ oN,
+ oNSquared,
+ oNCubed,
+ oLogN,
+ oNLogN,
+ oAuto
};
// State is passed to a running Benchmark and contains state for the
diff --git a/include/benchmark/reporter.h b/include/benchmark/reporter.h
index 564219a..5e0a552 100644
--- a/include/benchmark/reporter.h
+++ b/include/benchmark/reporter.h
@@ -49,7 +49,7 @@
bytes_per_second(0),
items_per_second(0),
max_heapbytes_used(0),
- complexity(O_None),
+ complexity(oNone),
arg1(0),
arg2(0),
report_big_o(false),
diff --git a/src/benchmark.cc b/src/benchmark.cc
index 874dc0c..dbab503 100644
--- a/src/benchmark.cc
+++ b/src/benchmark.cc
@@ -454,7 +454,7 @@
: name_(name), arg_count_(-1), time_unit_(kNanosecond),
range_multiplier_(kRangeMultiplier), min_time_(0.0),
use_real_time_(false), use_manual_time_(false),
- complexity_(O_None) {
+ complexity_(oNone) {
}
BenchmarkImp::~BenchmarkImp() {
@@ -803,7 +803,7 @@
report.complexity = b.complexity;
reports.push_back(report);
- if(report.complexity != O_None)
+ if(report.complexity != oNone)
complexity_reports.push_back(report);
break;
@@ -830,7 +830,7 @@
}
br->ReportRuns(reports);
- if((b.complexity != O_None) && b.last_benchmark_instance) {
+ if((b.complexity != oNone) && b.last_benchmark_instance) {
br->ReportComplexity(complexity_reports);
complexity_reports.clear();
}
diff --git a/src/csv_reporter.cc b/src/csv_reporter.cc
index 031736e..df662e4 100644
--- a/src/csv_reporter.cc
+++ b/src/csv_reporter.cc
@@ -72,12 +72,12 @@
return;
}
- Run bigO_data;
+ Run big_o_data;
Run rms_data;
- BenchmarkReporter::ComputeBigO(complexity_reports, &bigO_data, &rms_data);
+ BenchmarkReporter::ComputeBigO(complexity_reports, &big_o_data, &rms_data);
// Output using PrintRun.
- PrintRunData(bigO_data);
+ PrintRunData(big_o_data);
PrintRunData(rms_data);
}
diff --git a/src/json_reporter.cc b/src/json_reporter.cc
index c15fb10..bfa85e4 100644
--- a/src/json_reporter.cc
+++ b/src/json_reporter.cc
@@ -127,13 +127,13 @@
out << ",\n";
}
- Run bigO_data;
+ Run big_o_data;
Run rms_data;
- BenchmarkReporter::ComputeBigO(complexity_reports, &bigO_data, &rms_data);
+ BenchmarkReporter::ComputeBigO(complexity_reports, &big_o_data, &rms_data);
// Output using PrintRun.
out << indent << "{\n";
- PrintRunData(bigO_data);
+ PrintRunData(big_o_data);
out << indent << "},\n";
out << indent << "{\n";
PrintRunData(rms_data);
diff --git a/src/minimal_leastsq.cc b/src/minimal_leastsq.cc
index f3c841d..0b6e665 100644
--- a/src/minimal_leastsq.cc
+++ b/src/minimal_leastsq.cc
@@ -16,95 +16,94 @@
// Adapted to be used with google benchmark
#include "minimal_leastsq.h"
-
+#include "check.h"
#include <math.h>
// Internal function to calculate the different scalability forms
-double fittingCurve(double n, benchmark::BigO complexity) {
+double FittingCurve(double n, benchmark::BigO complexity) {
switch (complexity) {
- case benchmark::O_N:
+ case benchmark::oN:
return n;
- case benchmark::O_N_Squared:
+ case benchmark::oNSquared:
return pow(n, 2);
- case benchmark::O_N_Cubed:
+ case benchmark::oNCubed:
return pow(n, 3);
- case benchmark::O_log_N:
+ case benchmark::oLogN:
return log2(n);
- case benchmark::O_N_log_N:
+ case benchmark::oNLogN:
return n * log2(n);
- case benchmark::O_1:
+ case benchmark::o1:
default:
return 1;
}
}
// Internal function to find the coefficient for the high-order term in the running time, by minimizing the sum of squares of relative error.
-// - N : Vector containing the size of the benchmark tests.
-// - Time : Vector containing the times for the benchmark tests.
-// - Complexity : Fitting curve.
+// - n : Vector containing the size of the benchmark tests.
+// - time : Vector containing the times for the benchmark tests.
+// - complexity : Fitting curve.
// For a deeper explanation on the algorithm logic, look the README file at http://github.com/ismaelJimenez/Minimal-Cpp-Least-Squared-Fit
-LeastSq leastSq(const std::vector<int>& N, const std::vector<double>& Time, const benchmark::BigO Complexity) {
- assert(N.size() == Time.size() && N.size() >= 2);
- assert(Complexity != benchmark::O_None &&
- Complexity != benchmark::O_Auto);
+LeastSq CalculateLeastSq(const std::vector<int>& n, const std::vector<double>& time, const benchmark::BigO complexity) {
+ CHECK_NE(complexity, benchmark::oAuto);
- double sigmaGN = 0;
- double sigmaGNSquared = 0;
- double sigmaTime = 0;
- double sigmaTimeGN = 0;
+ double sigma_gn = 0;
+ double sigma_gn_squared = 0;
+ double sigma_time = 0;
+ double sigma_time_gn = 0;
// Calculate least square fitting parameter
- for (size_t i = 0; i < N.size(); ++i) {
- double GNi = fittingCurve(N[i], Complexity);
- sigmaGN += GNi;
- sigmaGNSquared += GNi * GNi;
- sigmaTime += Time[i];
- sigmaTimeGN += Time[i] * GNi;
+ for (size_t i = 0; i < n.size(); ++i) {
+ double gn_i = FittingCurve(n[i], complexity);
+ sigma_gn += gn_i;
+ sigma_gn_squared += gn_i * gn_i;
+ sigma_time += time[i];
+ sigma_time_gn += time[i] * gn_i;
}
LeastSq result;
- result.complexity = Complexity;
+ result.complexity = complexity;
// Calculate complexity.
- // O_1 is treated as an special case
- if (Complexity != benchmark::O_1)
- result.coef = sigmaTimeGN / sigmaGNSquared;
+ // o1 is treated as an special case
+ if (complexity != benchmark::o1)
+ result.coef = sigma_time_gn / sigma_gn_squared;
else
- result.coef = sigmaTime / N.size();
+ result.coef = sigma_time / n.size();
// Calculate RMS
double rms = 0;
- for (size_t i = 0; i < N.size(); ++i) {
- double fit = result.coef * fittingCurve(N[i], Complexity);
- rms += pow((Time[i] - fit), 2);
+ for (size_t i = 0; i < n.size(); ++i) {
+ double fit = result.coef * FittingCurve(n[i], complexity);
+ rms += pow((time[i] - fit), 2);
}
- double mean = sigmaTime / N.size();
+ double mean = sigma_time / n.size();
- result.rms = sqrt(rms / N.size()) / mean; // Normalized RMS by the mean of the observed values
+ result.rms = sqrt(rms / n.size()) / mean; // Normalized RMS by the mean of the observed values
return result;
}
// Find the coefficient for the high-order term in the running time, by minimizing the sum of squares of relative error.
-// - N : Vector containing the size of the benchmark tests.
-// - Time : Vector containing the times for the benchmark tests.
-// - Complexity : If different than O_Auto, the fitting curve will stick to this one. If it is O_Auto, it will be calculated
+// - n : Vector containing the size of the benchmark tests.
+// - time : Vector containing the times for the benchmark tests.
+// - complexity : If different than oAuto, the fitting curve will stick to this one. If it is oAuto, it will be calculated
// the best fitting curve.
-LeastSq minimalLeastSq(const std::vector<int>& N, const std::vector<double>& Time, const benchmark::BigO Complexity) {
- assert(N.size() == Time.size() && N.size() >= 2); // Do not compute fitting curve is less than two benchmark runs are given
- assert(Complexity != benchmark::O_None); // Check that complexity is a valid parameter.
+LeastSq MinimalLeastSq(const std::vector<int>& n, const std::vector<double>& time, const benchmark::BigO complexity) {
+ CHECK_EQ(n.size(), time.size());
+ CHECK_GE(n.size(), 2); // Do not compute fitting curve is less than two benchmark runs are given
+ CHECK_NE(complexity, benchmark::oNone);
- if(Complexity == benchmark::O_Auto) {
- std::vector<benchmark::BigO> fitCurves = { benchmark::O_log_N, benchmark::O_N, benchmark::O_N_log_N, benchmark::O_N_Squared, benchmark::O_N_Cubed };
+ if(complexity == benchmark::oAuto) {
+ std::vector<benchmark::BigO> fit_curves = { benchmark::oLogN, benchmark::oN, benchmark::oNLogN, benchmark::oNSquared, benchmark::oNCubed };
- LeastSq best_fit = leastSq(N, Time, benchmark::O_1); // Take O_1 as default best fitting curve
+ LeastSq best_fit = CalculateLeastSq(n, time, benchmark::o1); // Take o1 as default best fitting curve
// Compute all possible fitting curves and stick to the best one
- for (const auto& fit : fitCurves) {
- LeastSq current_fit = leastSq(N, Time, fit);
+ for (const auto& fit : fit_curves) {
+ LeastSq current_fit = CalculateLeastSq(n, time, fit);
if (current_fit.rms < best_fit.rms)
best_fit = current_fit;
}
@@ -112,5 +111,5 @@
return best_fit;
}
else
- return leastSq(N, Time, Complexity);
+ return CalculateLeastSq(n, time, complexity);
}
\ No newline at end of file
diff --git a/src/minimal_leastsq.h b/src/minimal_leastsq.h
index 0b137fb..3f7be34 100644
--- a/src/minimal_leastsq.h
+++ b/src/minimal_leastsq.h
@@ -22,18 +22,18 @@
#include <vector>
-// This data structure will contain the result returned by minimalLeastSq
+// This data structure will contain the result returned by MinimalLeastSq
// - coef : Estimated coeficient for the high-order term as interpolated from data.
// - rms : Normalized Root Mean Squared Error.
-// - complexity : Scalability form (e.g. O_N, O_N_log_N). In case a scalability form has been provided to minimalLeastSq
-// this will return the same value. In case BigO::O_Auto has been selected, this parameter will return the
+// - complexity : Scalability form (e.g. oN, oNLogN). In case a scalability form has been provided to MinimalLeastSq
+// this will return the same value. In case BigO::oAuto has been selected, this parameter will return the
// best fitting curve detected.
struct LeastSq {
LeastSq() :
coef(0),
rms(0),
- complexity(benchmark::O_None) {}
+ complexity(benchmark::oNone) {}
double coef;
double rms;
@@ -41,6 +41,6 @@
};
// Find the coefficient for the high-order term in the running time, by minimizing the sum of squares of relative error.
-LeastSq minimalLeastSq(const std::vector<int>& N, const std::vector<double>& Time, const benchmark::BigO Complexity = benchmark::O_Auto);
+LeastSq MinimalLeastSq(const std::vector<int>& N, const std::vector<double>& Time, const benchmark::BigO Complexity = benchmark::oAuto);
#endif
diff --git a/src/reporter.cc b/src/reporter.cc
index 27dca85..0e1c581 100644
--- a/src/reporter.cc
+++ b/src/reporter.cc
@@ -95,13 +95,13 @@
CpuTime.push_back(run.cpu_accumulated_time/run.iterations);
}
- LeastSq resultCpu = minimalLeastSq(N, CpuTime, reports[0].complexity);
+ LeastSq resultCpu = MinimalLeastSq(N, CpuTime, reports[0].complexity);
// resultCpu.complexity is passed as parameter to resultReal because in case
- // reports[0].complexity is O_Auto, the noise on the measured data could make
+ // reports[0].complexity is oAuto, the noise on the measured data could make
// the best fit function of Cpu and Real differ. In order to solve this, we take
// the best fitting function for the Cpu, and apply it to Real data.
- LeastSq resultReal = minimalLeastSq(N, RealTime, resultCpu.complexity);
+ LeastSq resultReal = MinimalLeastSq(N, RealTime, resultCpu.complexity);
std::string benchmark_name = reports[0].benchmark_name.substr(0, reports[0].benchmark_name.find('/'));
@@ -130,17 +130,17 @@
std::string BenchmarkReporter::GetBigO(BigO complexity) {
switch (complexity) {
- case O_N:
+ case oN:
return "* N";
- case O_N_Squared:
+ case oNSquared:
return "* N**2";
- case O_N_Cubed:
+ case oNCubed:
return "* N**3";
- case O_log_N:
+ case oLogN:
return "* lgN";
- case O_N_log_N:
+ case oNLogN:
return "* NlgN";
- case O_1:
+ case o1:
return "* 1";
default:
return "";
diff --git a/test/complexity_test.cc b/test/complexity_test.cc
index e7e16d3..e81742e 100644
--- a/test/complexity_test.cc
+++ b/test/complexity_test.cc
@@ -27,7 +27,7 @@
while (state.KeepRunning()) {
}
}
-BENCHMARK(BM_Complexity_O1) -> Range(1, 1<<18) -> Complexity(benchmark::O_1);
+BENCHMARK(BM_Complexity_O1) -> Range(1, 1<<18) -> Complexity(benchmark::o1);
static void BM_Complexity_O_N(benchmark::State& state) {
auto v = ConstructRandomVector(state.range_x());
@@ -36,8 +36,8 @@
benchmark::DoNotOptimize(std::find(v.begin(), v.end(), itemNotInVector));
}
}
-BENCHMARK(BM_Complexity_O_N) -> RangeMultiplier(2) -> Range(1<<10, 1<<16) -> Complexity(benchmark::O_N);
-BENCHMARK(BM_Complexity_O_N) -> RangeMultiplier(2) -> Range(1<<10, 1<<16) -> Complexity(benchmark::O_Auto);
+BENCHMARK(BM_Complexity_O_N) -> RangeMultiplier(2) -> Range(1<<10, 1<<16) -> Complexity(benchmark::oN);
+BENCHMARK(BM_Complexity_O_N) -> RangeMultiplier(2) -> Range(1<<10, 1<<16) -> Complexity(benchmark::oAuto);
static void BM_Complexity_O_N_Squared(benchmark::State& state) {
std::string s1(state.range_x(), '-');
@@ -50,7 +50,7 @@
}
}
}
-BENCHMARK(BM_Complexity_O_N_Squared) -> Range(1, 1<<8) -> Complexity(benchmark::O_N_Squared);
+BENCHMARK(BM_Complexity_O_N_Squared) -> Range(1, 1<<8) -> Complexity(benchmark::oNSquared);
static void BM_Complexity_O_N_Cubed(benchmark::State& state) {
std::string s1(state.range_x(), '-');
@@ -67,7 +67,7 @@
}
}
}
-BENCHMARK(BM_Complexity_O_N_Cubed) -> DenseRange(1, 8) -> Complexity(benchmark::O_N_Cubed);
+BENCHMARK(BM_Complexity_O_N_Cubed) -> DenseRange(1, 8) -> Complexity(benchmark::oNCubed);
static void BM_Complexity_O_log_N(benchmark::State& state) {
auto m = ConstructRandomMap(state.range_x());
@@ -77,7 +77,7 @@
}
}
BENCHMARK(BM_Complexity_O_log_N)
- -> RangeMultiplier(2) -> Range(1<<10, 1<<16) -> Complexity(benchmark::O_log_N);
+ -> RangeMultiplier(2) -> Range(1<<10, 1<<16) -> Complexity(benchmark::oLogN);
static void BM_Complexity_O_N_log_N(benchmark::State& state) {
auto v = ConstructRandomVector(state.range_x());
@@ -85,15 +85,15 @@
std::sort(v.begin(), v.end());
}
}
-BENCHMARK(BM_Complexity_O_N_log_N) -> RangeMultiplier(2) -> Range(1<<10, 1<<16) -> Complexity(benchmark::O_N_log_N);
-BENCHMARK(BM_Complexity_O_N_log_N) -> RangeMultiplier(2) -> Range(1<<10, 1<<16) -> Complexity(benchmark::O_Auto);
+BENCHMARK(BM_Complexity_O_N_log_N) -> RangeMultiplier(2) -> Range(1<<10, 1<<16) -> Complexity(benchmark::oNLogN);
+BENCHMARK(BM_Complexity_O_N_log_N) -> RangeMultiplier(2) -> Range(1<<10, 1<<16) -> Complexity(benchmark::oAuto);
// Test benchmark with no range and check no complexity is calculated.
void BM_Extreme_Cases(benchmark::State& state) {
while (state.KeepRunning()) {
}
}
-BENCHMARK(BM_Extreme_Cases) -> Complexity(benchmark::O_N_log_N);
-BENCHMARK(BM_Extreme_Cases) -> Arg(42) -> Complexity(benchmark::O_Auto);
+BENCHMARK(BM_Extreme_Cases) -> Complexity(benchmark::oNLogN);
+BENCHMARK(BM_Extreme_Cases) -> Arg(42) -> Complexity(benchmark::oAuto);
BENCHMARK_MAIN()
\ No newline at end of file