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:
BenchmarkFamilies()82 BenchmarkFamilies() {}
83
84 std::vector<std::unique_ptr<Benchmark>> families_;
85 Mutex mutex_;
86 };
87
GetInstance()88 BenchmarkFamilies* BenchmarkFamilies::GetInstance() {
89 static BenchmarkFamilies instance;
90 return &instance;
91 }
92
AddBenchmark(std::unique_ptr<Benchmark> family)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
ClearBenchmarks()100 void BenchmarkFamilies::ClearBenchmarks() {
101 MutexLock l(mutex_);
102 families_.clear();
103 families_.shrink_to_fit();
104 }
105
FindBenchmarks(const std::string & spec,std::vector<Benchmark::Instance> * benchmarks,std::ostream * ErrStream)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
RegisterBenchmarkInternal(Benchmark * bench)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`
FindBenchmarksInternal(const std::string & re,std::vector<Benchmark::Instance> * benchmarks,std::ostream * Err)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
Benchmark(const char * name)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
~Benchmark()245 Benchmark::~Benchmark() {}
246
AddRange(std::vector<int> * dst,int lo,int hi,int mult)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
Arg(int x)270 Benchmark* Benchmark::Arg(int x) {
271 CHECK(ArgsCnt() == -1 || ArgsCnt() == 1);
272 args_.push_back({x});
273 return this;
274 }
275
Unit(TimeUnit unit)276 Benchmark* Benchmark::Unit(TimeUnit unit) {
277 time_unit_ = unit;
278 return this;
279 }
280
Range(int start,int limit)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
Ranges(const std::vector<std::pair<int,int>> & ranges)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
ArgName(const std::string & name)325 Benchmark* Benchmark::ArgName(const std::string& name) {
326 CHECK(ArgsCnt() == -1 || ArgsCnt() == 1);
327 arg_names_ = {name};
328 return this;
329 }
330
ArgNames(const std::vector<std::string> & names)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
DenseRange(int start,int limit,int step)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
Args(const std::vector<int> & args)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
Apply(void (* custom_arguments)(Benchmark * benchmark))353 Benchmark* Benchmark::Apply(void (*custom_arguments)(Benchmark* benchmark)) {
354 custom_arguments(this);
355 return this;
356 }
357
RangeMultiplier(int multiplier)358 Benchmark* Benchmark::RangeMultiplier(int multiplier) {
359 CHECK(multiplier > 1);
360 range_multiplier_ = multiplier;
361 return this;
362 }
363
364
MinTime(double t)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
Iterations(size_t n)373 Benchmark* Benchmark::Iterations(size_t n) {
374 CHECK(n > 0);
375 CHECK(IsZero(min_time_));
376 iterations_ = n;
377 return this;
378 }
379
Repetitions(int n)380 Benchmark* Benchmark::Repetitions(int n) {
381 CHECK(n > 0);
382 repetitions_ = n;
383 return this;
384 }
385
ReportAggregatesOnly(bool value)386 Benchmark* Benchmark::ReportAggregatesOnly(bool value) {
387 report_mode_ = value ? RM_ReportAggregatesOnly : RM_Default;
388 return this;
389 }
390
UseRealTime()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
UseManualTime()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
Complexity(BigO complexity)405 Benchmark* Benchmark::Complexity(BigO complexity) {
406 complexity_ = complexity;
407 return this;
408 }
409
Complexity(BigOFunc * complexity)410 Benchmark* Benchmark::Complexity(BigOFunc* complexity) {
411 complexity_lambda_ = complexity;
412 complexity_ = oLambda;
413 return this;
414 }
415
ComputeStatistics(std::string name,StatisticsFunc * statistics)416 Benchmark* Benchmark::ComputeStatistics(std::string name,
417 StatisticsFunc* statistics) {
418 statistics_.emplace_back(name, statistics);
419 return this;
420 }
421
Threads(int t)422 Benchmark* Benchmark::Threads(int t) {
423 CHECK_GT(t, 0);
424 thread_counts_.push_back(t);
425 return this;
426 }
427
ThreadRange(int min_threads,int max_threads)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
DenseThreadRange(int min_threads,int max_threads,int stride)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
ThreadPerCpu()449 Benchmark* Benchmark::ThreadPerCpu() {
450 thread_counts_.push_back(CPUInfo::Get().num_cpus);
451 return this;
452 }
453
SetName(const char * name)454 void Benchmark::SetName(const char* name) { name_ = name; }
455
ArgsCnt() const456 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
Run(State & st)468 void FunctionBenchmark::Run(State& st) { func_(st); }
469
470 } // end namespace internal
471
ClearRegisteredBenchmarks()472 void ClearRegisteredBenchmarks() {
473 internal::BenchmarkFamilies::GetInstance()->ClearBenchmarks();
474 }
475
476 } // end namespace benchmark
477