summaryrefslogtreecommitdiffstatshomepage
path: root/3rdparty/benchmark/src
diff options
context:
space:
mode:
Diffstat (limited to '3rdparty/benchmark/src')
-rw-r--r--3rdparty/benchmark/src/CMakeLists.txt51
-rw-r--r--3rdparty/benchmark/src/arraysize.h34
-rw-r--r--3rdparty/benchmark/src/benchmark.cc919
-rw-r--r--3rdparty/benchmark/src/check.h60
-rw-r--r--3rdparty/benchmark/src/colorprint.cc116
-rw-r--r--3rdparty/benchmark/src/colorprint.h19
-rw-r--r--3rdparty/benchmark/src/commandlineflags.cc220
-rw-r--r--3rdparty/benchmark/src/commandlineflags.h76
-rw-r--r--3rdparty/benchmark/src/console_reporter.cc116
-rw-r--r--3rdparty/benchmark/src/csv_reporter.cc105
-rw-r--r--3rdparty/benchmark/src/cycleclock.h137
-rw-r--r--3rdparty/benchmark/src/internal_macros.h40
-rw-r--r--3rdparty/benchmark/src/json_reporter.cc159
-rw-r--r--3rdparty/benchmark/src/log.cc40
-rw-r--r--3rdparty/benchmark/src/log.h28
-rw-r--r--3rdparty/benchmark/src/mutex.h142
-rw-r--r--3rdparty/benchmark/src/re.h60
-rw-r--r--3rdparty/benchmark/src/re_posix.cc59
-rw-r--r--3rdparty/benchmark/src/re_std.cc44
-rw-r--r--3rdparty/benchmark/src/reporter.cc86
-rw-r--r--3rdparty/benchmark/src/sleep.cc50
-rw-r--r--3rdparty/benchmark/src/sleep.h17
-rw-r--r--3rdparty/benchmark/src/stat.h307
-rw-r--r--3rdparty/benchmark/src/string_util.cc169
-rw-r--r--3rdparty/benchmark/src/string_util.h44
-rw-r--r--3rdparty/benchmark/src/sysinfo.cc416
-rw-r--r--3rdparty/benchmark/src/sysinfo.h12
-rw-r--r--3rdparty/benchmark/src/walltime.cc263
-rw-r--r--3rdparty/benchmark/src/walltime.h17
29 files changed, 3806 insertions, 0 deletions
diff --git a/3rdparty/benchmark/src/CMakeLists.txt b/3rdparty/benchmark/src/CMakeLists.txt
new file mode 100644
index 00000000000..811d075575a
--- /dev/null
+++ b/3rdparty/benchmark/src/CMakeLists.txt
@@ -0,0 +1,51 @@
+# Allow the source files to find headers in src/
+include_directories(${PROJECT_SOURCE_DIR}/src)
+
+# Define the source files
+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")
+# Determine the correct regular expression engine to use
+if(HAVE_STD_REGEX)
+ set(RE_FILES "re_std.cc")
+elseif(HAVE_GNU_POSIX_REGEX)
+ set(RE_FILES "re_posix.cc")
+elseif(HAVE_POSIX_REGEX)
+ set(RE_FILES "re_posix.cc")
+else()
+ message(FATAL_ERROR "Failed to determine the source files for the regular expression backend")
+endif()
+
+add_library(benchmark ${SOURCE_FILES} ${RE_FILES})
+
+
+set_target_properties(benchmark PROPERTIES
+ OUTPUT_NAME "benchmark"
+ VERSION ${GENERIC_LIB_VERSION}
+ SOVERSION ${GENERIC_LIB_SOVERSION}
+)
+
+# Link threads.
+target_link_libraries(benchmark ${CMAKE_THREAD_LIBS_INIT})
+
+# We need extra libraries on Windows
+if(${CMAKE_SYSTEM_NAME} MATCHES "Windows")
+ target_link_libraries(benchmark Shlwapi)
+endif()
+
+# Expose public API
+target_include_directories(benchmark PUBLIC ${PROJECT_SOURCE_DIR}/include)
+
+# Install target (will install the library to specified CMAKE_INSTALL_PREFIX variable)
+install(
+ TARGETS benchmark
+ ARCHIVE DESTINATION lib
+ LIBRARY DESTINATION lib
+ RUNTIME DESTINATION bin
+ COMPONENT library)
+
+install(
+ DIRECTORY "${PROJECT_SOURCE_DIR}/include/benchmark"
+ DESTINATION include
+ FILES_MATCHING PATTERN "*.*h")
diff --git a/3rdparty/benchmark/src/arraysize.h b/3rdparty/benchmark/src/arraysize.h
new file mode 100644
index 00000000000..638a52a0ecb
--- /dev/null
+++ b/3rdparty/benchmark/src/arraysize.h
@@ -0,0 +1,34 @@
+#ifndef BENCHMARK_ARRAYSIZE_H_
+#define BENCHMARK_ARRAYSIZE_H_
+
+#include "internal_macros.h"
+
+namespace benchmark {
+namespace internal {
+// The arraysize(arr) macro returns the # of elements in an array arr.
+// The expression is a compile-time constant, and therefore can be
+// used in defining new arrays, for example. If you use arraysize on
+// a pointer by mistake, you will get a compile-time error.
+//
+
+
+// This template function declaration is used in defining arraysize.
+// Note that the function doesn't need an implementation, as we only
+// use its type.
+template <typename T, size_t N>
+char (&ArraySizeHelper(T (&array)[N]))[N];
+
+// That gcc wants both of these prototypes seems mysterious. VC, for
+// its part, can't decide which to use (another mystery). Matching of
+// template overloads: the final frontier.
+#ifndef COMPILER_MSVC
+template <typename T, size_t N>
+char (&ArraySizeHelper(const T (&array)[N]))[N];
+#endif
+
+#define arraysize(array) (sizeof(::benchmark::internal::ArraySizeHelper(array)))
+
+} // end namespace internal
+} // end namespace benchmark
+
+#endif // BENCHMARK_ARRAYSIZE_H_
diff --git a/3rdparty/benchmark/src/benchmark.cc b/3rdparty/benchmark/src/benchmark.cc
new file mode 100644
index 00000000000..269b7978023
--- /dev/null
+++ b/3rdparty/benchmark/src/benchmark.cc
@@ -0,0 +1,919 @@
+// Copyright 2015 Google Inc. 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.
+
+#include "benchmark/benchmark.h"
+#include "internal_macros.h"
+
+#ifndef BENCHMARK_OS_WINDOWS
+#include <sys/time.h>
+#include <sys/resource.h>
+#include <unistd.h>
+#endif
+
+#include <cstdlib>
+#include <cstring>
+#include <cstdio>
+#include <algorithm>
+#include <atomic>
+#include <condition_variable>
+#include <iostream>
+#include <memory>
+#include <thread>
+
+#include "check.h"
+#include "commandlineflags.h"
+#include "log.h"
+#include "mutex.h"
+#include "re.h"
+#include "stat.h"
+#include "string_util.h"
+#include "sysinfo.h"
+#include "walltime.h"
+
+DEFINE_bool(benchmark_list_tests, false,
+ "Print a list of benchmarks. This option overrides all other "
+ "options.");
+
+DEFINE_string(benchmark_filter, ".",
+ "A regular expression that specifies the set of benchmarks "
+ "to execute. If this flag is empty, no benchmarks are run. "
+ "If this flag is the string \"all\", all benchmarks linked "
+ "into the process are run.");
+
+DEFINE_double(benchmark_min_time, 0.5,
+ "Minimum number of seconds we should run benchmark before "
+ "results are considered significant. For cpu-time based "
+ "tests, this is the lower bound on the total cpu time "
+ "used by all threads that make up the test. For real-time "
+ "based tests, this is the lower bound on the elapsed time "
+ "of the benchmark execution, regardless of number of "
+ "threads.");
+
+DEFINE_int32(benchmark_repetitions, 1,
+ "The number of runs of each benchmark. If greater than 1, the "
+ "mean and standard deviation of the runs will be reported.");
+
+DEFINE_string(benchmark_format, "tabular",
+ "The format to use for console output. Valid values are "
+ "'tabular', 'json', or 'csv'.");
+
+DEFINE_bool(color_print, true, "Enables colorized logging.");
+
+DEFINE_int32(v, 0, "The level of verbose logging to output");
+
+
+namespace benchmark {
+
+namespace internal {
+
+void UseCharPointer(char const volatile*) {}
+
+// NOTE: This is a dummy "mutex" type used to denote the actual mutex
+// returned by GetBenchmarkLock(). This is only used to placate the thread
+// safety warnings by giving the return of GetBenchmarkLock() a name.
+struct CAPABILITY("mutex") BenchmarkLockType {};
+BenchmarkLockType BenchmarkLockVar;
+
+} // end namespace internal
+
+inline Mutex& RETURN_CAPABILITY(::benchmark::internal::BenchmarkLockVar)
+GetBenchmarkLock()
+{
+ static Mutex lock;
+ return lock;
+}
+
+namespace {
+
+bool IsZero(double n) {
+ return std::abs(n) < std::numeric_limits<double>::epsilon();
+}
+
+// For non-dense Range, intermediate values are powers of kRangeMultiplier.
+static const int kRangeMultiplier = 8;
+static const size_t kMaxIterations = 1000000000;
+
+bool running_benchmark = false;
+
+// Global variable so that a benchmark can cause a little extra printing
+std::string* GetReportLabel() {
+ static std::string label GUARDED_BY(GetBenchmarkLock());
+ return &label;
+}
+
+// TODO(ericwf): support MallocCounter.
+//static benchmark::MallocCounter *benchmark_mc;
+
+struct ThreadStats {
+ ThreadStats() : bytes_processed(0), items_processed(0) {}
+ int64_t bytes_processed;
+ int64_t items_processed;
+};
+
+// Timer management class
+class TimerManager {
+ public:
+ TimerManager(int num_threads, Notification* done)
+ : num_threads_(num_threads),
+ done_(done),
+ running_(false),
+ real_time_used_(0),
+ cpu_time_used_(0),
+ num_finalized_(0),
+ phase_number_(0),
+ entered_(0) {
+ }
+
+ // Called by each thread
+ void StartTimer() EXCLUDES(lock_) {
+ bool last_thread = false;
+ {
+ MutexLock ml(lock_);
+ last_thread = Barrier(ml);
+ if (last_thread) {
+ CHECK(!running_) << "Called StartTimer when timer is already running";
+ running_ = true;
+ start_real_time_ = walltime::Now();
+ start_cpu_time_ = MyCPUUsage() + ChildrenCPUUsage();
+ }
+ }
+ if (last_thread) {
+ phase_condition_.notify_all();
+ }
+ }
+
+ // Called by each thread
+ void StopTimer() EXCLUDES(lock_) {
+ bool last_thread = false;
+ {
+ MutexLock ml(lock_);
+ last_thread = Barrier(ml);
+ if (last_thread) {
+ CHECK(running_) << "Called StopTimer when timer is already stopped";
+ InternalStop();
+ }
+ }
+ if (last_thread) {
+ phase_condition_.notify_all();
+ }
+ }
+
+ // Called by each thread
+ void Finalize() EXCLUDES(lock_) {
+ MutexLock l(lock_);
+ num_finalized_++;
+ if (num_finalized_ == num_threads_) {
+ CHECK(!running_) <<
+ "The timer should be stopped before the timer is finalized";
+ done_->Notify();
+ }
+ }
+
+ // REQUIRES: timer is not running
+ double real_time_used() EXCLUDES(lock_) {
+ MutexLock l(lock_);
+ CHECK(!running_);
+ return real_time_used_;
+ }
+
+ // REQUIRES: timer is not running
+ double cpu_time_used() EXCLUDES(lock_) {
+ MutexLock l(lock_);
+ CHECK(!running_);
+ return cpu_time_used_;
+ }
+
+ private:
+ Mutex lock_;
+ Condition phase_condition_;
+ int num_threads_;
+ Notification* done_;
+
+ bool running_; // Is the timer running
+ double start_real_time_; // If running_
+ double start_cpu_time_; // If running_
+
+ // Accumulated time so far (does not contain current slice if running_)
+ double real_time_used_;
+ double cpu_time_used_;
+
+ // How many threads have called Finalize()
+ int num_finalized_;
+
+ // State for barrier management
+ int phase_number_;
+ int entered_; // Number of threads that have entered this barrier
+
+ void InternalStop() REQUIRES(lock_) {
+ CHECK(running_);
+ running_ = false;
+ real_time_used_ += walltime::Now() - start_real_time_;
+ cpu_time_used_ += ((MyCPUUsage() + ChildrenCPUUsage())
+ - start_cpu_time_);
+ }
+
+ // Enter the barrier and wait until all other threads have also
+ // entered the barrier. Returns iff this is the last thread to
+ // enter the barrier.
+ bool Barrier(MutexLock& ml) REQUIRES(lock_) {
+ CHECK_LT(entered_, num_threads_);
+ entered_++;
+ if (entered_ < num_threads_) {
+ // Wait for all threads to enter
+ int phase_number_cp = phase_number_;
+ auto cb = [this, phase_number_cp]() {
+ return this->phase_number_ > phase_number_cp;
+ };
+ phase_condition_.wait(ml.native_handle(), cb);
+ return false; // I was not the last one
+ } else {
+ // Last thread has reached the barrier
+ phase_number_++;
+ entered_ = 0;
+ return true;
+ }
+ }
+};
+
+// TimerManager for current run.
+static std::unique_ptr<TimerManager> timer_manager = nullptr;
+
+} // end namespace
+
+namespace internal {
+
+// Information kept per benchmark we may want to run
+struct Benchmark::Instance {
+ std::string name;
+ Benchmark* benchmark;
+ bool has_arg1;
+ int arg1;
+ bool has_arg2;
+ int arg2;
+ bool use_real_time;
+ double min_time;
+ int threads; // Number of concurrent threads to use
+ bool multithreaded; // Is benchmark multi-threaded?
+};
+
+// Class for managing registered benchmarks. Note that each registered
+// benchmark identifies a family of related benchmarks to run.
+class BenchmarkFamilies {
+ public:
+ static BenchmarkFamilies* GetInstance();
+
+ // Registers a benchmark family and returns the index assigned to it.
+ size_t AddBenchmark(std::unique_ptr<Benchmark> family);
+
+ // Extract the list of benchmark instances that match the specified
+ // regular expression.
+ bool FindBenchmarks(const std::string& re,
+ std::vector<Benchmark::Instance>* benchmarks);
+ private:
+ BenchmarkFamilies() {}
+
+ std::vector<std::unique_ptr<Benchmark>> families_;
+ Mutex mutex_;
+};
+
+
+class BenchmarkImp {
+public:
+ explicit BenchmarkImp(const char* name);
+ ~BenchmarkImp();
+
+ void Arg(int x);
+ void Range(int start, int limit);
+ void DenseRange(int start, int limit);
+ void ArgPair(int start, int limit);
+ void RangePair(int lo1, int hi1, int lo2, int hi2);
+ void MinTime(double n);
+ void UseRealTime();
+ void Threads(int t);
+ void ThreadRange(int min_threads, int max_threads);
+ void ThreadPerCpu();
+ void SetName(const char* name);
+
+ static void AddRange(std::vector<int>* dst, int lo, int hi, int mult);
+
+private:
+ friend class BenchmarkFamilies;
+
+ std::string name_;
+ int arg_count_;
+ std::vector< std::pair<int, int> > args_; // Args for all benchmark runs
+ double min_time_;
+ bool use_real_time_;
+ std::vector<int> thread_counts_;
+
+ BenchmarkImp& operator=(BenchmarkImp const&);
+};
+
+BenchmarkFamilies* BenchmarkFamilies::GetInstance() {
+ static BenchmarkFamilies instance;
+ return &instance;
+}
+
+
+size_t BenchmarkFamilies::AddBenchmark(std::unique_ptr<Benchmark> family) {
+ MutexLock l(mutex_);
+ size_t index = families_.size();
+ families_.push_back(std::move(family));
+ return index;
+}
+
+bool BenchmarkFamilies::FindBenchmarks(
+ const std::string& spec,
+ std::vector<Benchmark::Instance>* benchmarks) {
+ // Make regular expression out of command-line flag
+ std::string error_msg;
+ Regex re;
+ if (!re.Init(spec, &error_msg)) {
+ std::cerr << "Could not compile benchmark re: " << error_msg << std::endl;
+ return false;
+ }
+
+ // Special list of thread counts to use when none are specified
+ std::vector<int> one_thread;
+ one_thread.push_back(1);
+
+ MutexLock l(mutex_);
+ for (std::unique_ptr<Benchmark>& bench_family : families_) {
+ // Family was deleted or benchmark doesn't match
+ if (!bench_family) continue;
+ BenchmarkImp* family = bench_family->imp_;
+
+ if (family->arg_count_ == -1) {
+ family->arg_count_ = 0;
+ family->args_.emplace_back(-1, -1);
+ }
+ for (auto const& args : family->args_) {
+ const std::vector<int>* thread_counts =
+ (family->thread_counts_.empty()
+ ? &one_thread
+ : &family->thread_counts_);
+ for (int num_threads : *thread_counts) {
+
+ Benchmark::Instance instance;
+ instance.name = family->name_;
+ instance.benchmark = bench_family.get();
+ instance.has_arg1 = family->arg_count_ >= 1;
+ instance.arg1 = args.first;
+ instance.has_arg2 = family->arg_count_ == 2;
+ instance.arg2 = args.second;
+ instance.min_time = family->min_time_;
+ instance.use_real_time = family->use_real_time_;
+ instance.threads = num_threads;
+ instance.multithreaded = !(family->thread_counts_.empty());
+
+ // Add arguments to instance name
+ if (family->arg_count_ >= 1) {
+ AppendHumanReadable(instance.arg1, &instance.name);
+ }
+ if (family->arg_count_ >= 2) {
+ AppendHumanReadable(instance.arg2, &instance.name);
+ }
+ if (!IsZero(family->min_time_)) {
+ instance.name += StringPrintF("/min_time:%0.3f", family->min_time_);
+ }
+ if (family->use_real_time_) {
+ instance.name += "/real_time";
+ }
+
+ // Add the number of threads used to the name
+ if (!family->thread_counts_.empty()) {
+ instance.name += StringPrintF("/threads:%d", instance.threads);
+ }
+
+ if (re.Match(instance.name)) {
+ benchmarks->push_back(instance);
+ }
+ }
+ }
+ }
+ return true;
+}
+
+BenchmarkImp::BenchmarkImp(const char* name)
+ : name_(name), arg_count_(-1),
+ min_time_(0.0), use_real_time_(false) {
+}
+
+BenchmarkImp::~BenchmarkImp() {
+}
+
+void BenchmarkImp::Arg(int x) {
+ CHECK(arg_count_ == -1 || arg_count_ == 1);
+ arg_count_ = 1;
+ args_.emplace_back(x, -1);
+}
+
+void BenchmarkImp::Range(int start, int limit) {
+ CHECK(arg_count_ == -1 || arg_count_ == 1);
+ arg_count_ = 1;
+ std::vector<int> arglist;
+ AddRange(&arglist, start, limit, kRangeMultiplier);
+
+ for (int i : arglist) {
+ args_.emplace_back(i, -1);
+ }
+}
+
+void BenchmarkImp::DenseRange(int start, int limit) {
+ CHECK(arg_count_ == -1 || arg_count_ == 1);
+ arg_count_ = 1;
+ CHECK_GE(start, 0);
+ CHECK_LE(start, limit);
+ for (int arg = start; arg <= limit; arg++) {
+ args_.emplace_back(arg, -1);
+ }
+}
+
+void BenchmarkImp::ArgPair(int x, int y) {
+ CHECK(arg_count_ == -1 || arg_count_ == 2);
+ arg_count_ = 2;
+ args_.emplace_back(x, y);
+}
+
+void BenchmarkImp::RangePair(int lo1, int hi1, int lo2, int hi2) {
+ CHECK(arg_count_ == -1 || arg_count_ == 2);
+ arg_count_ = 2;
+ std::vector<int> arglist1, arglist2;
+ AddRange(&arglist1, lo1, hi1, kRangeMultiplier);
+ AddRange(&arglist2, lo2, hi2, kRangeMultiplier);
+
+ for (int i : arglist1) {
+ for (int j : arglist2) {
+ args_.emplace_back(i, j);
+ }
+ }
+}
+
+void BenchmarkImp::MinTime(double t) {
+ CHECK(t > 0.0);
+ min_time_ = t;
+}
+
+void BenchmarkImp::UseRealTime() {
+ use_real_time_ = true;
+}
+
+void BenchmarkImp::Threads(int t) {
+ CHECK_GT(t, 0);
+ thread_counts_.push_back(t);
+}
+
+void BenchmarkImp::ThreadRange(int min_threads, int max_threads) {
+ CHECK_GT(min_threads, 0);
+ CHECK_GE(max_threads, min_threads);
+
+ AddRange(&thread_counts_, min_threads, max_threads, 2);
+}
+
+void BenchmarkImp::ThreadPerCpu() {
+ static int num_cpus = NumCPUs();
+ thread_counts_.push_back(num_cpus);
+}
+
+void BenchmarkImp::SetName(const char* name) {
+ name_ = name;
+}
+
+void BenchmarkImp::AddRange(std::vector<int>* dst, int lo, int hi, int mult) {
+ CHECK_GE(lo, 0);
+ CHECK_GE(hi, lo);
+
+ // Add "lo"
+ dst->push_back(lo);
+
+ static const int kint32max = std::numeric_limits<int32_t>::max();
+
+ // Now space out the benchmarks in multiples of "mult"
+ for (int32_t i = 1; i < kint32max/mult; i *= mult) {
+ if (i >= hi) break;
+ if (i > lo) {
+ dst->push_back(i);
+ }
+ }
+ // Add "hi" (if different from "lo")
+ if (hi != lo) {
+ dst->push_back(hi);
+ }
+}
+
+Benchmark::Benchmark(const char* name)
+ : imp_(new BenchmarkImp(name))
+{
+}
+
+Benchmark::~Benchmark() {
+ delete imp_;
+}
+
+Benchmark::Benchmark(Benchmark const& other)
+ : imp_(new BenchmarkImp(*other.imp_))
+{
+}
+
+Benchmark* Benchmark::Arg(int x) {
+ imp_->Arg(x);
+ return this;
+}
+
+Benchmark* Benchmark::Range(int start, int limit) {
+ imp_->Range(start, limit);
+ return this;
+}
+
+Benchmark* Benchmark::DenseRange(int start, int limit) {
+ imp_->DenseRange(start, limit);
+ return this;
+}
+
+Benchmark* Benchmark::ArgPair(int x, int y) {
+ imp_->ArgPair(x, y);
+ return this;
+}
+
+Benchmark* Benchmark::RangePair(int lo1, int hi1, int lo2, int hi2) {
+ imp_->RangePair(lo1, hi1, lo2, hi2);
+ return this;
+}
+
+Benchmark* Benchmark::Apply(void (*custom_arguments)(Benchmark* benchmark)) {
+ custom_arguments(this);
+ return this;
+}
+
+Benchmark* Benchmark::MinTime(double t) {
+ imp_->MinTime(t);
+ return this;
+}
+
+Benchmark* Benchmark::UseRealTime() {
+ imp_->UseRealTime();
+ return this;
+}
+
+Benchmark* Benchmark::Threads(int t) {
+ imp_->Threads(t);
+ return this;
+}
+
+Benchmark* Benchmark::ThreadRange(int min_threads, int max_threads) {
+ imp_->ThreadRange(min_threads, max_threads);
+ return this;
+}
+
+Benchmark* Benchmark::ThreadPerCpu() {
+ imp_->ThreadPerCpu();
+ return this;
+}
+
+void Benchmark::SetName(const char* name) {
+ imp_->SetName(name);
+}
+
+void FunctionBenchmark::Run(State& st) {
+ func_(st);
+}
+
+} // end namespace internal
+
+namespace {
+
+
+// Execute one thread of benchmark b for the specified number of iterations.
+// Adds the stats collected for the thread into *total.
+void RunInThread(const benchmark::internal::Benchmark::Instance* b,
+ size_t iters, int thread_id,
+ ThreadStats* total) EXCLUDES(GetBenchmarkLock()) {
+ State st(iters, b->has_arg1, b->arg1, b->has_arg2, b->arg2, thread_id);
+ b->benchmark->Run(st);
+ CHECK(st.iterations() == st.max_iterations) <<
+ "Benchmark returned before State::KeepRunning() returned false!";
+ {
+ MutexLock l(GetBenchmarkLock());
+ total->bytes_processed += st.bytes_processed();
+ total->items_processed += st.items_processed();
+ }
+
+ timer_manager->Finalize();
+}
+
+void RunBenchmark(const benchmark::internal::Benchmark::Instance& b,
+ BenchmarkReporter* br) EXCLUDES(GetBenchmarkLock()) {
+ size_t iters = 1;
+
+ std::vector<BenchmarkReporter::Run> reports;
+
+ std::vector<std::thread> pool;
+ if (b.multithreaded)
+ pool.resize(b.threads);
+
+ for (int i = 0; i < FLAGS_benchmark_repetitions; i++) {
+ std::string mem;
+ for (;;) {
+ // Try benchmark
+ VLOG(2) << "Running " << b.name << " for " << iters << "\n";
+
+ {
+ MutexLock l(GetBenchmarkLock());
+ GetReportLabel()->clear();
+ }
+
+ Notification done;
+ timer_manager = std::unique_ptr<TimerManager>(new TimerManager(b.threads, &done));
+
+ ThreadStats total;
+ running_benchmark = true;
+ if (b.multithreaded) {
+ // If this is out first iteration of the while(true) loop then the
+ // threads haven't been started and can't be joined. Otherwise we need
+ // to join the thread before replacing them.
+ for (std::thread& thread : pool) {
+ if (thread.joinable())
+ thread.join();
+ }
+ for (std::size_t ti = 0; ti < pool.size(); ++ti) {
+ pool[ti] = std::thread(&RunInThread, &b, iters, ti, &total);
+ }
+ } else {
+ // Run directly in this thread
+ RunInThread(&b, iters, 0, &total);
+ }
+ done.WaitForNotification();
+ running_benchmark = false;
+
+ const double cpu_accumulated_time = timer_manager->cpu_time_used();
+ const double real_accumulated_time = timer_manager->real_time_used();
+ timer_manager.reset();
+
+ VLOG(2) << "Ran in " << cpu_accumulated_time << "/"
+ << real_accumulated_time << "\n";
+
+ // Base decisions off of real time if requested by this benchmark.
+ double seconds = cpu_accumulated_time;
+ if (b.use_real_time) {
+ seconds = real_accumulated_time;
+ }
+
+ std::string label;
+ {
+ MutexLock l(GetBenchmarkLock());
+ label = *GetReportLabel();
+ }
+
+ const double min_time = !IsZero(b.min_time) ? b.min_time
+ : FLAGS_benchmark_min_time;
+
+ // If this was the first run, was elapsed time or cpu time large enough?
+ // If this is not the first run, go with the current value of iter.
+ if ((i > 0) ||
+ (iters >= kMaxIterations) ||
+ (seconds >= min_time) ||
+ (real_accumulated_time >= 5*min_time)) {
+ double bytes_per_second = 0;
+ if (total.bytes_processed > 0 && seconds > 0.0) {
+ bytes_per_second = (total.bytes_processed / seconds);
+ }
+ double items_per_second = 0;
+ if (total.items_processed > 0 && seconds > 0.0) {
+ items_per_second = (total.items_processed / seconds);
+ }
+
+ // Create report about this benchmark run.
+ BenchmarkReporter::Run report;
+ report.benchmark_name = b.name;
+ report.report_label = label;
+ // Report the total iterations across all threads.
+ report.iterations = static_cast<int64_t>(iters) * b.threads;
+ report.real_accumulated_time = real_accumulated_time;
+ report.cpu_accumulated_time = cpu_accumulated_time;
+ report.bytes_per_second = bytes_per_second;
+ report.items_per_second = items_per_second;
+ reports.push_back(report);
+ break;
+ }
+
+ // See how much iterations should be increased by
+ // Note: Avoid division by zero with max(seconds, 1ns).
+ double multiplier = min_time * 1.4 / std::max(seconds, 1e-9);
+ // If our last run was at least 10% of FLAGS_benchmark_min_time then we
+ // use the multiplier directly. Otherwise we use at most 10 times
+ // expansion.
+ // NOTE: When the last run was at least 10% of the min time the max
+ // expansion should be 14x.
+ bool is_significant = (seconds / min_time) > 0.1;
+ multiplier = is_significant ? multiplier : std::min(10.0, multiplier);
+ if (multiplier <= 1.0) multiplier = 2.0;
+ double next_iters = std::max(multiplier * iters, iters + 1.0);
+ if (next_iters > kMaxIterations) {
+ next_iters = kMaxIterations;
+ }
+ VLOG(3) << "Next iters: " << next_iters << ", " << multiplier << "\n";
+ iters = static_cast<int>(next_iters + 0.5);
+ }
+ }
+ br->ReportRuns(reports);
+ if (b.multithreaded) {
+ for (std::thread& thread : pool)
+ thread.join();
+ }
+}
+
+} // namespace
+
+State::State(size_t max_iters, bool has_x, int x, bool has_y, int y,
+ int thread_i)
+ : started_(false), total_iterations_(0),
+ has_range_x_(has_x), range_x_(x),
+ has_range_y_(has_y), range_y_(y),
+ bytes_processed_(0), items_processed_(0),
+ thread_index(thread_i),
+ max_iterations(max_iters)
+{
+ CHECK(max_iterations != 0) << "At least one iteration must be run";
+}
+
+void State::PauseTiming() {
+ // Add in time accumulated so far
+ CHECK(running_benchmark);
+ timer_manager->StopTimer();
+}
+
+void State::ResumeTiming() {
+ CHECK(running_benchmark);
+ timer_manager->StartTimer();
+}
+
+void State::SetLabel(const char* label) {
+ CHECK(running_benchmark);
+ MutexLock l(GetBenchmarkLock());
+ *GetReportLabel() = label;
+}
+
+namespace internal {
+namespace {
+
+void PrintBenchmarkList() {
+ std::vector<Benchmark::Instance> benchmarks;
+ auto families = BenchmarkFamilies::GetInstance();
+ if (!families->FindBenchmarks(".", &benchmarks)) return;
+
+ for (const internal::Benchmark::Instance& benchmark : benchmarks) {
+ std::cout << benchmark.name << "\n";
+ }
+}
+
+void RunMatchingBenchmarks(const std::string& spec,
+ BenchmarkReporter* reporter) {
+ CHECK(reporter != nullptr);
+ if (spec.empty()) return;
+
+ std::vector<Benchmark::Instance> benchmarks;
+ auto families = BenchmarkFamilies::GetInstance();
+ if (!families->FindBenchmarks(spec, &benchmarks)) return;
+
+ // Determine the width of the name field using a minimum width of 10.
+ size_t name_field_width = 10;
+ for (const Benchmark::Instance& benchmark : benchmarks) {
+ name_field_width =
+ std::max<size_t>(name_field_width, benchmark.name.size());
+ }
+ if (FLAGS_benchmark_repetitions > 1)
+ name_field_width += std::strlen("_stddev");
+
+ // Print header here
+ BenchmarkReporter::Context context;
+ context.num_cpus = NumCPUs();
+ context.mhz_per_cpu = CyclesPerSecond() / 1000000.0f;
+
+ context.cpu_scaling_enabled = CpuScalingEnabled();
+ context.name_field_width = name_field_width;
+
+ if (reporter->ReportContext(context)) {
+ for (const auto& benchmark : benchmarks) {
+ RunBenchmark(benchmark, reporter);
+ }
+ }
+}
+
+std::unique_ptr<BenchmarkReporter> GetDefaultReporter() {
+ typedef std::unique_ptr<BenchmarkReporter> PtrType;
+ if (FLAGS_benchmark_format == "tabular") {
+ return PtrType(new ConsoleReporter);
+ } else if (FLAGS_benchmark_format == "json") {
+ return PtrType(new JSONReporter);
+ } else if (FLAGS_benchmark_format == "csv") {
+ return PtrType(new CSVReporter);
+ } else {
+ std::cerr << "Unexpected format: '" << FLAGS_benchmark_format << "'\n";
+ std::exit(1);
+ }
+}
+
+} // end namespace
+} // end namespace internal
+
+void RunSpecifiedBenchmarks() {
+ RunSpecifiedBenchmarks(nullptr);
+}
+
+void RunSpecifiedBenchmarks(BenchmarkReporter* reporter) {
+ if (FLAGS_benchmark_list_tests) {
+ internal::PrintBenchmarkList();
+ return;
+ }
+ std::string spec = FLAGS_benchmark_filter;
+ if (spec.empty() || spec == "all")
+ spec = "."; // Regexp that matches all benchmarks
+
+ std::unique_ptr<BenchmarkReporter> default_reporter;
+ if (!reporter) {
+ default_reporter = internal::GetDefaultReporter();
+ reporter = default_reporter.get();
+ }
+ internal::RunMatchingBenchmarks(spec, reporter);
+ reporter->Finalize();
+}
+
+namespace internal {
+
+void PrintUsageAndExit() {
+ fprintf(stdout,
+ "benchmark"
+ " [--benchmark_list_tests={true|false}]\n"
+ " [--benchmark_filter=<regex>]\n"
+ " [--benchmark_min_time=<min_time>]\n"
+ " [--benchmark_repetitions=<num_repetitions>]\n"
+ " [--benchmark_format=<tabular|json|csv>]\n"
+ " [--color_print={true|false}]\n"
+ " [--v=<verbosity>]\n");
+ exit(0);
+}
+
+void ParseCommandLineFlags(int* argc, char** argv) {
+ using namespace benchmark;
+ for (int i = 1; i < *argc; ++i) {
+ if (
+ ParseBoolFlag(argv[i], "benchmark_list_tests",
+ &FLAGS_benchmark_list_tests) ||
+ ParseStringFlag(argv[i], "benchmark_filter",
+ &FLAGS_benchmark_filter) ||
+ ParseDoubleFlag(argv[i], "benchmark_min_time",
+ &FLAGS_benchmark_min_time) ||
+ ParseInt32Flag(argv[i], "benchmark_repetitions",
+ &FLAGS_benchmark_repetitions) ||
+ ParseStringFlag(argv[i], "benchmark_format",
+ &FLAGS_benchmark_format) ||
+ ParseBoolFlag(argv[i], "color_print",
+ &FLAGS_color_print) ||
+ ParseInt32Flag(argv[i], "v", &FLAGS_v)) {
+ for (int j = i; j != *argc; ++j) argv[j] = argv[j + 1];
+
+ --(*argc);
+ --i;
+ } else if (IsFlag(argv[i], "help")) {
+ PrintUsageAndExit();
+ }
+ }
+ if (FLAGS_benchmark_format != "tabular" &&
+ FLAGS_benchmark_format != "json" &&
+ FLAGS_benchmark_format != "csv") {
+ PrintUsageAndExit();
+ }
+}
+
+Benchmark* RegisterBenchmarkInternal(Benchmark* bench) {
+ std::unique_ptr<Benchmark> bench_ptr(bench);
+ BenchmarkFamilies* families = BenchmarkFamilies::GetInstance();
+ families->AddBenchmark(std::move(bench_ptr));
+ return bench;
+}
+
+} // end namespace internal
+
+void Initialize(int* argc, char** argv) {
+ internal::ParseCommandLineFlags(argc, argv);
+ internal::SetLogLevel(FLAGS_v);
+ // TODO remove this. It prints some output the first time it is called.
+ // We don't want to have this ouput printed during benchmarking.
+ MyCPUUsage();
+ // The first call to walltime::Now initialized it. Call it once to
+ // prevent the initialization from happening in a benchmark.
+ walltime::Now();
+}
+
+} // end namespace benchmark
diff --git a/3rdparty/benchmark/src/check.h b/3rdparty/benchmark/src/check.h
new file mode 100644
index 00000000000..12933f347fa
--- /dev/null
+++ b/3rdparty/benchmark/src/check.h
@@ -0,0 +1,60 @@
+#ifndef CHECK_H_
+#define CHECK_H_
+
+#include <cstdlib>
+#include <ostream>
+
+#include "internal_macros.h"
+#include "log.h"
+
+namespace benchmark {
+namespace internal {
+
+// CheckHandler is the class constructed by failing CHECK macros. CheckHandler
+// will log information about the failures and abort when it is destructed.
+class CheckHandler {
+public:
+ CheckHandler(const char* check, const char* file, const char* func, int line)
+ : log_(GetErrorLogInstance())
+ {
+ log_ << file << ":" << line << ": " << func << ": Check `"
+ << check << "' failed. ";
+ }
+
+ std::ostream& GetLog() {
+ return log_;
+ }
+
+ BENCHMARK_NORETURN ~CheckHandler() {
+ log_ << std::endl;
+ std::abort();
+ }
+
+ CheckHandler & operator=(const CheckHandler&) = delete;
+ CheckHandler(const CheckHandler&) = delete;
+ CheckHandler() = delete;
+private:
+ std::ostream& log_;
+};
+
+} // end namespace internal
+} // end namespace benchmark
+
+// The CHECK macro returns a std::ostream object that can have extra information
+// written to it.
+#ifndef NDEBUG
+# define CHECK(b) (b ? ::benchmark::internal::GetNullLogInstance() \
+ : ::benchmark::internal::CheckHandler( \
+ #b, __FILE__, __func__, __LINE__).GetLog())
+#else
+# define CHECK(b) ::benchmark::internal::GetNullLogInstance()
+#endif
+
+#define CHECK_EQ(a, b) CHECK((a) == (b))
+#define CHECK_NE(a, b) CHECK((a) != (b))
+#define CHECK_GE(a, b) CHECK((a) >= (b))
+#define CHECK_LE(a, b) CHECK((a) <= (b))
+#define CHECK_GT(a, b) CHECK((a) > (b))
+#define CHECK_LT(a, b) CHECK((a) < (b))
+
+#endif // CHECK_H_
diff --git a/3rdparty/benchmark/src/colorprint.cc b/3rdparty/benchmark/src/colorprint.cc
new file mode 100644
index 00000000000..81f917b2676
--- /dev/null
+++ b/3rdparty/benchmark/src/colorprint.cc
@@ -0,0 +1,116 @@
+// Copyright 2015 Google Inc. 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.
+
+#include "colorprint.h"
+
+#include <cstdarg>
+#include <cstdio>
+
+#include "commandlineflags.h"
+#include "internal_macros.h"
+
+#ifdef BENCHMARK_OS_WINDOWS
+#include <Windows.h>
+#endif
+
+DECLARE_bool(color_print);
+
+namespace benchmark {
+namespace {
+#ifdef BENCHMARK_OS_WINDOWS
+typedef WORD PlatformColorCode;
+#else
+typedef const char* PlatformColorCode;
+#endif
+
+PlatformColorCode GetPlatformColorCode(LogColor color) {
+#ifdef BENCHMARK_OS_WINDOWS
+ switch (color) {
+ case COLOR_RED:
+ return FOREGROUND_RED;
+ case COLOR_GREEN:
+ return FOREGROUND_GREEN;
+ case COLOR_YELLOW:
+ return FOREGROUND_RED | FOREGROUND_GREEN;
+ case COLOR_BLUE:
+ return FOREGROUND_BLUE;
+ case COLOR_MAGENTA:
+ return FOREGROUND_BLUE | FOREGROUND_RED;
+ case COLOR_CYAN:
+ return FOREGROUND_BLUE | FOREGROUND_GREEN;
+ case COLOR_WHITE: // fall through to default
+ default:
+ return 0;
+ }
+#else
+ switch (color) {
+ case COLOR_RED:
+ return "1";
+ case COLOR_GREEN:
+ return "2";
+ case COLOR_YELLOW:
+ return "3";
+ case COLOR_BLUE:
+ return "4";
+ case COLOR_MAGENTA:
+ return "5";
+ case COLOR_CYAN:
+ return "6";
+ case COLOR_WHITE:
+ return "7";
+ default:
+ return nullptr;
+ };
+#endif
+}
+} // end namespace
+
+void ColorPrintf(LogColor color, const char* fmt, ...) {
+ va_list args;
+ va_start(args, fmt);
+
+ if (!FLAGS_color_print) {
+ vprintf(fmt, args);
+ va_end(args);
+ return;
+ }
+
+#ifdef BENCHMARK_OS_WINDOWS
+ const HANDLE stdout_handle = GetStdHandle(STD_OUTPUT_HANDLE);
+
+ // Gets the current text color.
+ CONSOLE_SCREEN_BUFFER_INFO buffer_info;
+ GetConsoleScreenBufferInfo(stdout_handle, &buffer_info);
+ const WORD old_color_attrs = buffer_info.wAttributes;
+
+ // We need to flush the stream buffers into the console before each
+ // SetConsoleTextAttribute call lest it affect the text that is already
+ // printed but has not yet reached the console.
+ fflush(stdout);
+ SetConsoleTextAttribute(stdout_handle,
+ GetPlatformColorCode(color) | FOREGROUND_INTENSITY);
+ vprintf(fmt, args);
+
+ fflush(stdout);
+ // Restores the text color.
+ SetConsoleTextAttribute(stdout_handle, old_color_attrs);
+#else
+ const char* color_code = GetPlatformColorCode(color);
+ if (color_code) fprintf(stdout, "\033[0;3%sm", color_code);
+ vprintf(fmt, args);
+ printf("\033[m"); // Resets the terminal to default.
+#endif
+ va_end(args);
+}
+} // end namespace benchmark
diff --git a/3rdparty/benchmark/src/colorprint.h b/3rdparty/benchmark/src/colorprint.h
new file mode 100644
index 00000000000..54d1f664b3b
--- /dev/null
+++ b/3rdparty/benchmark/src/colorprint.h
@@ -0,0 +1,19 @@
+#ifndef BENCHMARK_COLORPRINT_H_
+#define BENCHMARK_COLORPRINT_H_
+
+namespace benchmark {
+enum LogColor {
+ COLOR_DEFAULT,
+ COLOR_RED,
+ COLOR_GREEN,
+ COLOR_YELLOW,
+ COLOR_BLUE,
+ COLOR_MAGENTA,
+ COLOR_CYAN,
+ COLOR_WHITE
+};
+
+void ColorPrintf(LogColor color, const char* fmt, ...);
+} // end namespace benchmark
+
+#endif // BENCHMARK_COLORPRINT_H_
diff --git a/3rdparty/benchmark/src/commandlineflags.cc b/3rdparty/benchmark/src/commandlineflags.cc
new file mode 100644
index 00000000000..3e9a37a71d6
--- /dev/null
+++ b/3rdparty/benchmark/src/commandlineflags.cc
@@ -0,0 +1,220 @@
+// Copyright 2015 Google Inc. 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.
+
+#include "commandlineflags.h"
+
+#include <cstdlib>
+#include <cstring>
+#include <iostream>
+#include <limits>
+
+namespace benchmark {
+// Parses 'str' for a 32-bit signed integer. If successful, writes
+// the result to *value and returns true; otherwise leaves *value
+// unchanged and returns false.
+bool ParseInt32(const std::string& src_text, const char* str, int32_t* value) {
+ // Parses the environment variable as a decimal integer.
+ char* end = nullptr;
+ const long long_value = strtol(str, &end, 10); // NOLINT
+
+ // Has strtol() consumed all characters in the string?
+ if (*end != '\0') {
+ // No - an invalid character was encountered.
+ std::cerr << src_text << " is expected to be a 32-bit integer, "
+ << "but actually has value \"" << str << "\".\n";
+ return false;
+ }
+
+ // Is the parsed value in the range of an Int32?
+ const int32_t result = static_cast<int32_t>(long_value);
+ if (long_value == std::numeric_limits<long>::max() ||
+ long_value == std::numeric_limits<long>::min() ||
+ // The parsed value overflows as a long. (strtol() returns
+ // LONG_MAX or LONG_MIN when the input overflows.)
+ result != long_value
+ // The parsed value overflows as an Int32.
+ ) {
+ std::cerr << src_text << " is expected to be a 32-bit integer, "
+ << "but actually has value \"" << str << "\", "
+ << "which overflows.\n";
+ return false;
+ }
+
+ *value = result;
+ return true;
+}
+
+// Parses 'str' for a double. If successful, writes the result to *value and
+// returns true; otherwise leaves *value unchanged and returns false.
+bool ParseDouble(const std::string& src_text, const char* str, double* value) {
+ // Parses the environment variable as a decimal integer.
+ char* end = nullptr;
+ const double double_value = strtod(str, &end); // NOLINT
+
+ // Has strtol() consumed all characters in the string?
+ if (*end != '\0') {
+ // No - an invalid character was encountered.
+ std::cerr << src_text << " is expected to be a double, "
+ << "but actually has value \"" << str << "\".\n";
+ return false;
+ }
+
+ *value = double_value;
+ return true;
+}
+
+inline const char* GetEnv(const char* name) {
+#if defined(__BORLANDC__) || defined(__SunOS_5_8) || defined(__SunOS_5_9)
+ // Environment variables which we programmatically clear will be set to the
+ // empty string rather than unset (nullptr). Handle that case.
+ const char* const env = getenv(name);
+ return (env != nullptr && env[0] != '\0') ? env : nullptr;
+#else
+ return getenv(name);
+#endif
+}
+
+// Returns the name of the environment variable corresponding to the
+// given flag. For example, FlagToEnvVar("foo") will return
+// "BENCHMARK_FOO" in the open-source version.
+static std::string FlagToEnvVar(const char* flag) {
+ const std::string flag_str(flag);
+
+ std::string env_var;
+ for (size_t i = 0; i != flag_str.length(); ++i)
+ env_var += static_cast<char>(::toupper(flag_str.c_str()[i]));
+
+ return "BENCHMARK_" + env_var;
+}
+
+// Reads and returns the Boolean environment variable corresponding to
+// the given flag; if it's not set, returns default_value.
+//
+// The value is considered true iff it's not "0".
+bool BoolFromEnv(const char* flag, bool default_value) {
+ const std::string env_var = FlagToEnvVar(flag);
+ const char* const string_value = GetEnv(env_var.c_str());
+ return string_value == nullptr ? default_value : strcmp(string_value, "0") != 0;
+}
+
+// Reads and returns a 32-bit integer stored in the environment
+// variable corresponding to the given flag; if it isn't set or
+// doesn't represent a valid 32-bit integer, returns default_value.
+int32_t Int32FromEnv(const char* flag, int32_t default_value) {
+ const std::string env_var = FlagToEnvVar(flag);
+ const char* const string_value = GetEnv(env_var.c_str());
+ if (string_value == nullptr) {
+ // The environment variable is not set.
+ return default_value;
+ }
+
+ int32_t result = default_value;
+ if (!ParseInt32(std::string("Environment variable ") + env_var, string_value,
+ &result)) {
+ std::cout << "The default value " << default_value << " is used.\n";
+ return default_value;
+ }
+
+ return result;
+}
+
+// Reads and returns the string environment variable corresponding to
+// the given flag; if it's not set, returns default_value.
+const char* StringFromEnv(const char* flag, const char* default_value) {
+ const std::string env_var = FlagToEnvVar(flag);
+ const char* const value = GetEnv(env_var.c_str());
+ return value == nullptr ? default_value : value;
+}
+
+// Parses a string as a command line flag. The string should have
+// the format "--flag=value". When def_optional is true, the "=value"
+// part can be omitted.
+//
+// Returns the value of the flag, or nullptr if the parsing failed.
+const char* ParseFlagValue(const char* str, const char* flag,
+ bool def_optional) {
+ // str and flag must not be nullptr.
+ if (str == nullptr || flag == nullptr) return nullptr;
+
+ // The flag must start with "--".
+ const std::string flag_str = std::string("--") + std::string(flag);
+ const size_t flag_len = flag_str.length();
+ if (strncmp(str, flag_str.c_str(), flag_len) != 0) return nullptr;
+
+ // Skips the flag name.
+ const char* flag_end = str + flag_len;
+
+ // When def_optional is true, it's OK to not have a "=value" part.
+ if (def_optional && (flag_end[0] == '\0')) return flag_end;
+
+ // If def_optional is true and there are more characters after the
+ // flag name, or if def_optional is false, there must be a '=' after
+ // the flag name.
+ if (flag_end[0] != '=') return nullptr;
+
+ // Returns the string after "=".
+ return flag_end + 1;
+}
+
+bool ParseBoolFlag(const char* str, const char* flag, bool* value) {
+ // Gets the value of the flag as a string.
+ const char* const value_str = ParseFlagValue(str, flag, true);
+
+ // Aborts if the parsing failed.
+ if (value_str == nullptr) return false;
+
+ // Converts the string value to a bool.
+ *value = !(*value_str == '0' || *value_str == 'f' || *value_str == 'F');
+ return true;
+}
+
+bool ParseInt32Flag(const char* str, const char* flag, int32_t* value) {
+ // Gets the value of the flag as a string.
+ const char* const value_str = ParseFlagValue(str, flag, false);
+
+ // Aborts if the parsing failed.
+ if (value_str == nullptr) return false;
+
+ // Sets *value to the value of the flag.
+ return ParseInt32(std::string("The value of flag --") + flag, value_str,
+ value);
+}
+
+bool ParseDoubleFlag(const char* str, const char* flag, double* value) {
+ // Gets the value of the flag as a string.
+ const char* const value_str = ParseFlagValue(str, flag, false);
+
+ // Aborts if the parsing failed.
+ if (value_str == nullptr) return false;
+
+ // Sets *value to the value of the flag.
+ return ParseDouble(std::string("The value of flag --") + flag, value_str,
+ value);
+}
+
+bool ParseStringFlag(const char* str, const char* flag, std::string* value) {
+ // Gets the value of the flag as a string.
+ const char* const value_str = ParseFlagValue(str, flag, false);
+
+ // Aborts if the parsing failed.
+ if (value_str == nullptr) return false;
+
+ *value = value_str;
+ return true;
+}
+
+bool IsFlag(const char* str, const char* flag) {
+ return (ParseFlagValue(str, flag, true) != nullptr);
+}
+} // end namespace benchmark
diff --git a/3rdparty/benchmark/src/commandlineflags.h b/3rdparty/benchmark/src/commandlineflags.h
new file mode 100644
index 00000000000..34b9c6f30e9
--- /dev/null
+++ b/3rdparty/benchmark/src/commandlineflags.h
@@ -0,0 +1,76 @@
+#ifndef BENCHMARK_COMMANDLINEFLAGS_H_
+#define BENCHMARK_COMMANDLINEFLAGS_H_
+
+#include <cstdint>
+#include <string>
+
+// Macro for referencing flags.
+#define FLAG(name) FLAGS_##name
+
+// Macros for declaring flags.
+#define DECLARE_bool(name) extern bool FLAG(name)
+#define DECLARE_int32(name) extern int32_t FLAG(name)
+#define DECLARE_int64(name) extern int64_t FLAG(name)
+#define DECLARE_double(name) extern double FLAG(name)
+#define DECLARE_string(name) extern std::string FLAG(name)
+
+// Macros for defining flags.
+#define DEFINE_bool(name, default_val, doc) bool FLAG(name) = (default_val)
+#define DEFINE_int32(name, default_val, doc) int32_t FLAG(name) = (default_val)
+#define DEFINE_int64(name, default_val, doc) int64_t FLAG(name) = (default_val)
+#define DEFINE_double(name, default_val, doc) double FLAG(name) = (default_val)
+#define DEFINE_string(name, default_val, doc) \
+ std::string FLAG(name) = (default_val)
+
+namespace benchmark {
+// Parses 'str' for a 32-bit signed integer. If successful, writes the result
+// to *value and returns true; otherwise leaves *value unchanged and returns
+// false.
+bool ParseInt32(const std::string& src_text, const char* str, int32_t* value);
+
+// Parses a bool/Int32/string from the environment variable
+// corresponding to the given Google Test flag.
+bool BoolFromEnv(const char* flag, bool default_val);
+int32_t Int32FromEnv(const char* flag, int32_t default_val);
+double DoubleFromEnv(const char* flag, double default_val);
+const char* StringFromEnv(const char* flag, const char* default_val);
+
+// Parses a string for a bool flag, in the form of either
+// "--flag=value" or "--flag".
+//
+// In the former case, the value is taken as true as long as it does
+// not start with '0', 'f', or 'F'.
+//
+// In the latter case, the value is taken as true.
+//
+// On success, stores the value of the flag in *value, and returns
+// true. On failure, returns false without changing *value.
+bool ParseBoolFlag(const char* str, const char* flag, bool* value);
+
+// Parses a string for an Int32 flag, in the form of
+// "--flag=value".
+//
+// On success, stores the value of the flag in *value, and returns
+// true. On failure, returns false without changing *value.
+bool ParseInt32Flag(const char* str, const char* flag, int32_t* value);
+
+// Parses a string for a Double flag, in the form of
+// "--flag=value".
+//
+// On success, stores the value of the flag in *value, and returns
+// true. On failure, returns false without changing *value.
+bool ParseDoubleFlag(const char* str, const char* flag, double* value);
+
+// Parses a string for a string flag, in the form of
+// "--flag=value".
+//
+// On success, stores the value of the flag in *value, and returns
+// true. On failure, returns false without changing *value.
+bool ParseStringFlag(const char* str, const char* flag, std::string* value);
+
+// Returns true if the string matches the flag.
+bool IsFlag(const char* str, const char* flag);
+
+} // end namespace benchmark
+
+#endif // BENCHMARK_COMMANDLINEFLAGS_H_
diff --git a/3rdparty/benchmark/src/console_reporter.cc b/3rdparty/benchmark/src/console_reporter.cc
new file mode 100644
index 00000000000..bee3c8576c0
--- /dev/null
+++ b/3rdparty/benchmark/src/console_reporter.cc
@@ -0,0 +1,116 @@
+// Copyright 2015 Google Inc. 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.
+
+#include "benchmark/reporter.h"
+
+#include <cstdint>
+#include <cstdio>
+#include <iostream>
+#include <string>
+#include <vector>
+
+#include "check.h"
+#include "colorprint.h"
+#include "string_util.h"
+#include "walltime.h"
+
+namespace benchmark {
+
+bool ConsoleReporter::ReportContext(const Context& context) {
+ name_field_width_ = context.name_field_width;
+
+ std::cerr << "Run on (" << context.num_cpus << " X " << context.mhz_per_cpu
+ << " MHz CPU " << ((context.num_cpus > 1) ? "s" : "") << ")\n";
+
+ std::cerr << LocalDateTimeString() << "\n";
+
+ if (context.cpu_scaling_enabled) {
+ std::cerr << "***WARNING*** CPU scaling is enabled, the benchmark "
+ "real time measurements may be noisy and will incure extra "
+ "overhead.\n";
+ }
+
+#ifndef NDEBUG
+ std::cerr << "***WARNING*** Library was built as DEBUG. Timings may be "
+ "affected.\n";
+#endif
+
+ int output_width = fprintf(stdout, "%-*s %10s %10s %10s\n",
+ static_cast<int>(name_field_width_), "Benchmark",
+ "Time(ns)", "CPU(ns)", "Iterations");
+ std::cout << std::string(output_width - 1, '-') << "\n";
+
+ return true;
+}
+
+void ConsoleReporter::ReportRuns(const std::vector<Run>& reports) {
+ if (reports.empty()) {
+ return;
+ }
+
+ for (Run const& run : reports) {
+ CHECK_EQ(reports[0].benchmark_name, run.benchmark_name);
+ PrintRunData(run);
+ }
+
+ if (reports.size() < 2) {
+ // We don't report aggregated data if there was a single run.
+ return;
+ }
+
+ Run mean_data;
+ Run stddev_data;
+ BenchmarkReporter::ComputeStats(reports, &mean_data, &stddev_data);
+
+ // Output using PrintRun.
+ PrintRunData(mean_data);
+ PrintRunData(stddev_data);
+}
+
+void ConsoleReporter::PrintRunData(const Run& result) {
+ // Format bytes per second
+ std::string rate;
+ if (result.bytes_per_second > 0) {
+ rate = StrCat(" ", HumanReadableNumber(result.bytes_per_second), "B/s");
+ }
+
+ // Format items per second
+ std::string items;
+ if (result.items_per_second > 0) {
+ items = StrCat(" ", HumanReadableNumber(result.items_per_second),
+ " items/s");
+ }
+
+ double const multiplier = 1e9; // nano second multiplier
+ ColorPrintf(COLOR_GREEN, "%-*s ",
+ name_field_width_, result.benchmark_name.c_str());
+ if (result.iterations == 0) {
+ ColorPrintf(COLOR_YELLOW, "%10.0f %10.0f ",
+ result.real_accumulated_time * multiplier,
+ result.cpu_accumulated_time * multiplier);
+ } else {
+ ColorPrintf(COLOR_YELLOW, "%10.0f %10.0f ",
+ (result.real_accumulated_time * multiplier) /
+ (static_cast<double>(result.iterations)),
+ (result.cpu_accumulated_time * multiplier) /
+ (static_cast<double>(result.iterations)));
+ }
+ ColorPrintf(COLOR_CYAN, "%10lld", result.iterations);
+ ColorPrintf(COLOR_DEFAULT, "%*s %*s %s\n",
+ 13, rate.c_str(),
+ 18, items.c_str(),
+ result.report_label.c_str());
+}
+
+} // end namespace benchmark
diff --git a/3rdparty/benchmark/src/csv_reporter.cc b/3rdparty/benchmark/src/csv_reporter.cc
new file mode 100644
index 00000000000..a83694338bd
--- /dev/null
+++ b/3rdparty/benchmark/src/csv_reporter.cc
@@ -0,0 +1,105 @@
+// Copyright 2015 Google Inc. 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.
+
+#include "benchmark/reporter.h"
+
+#include <cstdint>
+#include <iostream>
+#include <string>
+#include <vector>
+
+#include "string_util.h"
+#include "walltime.h"
+
+// File format reference: http://edoceo.com/utilitas/csv-file-format.
+
+namespace benchmark {
+
+bool CSVReporter::ReportContext(const Context& context) {
+ std::cerr << "Run on (" << context.num_cpus << " X " << context.mhz_per_cpu
+ << " MHz CPU " << ((context.num_cpus > 1) ? "s" : "") << ")\n";
+
+ std::cerr << LocalDateTimeString() << "\n";
+
+ if (context.cpu_scaling_enabled) {
+ std::cerr << "***WARNING*** CPU scaling is enabled, the benchmark "
+ "real time measurements may be noisy and will incure extra "
+ "overhead.\n";
+ }
+
+#ifndef NDEBUG
+ std::cerr << "***WARNING*** Library was built as DEBUG. Timings may be "
+ "affected.\n";
+#endif
+ std::cout << "name,iterations,real_time,cpu_time,bytes_per_second,"
+ "items_per_second,label\n";
+ return true;
+}
+
+void CSVReporter::ReportRuns(std::vector<Run> const& reports) {
+ if (reports.empty()) {
+ return;
+ }
+
+ std::vector<Run> reports_cp = reports;
+ if (reports.size() >= 2) {
+ Run mean_data;
+ Run stddev_data;
+ BenchmarkReporter::ComputeStats(reports, &mean_data, &stddev_data);
+ reports_cp.push_back(mean_data);
+ reports_cp.push_back(stddev_data);
+ }
+ for (auto it = reports_cp.begin(); it != reports_cp.end(); ++it) {
+ PrintRunData(*it);
+ }
+}
+
+void CSVReporter::PrintRunData(Run const& run) {
+ double const multiplier = 1e9; // nano second multiplier
+ double cpu_time = run.cpu_accumulated_time * multiplier;
+ double real_time = run.real_accumulated_time * multiplier;
+ if (run.iterations != 0) {
+ real_time = real_time / static_cast<double>(run.iterations);
+ cpu_time = cpu_time / static_cast<double>(run.iterations);
+ }
+
+ // Field with embedded double-quote characters must be doubled and the field
+ // delimited with double-quotes.
+ std::string name = run.benchmark_name;
+ ReplaceAll(&name, "\"", "\"\"");
+ std::cout << "\"" << name << "\",";
+
+ std::cout << run.iterations << ",";
+ std::cout << real_time << ",";
+ std::cout << cpu_time << ",";
+
+ if (run.bytes_per_second > 0.0) {
+ std::cout << run.bytes_per_second;
+ }
+ std::cout << ",";
+ if (run.items_per_second > 0.0) {
+ std::cout << run.items_per_second;
+ }
+ std::cout << ",";
+ if (!run.report_label.empty()) {
+ // Field with embedded double-quote characters must be doubled and the field
+ // delimited with double-quotes.
+ std::string label = run.report_label;
+ ReplaceAll(&label, "\"", "\"\"");
+ std::cout << "\"" << label << "\"";
+ }
+ std::cout << '\n';
+}
+
+} // end namespace benchmark
diff --git a/3rdparty/benchmark/src/cycleclock.h b/3rdparty/benchmark/src/cycleclock.h
new file mode 100644
index 00000000000..42541dafc88
--- /dev/null
+++ b/3rdparty/benchmark/src/cycleclock.h
@@ -0,0 +1,137 @@
+// ----------------------------------------------------------------------
+// CycleClock
+// A CycleClock tells you the current time in Cycles. The "time"
+// is actually time since power-on. This is like time() but doesn't
+// involve a system call and is much more precise.
+//
+// NOTE: Not all cpu/platform/kernel combinations guarantee that this
+// clock increments at a constant rate or is synchronized across all logical
+// cpus in a system.
+//
+// If you need the above guarantees, please consider using a different
+// API. There are efforts to provide an interface which provides a millisecond
+// granularity and implemented as a memory read. A memory read is generally
+// cheaper than the CycleClock for many architectures.
+//
+// Also, in some out of order CPU implementations, the CycleClock is not
+// serializing. So if you're trying to count at cycles granularity, your
+// data might be inaccurate due to out of order instruction execution.
+// ----------------------------------------------------------------------
+
+#ifndef BENCHMARK_CYCLECLOCK_H_
+#define BENCHMARK_CYCLECLOCK_H_
+
+#include <cstdint>
+
+#include "benchmark/macros.h"
+#include "internal_macros.h"
+
+#if defined(BENCHMARK_OS_MACOSX)
+#include <mach/mach_time.h>
+#endif
+// For MSVC, we want to use '_asm rdtsc' when possible (since it works
+// with even ancient MSVC compilers), and when not possible the
+// __rdtsc intrinsic, declared in <intrin.h>. Unfortunately, in some
+// environments, <windows.h> and <intrin.h> have conflicting
+// declarations of some other intrinsics, breaking compilation.
+// Therefore, we simply declare __rdtsc ourselves. See also
+// http://connect.microsoft.com/VisualStudio/feedback/details/262047
+#if defined(COMPILER_MSVC) && !defined(_M_IX86)
+extern "C" uint64_t __rdtsc();
+#pragma intrinsic(__rdtsc)
+#endif
+
+#ifndef BENCHMARK_OS_WINDOWS
+#include <sys/time.h>
+#endif
+
+namespace benchmark {
+// NOTE: only i386 and x86_64 have been well tested.
+// PPC, sparc, alpha, and ia64 are based on
+// http://peter.kuscsik.com/wordpress/?p=14
+// with modifications by m3b. See also
+// https://setisvn.ssl.berkeley.edu/svn/lib/fftw-3.0.1/kernel/cycle.h
+namespace cycleclock {
+// This should return the number of cycles since power-on. Thread-safe.
+inline BENCHMARK_ALWAYS_INLINE int64_t Now() {
+#if defined(BENCHMARK_OS_MACOSX)
+ // this goes at the top because we need ALL Macs, regardless of
+ // architecture, to return the number of "mach time units" that
+ // have passed since startup. See sysinfo.cc where
+ // InitializeSystemInfo() sets the supposed cpu clock frequency of
+ // macs to the number of mach time units per second, not actual
+ // CPU clock frequency (which can change in the face of CPU
+ // frequency scaling). Also note that when the Mac sleeps, this
+ // counter pauses; it does not continue counting, nor does it
+ // reset to zero.
+ return mach_absolute_time();
+#elif defined(__i386__)
+ int64_t ret;
+ __asm__ volatile("rdtsc" : "=A"(ret));
+ return ret;
+#elif defined(__x86_64__) || defined(__amd64__)
+ uint64_t low, high;
+ __asm__ volatile("rdtsc" : "=a"(low), "=d"(high));
+ return (high << 32) | low;
+#elif defined(__powerpc__) || defined(__ppc__)
+ // This returns a time-base, which is not always precisely a cycle-count.
+ int64_t tbl, tbu0, tbu1;
+ asm("mftbu %0" : "=r"(tbu0));
+ asm("mftb %0" : "=r"(tbl));
+ asm("mftbu %0" : "=r"(tbu1));
+ tbl &= -static_cast<int64>(tbu0 == tbu1);
+ // high 32 bits in tbu1; low 32 bits in tbl (tbu0 is garbage)
+ return (tbu1 << 32) | tbl;
+#elif defined(__sparc__)
+ int64_t tick;
+ asm(".byte 0x83, 0x41, 0x00, 0x00");
+ asm("mov %%g1, %0" : "=r"(tick));
+ return tick;
+#elif defined(__ia64__)
+ int64_t itc;
+ asm("mov %0 = ar.itc" : "=r"(itc));
+ return itc;
+#elif defined(COMPILER_MSVC) && defined(_M_IX86)
+ // Older MSVC compilers (like 7.x) don't seem to support the
+ // __rdtsc intrinsic properly, so I prefer to use _asm instead
+ // when I know it will work. Otherwise, I'll use __rdtsc and hope
+ // the code is being compiled with a non-ancient compiler.
+ _asm rdtsc
+#elif defined(COMPILER_MSVC)
+ return __rdtsc();
+#elif defined(__ARM_ARCH)
+#if (__ARM_ARCH >= 6) // V6 is the earliest arch that has a standard cyclecount
+ uint32_t pmccntr;
+ uint32_t pmuseren;
+ uint32_t pmcntenset;
+ // Read the user mode perf monitor counter access permissions.
+ asm("mrc p15, 0, %0, c9, c14, 0" : "=r"(pmuseren));
+ if (pmuseren & 1) { // Allows reading perfmon counters for user mode code.
+ asm("mrc p15, 0, %0, c9, c12, 1" : "=r"(pmcntenset));
+ if (pmcntenset & 0x80000000ul) { // Is it counting?
+ asm("mrc p15, 0, %0, c9, c13, 0" : "=r"(pmccntr));
+ // The counter is set up to count every 64th cycle
+ return static_cast<int64_t>(pmccntr) * 64; // Should optimize to << 6
+ }
+ }
+#endif
+ struct timeval tv;
+ gettimeofday(&tv, nullptr);
+ return static_cast<int64_t>(tv.tv_sec) * 1000000 + tv.tv_usec;
+#elif defined(__mips__)
+ // mips apparently only allows rdtsc for superusers, so we fall
+ // back to gettimeofday. It's possible clock_gettime would be better.
+ struct timeval tv;
+ gettimeofday(&tv, nullptr);
+ return static_cast<int64_t>(tv.tv_sec) * 1000000 + tv.tv_usec;
+#else
+// The soft failover to a generic implementation is automatic only for ARM.
+// For other platforms the developer is expected to make an attempt to create
+// a fast implementation and use generic version if nothing better is available.
+#error You need to define CycleTimer for your OS and CPU
+#endif
+}
+} // end namespace cycleclock
+} // end namespace benchmark
+
+#endif // BENCHMARK_CYCLECLOCK_H_
diff --git a/3rdparty/benchmark/src/internal_macros.h b/3rdparty/benchmark/src/internal_macros.h
new file mode 100644
index 00000000000..1080ac9435a
--- /dev/null
+++ b/3rdparty/benchmark/src/internal_macros.h
@@ -0,0 +1,40 @@
+#ifndef BENCHMARK_INTERNAL_MACROS_H_
+#define BENCHMARK_INTERNAL_MACROS_H_
+
+#include "benchmark/macros.h"
+
+#ifndef __has_feature
+# define __has_feature(x) 0
+#endif
+
+#if __has_feature(cxx_attributes)
+# define BENCHMARK_NORETURN [[noreturn]]
+#elif defined(__GNUC__)
+# define BENCHMARK_NORETURN __attribute__((noreturn))
+#else
+# define BENCHMARK_NORETURN
+#endif
+
+#if defined(__CYGWIN__)
+# define BENCHMARK_OS_CYGWIN 1
+#elif defined(_WIN32)
+# define BENCHMARK_OS_WINDOWS 1
+#elif defined(__APPLE__)
+// TODO(ericwf) This doesn't actually check that it is a Mac OSX system. Just
+// that it is an apple system.
+# define BENCHMARK_OS_MACOSX 1
+#elif defined(__FreeBSD__)
+# define BENCHMARK_OS_FREEBSD 1
+#elif defined(__linux__)
+# define BENCHMARK_OS_LINUX 1
+#endif
+
+#if defined(__clang__)
+# define COMPILER_CLANG
+#elif defined(_MSC_VER)
+# define COMPILER_MSVC
+#elif defined(__GNUC__)
+# define COMPILER_GCC
+#endif
+
+#endif // BENCHMARK_INTERNAL_MACROS_H_
diff --git a/3rdparty/benchmark/src/json_reporter.cc b/3rdparty/benchmark/src/json_reporter.cc
new file mode 100644
index 00000000000..def50ac49cf
--- /dev/null
+++ b/3rdparty/benchmark/src/json_reporter.cc
@@ -0,0 +1,159 @@
+// Copyright 2015 Google Inc. 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.
+
+#include "benchmark/reporter.h"
+
+#include <cstdint>
+#include <iostream>
+#include <string>
+#include <vector>
+
+#include "string_util.h"
+#include "walltime.h"
+
+namespace benchmark {
+
+namespace {
+
+std::string FormatKV(std::string const& key, std::string const& value) {
+ return StringPrintF("\"%s\": \"%s\"", key.c_str(), value.c_str());
+}
+
+std::string FormatKV(std::string const& key, const char* value) {
+ return StringPrintF("\"%s\": \"%s\"", key.c_str(), value);
+}
+
+std::string FormatKV(std::string const& key, bool value) {
+ return StringPrintF("\"%s\": %s", key.c_str(), value ? "true" : "false");
+}
+
+std::string FormatKV(std::string const& key, int64_t value) {
+ std::stringstream ss;
+ ss << '"' << key << "\": " << value;
+ return ss.str();
+}
+
+int64_t RoundDouble(double v) {
+ return static_cast<int64_t>(v + 0.5);
+}
+
+} // end namespace
+
+bool JSONReporter::ReportContext(const Context& context) {
+ std::ostream& out = std::cout;
+
+ out << "{\n";
+ std::string inner_indent(2, ' ');
+
+ // Open context block and print context information.
+ out << inner_indent << "\"context\": {\n";
+ std::string indent(4, ' ');
+
+ std::string walltime_value = LocalDateTimeString();
+ out << indent << FormatKV("date", walltime_value) << ",\n";
+
+ out << indent
+ << FormatKV("num_cpus", static_cast<int64_t>(context.num_cpus))
+ << ",\n";
+ out << indent
+ << FormatKV("mhz_per_cpu", RoundDouble(context.mhz_per_cpu))
+ << ",\n";
+ out << indent
+ << FormatKV("cpu_scaling_enabled", context.cpu_scaling_enabled)
+ << ",\n";
+
+#if defined(NDEBUG)
+ const char build_type[] = "release";
+#else
+ const char build_type[] = "debug";
+#endif
+ out << indent << FormatKV("library_build_type", build_type) << "\n";
+ // Close context block and open the list of benchmarks.
+ out << inner_indent << "},\n";
+ out << inner_indent << "\"benchmarks\": [\n";
+ return true;
+}
+
+void JSONReporter::ReportRuns(std::vector<Run> const& reports) {
+ if (reports.empty()) {
+ return;
+ }
+ std::string indent(4, ' ');
+ std::ostream& out = std::cout;
+ if (!first_report_) {
+ out << ",\n";
+ }
+ first_report_ = false;
+ std::vector<Run> reports_cp = reports;
+ if (reports.size() >= 2) {
+ Run mean_data;
+ Run stddev_data;
+ BenchmarkReporter::ComputeStats(reports, &mean_data, &stddev_data);
+ reports_cp.push_back(mean_data);
+ reports_cp.push_back(stddev_data);
+ }
+ for (auto it = reports_cp.begin(); it != reports_cp.end(); ++it) {
+ out << indent << "{\n";
+ PrintRunData(*it);
+ out << indent << '}';
+ auto it_cp = it;
+ if (++it_cp != reports_cp.end()) {
+ out << ",\n";
+ }
+ }
+}
+
+void JSONReporter::Finalize() {
+ // Close the list of benchmarks and the top level object.
+ std::cout << "\n ]\n}\n";
+}
+
+void JSONReporter::PrintRunData(Run const& run) {
+ double const multiplier = 1e9; // nano second multiplier
+ double cpu_time = run.cpu_accumulated_time * multiplier;
+ double real_time = run.real_accumulated_time * multiplier;
+ if (run.iterations != 0) {
+ real_time = real_time / static_cast<double>(run.iterations);
+ cpu_time = cpu_time / static_cast<double>(run.iterations);
+ }
+
+ std::string indent(6, ' ');
+ std::ostream& out = std::cout;
+ out << indent
+ << FormatKV("name", run.benchmark_name)
+ << ",\n";
+ out << indent
+ << FormatKV("iterations", run.iterations)
+ << ",\n";
+ out << indent
+ << FormatKV("real_time", RoundDouble(real_time))
+ << ",\n";
+ out << indent
+ << FormatKV("cpu_time", RoundDouble(cpu_time));
+ if (run.bytes_per_second > 0.0) {
+ out << ",\n" << indent
+ << FormatKV("bytes_per_second", RoundDouble(run.bytes_per_second));
+ }
+ if (run.items_per_second > 0.0) {
+ out << ",\n" << indent
+ << FormatKV("items_per_second", RoundDouble(run.items_per_second));
+ }
+ if (!run.report_label.empty()) {
+ out << ",\n" << indent
+ << FormatKV("label", run.report_label);
+ }
+ out << '\n';
+}
+
+} // end namespace benchmark
diff --git a/3rdparty/benchmark/src/log.cc b/3rdparty/benchmark/src/log.cc
new file mode 100644
index 00000000000..b660309d324
--- /dev/null
+++ b/3rdparty/benchmark/src/log.cc
@@ -0,0 +1,40 @@
+#include "log.h"
+
+#include <iostream>
+
+namespace benchmark {
+namespace internal {
+
+int& LoggingLevelImp() {
+ static int level = 0;
+ return level;
+}
+
+void SetLogLevel(int value) {
+ LoggingLevelImp() = value;
+}
+
+int GetLogLevel() {
+ return LoggingLevelImp();
+}
+
+class NullLogBuffer : public std::streambuf
+{
+public:
+ int overflow(int c) {
+ return c;
+ }
+};
+
+std::ostream& GetNullLogInstance() {
+ static NullLogBuffer log_buff;
+ static std::ostream null_log(&log_buff);
+ return null_log;
+}
+
+std::ostream& GetErrorLogInstance() {
+ return std::clog;
+}
+
+} // end namespace internal
+} // end namespace benchmark \ No newline at end of file
diff --git a/3rdparty/benchmark/src/log.h b/3rdparty/benchmark/src/log.h
new file mode 100644
index 00000000000..3777810e1c9
--- /dev/null
+++ b/3rdparty/benchmark/src/log.h
@@ -0,0 +1,28 @@
+#ifndef BENCHMARK_LOG_H_
+#define BENCHMARK_LOG_H_
+
+#include <ostream>
+
+namespace benchmark {
+namespace internal {
+
+int GetLogLevel();
+void SetLogLevel(int level);
+
+std::ostream& GetNullLogInstance();
+std::ostream& GetErrorLogInstance();
+
+inline std::ostream& GetLogInstanceForLevel(int level) {
+ if (level <= GetLogLevel()) {
+ return GetErrorLogInstance();
+ }
+ return GetNullLogInstance();
+}
+
+} // end namespace internal
+} // end namespace benchmark
+
+#define VLOG(x) (::benchmark::internal::GetLogInstanceForLevel(x) \
+ << "-- LOG(" << x << "): ")
+
+#endif \ No newline at end of file
diff --git a/3rdparty/benchmark/src/mutex.h b/3rdparty/benchmark/src/mutex.h
new file mode 100644
index 00000000000..f37ec35b3a4
--- /dev/null
+++ b/3rdparty/benchmark/src/mutex.h
@@ -0,0 +1,142 @@
+#ifndef BENCHMARK_MUTEX_H_
+#define BENCHMARK_MUTEX_H_
+
+#include <mutex>
+#include <condition_variable>
+
+// Enable thread safety attributes only with clang.
+// The attributes can be safely erased when compiling with other compilers.
+#if defined(HAVE_THREAD_SAFETY_ATTRIBUTES)
+#define THREAD_ANNOTATION_ATTRIBUTE__(x) __attribute__((x))
+#else
+#define THREAD_ANNOTATION_ATTRIBUTE__(x) // no-op
+#endif
+
+#define CAPABILITY(x) \
+ THREAD_ANNOTATION_ATTRIBUTE__(capability(x))
+
+#define SCOPED_CAPABILITY \
+ THREAD_ANNOTATION_ATTRIBUTE__(scoped_lockable)
+
+#define GUARDED_BY(x) \
+ THREAD_ANNOTATION_ATTRIBUTE__(guarded_by(x))
+
+#define PT_GUARDED_BY(x) \
+ THREAD_ANNOTATION_ATTRIBUTE__(pt_guarded_by(x))
+
+#define ACQUIRED_BEFORE(...) \
+ THREAD_ANNOTATION_ATTRIBUTE__(acquired_before(__VA_ARGS__))
+
+#define ACQUIRED_AFTER(...) \
+ THREAD_ANNOTATION_ATTRIBUTE__(acquired_after(__VA_ARGS__))
+
+#define REQUIRES(...) \
+ THREAD_ANNOTATION_ATTRIBUTE__(requires_capability(__VA_ARGS__))
+
+#define REQUIRES_SHARED(...) \
+ THREAD_ANNOTATION_ATTRIBUTE__(requires_shared_capability(__VA_ARGS__))
+
+#define ACQUIRE(...) \
+ THREAD_ANNOTATION_ATTRIBUTE__(acquire_capability(__VA_ARGS__))
+
+#define ACQUIRE_SHARED(...) \
+ THREAD_ANNOTATION_ATTRIBUTE__(acquire_shared_capability(__VA_ARGS__))
+
+#define RELEASE(...) \
+ THREAD_ANNOTATION_ATTRIBUTE__(release_capability(__VA_ARGS__))
+
+#define RELEASE_SHARED(...) \
+ THREAD_ANNOTATION_ATTRIBUTE__(release_shared_capability(__VA_ARGS__))
+
+#define TRY_ACQUIRE(...) \
+ THREAD_ANNOTATION_ATTRIBUTE__(try_acquire_capability(__VA_ARGS__))
+
+#define TRY_ACQUIRE_SHARED(...) \
+ THREAD_ANNOTATION_ATTRIBUTE__(try_acquire_shared_capability(__VA_ARGS__))
+
+#define EXCLUDES(...) \
+ THREAD_ANNOTATION_ATTRIBUTE__(locks_excluded(__VA_ARGS__))
+
+#define ASSERT_CAPABILITY(x) \
+ THREAD_ANNOTATION_ATTRIBUTE__(assert_capability(x))
+
+#define ASSERT_SHARED_CAPABILITY(x) \
+ THREAD_ANNOTATION_ATTRIBUTE__(assert_shared_capability(x))
+
+#define RETURN_CAPABILITY(x) \
+ THREAD_ANNOTATION_ATTRIBUTE__(lock_returned(x))
+
+#define NO_THREAD_SAFETY_ANALYSIS \
+ THREAD_ANNOTATION_ATTRIBUTE__(no_thread_safety_analysis)
+
+
+namespace benchmark {
+
+typedef std::condition_variable Condition;
+
+// NOTE: Wrappers for std::mutex and std::unique_lock are provided so that
+// we can annotate them with thread safety attributes and use the
+// -Wthread-safety warning with clang. The standard library types cannot be
+// used directly because they do not provided the required annotations.
+class CAPABILITY("mutex") Mutex
+{
+public:
+ Mutex() {}
+
+ void lock() ACQUIRE() { mut_.lock(); }
+ void unlock() RELEASE() { mut_.unlock(); }
+ std::mutex& native_handle() {
+ return mut_;
+ }
+private:
+ std::mutex mut_;
+};
+
+
+class SCOPED_CAPABILITY MutexLock
+{
+ typedef std::unique_lock<std::mutex> MutexLockImp;
+public:
+ MutexLock(Mutex& m) ACQUIRE(m) : ml_(m.native_handle())
+ { }
+ ~MutexLock() RELEASE() {}
+ MutexLockImp& native_handle() { return ml_; }
+private:
+ MutexLockImp ml_;
+};
+
+
+class Notification
+{
+public:
+ Notification() : notified_yet_(false) { }
+
+ void WaitForNotification() const EXCLUDES(mutex_) {
+ MutexLock m_lock(mutex_);
+ auto notified_fn = [this]() REQUIRES(mutex_) {
+ return this->HasBeenNotified();
+ };
+ cv_.wait(m_lock.native_handle(), notified_fn);
+ }
+
+ void Notify() EXCLUDES(mutex_) {
+ {
+ MutexLock lock(mutex_);
+ notified_yet_ = 1;
+ }
+ cv_.notify_all();
+ }
+
+private:
+ bool HasBeenNotified() const REQUIRES(mutex_) {
+ return notified_yet_;
+ }
+
+ mutable Mutex mutex_;
+ mutable std::condition_variable cv_;
+ bool notified_yet_ GUARDED_BY(mutex_);
+};
+
+} // end namespace benchmark
+
+#endif // BENCHMARK_MUTEX_H_
diff --git a/3rdparty/benchmark/src/re.h b/3rdparty/benchmark/src/re.h
new file mode 100644
index 00000000000..af57a39cffb
--- /dev/null
+++ b/3rdparty/benchmark/src/re.h
@@ -0,0 +1,60 @@
+// Copyright 2015 Google Inc. 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.
+
+#ifndef BENCHMARK_RE_H_
+#define BENCHMARK_RE_H_
+
+#if defined(HAVE_STD_REGEX)
+#include <regex>
+#elif defined(HAVE_GNU_POSIX_REGEX)
+#include <gnuregex.h>
+#elif defined(HAVE_POSIX_REGEX)
+#include <regex.h>
+#else
+#error No regular expression backend was found!
+#endif
+#include <string>
+
+namespace benchmark {
+
+// A wrapper around the POSIX regular expression API that provides automatic
+// cleanup
+class Regex {
+ public:
+ Regex();
+ ~Regex();
+
+ // Compile a regular expression matcher from spec. Returns true on success.
+ //
+ // On failure (and if error is not nullptr), error is populated with a human
+ // readable error message if an error occurs.
+ bool Init(const std::string& spec, std::string* error);
+
+ // Returns whether str matches the compiled regular expression.
+ bool Match(const std::string& str);
+ private:
+ bool init_;
+ // Underlying regular expression object
+#if defined(HAVE_STD_REGEX)
+ std::regex re_;
+#elif defined(HAVE_POSIX_REGEX) || defined(HAVE_GNU_POSIX_REGEX)
+ regex_t re_;
+#else
+# error No regular expression backend implementation available
+#endif
+};
+
+} // end namespace benchmark
+
+#endif // BENCHMARK_RE_H_
diff --git a/3rdparty/benchmark/src/re_posix.cc b/3rdparty/benchmark/src/re_posix.cc
new file mode 100644
index 00000000000..95b086ffd6d
--- /dev/null
+++ b/3rdparty/benchmark/src/re_posix.cc
@@ -0,0 +1,59 @@
+// Copyright 2015 Google Inc. 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.
+
+#include "check.h"
+#include "re.h"
+
+namespace benchmark {
+
+Regex::Regex() : init_(false) { }
+
+bool Regex::Init(const std::string& spec, std::string* error) {
+ int ec = regcomp(&re_, spec.c_str(), REG_EXTENDED | REG_NOSUB);
+ if (ec != 0) {
+ if (error) {
+ size_t needed = regerror(ec, &re_, nullptr, 0);
+ char* errbuf = new char[needed];
+ regerror(ec, &re_, errbuf, needed);
+
+ // regerror returns the number of bytes necessary to null terminate
+ // the string, so we move that when assigning to error.
+ CHECK_NE(needed, 0);
+ error->assign(errbuf, needed - 1);
+
+ delete[] errbuf;
+ }
+
+ return false;
+ }
+
+ init_ = true;
+ return true;
+}
+
+Regex::~Regex() {
+ if (init_) {
+ regfree(&re_);
+ }
+}
+
+bool Regex::Match(const std::string& str) {
+ if (!init_) {
+ return false;
+ }
+
+ return regexec(&re_, str.c_str(), 0, nullptr, 0) == 0;
+}
+
+} // end namespace benchmark
diff --git a/3rdparty/benchmark/src/re_std.cc b/3rdparty/benchmark/src/re_std.cc
new file mode 100644
index 00000000000..cfd7a218ab4
--- /dev/null
+++ b/3rdparty/benchmark/src/re_std.cc
@@ -0,0 +1,44 @@
+// Copyright 2015 Google Inc. 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.
+
+#include "re.h"
+
+namespace benchmark {
+
+Regex::Regex() : init_(false) { }
+
+bool Regex::Init(const std::string& spec, std::string* error) {
+ try {
+ re_ = std::regex(spec, std::regex_constants::extended);
+
+ init_ = true;
+ } catch (const std::regex_error& e) {
+ if (error) {
+ *error = e.what();
+ }
+ }
+ return init_;
+}
+
+Regex::~Regex() { }
+
+bool Regex::Match(const std::string& str) {
+ if (!init_) {
+ return false;
+ }
+
+ return std::regex_search(str, re_);
+}
+
+} // end namespace benchmark
diff --git a/3rdparty/benchmark/src/reporter.cc b/3rdparty/benchmark/src/reporter.cc
new file mode 100644
index 00000000000..4b47e3d556c
--- /dev/null
+++ b/3rdparty/benchmark/src/reporter.cc
@@ -0,0 +1,86 @@
+// Copyright 2015 Google Inc. 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.
+
+#include "benchmark/reporter.h"
+
+#include <cstdlib>
+#include <vector>
+
+#include "check.h"
+#include "stat.h"
+
+namespace benchmark {
+
+void BenchmarkReporter::ComputeStats(
+ const std::vector<Run>& reports,
+ Run* mean_data, Run* stddev_data) {
+ CHECK(reports.size() >= 2) << "Cannot compute stats for less than 2 reports";
+ // Accumulators.
+ Stat1_d real_accumulated_time_stat;
+ Stat1_d cpu_accumulated_time_stat;
+ Stat1_d bytes_per_second_stat;
+ Stat1_d items_per_second_stat;
+ // All repetitions should be run with the same number of iterations so we
+ // can take this information from the first benchmark.
+ int64_t const run_iterations = reports.front().iterations;
+
+ // Populate the accumulators.
+ for (Run const& run : reports) {
+ CHECK_EQ(reports[0].benchmark_name, run.benchmark_name);
+ CHECK_EQ(run_iterations, run.iterations);
+ real_accumulated_time_stat +=
+ Stat1_d(run.real_accumulated_time/run.iterations, run.iterations);
+ cpu_accumulated_time_stat +=
+ Stat1_d(run.cpu_accumulated_time/run.iterations, run.iterations);
+ items_per_second_stat += Stat1_d(run.items_per_second, run.iterations);
+ bytes_per_second_stat += Stat1_d(run.bytes_per_second, run.iterations);
+ }
+
+ // Get the data from the accumulator to BenchmarkReporter::Run's.
+ mean_data->benchmark_name = reports[0].benchmark_name + "_mean";
+ mean_data->iterations = run_iterations;
+ mean_data->real_accumulated_time = real_accumulated_time_stat.Mean() *
+ run_iterations;
+ mean_data->cpu_accumulated_time = cpu_accumulated_time_stat.Mean() *
+ run_iterations;
+ mean_data->bytes_per_second = bytes_per_second_stat.Mean();
+ mean_data->items_per_second = items_per_second_stat.Mean();
+
+ // Only add label to mean/stddev if it is same for all runs
+ mean_data->report_label = reports[0].report_label;
+ for (std::size_t i = 1; i < reports.size(); i++) {
+ if (reports[i].report_label != reports[0].report_label) {
+ mean_data->report_label = "";
+ break;
+ }
+ }
+
+ stddev_data->benchmark_name = reports[0].benchmark_name + "_stddev";
+ stddev_data->report_label = mean_data->report_label;
+ stddev_data->iterations = 0;
+ stddev_data->real_accumulated_time =
+ real_accumulated_time_stat.StdDev();
+ stddev_data->cpu_accumulated_time =
+ cpu_accumulated_time_stat.StdDev();
+ stddev_data->bytes_per_second = bytes_per_second_stat.StdDev();
+ stddev_data->items_per_second = items_per_second_stat.StdDev();
+}
+
+void BenchmarkReporter::Finalize() {
+}
+
+BenchmarkReporter::~BenchmarkReporter() {
+}
+
+} // end namespace benchmark
diff --git a/3rdparty/benchmark/src/sleep.cc b/3rdparty/benchmark/src/sleep.cc
new file mode 100644
index 00000000000..918abc485dc
--- /dev/null
+++ b/3rdparty/benchmark/src/sleep.cc
@@ -0,0 +1,50 @@
+// Copyright 2015 Google Inc. 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.
+
+#include "sleep.h"
+
+#include <cerrno>
+#include <ctime>
+
+#include "internal_macros.h"
+
+#ifdef BENCHMARK_OS_WINDOWS
+#include <Windows.h>
+#endif
+
+namespace benchmark {
+#ifdef BENCHMARK_OS_WINDOWS
+// Window's Sleep takes milliseconds argument.
+void SleepForMilliseconds(int milliseconds) { Sleep(milliseconds); }
+void SleepForSeconds(double seconds) {
+ SleepForMilliseconds(static_cast<int>(kNumMillisPerSecond * seconds));
+}
+#else // BENCHMARK_OS_WINDOWS
+void SleepForMicroseconds(int microseconds) {
+ struct timespec sleep_time;
+ sleep_time.tv_sec = microseconds / kNumMicrosPerSecond;
+ sleep_time.tv_nsec = (microseconds % kNumMicrosPerSecond) * kNumNanosPerMicro;
+ while (nanosleep(&sleep_time, &sleep_time) != 0 && errno == EINTR)
+ ; // Ignore signals and wait for the full interval to elapse.
+}
+
+void SleepForMilliseconds(int milliseconds) {
+ SleepForMicroseconds(static_cast<int>(milliseconds) * kNumMicrosPerMilli);
+}
+
+void SleepForSeconds(double seconds) {
+ SleepForMicroseconds(static_cast<int>(seconds * kNumMicrosPerSecond));
+}
+#endif // BENCHMARK_OS_WINDOWS
+} // end namespace benchmark
diff --git a/3rdparty/benchmark/src/sleep.h b/3rdparty/benchmark/src/sleep.h
new file mode 100644
index 00000000000..f1e515ca4f3
--- /dev/null
+++ b/3rdparty/benchmark/src/sleep.h
@@ -0,0 +1,17 @@
+#ifndef BENCHMARK_SLEEP_H_
+#define BENCHMARK_SLEEP_H_
+
+#include <cstdint>
+
+namespace benchmark {
+const int64_t kNumMillisPerSecond = 1000LL;
+const int64_t kNumMicrosPerMilli = 1000LL;
+const int64_t kNumMicrosPerSecond = kNumMillisPerSecond * 1000LL;
+const int64_t kNumNanosPerMicro = 1000LL;
+const int64_t kNumNanosPerSecond = kNumNanosPerMicro * kNumMicrosPerSecond;
+
+void SleepForMilliseconds(int milliseconds);
+void SleepForSeconds(double seconds);
+} // end namespace benchmark
+
+#endif // BENCHMARK_SLEEP_H_
diff --git a/3rdparty/benchmark/src/stat.h b/3rdparty/benchmark/src/stat.h
new file mode 100644
index 00000000000..c4ecfe8e044
--- /dev/null
+++ b/3rdparty/benchmark/src/stat.h
@@ -0,0 +1,307 @@
+#ifndef BENCHMARK_STAT_H_
+#define BENCHMARK_STAT_H_
+
+#include <cmath>
+#include <limits>
+#include <ostream>
+#include <type_traits>
+
+
+namespace benchmark {
+
+template <typename VType, typename NumType>
+class Stat1;
+
+template <typename VType, typename NumType>
+class Stat1MinMax;
+
+typedef Stat1<float, int64_t> Stat1_f;
+typedef Stat1<double, int64_t> Stat1_d;
+typedef Stat1MinMax<float, int64_t> Stat1MinMax_f;
+typedef Stat1MinMax<double, int64_t> Stat1MinMax_d;
+
+template <typename VType>
+class Vector2;
+template <typename VType>
+class Vector3;
+template <typename VType>
+class Vector4;
+
+template <typename VType, typename NumType>
+class Stat1 {
+ public:
+ typedef Stat1<VType, NumType> Self;
+
+ Stat1() { Clear(); }
+ // Create a sample of value dat and weight 1
+ explicit Stat1(const VType &dat) {
+ sum_ = dat;
+ sum_squares_ = Sqr(dat);
+ numsamples_ = 1;
+ }
+ // Create statistics for all the samples between begin (included)
+ // and end(excluded)
+ explicit Stat1(const VType *begin, const VType *end) {
+ Clear();
+ for (const VType *item = begin; item < end; ++item) {
+ (*this) += Stat1(*item);
+ }
+ }
+ // Create a sample of value dat and weight w
+ Stat1(const VType &dat, const NumType &w) {
+ sum_ = w * dat;
+ sum_squares_ = w * Sqr(dat);
+ numsamples_ = w;
+ }
+ // Copy operator
+ Stat1(const Self &stat) {
+ sum_ = stat.sum_;
+ sum_squares_ = stat.sum_squares_;
+ numsamples_ = stat.numsamples_;
+ }
+
+ void Clear() {
+ numsamples_ = NumType();
+ sum_squares_ = sum_ = VType();
+ }
+
+ Self &operator=(const Self &stat) {
+ sum_ = stat.sum_;
+ sum_squares_ = stat.sum_squares_;
+ numsamples_ = stat.numsamples_;
+ return (*this);
+ }
+ // Merge statistics from two sample sets.
+ Self &operator+=(const Self &stat) {
+ sum_ += stat.sum_;
+ sum_squares_ += stat.sum_squares_;
+ numsamples_ += stat.numsamples_;
+ return (*this);
+ }
+ // The operation opposite to +=
+ Self &operator-=(const Self &stat) {
+ sum_ -= stat.sum_;
+ sum_squares_ -= stat.sum_squares_;
+ numsamples_ -= stat.numsamples_;
+ return (*this);
+ }
+ // Multiply the weight of the set of samples by a factor k
+ Self &operator*=(const VType &k) {
+ sum_ *= k;
+ sum_squares_ *= k;
+ numsamples_ *= k;
+ return (*this);
+ }
+
+ // Merge statistics from two sample sets.
+ Self operator+(const Self &stat) const { return Self(*this) += stat; }
+
+ // The operation opposite to +
+ Self operator-(const Self &stat) const { return Self(*this) -= stat; }
+
+ // Multiply the weight of the set of samples by a factor k
+ Self operator*(const VType &k) const { return Self(*this) *= k; }
+
+ // Return the total weight of this sample set
+ NumType numSamples() const { return numsamples_; }
+
+ // Return the sum of this sample set
+ VType Sum() const { return sum_; }
+
+ // Return the mean of this sample set
+ VType Mean() const {
+ if (numsamples_ == 0) return VType();
+ return sum_ * (1.0 / numsamples_);
+ }
+
+ // Return the mean of this sample set and compute the standard deviation at
+ // the same time.
+ VType Mean(VType *stddev) const {
+ if (numsamples_ == 0) return VType();
+ VType mean = sum_ * (1.0 / numsamples_);
+ if (stddev) {
+ VType avg_squares = sum_squares_ * (1.0 / numsamples_);
+ *stddev = Sqrt(avg_squares - Sqr(mean));
+ }
+ return mean;
+ }
+
+ // Return the standard deviation of the sample set
+ VType StdDev() const {
+ if (numsamples_ == 0) return VType();
+ VType mean = Mean();
+ VType avg_squares = sum_squares_ * (1.0 / numsamples_);
+ return Sqrt(avg_squares - Sqr(mean));
+ }
+
+ private:
+ static_assert(std::is_integral<NumType>::value &&
+ !std::is_same<NumType, bool>::value,
+ "NumType must be an integral type that is not bool.");
+ // Let i be the index of the samples provided (using +=)
+ // and weight[i],value[i] be the data of sample #i
+ // then the variables have the following meaning:
+ NumType numsamples_; // sum of weight[i];
+ VType sum_; // sum of weight[i]*value[i];
+ VType sum_squares_; // sum of weight[i]*value[i]^2;
+
+ // Template function used to square a number.
+ // For a vector we square all components
+ template <typename SType>
+ static inline SType Sqr(const SType &dat) {
+ return dat * dat;
+ }
+
+ template <typename SType>
+ static inline Vector2<SType> Sqr(const Vector2<SType> &dat) {
+ return dat.MulComponents(dat);
+ }
+
+ template <typename SType>
+ static inline Vector3<SType> Sqr(const Vector3<SType> &dat) {
+ return dat.MulComponents(dat);
+ }
+
+ template <typename SType>
+ static inline Vector4<SType> Sqr(const Vector4<SType> &dat) {
+ return dat.MulComponents(dat);
+ }
+
+ // Template function used to take the square root of a number.
+ // For a vector we square all components
+ template <typename SType>
+ static inline SType Sqrt(const SType &dat) {
+ // Avoid NaN due to imprecision in the calculations
+ if (dat < 0) return 0;
+ return sqrt(dat);
+ }
+
+ template <typename SType>
+ static inline Vector2<SType> Sqrt(const Vector2<SType> &dat) {
+ // Avoid NaN due to imprecision in the calculations
+ return Max(dat, Vector2<SType>()).Sqrt();
+ }
+
+ template <typename SType>
+ static inline Vector3<SType> Sqrt(const Vector3<SType> &dat) {
+ // Avoid NaN due to imprecision in the calculations
+ return Max(dat, Vector3<SType>()).Sqrt();
+ }
+
+ template <typename SType>
+ static inline Vector4<SType> Sqrt(const Vector4<SType> &dat) {
+ // Avoid NaN due to imprecision in the calculations
+ return Max(dat, Vector4<SType>()).Sqrt();
+ }
+};
+
+// Useful printing function
+template <typename VType, typename NumType>
+std::ostream &operator<<(std::ostream &out, const Stat1<VType, NumType> &s) {
+ out << "{ avg = " << s.Mean() << " std = " << s.StdDev()
+ << " nsamples = " << s.NumSamples() << "}";
+ return out;
+}
+
+// Stat1MinMax: same as Stat1, but it also
+// keeps the Min and Max values; the "-"
+// operator is disabled because it cannot be implemented
+// efficiently
+template <typename VType, typename NumType>
+class Stat1MinMax : public Stat1<VType, NumType> {
+ public:
+ typedef Stat1MinMax<VType, NumType> Self;
+
+ Stat1MinMax() { Clear(); }
+ // Create a sample of value dat and weight 1
+ explicit Stat1MinMax(const VType &dat) : Stat1<VType, NumType>(dat) {
+ max_ = dat;
+ min_ = dat;
+ }
+ // Create statistics for all the samples between begin (included)
+ // and end(excluded)
+ explicit Stat1MinMax(const VType *begin, const VType *end) {
+ Clear();
+ for (const VType *item = begin; item < end; ++item) {
+ (*this) += Stat1MinMax(*item);
+ }
+ }
+ // Create a sample of value dat and weight w
+ Stat1MinMax(const VType &dat, const NumType &w)
+ : Stat1<VType, NumType>(dat, w) {
+ max_ = dat;
+ min_ = dat;
+ }
+ // Copy operator
+ Stat1MinMax(const Self &stat) : Stat1<VType, NumType>(stat) {
+ max_ = stat.max_;
+ min_ = stat.min_;
+ }
+
+ void Clear() {
+ Stat1<VType, NumType>::Clear();
+ if (std::numeric_limits<VType>::has_infinity) {
+ min_ = std::numeric_limits<VType>::infinity();
+ max_ = -std::numeric_limits<VType>::infinity();
+ } else {
+ min_ = std::numeric_limits<VType>::max();
+ max_ = std::numeric_limits<VType>::min();
+ }
+ }
+
+ Self &operator=(const Self &stat) {
+ this->Stat1<VType, NumType>::operator=(stat);
+ max_ = stat.max_;
+ min_ = stat.min_;
+ return (*this);
+ }
+ // Merge statistics from two sample sets.
+ Self &operator+=(const Self &stat) {
+ this->Stat1<VType, NumType>::operator+=(stat);
+ if (stat.max_ > max_) max_ = stat.max_;
+ if (stat.min_ < min_) min_ = stat.min_;
+ return (*this);
+ }
+ // Multiply the weight of the set of samples by a factor k
+ Self &operator*=(const VType &stat) {
+ this->Stat1<VType, NumType>::operator*=(stat);
+ return (*this);
+ }
+ // Merge statistics from two sample sets.
+ Self operator+(const Self &stat) const { return Self(*this) += stat; }
+ // Multiply the weight of the set of samples by a factor k
+ Self operator*(const VType &k) const { return Self(*this) *= k; }
+
+ // Return the maximal value in this sample set
+ VType Max() const { return max_; }
+ // Return the minimal value in this sample set
+ VType Min() const { return min_; }
+
+ private:
+ // The - operation makes no sense with Min/Max
+ // unless we keep the full list of values (but we don't)
+ // make it private, and let it undefined so nobody can call it
+ Self &operator-=(const Self &stat); // senseless. let it undefined.
+
+ // The operation opposite to -
+ Self operator-(const Self &stat) const; // senseless. let it undefined.
+
+ // Let i be the index of the samples provided (using +=)
+ // and weight[i],value[i] be the data of sample #i
+ // then the variables have the following meaning:
+ VType max_; // max of value[i]
+ VType min_; // min of value[i]
+};
+
+// Useful printing function
+template <typename VType, typename NumType>
+std::ostream &operator<<(std::ostream &out,
+ const Stat1MinMax<VType, NumType> &s) {
+ out << "{ avg = " << s.Mean() << " std = " << s.StdDev()
+ << " nsamples = " << s.NumSamples() << " min = " << s.Min()
+ << " max = " << s.Max() << "}";
+ return out;
+}
+} // end namespace benchmark
+
+#endif // BENCHMARK_STAT_H_
diff --git a/3rdparty/benchmark/src/string_util.cc b/3rdparty/benchmark/src/string_util.cc
new file mode 100644
index 00000000000..30d130500d3
--- /dev/null
+++ b/3rdparty/benchmark/src/string_util.cc
@@ -0,0 +1,169 @@
+#include "string_util.h"
+
+#include <cmath>
+#include <cstdarg>
+#include <array>
+#include <memory>
+#include <sstream>
+#include <stdio.h>
+
+#include "arraysize.h"
+
+namespace benchmark {
+namespace {
+
+// kilo, Mega, Giga, Tera, Peta, Exa, Zetta, Yotta.
+const char kBigSIUnits[] = "kMGTPEZY";
+// Kibi, Mebi, Gibi, Tebi, Pebi, Exbi, Zebi, Yobi.
+const char kBigIECUnits[] = "KMGTPEZY";
+// milli, micro, nano, pico, femto, atto, zepto, yocto.
+const char kSmallSIUnits[] = "munpfazy";
+
+// We require that all three arrays have the same size.
+static_assert(arraysize(kBigSIUnits) == arraysize(kBigIECUnits),
+ "SI and IEC unit arrays must be the same size");
+static_assert(arraysize(kSmallSIUnits) == arraysize(kBigSIUnits),
+ "Small SI and Big SI unit arrays must be the same size");
+
+static const int64_t kUnitsSize = arraysize(kBigSIUnits);
+
+} // end anonymous namespace
+
+void ToExponentAndMantissa(double val, double thresh, int precision,
+ double one_k, std::string* mantissa,
+ int64_t* exponent) {
+ std::stringstream mantissa_stream;
+
+ if (val < 0) {
+ mantissa_stream << "-";
+ val = -val;
+ }
+
+ // Adjust threshold so that it never excludes things which can't be rendered
+ // in 'precision' digits.
+ const double adjusted_threshold =
+ std::max(thresh, 1.0 / std::pow(10.0, precision));
+ const double big_threshold = adjusted_threshold * one_k;
+ const double small_threshold = adjusted_threshold;
+
+ if (val > big_threshold) {
+ // Positive powers
+ double scaled = val;
+ for (size_t i = 0; i < arraysize(kBigSIUnits); ++i) {
+ scaled /= one_k;
+ if (scaled <= big_threshold) {
+ mantissa_stream << scaled;
+ *exponent = i + 1;
+ *mantissa = mantissa_stream.str();
+ return;
+ }
+ }
+ mantissa_stream << val;
+ *exponent = 0;
+ } else if (val < small_threshold) {
+ // Negative powers
+ double scaled = val;
+ for (size_t i = 0; i < arraysize(kSmallSIUnits); ++i) {
+ scaled *= one_k;
+ if (scaled >= small_threshold) {
+ mantissa_stream << scaled;
+ *exponent = -static_cast<int64_t>(i + 1);
+ *mantissa = mantissa_stream.str();
+ return;
+ }
+ }
+ mantissa_stream << val;
+ *exponent = 0;
+ } else {
+ mantissa_stream << val;
+ *exponent = 0;
+ }
+ *mantissa = mantissa_stream.str();
+}
+
+std::string ExponentToPrefix(int64_t exponent, bool iec) {
+ if (exponent == 0) return "";
+
+ const int64_t index = (exponent > 0 ? exponent - 1 : -exponent - 1);
+ if (index >= kUnitsSize) return "";
+
+ const char* array =
+ (exponent > 0 ? (iec ? kBigIECUnits : kBigSIUnits) : kSmallSIUnits);
+ if (iec)
+ return array[index] + std::string("i");
+ else
+ return std::string(1, array[index]);
+}
+
+std::string ToBinaryStringFullySpecified(double value, double threshold,
+ int precision) {
+ std::string mantissa;
+ int64_t exponent;
+ ToExponentAndMantissa(value, threshold, precision, 1024.0, &mantissa,
+ &exponent);
+ return mantissa + ExponentToPrefix(exponent, false);
+}
+
+void AppendHumanReadable(int n, std::string* str) {
+ std::stringstream ss;
+ // Round down to the nearest SI prefix.
+ ss << "/" << ToBinaryStringFullySpecified(n, 1.0, 0);
+ *str += ss.str();
+}
+
+std::string HumanReadableNumber(double n) {
+ // 1.1 means that figures up to 1.1k should be shown with the next unit down;
+ // this softens edge effects.
+ // 1 means that we should show one decimal place of precision.
+ return ToBinaryStringFullySpecified(n, 1.1, 1);
+}
+
+std::string StringPrintFImp(const char *msg, va_list args)
+{
+ // we might need a second shot at this, so pre-emptivly make a copy
+ va_list args_cp;
+ va_copy(args_cp, args);
+
+ // TODO(ericwf): use std::array for first attempt to avoid one memory
+ // allocation guess what the size might be
+ std::array<char, 256> local_buff;
+ std::size_t size = local_buff.size();
+ // 2015-10-08: vsnprintf is used instead of snd::vsnprintf due to a limitation in the android-ndk
+ auto ret = vsnprintf(local_buff.data(), size, msg, args_cp);
+
+ va_end(args_cp);
+
+ // handle empty expansion
+ if (ret == 0)
+ return std::string{};
+ if (static_cast<std::size_t>(ret) < size)
+ return std::string(local_buff.data());
+
+ // we did not provide a long enough buffer on our first attempt.
+ // add 1 to size to account for null-byte in size cast to prevent overflow
+ size = static_cast<std::size_t>(ret) + 1;
+ auto buff_ptr = std::unique_ptr<char[]>(new char[size]);
+ // 2015-10-08: vsnprintf is used instead of snd::vsnprintf due to a limitation in the android-ndk
+ ret = vsnprintf(buff_ptr.get(), size, msg, args);
+ return std::string(buff_ptr.get());
+}
+
+std::string StringPrintF(const char* format, ...)
+{
+ va_list args;
+ va_start(args, format);
+ std::string tmp = StringPrintFImp(format, args);
+ va_end(args);
+ return tmp;
+}
+
+void ReplaceAll(std::string* str, const std::string& from,
+ const std::string& to) {
+ std::size_t start = 0;
+ while((start = str->find(from, start)) != std::string::npos) {
+ str->replace(start, from.length(), to);
+ start += to.length();
+ }
+}
+
+} // end namespace benchmark
diff --git a/3rdparty/benchmark/src/string_util.h b/3rdparty/benchmark/src/string_util.h
new file mode 100644
index 00000000000..b89fef5ff36
--- /dev/null
+++ b/3rdparty/benchmark/src/string_util.h
@@ -0,0 +1,44 @@
+#ifndef BENCHMARK_STRING_UTIL_H_
+#define BENCHMARK_STRING_UTIL_H_
+
+#include <string>
+#include <sstream>
+#include <utility>
+#include "internal_macros.h"
+
+namespace benchmark {
+
+void AppendHumanReadable(int n, std::string* str);
+
+std::string HumanReadableNumber(double n);
+
+std::string StringPrintF(const char* format, ...);
+
+inline std::ostream&
+StringCatImp(std::ostream& out) BENCHMARK_NOEXCEPT
+{
+ return out;
+}
+
+template <class First, class ...Rest>
+inline std::ostream&
+StringCatImp(std::ostream& out, First&& f, Rest&&... rest)
+{
+ out << std::forward<First>(f);
+ return StringCatImp(out, std::forward<Rest>(rest)...);
+}
+
+template<class ...Args>
+inline std::string StrCat(Args&&... args)
+{
+ std::ostringstream ss;
+ StringCatImp(ss, std::forward<Args>(args)...);
+ return ss.str();
+}
+
+void ReplaceAll(std::string* str, const std::string& from,
+ const std::string& to);
+
+} // end namespace benchmark
+
+#endif // BENCHMARK_STRING_UTIL_H_
diff --git a/3rdparty/benchmark/src/sysinfo.cc b/3rdparty/benchmark/src/sysinfo.cc
new file mode 100644
index 00000000000..d1f312024d3
--- /dev/null
+++ b/3rdparty/benchmark/src/sysinfo.cc
@@ -0,0 +1,416 @@
+// Copyright 2015 Google Inc. 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.
+
+#include "sysinfo.h"
+#include "internal_macros.h"
+
+#ifdef BENCHMARK_OS_WINDOWS
+#include <Shlwapi.h>
+#include <Windows.h>
+#include <VersionHelpers.h>
+#else
+#include <fcntl.h>
+#include <sys/resource.h>
+#include <sys/types.h> // this header must be included before 'sys/sysctl.h' to avoid compilation error on FreeBSD
+#include <sys/time.h>
+#include <unistd.h>
+#if defined BENCHMARK_OS_FREEBSD || defined BENCHMARK_OS_MACOSX
+#include <sys/sysctl.h>
+#endif
+#endif
+
+#include <cerrno>
+#include <cstdio>
+#include <cstdint>
+#include <cstdlib>
+#include <cstring>
+#include <iostream>
+#include <limits>
+#include <mutex>
+
+#include "arraysize.h"
+#include "check.h"
+#include "cycleclock.h"
+#include "internal_macros.h"
+#include "log.h"
+#include "sleep.h"
+#include "string_util.h"
+
+namespace benchmark {
+namespace {
+std::once_flag cpuinfo_init;
+double cpuinfo_cycles_per_second = 1.0;
+int cpuinfo_num_cpus = 1; // Conservative guess
+std::mutex cputimens_mutex;
+
+#if !defined BENCHMARK_OS_MACOSX
+const int64_t estimate_time_ms = 1000;
+
+// Helper function estimates cycles/sec by observing cycles elapsed during
+// sleep(). Using small sleep time decreases accuracy significantly.
+int64_t EstimateCyclesPerSecond() {
+ const int64_t start_ticks = cycleclock::Now();
+ SleepForMilliseconds(estimate_time_ms);
+ return cycleclock::Now() - start_ticks;
+}
+#endif
+
+#if defined BENCHMARK_OS_LINUX || defined BENCHMARK_OS_CYGWIN
+// Helper function for reading an int from a file. Returns true if successful
+// and the memory location pointed to by value is set to the value read.
+bool ReadIntFromFile(const char* file, long* value) {
+ bool ret = false;
+ int fd = open(file, O_RDONLY);
+ if (fd != -1) {
+ char line[1024];
+ char* err;
+ memset(line, '\0', sizeof(line));
+ CHECK(read(fd, line, sizeof(line) - 1));
+ const long temp_value = strtol(line, &err, 10);
+ if (line[0] != '\0' && (*err == '\n' || *err == '\0')) {
+ *value = temp_value;
+ ret = true;
+ }
+ close(fd);
+ }
+ return ret;
+}
+#endif
+
+void InitializeSystemInfo() {
+#if defined BENCHMARK_OS_LINUX || defined BENCHMARK_OS_CYGWIN
+ char line[1024];
+ char* err;
+ long freq;
+
+ bool saw_mhz = false;
+
+ // If the kernel is exporting the tsc frequency use that. There are issues
+ // where cpuinfo_max_freq cannot be relied on because the BIOS may be
+ // exporintg an invalid p-state (on x86) or p-states may be used to put the
+ // processor in a new mode (turbo mode). Essentially, those frequencies
+ // cannot always be relied upon. The same reasons apply to /proc/cpuinfo as
+ // well.
+ if (!saw_mhz &&
+ ReadIntFromFile("/sys/devices/system/cpu/cpu0/tsc_freq_khz", &freq)) {
+ // The value is in kHz (as the file name suggests). For example, on a
+ // 2GHz warpstation, the file contains the value "2000000".
+ cpuinfo_cycles_per_second = freq * 1000.0;
+ saw_mhz = true;
+ }
+
+ // If CPU scaling is in effect, we want to use the *maximum* frequency,
+ // not whatever CPU speed some random processor happens to be using now.
+ if (!saw_mhz &&
+ ReadIntFromFile("/sys/devices/system/cpu/cpu0/cpufreq/cpuinfo_max_freq",
+ &freq)) {
+ // The value is in kHz. For example, on a 2GHz warpstation, the file
+ // contains the value "2000000".
+ cpuinfo_cycles_per_second = freq * 1000.0;
+ saw_mhz = true;
+ }
+
+ // Read /proc/cpuinfo for other values, and if there is no cpuinfo_max_freq.
+ const char* pname = "/proc/cpuinfo";
+ int fd = open(pname, O_RDONLY);
+ if (fd == -1) {
+ perror(pname);
+ if (!saw_mhz) {
+ cpuinfo_cycles_per_second = static_cast<double>(EstimateCyclesPerSecond());
+ }
+ return;
+ }
+
+ double bogo_clock = 1.0;
+ bool saw_bogo = false;
+ long max_cpu_id = 0;
+ int num_cpus = 0;
+ line[0] = line[1] = '\0';
+ size_t chars_read = 0;
+ do { // we'll exit when the last read didn't read anything
+ // Move the next line to the beginning of the buffer
+ const size_t oldlinelen = strlen(line);
+ if (sizeof(line) == oldlinelen + 1) // oldlinelen took up entire line
+ line[0] = '\0';
+ else // still other lines left to save
+ memmove(line, line + oldlinelen + 1, sizeof(line) - (oldlinelen + 1));
+ // Terminate the new line, reading more if we can't find the newline
+ char* newline = strchr(line, '\n');
+ if (newline == nullptr) {
+ const size_t linelen = strlen(line);
+ const size_t bytes_to_read = sizeof(line) - 1 - linelen;
+ CHECK(bytes_to_read > 0); // because the memmove recovered >=1 bytes
+ chars_read = read(fd, line + linelen, bytes_to_read);
+ line[linelen + chars_read] = '\0';
+ newline = strchr(line, '\n');
+ }
+ if (newline != nullptr) *newline = '\0';
+
+ // When parsing the "cpu MHz" and "bogomips" (fallback) entries, we only
+ // accept postive values. Some environments (virtual machines) report zero,
+ // which would cause infinite looping in WallTime_Init.
+ if (!saw_mhz && strncasecmp(line, "cpu MHz", sizeof("cpu MHz") - 1) == 0) {
+ const char* freqstr = strchr(line, ':');
+ if (freqstr) {
+ cpuinfo_cycles_per_second = strtod(freqstr + 1, &err) * 1000000.0;
+ if (freqstr[1] != '\0' && *err == '\0' && cpuinfo_cycles_per_second > 0)
+ saw_mhz = true;
+ }
+ } else if (strncasecmp(line, "bogomips", sizeof("bogomips") - 1) == 0) {
+ const char* freqstr = strchr(line, ':');
+ if (freqstr) {
+ bogo_clock = strtod(freqstr + 1, &err) * 1000000.0;
+ if (freqstr[1] != '\0' && *err == '\0' && bogo_clock > 0)
+ saw_bogo = true;
+ }
+ } else if (strncasecmp(line, "processor", sizeof("processor") - 1) == 0) {
+ num_cpus++; // count up every time we see an "processor :" entry
+ const char* freqstr = strchr(line, ':');
+ if (freqstr) {
+ const long cpu_id = strtol(freqstr + 1, &err, 10);
+ if (freqstr[1] != '\0' && *err == '\0' && max_cpu_id < cpu_id)
+ max_cpu_id = cpu_id;
+ }
+ }
+ } while (chars_read > 0);
+ close(fd);
+
+ if (!saw_mhz) {
+ if (saw_bogo) {
+ // If we didn't find anything better, we'll use bogomips, but
+ // we're not happy about it.
+ cpuinfo_cycles_per_second = bogo_clock;
+ } else {
+ // If we don't even have bogomips, we'll use the slow estimation.
+ cpuinfo_cycles_per_second = static_cast<double>(EstimateCyclesPerSecond());
+ }
+ }
+ if (num_cpus == 0) {
+ fprintf(stderr, "Failed to read num. CPUs correctly from /proc/cpuinfo\n");
+ } else {
+ if ((max_cpu_id + 1) != num_cpus) {
+ fprintf(stderr,
+ "CPU ID assignments in /proc/cpuinfo seems messed up."
+ " This is usually caused by a bad BIOS.\n");
+ }
+ cpuinfo_num_cpus = num_cpus;
+ }
+
+#elif defined BENCHMARK_OS_FREEBSD
+// For this sysctl to work, the machine must be configured without
+// SMP, APIC, or APM support. hz should be 64-bit in freebsd 7.0
+// and later. Before that, it's a 32-bit quantity (and gives the
+// wrong answer on machines faster than 2^32 Hz). See
+// http://lists.freebsd.org/pipermail/freebsd-i386/2004-November/001846.html
+// But also compare FreeBSD 7.0:
+// http://fxr.watson.org/fxr/source/i386/i386/tsc.c?v=RELENG70#L223
+// 231 error = sysctl_handle_quad(oidp, &freq, 0, req);
+// To FreeBSD 6.3 (it's the same in 6-STABLE):
+// http://fxr.watson.org/fxr/source/i386/i386/tsc.c?v=RELENG6#L131
+// 139 error = sysctl_handle_int(oidp, &freq, sizeof(freq), req);
+#if __FreeBSD__ >= 7
+ uint64_t hz = 0;
+#else
+ unsigned int hz = 0;
+#endif
+ size_t sz = sizeof(hz);
+ const char* sysctl_path = "machdep.tsc_freq";
+ if (sysctlbyname(sysctl_path, &hz, &sz, nullptr, 0) != 0) {
+ fprintf(stderr, "Unable to determine clock rate from sysctl: %s: %s\n",
+ sysctl_path, strerror(errno));
+ cpuinfo_cycles_per_second = static_cast<double>(EstimateCyclesPerSecond());
+ } else {
+ cpuinfo_cycles_per_second = hz;
+ }
+// TODO: also figure out cpuinfo_num_cpus
+
+#elif defined BENCHMARK_OS_WINDOWS
+ // In NT, read MHz from the registry. If we fail to do so or we're in win9x
+ // then make a crude estimate.
+ DWORD data, data_size = sizeof(data);
+ if (IsWindowsXPOrGreater() &&
+ SUCCEEDED(
+ SHGetValueA(HKEY_LOCAL_MACHINE,
+ "HARDWARE\\DESCRIPTION\\System\\CentralProcessor\\0",
+ "~MHz", nullptr, &data, &data_size)))
+ cpuinfo_cycles_per_second = static_cast<double>((int64_t)data * (int64_t)(1000 * 1000)); // was mhz
+ else
+ cpuinfo_cycles_per_second = static_cast<double>(EstimateCyclesPerSecond());
+// TODO: also figure out cpuinfo_num_cpus
+
+#elif defined BENCHMARK_OS_MACOSX
+ // returning "mach time units" per second. the current number of elapsed
+ // mach time units can be found by calling uint64 mach_absolute_time();
+ // while not as precise as actual CPU cycles, it is accurate in the face
+ // of CPU frequency scaling and multi-cpu/core machines.
+ // Our mac users have these types of machines, and accuracy
+ // (i.e. correctness) trumps precision.
+ // See cycleclock.h: CycleClock::Now(), which returns number of mach time
+ // units on Mac OS X.
+ mach_timebase_info_data_t timebase_info;
+ mach_timebase_info(&timebase_info);
+ double mach_time_units_per_nanosecond =
+ static_cast<double>(timebase_info.denom) /
+ static_cast<double>(timebase_info.numer);
+ cpuinfo_cycles_per_second = mach_time_units_per_nanosecond * 1e9;
+
+ int num_cpus = 0;
+ size_t size = sizeof(num_cpus);
+ int numcpus_name[] = {CTL_HW, HW_NCPU};
+ if (::sysctl(numcpus_name, arraysize(numcpus_name), &num_cpus, &size, nullptr, 0) ==
+ 0 &&
+ (size == sizeof(num_cpus)))
+ cpuinfo_num_cpus = num_cpus;
+
+#else
+ // Generic cycles per second counter
+ cpuinfo_cycles_per_second = static_cast<double>(EstimateCyclesPerSecond());
+#endif
+}
+} // end namespace
+
+// getrusage() based implementation of MyCPUUsage
+static double MyCPUUsageRUsage() {
+#ifndef BENCHMARK_OS_WINDOWS
+ struct rusage ru;
+ if (getrusage(RUSAGE_SELF, &ru) == 0) {
+ return (static_cast<double>(ru.ru_utime.tv_sec) +
+ static_cast<double>(ru.ru_utime.tv_usec) * 1e-6 +
+ static_cast<double>(ru.ru_stime.tv_sec) +
+ static_cast<double>(ru.ru_stime.tv_usec) * 1e-6);
+ } else {
+ return 0.0;
+ }
+#else
+ HANDLE proc = GetCurrentProcess();
+ FILETIME creation_time;
+ FILETIME exit_time;
+ FILETIME kernel_time;
+ FILETIME user_time;
+ ULARGE_INTEGER kernel;
+ ULARGE_INTEGER user;
+ GetProcessTimes(proc, &creation_time, &exit_time, &kernel_time, &user_time);
+ kernel.HighPart = kernel_time.dwHighDateTime;
+ kernel.LowPart = kernel_time.dwLowDateTime;
+ user.HighPart = user_time.dwHighDateTime;
+ user.LowPart = user_time.dwLowDateTime;
+ return (static_cast<double>(kernel.QuadPart) +
+ static_cast<double>(user.QuadPart)) * 1e-7;
+#endif // OS_WINDOWS
+}
+
+#ifndef BENCHMARK_OS_WINDOWS
+static bool MyCPUUsageCPUTimeNsLocked(double* cputime) {
+ static int cputime_fd = -1;
+ if (cputime_fd == -1) {
+ cputime_fd = open("/proc/self/cputime_ns", O_RDONLY);
+ if (cputime_fd < 0) {
+ cputime_fd = -1;
+ return false;
+ }
+ }
+ char buff[64];
+ memset(buff, 0, sizeof(buff));
+ if (pread(cputime_fd, buff, sizeof(buff) - 1, 0) <= 0) {
+ close(cputime_fd);
+ cputime_fd = -1;
+ return false;
+ }
+ unsigned long long result = strtoull(buff, nullptr, 0);
+ if (result == (std::numeric_limits<unsigned long long>::max)()) {
+ close(cputime_fd);
+ cputime_fd = -1;
+ return false;
+ }
+ *cputime = static_cast<double>(result) / 1e9;
+ return true;
+}
+#endif // OS_WINDOWS
+
+double MyCPUUsage() {
+#ifndef BENCHMARK_OS_WINDOWS
+ {
+ std::lock_guard<std::mutex> l(cputimens_mutex);
+ static bool use_cputime_ns = true;
+ if (use_cputime_ns) {
+ double value;
+ if (MyCPUUsageCPUTimeNsLocked(&value)) {
+ return value;
+ }
+ // Once MyCPUUsageCPUTimeNsLocked fails once fall back to getrusage().
+ VLOG(1) << "Reading /proc/self/cputime_ns failed. Using getrusage().\n";
+ use_cputime_ns = false;
+ }
+ }
+#endif // OS_WINDOWS
+ return MyCPUUsageRUsage();
+}
+
+double ChildrenCPUUsage() {
+#ifndef BENCHMARK_OS_WINDOWS
+ struct rusage ru;
+ if (getrusage(RUSAGE_CHILDREN, &ru) == 0) {
+ return (static_cast<double>(ru.ru_utime.tv_sec) +
+ static_cast<double>(ru.ru_utime.tv_usec) * 1e-6 +
+ static_cast<double>(ru.ru_stime.tv_sec) +
+ static_cast<double>(ru.ru_stime.tv_usec) * 1e-6);
+ } else {
+ return 0.0;
+ }
+#else
+ // TODO: Not sure what this even means on Windows
+ return 0.0;
+#endif // OS_WINDOWS
+}
+
+double CyclesPerSecond(void) {
+ std::call_once(cpuinfo_init, InitializeSystemInfo);
+ return cpuinfo_cycles_per_second;
+}
+
+int NumCPUs(void) {
+ std::call_once(cpuinfo_init, InitializeSystemInfo);
+ return cpuinfo_num_cpus;
+}
+
+// The ""'s catch people who don't pass in a literal for "str"
+#define strliterallen(str) (sizeof("" str "") - 1)
+
+// Must use a string literal for prefix.
+#define memprefix(str, len, prefix) \
+ ((((len) >= strliterallen(prefix)) && \
+ std::memcmp(str, prefix, strliterallen(prefix)) == 0) \
+ ? str + strliterallen(prefix) \
+ : nullptr)
+
+bool CpuScalingEnabled() {
+#ifndef BENCHMARK_OS_WINDOWS
+ // On Linux, the CPUfreq subsystem exposes CPU information as files on the
+ // local file system. If reading the exported files fails, then we may not be
+ // running on Linux, so we silently ignore all the read errors.
+ for (int cpu = 0, num_cpus = NumCPUs(); cpu < num_cpus; ++cpu) {
+ std::string governor_file = StrCat("/sys/devices/system/cpu/cpu", cpu,
+ "/cpufreq/scaling_governor");
+ FILE* file = fopen(governor_file.c_str(), "r");
+ if (!file) break;
+ char buff[16];
+ size_t bytes_read = fread(buff, 1, sizeof(buff), file);
+ fclose(file);
+ if (memprefix(buff, bytes_read, "performance") == nullptr) return true;
+ }
+#endif
+ return false;
+}
+
+} // end namespace benchmark
diff --git a/3rdparty/benchmark/src/sysinfo.h b/3rdparty/benchmark/src/sysinfo.h
new file mode 100644
index 00000000000..eaf77e07ccb
--- /dev/null
+++ b/3rdparty/benchmark/src/sysinfo.h
@@ -0,0 +1,12 @@
+#ifndef BENCHMARK_SYSINFO_H_
+#define BENCHMARK_SYSINFO_H_
+
+namespace benchmark {
+double MyCPUUsage();
+double ChildrenCPUUsage();
+int NumCPUs();
+double CyclesPerSecond();
+bool CpuScalingEnabled();
+} // end namespace benchmark
+
+#endif // BENCHMARK_SYSINFO_H_
diff --git a/3rdparty/benchmark/src/walltime.cc b/3rdparty/benchmark/src/walltime.cc
new file mode 100644
index 00000000000..4bdbaa59859
--- /dev/null
+++ b/3rdparty/benchmark/src/walltime.cc
@@ -0,0 +1,263 @@
+// Copyright 2015 Google Inc. 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.
+
+#include "benchmark/macros.h"
+#include "internal_macros.h"
+#include "walltime.h"
+
+#if defined(BENCHMARK_OS_WINDOWS)
+#include <time.h>
+#include <winsock.h> // for timeval
+#else
+#include <sys/time.h>
+#endif
+
+#include <cstdio>
+#include <cstdint>
+#include <cstring>
+#include <ctime>
+
+#include <atomic>
+#include <chrono>
+#include <limits>
+
+#include "arraysize.h"
+#include "check.h"
+#include "cycleclock.h"
+#include "log.h"
+#include "sysinfo.h"
+
+namespace benchmark {
+namespace walltime {
+
+namespace {
+
+#if defined(HAVE_STEADY_CLOCK)
+template <bool HighResIsSteady = std::chrono::high_resolution_clock::is_steady>
+struct ChooseSteadyClock {
+ typedef std::chrono::high_resolution_clock type;
+};
+
+template <>
+struct ChooseSteadyClock<false> {
+ typedef std::chrono::steady_clock type;
+};
+#endif
+
+struct ChooseClockType {
+#if defined(HAVE_STEADY_CLOCK)
+ typedef ChooseSteadyClock<>::type type;
+#else
+ typedef std::chrono::high_resolution_clock type;
+#endif
+};
+
+class WallTimeImp
+{
+public:
+ WallTime Now();
+
+ static WallTimeImp& GetWallTimeImp() {
+ static WallTimeImp* imp = new WallTimeImp();
+ return *imp;
+ }
+
+private:
+ WallTimeImp();
+ // Helper routines to load/store a float from an AtomicWord. Required because
+ // g++ < 4.7 doesn't support std::atomic<float> correctly. I cannot wait to
+ // get rid of this horror show.
+ void SetDrift(float f) {
+ int32_t w;
+ memcpy(&w, &f, sizeof(f));
+ std::atomic_store(&drift_adjust_, w);
+ }
+
+ float GetDrift() const {
+ float f;
+ int32_t w = std::atomic_load(&drift_adjust_);
+ memcpy(&f, &w, sizeof(f));
+ return f;
+ }
+
+ WallTime Slow() const {
+ struct timeval tv;
+#if defined(BENCHMARK_OS_WINDOWS)
+ FILETIME file_time;
+ SYSTEMTIME system_time;
+ ULARGE_INTEGER ularge;
+ const unsigned __int64 epoch = 116444736000000000LL;
+
+ GetSystemTime(&system_time);
+ SystemTimeToFileTime(&system_time, &file_time);
+ ularge.LowPart = file_time.dwLowDateTime;
+ ularge.HighPart = file_time.dwHighDateTime;
+
+ tv.tv_sec = (long)((ularge.QuadPart - epoch) / (10L * 1000 * 1000));
+ tv.tv_usec = (long)(system_time.wMilliseconds * 1000);
+#else
+ gettimeofday(&tv, nullptr);
+#endif
+ return tv.tv_sec + tv.tv_usec * 1e-6;
+ }
+
+private:
+ static_assert(sizeof(float) <= sizeof(int32_t),
+ "type sizes don't allow the drift_adjust hack");
+
+ WallTime base_walltime_;
+ int64_t base_cycletime_;
+ int64_t cycles_per_second_;
+ double seconds_per_cycle_;
+ uint32_t last_adjust_time_;
+ std::atomic<int32_t> drift_adjust_;
+ int64_t max_interval_cycles_;
+
+ BENCHMARK_DISALLOW_COPY_AND_ASSIGN(WallTimeImp);
+};
+
+
+WallTime WallTimeImp::Now() {
+ WallTime now = 0.0;
+ WallTime result = 0.0;
+ int64_t ct = 0;
+ uint32_t top_bits = 0;
+ do {
+ ct = cycleclock::Now();
+ int64_t cycle_delta = ct - base_cycletime_;
+ result = base_walltime_ + cycle_delta * seconds_per_cycle_;
+
+ top_bits = static_cast<uint32_t>(uint64_t(ct) >> 32);
+ // Recompute drift no more often than every 2^32 cycles.
+ // I.e., @2GHz, ~ every two seconds
+ if (top_bits == last_adjust_time_) { // don't need to recompute drift
+ return result + GetDrift();
+ }
+
+ now = Slow();
+ } while (cycleclock::Now() - ct > max_interval_cycles_);
+ // We are now sure that "now" and "result" were produced within
+ // kMaxErrorInterval of one another.
+
+ SetDrift(static_cast<float>(now - result));
+ last_adjust_time_ = top_bits;
+ return now;
+}
+
+
+WallTimeImp::WallTimeImp()
+ : base_walltime_(0.0), base_cycletime_(0),
+ cycles_per_second_(0), seconds_per_cycle_(0.0),
+ last_adjust_time_(0), drift_adjust_(0),
+ max_interval_cycles_(0) {
+ const double kMaxErrorInterval = 100e-6;
+ cycles_per_second_ = static_cast<int64_t>(CyclesPerSecond());
+ CHECK(cycles_per_second_ != 0);
+ seconds_per_cycle_ = 1.0 / cycles_per_second_;
+ max_interval_cycles_ =
+ static_cast<int64_t>(cycles_per_second_ * kMaxErrorInterval);
+ do {
+ base_cycletime_ = cycleclock::Now();
+ base_walltime_ = Slow();
+ } while (cycleclock::Now() - base_cycletime_ > max_interval_cycles_);
+ // We are now sure that "base_walltime" and "base_cycletime" were produced
+ // within kMaxErrorInterval of one another.
+
+ SetDrift(0.0);
+ last_adjust_time_ = static_cast<uint32_t>(uint64_t(base_cycletime_) >> 32);
+}
+
+WallTime CPUWalltimeNow() {
+ static WallTimeImp& imp = WallTimeImp::GetWallTimeImp();
+ return imp.Now();
+}
+
+WallTime ChronoWalltimeNow() {
+ typedef ChooseClockType::type Clock;
+ typedef std::chrono::duration<WallTime, std::chrono::seconds::period>
+ FPSeconds;
+ static_assert(std::chrono::treat_as_floating_point<WallTime>::value,
+ "This type must be treated as a floating point type.");
+ auto now = Clock::now().time_since_epoch();
+ return std::chrono::duration_cast<FPSeconds>(now).count();
+}
+
+bool UseCpuCycleClock() {
+ bool useWallTime = !CpuScalingEnabled();
+ if (useWallTime) {
+ VLOG(1) << "Using the CPU cycle clock to provide walltime::Now().\n";
+ } else {
+ VLOG(1) << "Using std::chrono to provide walltime::Now().\n";
+ }
+ return useWallTime;
+}
+
+
+} // end anonymous namespace
+
+// WallTimeImp doesn't work when CPU Scaling is enabled. If CPU Scaling is
+// enabled at the start of the program then std::chrono::system_clock is used
+// instead.
+WallTime Now()
+{
+ static bool useCPUClock = UseCpuCycleClock();
+ if (useCPUClock) {
+ return CPUWalltimeNow();
+ } else {
+ return ChronoWalltimeNow();
+ }
+}
+
+} // end namespace walltime
+
+
+namespace {
+
+std::string DateTimeString(bool local) {
+ typedef std::chrono::system_clock Clock;
+ std::time_t now = Clock::to_time_t(Clock::now());
+ char storage[128];
+ std::size_t written;
+
+ if (local) {
+#if defined(BENCHMARK_OS_WINDOWS)
+ written = std::strftime(storage, sizeof(storage), "%x %X", ::localtime(&now));
+#else
+ std::tm timeinfo;
+ std::memset(&timeinfo, 0, sizeof(std::tm));
+ ::localtime_r(&now, &timeinfo);
+ written = std::strftime(storage, sizeof(storage), "%F %T", &timeinfo);
+#endif
+ } else {
+#if defined(BENCHMARK_OS_WINDOWS)
+ written = std::strftime(storage, sizeof(storage), "%x %X", ::gmtime(&now));
+#else
+ std::tm timeinfo;
+ std::memset(&timeinfo, 0, sizeof(std::tm));
+ ::gmtime_r(&now, &timeinfo);
+ written = std::strftime(storage, sizeof(storage), "%F %T", &timeinfo);
+#endif
+ }
+ CHECK(written < arraysize(storage));
+ ((void)written); // prevent unused variable in optimized mode.
+ return std::string(storage);
+}
+
+} // end namespace
+
+std::string LocalDateTimeString() {
+ return DateTimeString(true);
+}
+
+} // end namespace benchmark
diff --git a/3rdparty/benchmark/src/walltime.h b/3rdparty/benchmark/src/walltime.h
new file mode 100644
index 00000000000..38c26f33213
--- /dev/null
+++ b/3rdparty/benchmark/src/walltime.h
@@ -0,0 +1,17 @@
+#ifndef BENCHMARK_WALLTIME_H_
+#define BENCHMARK_WALLTIME_H_
+
+#include <string>
+
+namespace benchmark {
+typedef double WallTime;
+
+namespace walltime {
+WallTime Now();
+} // end namespace walltime
+
+std::string LocalDateTimeString();
+
+} // end namespace benchmark
+
+#endif // BENCHMARK_WALLTIME_H_