1 // Copyright 2015 Google Inc. All rights reserved. 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); 4 // you may not use this file except in compliance with the License. 5 // You may obtain a copy of the License at 6 // 7 // http://www.apache.org/licenses/LICENSE-2.0 8 // 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS IS" BASIS, 11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 // See the License for the specific language governing permissions and 13 // limitations under the License. 14 15 #include "benchmark/benchmark.h" 16 #include "benchmark_api_internal.h" 17 #include "internal_macros.h" 18 19 #ifndef BENCHMARK_OS_WINDOWS 20 #include <sys/resource.h> 21 #include <sys/time.h> 22 #include <unistd.h> 23 #endif 24 25 #include <algorithm> 26 #include <atomic> 27 #include <condition_variable> 28 #include <cstdio> 29 #include <cstdlib> 30 #include <cstring> 31 #include <fstream> 32 #include <iostream> 33 #include <memory> 34 #include <sstream> 35 #include <thread> 36 37 #include "check.h" 38 #include "commandlineflags.h" 39 #include "complexity.h" 40 #include "statistics.h" 41 #include "log.h" 42 #include "mutex.h" 43 #include "re.h" 44 #include "string_util.h" 45 #include "timers.h" 46 47 namespace benchmark { 48 49 namespace { 50 // For non-dense Range, intermediate values are powers of kRangeMultiplier. 51 static const int kRangeMultiplier = 8; 52 // The size of a benchmark family determines is the number of inputs to repeat 53 // the benchmark on. If this is "large" then warn the user during configuration. 54 static const size_t kMaxFamilySize = 100; 55 } // end namespace 56 57 namespace internal { 58 59 //=============================================================================// 60 // BenchmarkFamilies 61 //=============================================================================// 62 63 // Class for managing registered benchmarks. Note that each registered 64 // benchmark identifies a family of related benchmarks to run. 65 class BenchmarkFamilies { 66 public: 67 static BenchmarkFamilies* GetInstance(); 68 69 // Registers a benchmark family and returns the index assigned to it. 70 size_t AddBenchmark(std::unique_ptr<Benchmark> family); 71 72 // Clear all registered benchmark families. 73 void ClearBenchmarks(); 74 75 // Extract the list of benchmark instances that match the specified 76 // regular expression. 77 bool FindBenchmarks(const std::string& re, 78 std::vector<Benchmark::Instance>* benchmarks, 79 std::ostream* Err); 80 81 private: 82 BenchmarkFamilies() {} 83 84 std::vector<std::unique_ptr<Benchmark>> families_; 85 Mutex mutex_; 86 }; 87 88 BenchmarkFamilies* BenchmarkFamilies::GetInstance() { 89 static BenchmarkFamilies instance; 90 return &instance; 91 } 92 93 size_t BenchmarkFamilies::AddBenchmark(std::unique_ptr<Benchmark> family) { 94 MutexLock l(mutex_); 95 size_t index = families_.size(); 96 families_.push_back(std::move(family)); 97 return index; 98 } 99 100 void BenchmarkFamilies::ClearBenchmarks() { 101 MutexLock l(mutex_); 102 families_.clear(); 103 families_.shrink_to_fit(); 104 } 105 106 bool BenchmarkFamilies::FindBenchmarks( 107 const std::string& spec, std::vector<Benchmark::Instance>* benchmarks, 108 std::ostream* ErrStream) { 109 CHECK(ErrStream); 110 auto& Err = *ErrStream; 111 // Make regular expression out of command-line flag 112 std::string error_msg; 113 Regex re; 114 if (!re.Init(spec, &error_msg)) { 115 Err << "Could not compile benchmark re: " << error_msg << std::endl; 116 return false; 117 } 118 119 // Special list of thread counts to use when none are specified 120 const std::vector<int> one_thread = {1}; 121 122 MutexLock l(mutex_); 123 for (std::unique_ptr<Benchmark>& family : families_) { 124 // Family was deleted or benchmark doesn't match 125 if (!family) continue; 126 127 if (family->ArgsCnt() == -1) { 128 family->Args({}); 129 } 130 const std::vector<int>* thread_counts = 131 (family->thread_counts_.empty() 132 ? &one_thread 133 : &static_cast<const std::vector<int>&>(family->thread_counts_)); 134 const size_t family_size = family->args_.size() * thread_counts->size(); 135 // The benchmark will be run at least 'family_size' different inputs. 136 // If 'family_size' is very large warn the user. 137 if (family_size > kMaxFamilySize) { 138 Err << "The number of inputs is very large. " << family->name_ 139 << " will be repeated at least " << family_size << " times.\n"; 140 } 141 // reserve in the special case the regex ".", since we know the final 142 // family size. 143 if (spec == ".") benchmarks->reserve(family_size); 144 145 for (auto const& args : family->args_) { 146 for (int num_threads : *thread_counts) { 147 Benchmark::Instance instance; 148 instance.name = family->name_; 149 instance.benchmark = family.get(); 150 instance.report_mode = family->report_mode_; 151 instance.arg = args; 152 instance.time_unit = family->time_unit_; 153 instance.range_multiplier = family->range_multiplier_; 154 instance.min_time = family->min_time_; 155 instance.iterations = family->iterations_; 156 instance.repetitions = family->repetitions_; 157 instance.use_real_time = family->use_real_time_; 158 instance.use_manual_time = family->use_manual_time_; 159 instance.complexity = family->complexity_; 160 instance.complexity_lambda = family->complexity_lambda_; 161 instance.statistics = &family->statistics_; 162 instance.threads = num_threads; 163 164 // Add arguments to instance name 165 size_t arg_i = 0; 166 for (auto const& arg : args) { 167 instance.name += "/"; 168 169 if (arg_i < family->arg_names_.size()) { 170 const auto& arg_name = family->arg_names_[arg_i]; 171 if (!arg_name.empty()) { 172 instance.name += 173 StringPrintF("%s:", family->arg_names_[arg_i].c_str()); 174 } 175 } 176 177 instance.name += StringPrintF("%d", arg); 178 ++arg_i; 179 } 180 181 if (!IsZero(family->min_time_)) 182 instance.name += StringPrintF("/min_time:%0.3f", family->min_time_); 183 if (family->iterations_ != 0) 184 instance.name += StringPrintF("/iterations:%d", family->iterations_); 185 if (family->repetitions_ != 0) 186 instance.name += StringPrintF("/repeats:%d", family->repetitions_); 187 188 if (family->use_manual_time_) { 189 instance.name += "/manual_time"; 190 } else if (family->use_real_time_) { 191 instance.name += "/real_time"; 192 } 193 194 // Add the number of threads used to the name 195 if (!family->thread_counts_.empty()) { 196 instance.name += StringPrintF("/threads:%d", instance.threads); 197 } 198 199 if (re.Match(instance.name)) { 200 instance.last_benchmark_instance = (&args == &family->args_.back()); 201 benchmarks->push_back(std::move(instance)); 202 } 203 } 204 } 205 } 206 return true; 207 } 208 209 Benchmark* RegisterBenchmarkInternal(Benchmark* bench) { 210 std::unique_ptr<Benchmark> bench_ptr(bench); 211 BenchmarkFamilies* families = BenchmarkFamilies::GetInstance(); 212 families->AddBenchmark(std::move(bench_ptr)); 213 return bench; 214 } 215 216 // FIXME: This function is a hack so that benchmark.cc can access 217 // `BenchmarkFamilies` 218 bool FindBenchmarksInternal(const std::string& re, 219 std::vector<Benchmark::Instance>* benchmarks, 220 std::ostream* Err) { 221 return BenchmarkFamilies::GetInstance()->FindBenchmarks(re, benchmarks, Err); 222 } 223 224 //=============================================================================// 225 // Benchmark 226 //=============================================================================// 227 228 Benchmark::Benchmark(const char* name) 229 : name_(name), 230 report_mode_(RM_Unspecified), 231 time_unit_(kNanosecond), 232 range_multiplier_(kRangeMultiplier), 233 min_time_(0), 234 iterations_(0), 235 repetitions_(0), 236 use_real_time_(false), 237 use_manual_time_(false), 238 complexity_(oNone), 239 complexity_lambda_(nullptr) { 240 ComputeStatistics("mean", StatisticsMean); 241 ComputeStatistics("median", StatisticsMedian); 242 ComputeStatistics("stddev", StatisticsStdDev); 243 } 244 245 Benchmark::~Benchmark() {} 246 247 void Benchmark::AddRange(std::vector<int>* dst, int lo, int hi, int mult) { 248 CHECK_GE(lo, 0); 249 CHECK_GE(hi, lo); 250 CHECK_GE(mult, 2); 251 252 // Add "lo" 253 dst->push_back(lo); 254 255 static const int kint32max = std::numeric_limits<int32_t>::max(); 256 257 // Now space out the benchmarks in multiples of "mult" 258 for (int32_t i = 1; i < kint32max / mult; i *= mult) { 259 if (i >= hi) break; 260 if (i > lo) { 261 dst->push_back(i); 262 } 263 } 264 // Add "hi" (if different from "lo") 265 if (hi != lo) { 266 dst->push_back(hi); 267 } 268 } 269 270 Benchmark* Benchmark::Arg(int x) { 271 CHECK(ArgsCnt() == -1 || ArgsCnt() == 1); 272 args_.push_back({x}); 273 return this; 274 } 275 276 Benchmark* Benchmark::Unit(TimeUnit unit) { 277 time_unit_ = unit; 278 return this; 279 } 280 281 Benchmark* Benchmark::Range(int start, int limit) { 282 CHECK(ArgsCnt() == -1 || ArgsCnt() == 1); 283 std::vector<int> arglist; 284 AddRange(&arglist, start, limit, range_multiplier_); 285 286 for (int i : arglist) { 287 args_.push_back({i}); 288 } 289 return this; 290 } 291 292 Benchmark* Benchmark::Ranges(const std::vector<std::pair<int, int>>& ranges) { 293 CHECK(ArgsCnt() == -1 || ArgsCnt() == static_cast<int>(ranges.size())); 294 std::vector<std::vector<int>> arglists(ranges.size()); 295 std::size_t total = 1; 296 for (std::size_t i = 0; i < ranges.size(); i++) { 297 AddRange(&arglists[i], ranges[i].first, ranges[i].second, 298 range_multiplier_); 299 total *= arglists[i].size(); 300 } 301 302 std::vector<std::size_t> ctr(arglists.size(), 0); 303 304 for (std::size_t i = 0; i < total; i++) { 305 std::vector<int> tmp; 306 tmp.reserve(arglists.size()); 307 308 for (std::size_t j = 0; j < arglists.size(); j++) { 309 tmp.push_back(arglists[j].at(ctr[j])); 310 } 311 312 args_.push_back(std::move(tmp)); 313 314 for (std::size_t j = 0; j < arglists.size(); j++) { 315 if (ctr[j] + 1 < arglists[j].size()) { 316 ++ctr[j]; 317 break; 318 } 319 ctr[j] = 0; 320 } 321 } 322 return this; 323 } 324 325 Benchmark* Benchmark::ArgName(const std::string& name) { 326 CHECK(ArgsCnt() == -1 || ArgsCnt() == 1); 327 arg_names_ = {name}; 328 return this; 329 } 330 331 Benchmark* Benchmark::ArgNames(const std::vector<std::string>& names) { 332 CHECK(ArgsCnt() == -1 || ArgsCnt() == static_cast<int>(names.size())); 333 arg_names_ = names; 334 return this; 335 } 336 337 Benchmark* Benchmark::DenseRange(int start, int limit, int step) { 338 CHECK(ArgsCnt() == -1 || ArgsCnt() == 1); 339 CHECK_GE(start, 0); 340 CHECK_LE(start, limit); 341 for (int arg = start; arg <= limit; arg += step) { 342 args_.push_back({arg}); 343 } 344 return this; 345 } 346 347 Benchmark* Benchmark::Args(const std::vector<int>& args) { 348 CHECK(ArgsCnt() == -1 || ArgsCnt() == static_cast<int>(args.size())); 349 args_.push_back(args); 350 return this; 351 } 352 353 Benchmark* Benchmark::Apply(void (*custom_arguments)(Benchmark* benchmark)) { 354 custom_arguments(this); 355 return this; 356 } 357 358 Benchmark* Benchmark::RangeMultiplier(int multiplier) { 359 CHECK(multiplier > 1); 360 range_multiplier_ = multiplier; 361 return this; 362 } 363 364 365 Benchmark* Benchmark::MinTime(double t) { 366 CHECK(t > 0.0); 367 CHECK(iterations_ == 0); 368 min_time_ = t; 369 return this; 370 } 371 372 373 Benchmark* Benchmark::Iterations(size_t n) { 374 CHECK(n > 0); 375 CHECK(IsZero(min_time_)); 376 iterations_ = n; 377 return this; 378 } 379 380 Benchmark* Benchmark::Repetitions(int n) { 381 CHECK(n > 0); 382 repetitions_ = n; 383 return this; 384 } 385 386 Benchmark* Benchmark::ReportAggregatesOnly(bool value) { 387 report_mode_ = value ? RM_ReportAggregatesOnly : RM_Default; 388 return this; 389 } 390 391 Benchmark* Benchmark::UseRealTime() { 392 CHECK(!use_manual_time_) 393 << "Cannot set UseRealTime and UseManualTime simultaneously."; 394 use_real_time_ = true; 395 return this; 396 } 397 398 Benchmark* Benchmark::UseManualTime() { 399 CHECK(!use_real_time_) 400 << "Cannot set UseRealTime and UseManualTime simultaneously."; 401 use_manual_time_ = true; 402 return this; 403 } 404 405 Benchmark* Benchmark::Complexity(BigO complexity) { 406 complexity_ = complexity; 407 return this; 408 } 409 410 Benchmark* Benchmark::Complexity(BigOFunc* complexity) { 411 complexity_lambda_ = complexity; 412 complexity_ = oLambda; 413 return this; 414 } 415 416 Benchmark* Benchmark::ComputeStatistics(std::string name, 417 StatisticsFunc* statistics) { 418 statistics_.emplace_back(name, statistics); 419 return this; 420 } 421 422 Benchmark* Benchmark::Threads(int t) { 423 CHECK_GT(t, 0); 424 thread_counts_.push_back(t); 425 return this; 426 } 427 428 Benchmark* Benchmark::ThreadRange(int min_threads, int max_threads) { 429 CHECK_GT(min_threads, 0); 430 CHECK_GE(max_threads, min_threads); 431 432 AddRange(&thread_counts_, min_threads, max_threads, 2); 433 return this; 434 } 435 436 Benchmark* Benchmark::DenseThreadRange(int min_threads, int max_threads, 437 int stride) { 438 CHECK_GT(min_threads, 0); 439 CHECK_GE(max_threads, min_threads); 440 CHECK_GE(stride, 1); 441 442 for (auto i = min_threads; i < max_threads; i += stride) { 443 thread_counts_.push_back(i); 444 } 445 thread_counts_.push_back(max_threads); 446 return this; 447 } 448 449 Benchmark* Benchmark::ThreadPerCpu() { 450 thread_counts_.push_back(CPUInfo::Get().num_cpus); 451 return this; 452 } 453 454 void Benchmark::SetName(const char* name) { name_ = name; } 455 456 int Benchmark::ArgsCnt() const { 457 if (args_.empty()) { 458 if (arg_names_.empty()) return -1; 459 return static_cast<int>(arg_names_.size()); 460 } 461 return static_cast<int>(args_.front().size()); 462 } 463 464 //=============================================================================// 465 // FunctionBenchmark 466 //=============================================================================// 467 468 void FunctionBenchmark::Run(State& st) { func_(st); } 469 470 } // end namespace internal 471 472 void ClearRegisteredBenchmarks() { 473 internal::BenchmarkFamilies::GetInstance()->ClearBenchmarks(); 474 } 475 476 } // end namespace benchmark 477