addaptation of minimal_leastsq library
diff --git a/include/benchmark/benchmark_api.h b/include/benchmark/benchmark_api.h
index 8878b58..146a8cc 100644
--- a/include/benchmark/benchmark_api.h
+++ b/include/benchmark/benchmark_api.h
@@ -234,15 +234,14 @@
// BigO is passed to a benchmark in order to specify the asymptotic computational
// complexity for the benchmark.
enum BigO {
- O_None,
- O_1,
- O_N,
- O_M_plus_N,
- O_N_Squared,
- O_N_Cubed,
- O_log_N,
- O_N_log_N,
- O_Auto
+ O_None,
+ O_1,
+ O_N,
+ O_N_Squared,
+ O_N_Cubed,
+ O_log_N,
+ O_N_log_N,
+ O_Auto
};
// State is passed to a running Benchmark and contains state for the
diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt
index 811d075..a681b35 100644
--- a/src/CMakeLists.txt
+++ b/src/CMakeLists.txt
@@ -5,7 +5,7 @@
set(SOURCE_FILES "benchmark.cc" "colorprint.cc" "commandlineflags.cc"
"console_reporter.cc" "csv_reporter.cc" "json_reporter.cc"
"log.cc" "reporter.cc" "sleep.cc" "string_util.cc"
- "sysinfo.cc" "walltime.cc")
+ "sysinfo.cc" "walltime.cc" "minimal_leastsq.cc")
# Determine the correct regular expression engine to use
if(HAVE_STD_REGEX)
set(RE_FILES "re_std.cc")
diff --git a/src/minimal_leastsq.cc b/src/minimal_leastsq.cc
new file mode 100644
index 0000000..c4627d3
--- /dev/null
+++ b/src/minimal_leastsq.cc
@@ -0,0 +1,113 @@
+// Copyright 2016 Ismael Jimenez Martinez. All rights reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+// Source project : https://github.com/ismaelJimenez/cpp.leastsq
+// Addapted to be used with google benchmark
+
+#include "minimal_leastsq.h"
+
+#include <math.h>
+
+// Internal function to calculate the different scalability forms
+double fittingCurve(double N, benchmark::BigO Complexity) {
+ if (Complexity == benchmark::O_N)
+ return N;
+ else if (Complexity == benchmark::O_N_Squared)
+ return pow(N, 2);
+ else if (Complexity == benchmark::O_N_Cubed)
+ return pow(N, 3);
+ else if (Complexity == benchmark::O_log_N)
+ return log2(N);
+ else if (Complexity == benchmark::O_N_log_N)
+ return N * log2(N);
+
+ return 1; // Default value for O_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.
+// 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<int>& Time, const benchmark::BigO Complexity) {
+ assert(N.size() == Time.size() && N.size() >= 2);
+ assert(Complexity != benchmark::O_None &&
+ Complexity != benchmark::O_Auto);
+
+ double sigmaGN = 0;
+ double sigmaGNSquared = 0;
+ double sigmaTime = 0;
+ double sigmaTimeGN = 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;
+ }
+
+ LeastSq result;
+ result.complexity = Complexity;
+
+ // Calculate complexity.
+ // O_1 is treated as an special case
+ if (Complexity != benchmark::O_1)
+ result.coef = sigmaTimeGN / sigmaGNSquared;
+ else
+ result.coef = sigmaTime / 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);
+ }
+
+ double mean = sigmaTime / N.size();
+
+ result.rms = sqrt(rms) / 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
+// the best fitting curve.
+
+LeastSq minimalLeastSq(const std::vector<int>& N, const std::vector<int>& 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.
+
+ 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 };
+
+ LeastSq best_fit = leastSq(N, Time, benchmark::O_1); // Take O_1 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);
+ if (current_fit.rms < best_fit.rms)
+ best_fit = current_fit;
+ }
+
+ return best_fit;
+ }
+ else
+ return leastSq(N, Time, Complexity);
+}
\ No newline at end of file
diff --git a/src/minimal_leastsq.h b/src/minimal_leastsq.h
new file mode 100644
index 0000000..ae725d1
--- /dev/null
+++ b/src/minimal_leastsq.h
@@ -0,0 +1,46 @@
+// Copyright 2016 Ismael Jimenez Martinez. All rights reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+// Source project : https://github.com/ismaelJimenez/cpp.leastsq
+// Addapted to be used with google benchmark
+
+#if !defined(MINIMAL_LEASTSQ_H_)
+#define MINIMAL_LEASTSQ_H_
+
+#include "benchmark/benchmark_api.h"
+
+#include <vector>
+
+// This data structure will contain the result returned vy 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
+// best fitting curve detected.
+
+struct LeastSq {
+ LeastSq() :
+ coef(0),
+ rms(0),
+ complexity(benchmark::O_None) {}
+
+ double coef;
+ double rms;
+ benchmark::BigO complexity;
+};
+
+// 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<int>& Time, const benchmark::BigO Complexity = benchmark::O_Auto);
+
+#endif
diff --git a/src/reporter.cc b/src/reporter.cc
index fd97aba..dc7b76b 100644
--- a/src/reporter.cc
+++ b/src/reporter.cc
@@ -13,6 +13,7 @@
// limitations under the License.
#include "benchmark/reporter.h"
+#include "minimal_leastsq.h"
#include <cstdlib>
#include <vector>
diff --git a/test/complexity_test.cc b/test/complexity_test.cc
index afa82ed..54a6cff 100644
--- a/test/complexity_test.cc
+++ b/test/complexity_test.cc
@@ -38,15 +38,6 @@
}
BENCHMARK(BM_Complexity_O_N) -> Range(1, 1<<10) -> Complexity(benchmark::O_N);
BENCHMARK(BM_Complexity_O_N) -> Range(1, 1<<10) -> Complexity(benchmark::O_Auto);
-
-static void BM_Complexity_O_M_plus_N(benchmark::State& state) {
- std::string s1(state.range_x(), '-');
- std::string s2(state.range_x(), '-');
- while (state.KeepRunning())
- benchmark::DoNotOptimize(s1.compare(s2));
-}
-BENCHMARK(BM_Complexity_O_M_plus_N)
- ->RangeMultiplier(2)->Range(1<<10, 1<<18) -> Complexity(benchmark::O_M_plus_N);
static void BM_Complexity_O_N_Squared(benchmark::State& state) {
std::string s1(state.range_x(), '-');
